akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long
#define double long double
#define endre getchar();getchar();return 0
#define moder (int)(1e9+7)
#define inf (int)(5*1e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int kai(int x) {
	if (x == 0)return 1;
	return (kai(x - 1)*x) % moder;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
struct edge { int from, to, cost; };
int dx[5] = { 0,1,0,-1 }, dy[5] = { 1,0,-1,0 };
map<int, int>factor(int x) {
	map<int, int>res;
	for (int i = 2; i*i <= x; i++) {
		while (x%i == 0) {
			x /= i;
			res[i]++;
		}
	}
	if (x != 1)res[x]++;
	return res;
}
/*--------Library Zone!--------*/

int n, W;
vector<int>vec[5];
P p[105];
int sum[5][114];
signed main() {
	cin >> n >> W;
	rep(i, n) {
		cin >> p[i].first >> p[i].second;
		vec[p[i].first - p[0].first].push_back(p[i].second);
	}
	int li = p[0].first;
	rep(i, 4) {
		sort(all(vec[i]));
		reverse(all(vec[i]));
		rep(j, vec[i].size()) {
			sum[i][j + 1] = sum[i][j] + vec[i][j];
		}
	}
	int ans = 0;
	rep(i, vec[0].size() + 1) {
		rep(j, vec[1].size() + 1) {
			rep(k, vec[2].size() + 1) {
				if (i*li + j * (li + 1) + k * (li + 2) > W)continue;
				int l = min((W - i * li - j * (li + 1) - k * (li + 2)) / (li + 3), (int)vec[3].size());
				ans = max(ans, sum[0][i] + sum[1][j] + sum[2][k] + sum[3][l]);
			}
		}
	}
	cout << ans << endl;
	endre;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,memo;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for(int i = 0; i < N; i++){
    cin >> A[i];
    memo = A[i];
    B[memo-1] = i+1;
  }
  for(int i = 0; i < N; i++){
    cout << B[i] << endl;
  }
}
    

Measured memory_bytes: 1536
solve :: [Int] -> Int -> Int ->	String
solve all@(x:xs) n count
  | count > n =	[]
  | x == count = '1' : ' ' : solve xs n (count + 1)
  | otherwise = '0' : ' ' : solve all n (count + 1)

ctr :: Int -> [[Int]] -> [String]
ctr n (x:xs)
  | null xs = []
  | otherwise = solve (x ++ [-1]) n 1 : ctr n xs

main = do
  n <- readLn
  getContents >>= mapM_ putStrLn . map init . ctr n . (++[[1]]) . map (map read . drop 2 . words) . lines

Measured memory_bytes: 4012
#include<stdio.h>
#include<stdlib.h>

struct Node{
  struct Node *r;
  struct Node *l;
  struct Node *p;
  int key;
};

struct Node *root, *NIL;

void insert(int k){
  struct Node *y = NIL;
  struct Node *x = root;
  struct Node *z;

  z = (struct Node *)malloc(sizeof(struct Node));
  z->key = k;
  z->l = NIL;
  z->r = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key) {
      x = x->l;
    }else{
      x = x->r;
    }
  }
  z->p = y;
  if(y == NIL){
    root = z;
  }else{
    if(z->key < y->key){
      y->l = z;
    }else{
      y->r = z;
    }
  }
}

void inorder(struct Node *u){
  if(u == NIL) return;
  inorder(u->l);
  printf(" %d", u->key);
  inorder(u->r);
}
void preorder(struct Node *u){
  if(u == NIL) return;
  printf(" %d", u->key);
  preorder(u->l);
  preorder(u->r);
}

struct Node * find(struct Node *u, int k){
  while(u != NIL && k != u->key){
    if(k < u->key) u = u->l;
    else u = u->r;
  }
  return u;
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if( com[0] == 'f'){
      scanf("%d", &x);
      struct Node *t = find(root, x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }
  }

  return 0;
}



Measured memory_bytes: 20520
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int v=0;
  v+=(a<b?a:b);
  v+=(c<d?c:d);
  cout<<v<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  int H, W;
  while (true) {
    cin >> H >> W;
    if (!H && !W) break;
    for (int i{}; i < H; ++i) {
      for (int j{}; j < W; ++j) {
        if (i > 0 && i < H - 1 &&
            j > 0 && j < W - 1)
          cout << '.';
        else
          cout << '#';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3024
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i = x; i < n; i++)
#define MAX 100
#define INF 114514810

int N;

// char X[100][100];
// int dp[1000000001];
int a[51];
// vector<vector<int>> res(51,vector<int>(2));
vector<pair<int,int>> res;

bool isPositive(int *arr) {
    bool flag = true;
    REP(i,1,N+1) {
        if (arr[i] < 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

bool isNegative(int *arr) {
    bool flag = true;
    REP(i,1,N+1) {
        if (arr[i] > 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main(void){
    cin >> N;
    int max = 0;
    int maxIndex = 0;
    int min = 0;
    int minIndex = 0;
    REP(i,1,N+1) {
        cin >> a[i];
        if (a[i] >= max) {
            max = a[i];
            maxIndex = i;
        }
        if (a[i] <= min) {
            min = a[i];
            minIndex = i;
        }
    }
    
    // cout << isPositive(a) << endl;
    // cout << isNegative(a) << endl;
    
    if (isPositive(a)) {
        REP(i,1,N) {
            res.push_back({i,i+1});
        }
    }
    else if (isNegative(a)) {
        for(int i = N; i >= 2; i--) {
            res.push_back({i,i-1});
        }
    }
    else {
        if (abs(max) >= abs(min)) {
            REP(i,1,N+1) {
                res.push_back({maxIndex,i});
            }
            REP(i,1,N) {
                res.push_back({i,i+1});
            }
        }
        else {
            REP(i,1,N+1) {
                res.push_back({minIndex,i});
            }
            for(int i = N; i >= 2; i--) {
                res.push_back({i,i-1});
            }
        }
    }
    
    // cout << MakeStream::from({3, 2, 9, 6}) | any([](auto elem) { return (elem % 3) == 0;}) << endl;
    
    
    // REP(i,2,N+1) {
    //     if (a[i-1] > a[i]) {
    //         if (a[i-1] < 0) {
    //             while(a[i-1] > a[i]) {
    //                 a[i-1] += a[i-1];
    //                 res.push_back({i-1,i-1});
    //                 // cout << i-1 << " " << i-1 << endl;
    //             }
    //         }
    //         else {
    //             while(a[i-1] > a[i]) {
    //                 a[i] += a[i-1];
    //                 res.push_back({i-1,i});
    //                 // cout << i-1 << " " << i << endl;
    //             }
    //         }
    //     }
    // }

    cout << res.size() << endl;
    REP(i,0,res.size()) {
        cout << res[i].first << " " << res[i].second << endl;
    }
    

}

Measured memory_bytes: 256
#coding:utf-8
import math

n = int(input())
prime_count = 0
for i in range(n):
    x = int(input())
    div = 1
    div_count = 0

    while div <= math.sqrt(x) and div_count < 3:
        if x % div == 0 and div == math.sqrt(x):
             div_count += 1
        elif x % div == 0 and div != math.sqrt(x):
             div_count += 2
        div += 1

    if div_count == 2:
        prime_count += 1

print(prime_count)

Measured memory_bytes: 6808
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#define  rep(i,n)   for(int i = 0; i < (n); ++i)
#define rrep(i,n)   for(int i = 1; i <= (n); ++i)
#define drep(i,n)   for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for(int i = s; i < t;  ++i)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}
bool is_solve(const int& length, vector<ull> a, const int& times) {
  int cnt {};
  for (const auto& e : a) {
    if (e <= length) break;
    cnt += e/length;
  }
  return (cnt<=times);
}

int main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ull n, k;
  cin >> n >> k;
  vector<ull> a(n);
  rep(i, n) cin >> a[i];

  std::sort(a.rbegin(), a.rend());

  ull left {1};
  ull right {a[0]};

  for (ull mid = (left+right)/2;right>=left+2;) {
    mid = (left+right)/2;
    if (is_solve(mid, a, k)) {
      right = mid;
    } else {
      left = mid;
    }
    //cout << left << ' ' << right << '\n';
  }
  if (is_solve(left, a, k)) {
    std::cout << left << '\n';
  } else if (is_solve(right, a, k)) {
    std::cout << right << '\n';
  }
}


Measured memory_bytes: 6364
#include<bits/stdc++.h>
using namespace std;
struct node{
long long d,g;
bool operator<(const node &w)
{
	if(d!=w.d)
		return d<w.d;
}
};
bool func(node k,int n)
{
if(k.d<=n)
	return false;
else return true;
}
int main()
{
long long l,r,rem=2019;cin>>l>>r;
if(l+2019-l%2019<=r)
	rem=0;
else{
for(long long i=l;i<r;i++)
	for(long long j=l+1;j<=r;j++)
	{
		int k=((i%2019)*(j%2019))%2019;
		if(rem>k)
			rem=k;
	}
}
cout<<rem;
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;

 int main(){
   int n;
   double sum;
   cin >> n;
   vector<int> a(n);
   rep(i,n){
     cin >> a[0];
     sum += (double)1 / a[0];
   }
   cout << fixed << setprecision(10);

   cout << 1 / sum ;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define scanVec(vec , n) for(int i = 0; i < n ; i++){ cin>>vec[i];} 
#define printVec(vec , n) for(int i = 0; i < n ; i++){ cout<<vec[i]<<" ";} cout<<endl;
#define S second
#define F first
#define SZ(x) (int)x.size()
typedef long long ll;
const int  MOD = 1e9 + 7;
const int  N = 1e6 + 7;

bool cmp(const pair<ll , ll > x , const pair<ll , ll > y){
    return x.F + x.S < y.F + y.S;
}

void solve(){
    int n; cin>>n;
    vector<pair<ll , ll > > v(n);
    for(int i = 0 ; i < n ; i++){
        cin>>v[i].F>>v[i].S;

    }
    sort(v.begin() , v.end() , cmp);

    int last = -1;
    ll res = 0;
    for(int i = 0 ; i < n ; i++){
        if(last == -1){
            res++;
            last = i;
            continue;
        }
        if(v[last].F + v[last].S > v[i].F - v[i].S) continue;
        res++;
        last = i;
        continue;
    }  
    cout<<res<<endl;

}

int main(){
    ios::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--) solve();
    return 0;
}

Measured memory_bytes: 1792
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var a = Console.ReadLine().Split().Select(long.Parse).ToArray();
		var t = 0L;
		Console.WriteLine(Enumerable.Range(0, n).Sum(i => (t = Math.Max(t, a[i])) - a[i]));
	}
}


Measured memory_bytes: 47856
#include<stdio.h>
#include<math.h>
#define PI 3.14159265359
int n=0;

typedef struct{
  double x;
  double y;
} point;

void kock(int,point,point);

point p1={0,0};
point p2={100,0};

int main(){
  scanf("%d",&n);
  printf("%.8f %.8f\n",p1.x,p1.y);
   kock(n,p1,p2);
  printf("%.8f %.8f\n",p2.x,p2.y);
  return 0;

}


void kock(int n,point t1,point t2){
  point s={0,0},t={0,0},u={0,0};
  double deg=60;
  double rad=deg*PI/180.0;

  if(n==0){
    return ;
  }
  s.x=(2*t1.x+1*t2.x)/3;
  s.y=(2*t1.y+1*t2.y)/3;
  t.x=(1*t1.x+2*t2.x)/3;
  t.y=(1*t1.y+2*t2.y)/3;
  
  u.x=(t.x-s.x)*cos(PI/3)-(t.y-s.y)*sin(PI/3)+s.x;
  u.y=(t.x-s.x)*sin(PI/3)+(t.y-s.y)*cos(PI/3)+s.y;
  
  kock(n-1,t1,s);
  printf("%.8f %.8f\n",s.x,s.y);
  kock(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  kock(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  kock(n-1,t,t2);
}

Measured memory_bytes: 644
import numpy as np
n,d = [int(i) for i in input().split()]

l = []
for i in range(n):
    dots = [int(i) for i in input().split()]
    l.append(dots)
    
ans = 0
for i in range(len(l)):
    m = np.array(l.pop())
    for j in l:
        j = np.array(j) - m
        dist = np.sum(j**2)
        if np.sqrt(dist).is_integer():
            ans += 1
print(ans)

Measured memory_bytes: 12452
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 1e6 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const long long LINF = 1e18 + 3141;
const long long MAXL = 1e18;

ll fmax(ll a) {
    // i * (i + 1) <= a
    if(a < 0)
        return 0;
    ll l = 1, r = 1e6, f = -1;
    while(l <= r) {
        ll md = (l + r) / 2; // 
        if((md * (md + 1)) / 2 <= a) {
            l = md + 1;
            f = md;
        }else {
            r = md - 1;
        }
    }
    return f;
}


void solve(){
    ll n;
    cin >> n;
    map <ll,ll> mp;
    ll x = 1;
    for(ll i = 2; i * i <= n; ++i){
        int cnt = 0;
        while(n % i == 0){
            cnt ++;
            n /= i;
        }
        if(cnt)
            mp[i] += cnt;
    }
    if(n > 1)
        mp[n] ++;


    ll ans = 0;
    for(auto g : mp) {
        ans += fmax(g.Y);
    }
    cout << ans;
}

 
 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}


Measured memory_bytes: 3660
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始
int N,Ma,Mb;
int dp[50][500][500];

int main(){
  cin>>N>>Ma>>Mb;
  int a[N],b[N],c[N];
  for(int i = 0; i < N; i++) cin>>a[i]>>b[i]>>c[i];
  for(int i = 0; i <= N; i++){
    for(int j = 0; j < 500; j++){
      for(int k = 0; k < 500; k++){
        dp[i][j][k] = INF;
      }
    }
  }
  dp[0][0][0] = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < 500; j++){
      for(int k = 0; k < 500; k++){
        if(dp[i][j][k]==INF) continue;
        chmin(dp[i+1][j][k], dp[i][j][k]);
        chmin(dp[i+1][j+a[i]][k+b[i]],dp[i][j][k]+c[i]);
      }
    }
  }
  // for(int i = 0; i <= N; i++){
  //   for(int j = 0; j < 10; j++){
  //     for(int k = 0; k < 10; k++){
  //       if(dp[i][j][k]>=INF) cout<<"*"<<" ";
  //       else cout<<dp[i][j][k]<<" ";
  //     }
  //     cout<<endl;
  //   }
    
  // }
  
  int ans = 1e9;
  for(int i = 1; (Ma*i <= 400)&&(Mb*i <= 400); i++){
    ans = min(ans,dp[N][Ma*i][Mb*i]);
  }
  if(ans>=INF) cout<<"-1"<<endl;
  else cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 41216
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = (((1<<30)-1)<<1)+1;
const int nINF = 1<<31;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<char, int> pci;

/////////////////////////////////////////////////////////////////////

int solve(int a, int b, int c, int mx) {
	int ans = 0;
    int ac = (mx+1-a)/2;
    int bc = (mx+1-b)/2;
    int cc = (mx+1-c)/2;
    a += ac*2;
    b += bc*2;
    c += cc*2;
    // DEBUG(a);
    // DEBUG(b);
    // DEBUG(c);
    if(a > mx) ++ans;
    if(b > mx) ++ans;
    if(c > mx) ++ans;
    ans += (ac+bc+cc);
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    //cout << fixed << setprecision(7);
    int a, b, c;
    cin >> a >> b >> c;
    int mx = max(a, max(b, c));
    int ans = 0;
    ans = solve(a, b, c, mx);
    ans = min(ans, solve(a, b, c, mx-1));
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
ll s[201000],p[201000],a[101000],b[101000],n,cnt;
int main(){
	read(n);
	ll s1=0,s2=0;
	for(int i=1;i<=n;i++)
		read(a[i]),read(b[i]),s1+=a[i],s2+=b[i],p[++cnt]=a[i],p[++cnt]=b[i];
	sort(p+1,p+cnt+1);
	for(int i=1;i<=cnt;i++) s[i]=s[i-1]+p[i];
	ll ans=min(s1,s2);
	for(int i=1;i<=n;i++){
		int now=n;ll tag=0;
		if(min(a[i],b[i])<=p[now]) now++,tag-=min(a[i],b[i]);
		if(max(b[i],a[i])<=p[now]) now++,tag-=max(a[i],b[i]);
		ans=min(ans,s[now]+tag);
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define M 1000000007
#define ll long long
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define REPI(i,a,b) for(ll i=b-1;i>=a;i--)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define G(a,b) get<a>(b)
#define VI vector<int>
#define VLL vector<long long>

#define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define o_setll tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set

ll modI(ll a, ll m);
ll gcd(ll a, ll b);
ll powM(ll x, unsigned ll y, unsigned ll m);
void pairsort(int a[], int b[], int n);
void pairsortll(ll a[],ll b[],ll n);
ll logint(ll x,ll y);


ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}

ll powM(ll x,ll y,ll m)
{
    if(y==0) return 1;
    ll p=powM(x,y/2,m)%m;
    p=(p*p)%m;
    return (y%2==0)?p:(x*p)%m;
}

ll modI(ll a, ll m)
{
    ll m0=m,y=0,x=1;
    if(m==1) return 0;
    while(a>1)
    {
        ll q=a/m;
        ll t=m;
        m=a%m;
        a=t;
        t=y;
        y=x-q*y;
        x=t;
    }
    if(x<0) x+=m0;
    return x;
}

void pairsort(int a[],int b[],int n)
{
    pair<int,int> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}

void pairsortll(ll a[],ll b[],ll n)
{
    pair<ll,ll> v[n];
    REP(i,0,n)
    {
        v[i].F=a[i];
        v[i].S=b[i];
    }
    sort(v,v+n);
    REP(i,0,n)
    {
        a[i]=v[i].F;
        b[i]=v[i].S;
    }
}

ll logint(ll x,ll y)
{
    ll ans=0;
    ll a=1;
    for(ll i=0;i<=x;i++)
    {
        if(x<a)
        {
            return ans;
        }
        ans++;
        a*=y;
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */

    ll q=1;
    //cin>>q;
    while(q--)
    {
        ll n;
        cin>>n;
        ll a[n];
        ll d=0;
        REP(i,0,n)
        {
            ll t;
            cin>>t;
            a[i]=t;
            if(t!=i+1) d++;
        }
        if(d==2||d==0) cout<<"YES";
        else cout<<"NO";
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<bits/stdc++.h>
#define ll long long int
#define hell 1000000007LL
using namespace std;
ll power(ll x, ll y,ll z){ 
    if(y==0)
     return 1;
    else
    {
        ll p=power(x,y/2,z);
        ll w=(p*p)%z;
        if(y%2==0)
         return w;
        else
        return (x*w)%z;
    }}
ll gcd(ll x,ll y)
{
    if(y==0)
     return x;
    else
    return gcd(y,x%y);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20);
   int n;
   cin>>n;
   int k=n+1;
   ll f[k];
   f[0]=f[1]=1;
   for(int i=2;i<k;i++)
   f[i]=(f[i-1]*i)%hell;
   ll ans=0,p=f[n];
   for(int i=2;i<=n;i++)
   {
       ll a=((power((f[i]*f[n-i])%hell,hell-2,hell))*p)%hell;
       ll z=((power(2,3*n-2*i,hell)-power(2,3*n-3*i+1,hell)+hell))%hell;
       a=(a*z)%hell;
       ans=(ans+a)%hell;
   }
   cout<<ans;}


Measured memory_bytes: 11412
#include <stdio.h>

int main(void){
	int x = 600, d, i, S;
	while (scanf("%d", &d) != EOF){
		S = 0;
		for (i = 0; i < x/d; i++){
			S += d * (d*i)*(d*i);
		}
		printf("%d\n", S);
	}
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }

constexpr ll MOD = 1e9 + 7;
bool broken[100005];
ll memo[100005];
ll paths(int x) {
    if(broken[x]) return 0;
    if(x <= 1) return 1;
    if(memo[x] != -1) return memo[x];
    return memo[x] = (paths(x-2) + paths(x-1)) % MOD;
}

int main() {
    int n, m; cin >> n >> m;
    vint a(m);
    rep(i, m) cin >> a[i];
    rep(i, n+1) broken[i] = false;
    rep(i, m) broken[a[i]] = true;
    rep(i, n+1) memo[i] = -1;
    cout << paths(n) << endl;
    return 0;
}


Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <bitset>
 
using namespace std;
 
#define rep(i, N) for(int (i) = 0; (i) < (N); (i) ++)
typedef long long ll;
 
 
int main(){
    int N;
    cin >> N;
    vector<double> ts(N + 2, 0);
    vector<double> vs(N + 2, 0);
    int T = 0;
    rep(i, N){
        cin >> ts[i + 1];
        T += ts[i + 1];
    }
 
    rep(i, N){
        cin >> vs[i + 1];
    }
 
    rep(i, N + 1){
        ts[i + 1] += ts[i];
    }
 
    double ans = 0.0;
 
    double prev_v = 0.0;
 
    for(double i = 0.5; i <= T; i += 0.5){
        double v = 100;
        for(int j = 0; j < N + 2; j ++){
            if(j >= 1 && ts[j - 1] <= i && i <= ts[j]){
                v = min(v, (double)vs[j]);
            }
            if(ts[j] < i){
                v = min(v, (double)(vs[j] + (i - ts[j])));
            }
            if(j >= 1 && ts[j - 1] > i){
                v = min(v, (double)(vs[j] + (- i + ts[j - 1])));
            }
        }
        ans += (v + prev_v) * 0.25;
        prev_v = v;
    }
    cout.precision(20);
    cout << fixed << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#define int             long long int
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define endl            "\n"

#define vi              vector <int>
#define pii             pair <int, int>
#define vpii            vector <pii>
#define mii             map <int, int>
#define que_max         priority_queue <int>
#define que_min         priority_queue <int, vi, greater<int>>

#define loop(i,s,e)     for(int i=s;i<e;i++)
#define rloop(i,e,s)    for(int i=e;i>=s;i--)
#define mset(a,f)       memset(a,f,sizeof(a))

#define M               1000000007
#define sz(x)           ((int) x.size())
#define all(p)          p.begin(), p.end()

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)        for (auto x : a) cout << x << " "; cout << endl
#define Print(a,x,y)    for (int i=x; i<y; i++) cout<< a[i]<< " "; cout << endl

int add(int a, int b)
{
	return (a + b + M) % M;
}
int mul(int a, int b)
{
	return (a * b) % M;
}

inline int power(int a, int b)
{
	int x = 1;
	while (b)
	{
		if (b & 1) x = mul(x, a);

		a = mul(a, a);

		b >>= 1;
	}
	return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
	const char* comma = strchr (names + 1, ',');
	cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 2e5 + 7;
int dp[N];

void solve()
{
	int n, k;
	cin >> n >> k;
	int ans = 0;
	rloop(i, k, 1)
	{
		int x = k / i;
		int cnt = power(x, n);
		dp[i] = cnt;
		for (int j = 2 * i; j <= k; j += i)
		{
			dp[i] = add(dp[i], -dp[j]);
		}
		ans = add(ans, mul(i, dp[i]));
	}
	cout << ans;

	return;
}
int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);



	cout << setprecision(9) << fixed;

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}


	return 0;
}



Measured memory_bytes: 4420
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define countof(a) (sizeof(a)/sizeof((a)[0]))
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
template<class T> void sort3a(T& a,T& b,T& c) {if (a>b) swap(a,b); if (b>c) swap(b,c); if (a>b) swap(a,b);}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);

    string s; cin >> s;

    string::size_type c = s.find('C');
    string::size_type f = s.rfind('F');

    Yes(c != string::npos && f != string::npos && c < f);
}


Measured memory_bytes: 256
n = int(input())
adjMat = [[-1]*n for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        adjMat[i][x-1] = y
ans = 0
for i in range(1 << (n)):
    #print (bin(i))
    success = True
    for j in range(n):
        if i & 2**j:
            for k in range(n):
                if k == j:
                    continue
                if  i & 2**k == 0 and adjMat[j][k] == 1:
                    success = False
                if i & 2**k > 0 and adjMat[k][j] == 0:
                    success = False
                #print (j, k, adjMat[j][k], adjMat[k][j], success)
        if not success:
            break
    if success:
        i2 = i
        c = 0
        while i2 > 0:
            c += i2 & 1
            i2 //= 2
        ans = max(c, ans)
print (ans) 

Measured memory_bytes: 74216
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [set() for _ in range(N + 1)]
for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
    E[a].add((b, i))
    E[b].add((a, i))

A = [0] * (N - 1)
Q = deque([(0, 1)])
while Q:
    p, v = Q.popleft()
    c = 0
    for u, i in E[v]:
        E[u].remove((v, i))
        c += 1 + (c + 1 == p)
        Q.append((c, u))
        A[i] = c

print(max(A), *A)

Measured memory_bytes: 55084
#Tenka1 Programmer Beginner Contest-D Crossing
"""
1~nまでの数字を用いて、以下の条件を満たす集合を作る。

1.1~nのそれぞれの数字はちょうど2回出現する
2.ある2つの集合を見たときに、重複する要素がちょうど1つ存在する
集合の個数・要素数は任意に決定して良い

この問題で考えるべきは、
ある2頂点に同じ要素を入れたとき、残りの要素は必ず別のものになり、
それらはまた自分と同じ要素の頂点と比べたときに必ず残りの要素が別
のものになってないといけない。

という点であり、これを達成するにはかなり厳しい制約があるはず。

まず、1.の制約より、全要素数は
2*n として求まる。
また、2.の制約より、必ず1つの頂点に頂点数-1個の要素が存在すると言える。
よって、前提として、
(2*n)%(頂点数-1) == 0
となるようなnでないと達成は不可能であり、
逆にそのようなnであれば達成可能。
頂点数はn<=10**5であることから、全探索で求めることができる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
flag = 0
for i in range(1,n+2):
    if 2*n%i== 0: #そのような頂点数が存在するかどうか
        tops = i
        if 2*n//tops == tops-1:#要素数は頂点数-1になっていなければならない
            elements = tops-1
            g = [[] for _ in range(tops)]

            mod = n
            now = 0
            now2 = 1
            for j in range(n):
                g[now].append(j+1)
                g[now2].append(j+1)
                now2 += 1
                if len(g[now]) >= elements:
                    now += 1
                    now2 = now + 1
                 

            
            flag = 1
    if flag:break

if flag:
    print("Yes")
    print(len(g))
    for i in g:
        print(len(i),*i)
else:
    print("No")

Measured memory_bytes: 76148
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if(i%2 == 1&&a%2==1) ans++;

    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3624
import sys, heapq, bisect, math, fractions
from collections import deque


def ok(i, j, D):
    d = 0
    for k in range(D):
        d += (X[i][k] - X[j][k]) ** 2
    
    dd = int(math.sqrt(d))
    if dd ** 2 == d:
        return True
    else:
        return False


N, D = map(int, input().split())
X = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)]

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if ok(i, j, D):
            res += 1

print(res)

Measured memory_bytes: 5076
#include<iostream>
using namespace std;
int main(){
	int n=0;
	while(cin>>n,n){
		int flag=0,a=0,ans=100001,cnt=0;
		for(int i=0;i<n;i++){
			cin>>a;
			if(a==0)
			cnt++;
			if(a<ans && a>=2){
				ans=n+1;
				flag=1;
			}
		}
		if(flag==1){
			cout<<ans-cnt<<endl;
		}else{
			cout<<"NA"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
A,B = map(int,input().split())
grid = [["." for i in range(0,100)] for j in range(0,100)]
for j in range(50,100):
    for i in range(0,100):
        grid[j][i] = "#"
for count in range(0,B-1):
    x = (count*2)%100
    y = ((count*2)//100)*2
    grid[y][x] = "#"
for count in range(0,A-1):
    x = (count*2)%100
    y = ((count*2)//100)*2
    grid[y+51][x] = "."
print("100 100")
for j in range(0,100):
    for i in range(0,100):
        if i != 99:
            print(grid[j][i],end ="")
        else:
            print(grid[j][i])


Measured memory_bytes: 4596
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;
    
    long long num = n * m;
    long long ret = 0;
    
    if (n < 3 || m < 3)
    {
        if (n < 3 && m < 3)
        {
            if (num == 1)
            {
                ret = 1;
            }
            else
            {
                ret = 0;
            }
        }
        else
        {
            long long small = min(n, m);
            if (small == 1)
            {
                ret = num - 2;
            }
            else
            {
                ret = 0;
            }
        }
    }
    else
    {
        ret = (n - 2) * (m - 2);
    }
    
    cout << ret << endl;
    
    return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}



int main(void) {
    FAST_IO;
    
    string s;
    cin >> s;
    if (s.find("RRR") != -1) {
        cout << 3 <<endl;
    } else if (s.find("RR") != -1) {
        cout << 2 <<endl;
    } else if (s.find("R") != -1) {
        cout << 1 <<endl;
    } else {
        cout << 0 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int n;
int a[200000];

bool C(){
	int cnt=0;
	rep(i,n){
		if(a[i]%2==0)cnt++;
	}
	if(cnt%2==1)return true;
	return false;
}
int main(){
	cin>>n;
	rep(i,n){
		scanf("%d",&a[i]);
	}
	int turn=0;
	while(1){
		if(C()){
			puts(turn==0?"First":"Second");
			return 0;
		}
		int cnt=0;
		rep(i,n){
			if(a[i]%2==1)cnt++;
		}
		if(cnt!=1){
			puts(turn==0?"Second":"First");
			return 0;
		}
		rep(i,n){
			if(a[i]%2==1){
				if(a[i]==1){puts(turn==0?"Second":"First");return 0;}
				a[i]--;
			}
		}
		int g=a[0];
		rep(i,n)g=__gcd(g,a[i]);
		rep(i,n)a[i]/=g;
		turn=!turn;
	}
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  long long l,r,mod=2019,ans=123456;
  cin >> l >> r;
  for(ll i=l;i<r;i++){
    for(ll j=i+1;j<=r;j++){
      ans=min(ans, (i*j)%mod);
      if(ans==0){
        cout << ans << endl;
        return 0;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>


int h ,w ;

int mx[] = { 1 ,1 ,1 ,-1 ,-1 ,-1 ,0 ,0 } ;
int my[] = { 1 ,-1 ,0 ,1 ,-1 ,0 ,1 ,-1 } ;


char castle[ 1000 ][ 1000 ] ;
char castles[ 1000 ][ 1000 ] ;

char sand[ 1000 ][ 1000 ] ;


int del[ 999 * 999 ][ 2 ] ;
int DEL ;

#define x j + mx[ k ]
#define y i + my[ k ]

#define dy [ 0 ]
#define dx [ 1 ]


void make9( int i ,int j )
{
	int k ;
	for( k = 0 ; k < 8 ; ++k )
	{
		int kale = castle[ y ][ x ] ;

		if( kale < 9 && kale > -1 )
		{
			++castle[ y ][ x ] ;


			if( castle[ y ][ x ] == 9 )
			{
				make9( y ,x ) ;
			}
		}
	}
}

void look9( int H ,int W )
{
	int i ,j ;
	for( i = 1 ; i < H ; ++i )
	{
		for( j = 1 ; j < W ; ++j )
		{
			if( castle[ i ][ j ] == 9 )
			{
				make9( i ,j ) ;
			}
		}
	}
}


void input_del( int i ,int j )
{
	int minus = 0 ;

	int k ;
	for( k = 0 ; k < 8 ; ++k )
	{
		minus += castles[ y ][ x ] ;
	}

	if( castle[ i ][ j ] <= -minus )
	{
		castle[ i ][ j ] = -1 ;

		del[ DEL ] dy = i ;
		del[ DEL ] dx = j ;

		++DEL ;
	}
}

void undo( int H ,int W )
{
	int i ,j ;
	for( i = 1 ; i < H ; ++i )
	{
		for( j = 1 ; j < W ; ++j )
		{
			if( castle[ i ][ j ] < 9 )
			{
				castle[ i ][ j ] = castles[ i ][ j ] ;
			}
			
			if( castle[ i ][ j ] > -1 )
			{
				castles[ i ][ j ] = 0 ;
			}
		}
	}
}

void update( int i ,int j )
{
	castles[ i ][ j ] = -1 ;

	int k ;
	for( k = 0 ; k < 8 ; ++k )
	{
		if( castle[ y ][ x ] < 9 && castle[ y ][ x ] > -1 )
		{
			input_del( y ,x ) ;
		}
	}
}


int main()
{
	scanf( "%d %d" ,&h ,&w ) ;
	
	int i ,j ;
	for( i = 0 ; i < h ; ++i )
	{
		getchar() ;

		for( j = 0 ; j < w ; ++j )
		{
			char c = getchar() ;

			if( c == '.' )
			{
				castles[ i ][ j ] = castle[ i ][ j ] = -1 ;
			}

			else
			{
				castles[ i ][ j ] = castle[ i ][ j ] = c - '0' ;
			}
		}
	}
	
	look9( h - 1 ,w - 1 ) ;

	undo( h - 1 ,w - 1 ) ;

	for( i = 1 ; i < h - 1 ; ++i )
	{
		for( j = 1 ; j < w - 1 ; ++j )
		{
			if( castle[ i ][ j ] > -1 && castle[ i ][ j ] < 9 )
			{
				input_del( i ,j ) ;
			}
		}
	}

	int limit = 0 ;

	int ans = 0 ;

	int next_del = 0 ;

	while( limit != DEL )
	{

		++ans ;

		limit = DEL ;
		for( i = next_del ,next_del = limit ; i < limit ; ++i )
		{
			if( del[ i ] dy > 0 )
			{
				update( del[ i ] dy ,del[ i ] dx ) ;
			}
		}
	}

	printf( "%d\n" ,ans ) ;

	return 0 ;
}

Measured memory_bytes: 11440
n, kosuu = map(int, input().split(" "))
a=list(map(int, input().split(" ")))
first = sum(a[:kosuu])
temp = []
temp.append(first)
for i in range(n - kosuu):
  first = first + a[i + kosuu] - a[i]
  temp.append(first)
print((max(temp) + kosuu) / 2)

Measured memory_bytes: 70920
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;

long long gcd(long long a,long long b)
{
    return !b?a:gcd(b,a%b);
}

long long lms(long long  a,long long  b)
{
    return (a*b)/gcd(a,b);
}

int main()
{
    long long a,b,c,d,nc=0;
    //long long i,j;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)){
    nc=0;
    long long Lms=lms(c,d);
    if(a%c==0) nc++;
    //if(b%c==0) nc++;
    if(a%d==0) nc++;
    //if(b%d==0) nc++;
    nc+=(b/c-a/c);
    nc+=(b/d-a/d);
    if(a%Lms==0) nc--;
    //if(b%Lms==0) nc--;
    nc-=(b/Lms-a/Lms);
    printf("%lld",b-a+1-nc);}
}


Measured memory_bytes: 128
let is_agct c = c = 'A' || c = 'G' || c = 'C' || c = 'T';;

let solve s =
  let rec find_left s i =
    if i = String.length s then i
    else if is_agct s.[i] then i
    else find_left s (i + 1) in
  let rec longest s i j res =
    if i = String.length s then res
    else if j = String.length s then max res (j - i)
    else if is_agct s.[j] then longest s i (j + 1) res
    else let beg = find_left s j in longest s beg (beg + 1) (max res (j - i)) in
  let beg = find_left s 0 in longest s beg (beg + 1) 0
;;

let () = Scanf.scanf "%s" (fun s -> (
  solve s |> print_int
))

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>

using namespace std; 

#define NOT_FOUND -1
#define rep(i,n) for(int i=0;i<(int)(n); i++)
/*for文のマクロ定義
rep(i,回数){
    処理
}
*/

void swap(int *a, int *b){
	*b=*a-*b;
	*a-=*b;
	*b+=*a;
}

int sosu_judge(int N){
	/*素数ならば1
	  素数でなければ0を返す
	*/
	int i,j;

	if(N==2)   return 1;
	if(N%2==0) return 0;

	for(i=3;i<N && N%i!=0;i+=2);

	if(i>=N) return 1;
	
	return 0;
}

int factorial(int N){  //Nの階乗を求める関数
	int ans=1;

	while(N--) ans*=(N+1);
	return ans;
}

//クイックソートをする関数
void q_sort(int a[], int first, int last){
    int i,j;
    int x,t;

    x = a[(first + last) / 2];
    i = first; j=last;

    while(1){
        while( a[i] < x) i++;
        while( x < a[j]) j--;
        
        if( i >= j) break;
        
        swap(&a[i],&a[j]);
        i++; j--;
    }
    if(first < i-1) q_sort(a, first,i-1 );
    if(last > j+1)  q_sort(a, j+1,  last);
}

int b_search(int target, int array[],int right, int left){
    int mid;
    while(left<right){
        mid=(right+left)/2;
        if(array[mid]<target) left =mid+1;
        else                  right=mid;
    }
    if(array[mid]==target) return mid;
    return NOT_FOUND;
}

int main(){
    int N,K;
    int ans;

    cin>>N>>K;

    ans=log10(N)/log10(K)+1;
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;


const int MAX_N = 100;


int N, M;
int sum = 0;

int A[100];

void solve()
{
    sort(A, A + N, greater<>());
    for (int i = 0 ; i < N  ; i++)
    {
        sum += A[i];
    }
    
    if(A[M-1] >= double(sum)/double(4*M)) cout << "Yes";
    else cout << "No";
}

int main()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++) cin >> A[i];
    
    solve();


    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N;
    cin >> N;
    vector<ll> x(N), y(N), h(N);
    vector<pair<ll, pair<ll, ll>>> infoPair(N);
    REP(i, N)
    {
        cin >> x[i] >> y[i] >> h[i];
        infoPair[i] = make_pair(h[i], make_pair(x[i], y[i]));
    }
    sort(ALL(infoPair));
    reverse(ALL(infoPair));

    const ll MAXC = 100;
    REP(cx, MAXC + 1)
    {
        REP(cy, MAXC + 1)
        {
            bool flag = true;
            pair<ll, pair<ll, ll>> ip = infoPair[0];
            ll h = ip.first;
            ll x = (ip.second).first;
            ll y = (ip.second).second;
            ll H = h + abs(x - cx) + abs(y - cy);
            REP(i, N - 1)
            {
                pair<ll, pair<ll, ll>> ipNow = infoPair[i + 1];
                ll hNow = ipNow.first;
                ll xNow = (ipNow.second).first;
                ll yNow = (ipNow.second).second;
                ll calch = max(H - abs(xNow - cx) - abs(yNow - cy), 0ll);
                if (hNow != calch)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){

    int x;cin>>x;

    ll ans=0;

    ans+=1000*(x/500);
    x-=ans/2;

    ans+=5*(x/5);

    cout<<ans<<"\n";

    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> Monsters(N+1);
  vector<int> Heros(N);

  long long int monsterTotal = 0;

  for(int i=0;i<N+1;i++) {
    cin >> Monsters[i];
    monsterTotal += Monsters[i];
  }

  for(int i=0;i<N;i++) {
    cin >> Heros[i];
  }

  for(int i=N-1;i>=0;i--) {
    Heros[i] = Heros[i] - Monsters[i+1];
    if(Heros[i] > 0) {
      Monsters[i+1] = 0;
      Monsters[i] = Monsters[i] - Heros[i];
      if(Monsters[i] < 0) {
        Monsters[i] = 0;
      }
    } else {
      Monsters[i+1] = Heros[i] * (-1);
    }
  }

  long long int totalAfter = 0;

  for(int i=0;i<N+1;i++) {
    totalAfter += Monsters[i];
  }

  cout << monsterTotal - totalAfter << endl;
}

Measured memory_bytes: 1024
import math


def find(X):
    ans = 1
    sq = math.floor(math.sqrt(X))
    for i in range(2, sq + 1):
        if X % i == 0:
            ans = -1
            break
        if i == sq and ans == 1:
            print(X)
            exit()


X = int(input())

if X == 2:
    print(2)
    exit()

while True:
    find(X)
    X += 1


Measured memory_bytes: 38512
for t in range(int(input())):
	a,b,c,d=map(int,input().split(' '));l,x,y,o=(a+b)//(min(a,b)+1),0,0,""
	if a*l<=b:y=a+b
	elif b*l<=a:x=a+b
	else:x,y=(a*l-b)//(l-1),(b*l-a)//(l-1)
	for i in range(c,d+1):o+="AB"[i%(l+1)==0] if i<=x else "BA"[(a+b-i+1)%(l+1)==0] if a+b-i+1<=y else "AB"[a-x+x//(l+1)-y//(l+1)==0]
	print(o)

Measured memory_bytes: 3188
# coding: utf-8
from sys import stdin
import sys
import numpy as np

n, l = stdin.readline().rstrip().split()
n, l = int(n), int(l)

#print(n, l)
array = np.arange(l, l+n)
abs_min = 300
index = 300
#ans = 300
for i in range(n):
    if abs_min > np.abs(array[i]):
        abs_min = np.abs(array[i])
        index = i

#print(array, abs_min)
ans = np.sum(array) - array[index]
print(ans)

    




Measured memory_bytes: 21372
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
struct ver{
  ll p,id; string s;
  bool operator<(const ver&key)const{
      if(this->s==key.s)return this->p>key.p;
      return this->s<key.s;
  }  
  ver(ll p,ll id,string s){
      this->p=p,this->id=id,this->s=s;
  }
};
vector<ver> v;
int main(){
  ll n;
  cin>>n;
  for(int i=1;i<=n;i++){
      ll p; string s;
      cin>>s>>p;
      v.push_back(ver(p,i,s));
  }
  sort(v.begin(),v.end());
  for(int i=0;i<v.size();i++){
      cout<<v[i].id<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
using namespace std;
int main() {
string s,t,u;
int a,b;
cin>>s>>t;
cin>>a>>b;
cin>>u;
if(s==u){
  a=a-1;
  cout<<a<<" "<<b;
}
if(t==u){
    b=b-1;
    cout<<a<<" "<<b;
}
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,k,n) for(int (i)=(k);(i)<(n);(i)++)
using namespace std;
typedef long long int ll;

void foreach_permutation(int n, std::function<void(int *)> f) {
    int indexes[n];
    for (int i = 0; i < n; i++) indexes[i] = i+1;
    do {
        f(indexes);
    } while (std::next_permutation(indexes, indexes + n));
}



int main() {
   int X,Y,Z;
   cin >> X >> Y >> Z;
   int temp;
   temp = X;
   X = Y;
   Y = temp;
   temp = X;
   X = Z;
   Z = temp ;
   printf("%d %d %d",X,Y,Z);



}


Measured memory_bytes: 256