akhauriyash/Code-Regression huggingface dataset:
n, x = map(int, input().split())

a = list(map(int, input().split()))
a.append(x)
r = 0

def g(k, l):
    if l>k:
        k, l = l, k
    m = k%l
    while m!= 0:
        k = l
        l = m
        m = k%l
    return l
        

for i in range(n):
    b = abs(a[i+1]-a[i])
    if i == 0:
        r = b
    else:
        r = g(r, b)
    
print(r)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
int main(){
    ll n;
    cin >> n;
    ll c[n];
    for(ll i = 0; i < n; i++) cin >> c[i];
    ll kaz[n] = {};
    ll q;
    cin >> q;
    for(ll i = 0; i < q; i++){
        ll t, x, d;
        cin >> t >> x >> d;
        x--;
        if(t == 1){
            kaz[x] += d;
            if(c[x] < kaz[x]){
                cout << x + 1 << endl;
                return 0;
            }
        }else{
            kaz[x] -= d;
            if(kaz[x] < 0){
                cout << x + 1 << endl;
                return 0;
            }
        }
    }
    cout << 0 << endl;
    return 0;
}


Measured memory_bytes: 3116
N = int(input())
A = list(map(int, input().split()))

ans = 0
for a in A:
    if a % 4 == 0:
        ans += 1
    elif a % 2 != 0:
        ans -= 1
if N % 2 != 0:
    ans += 1
print('Yes' if ans >= 0 else 'No')


Measured memory_bytes: 14224
N = int(input())
omori_list = list(map(int,input().split()))
S1, S2 = 0,0

#print(omori_list)#

omori_sum = sum(omori_list)

#print(omori_sum)#dbg

for i in range(N):
  if S1 < int(omori_sum/2):
    oldS1 = S1
    S1 += omori_list[i]
    
S2 = omori_sum - S1
oldS2 = omori_sum - oldS1

print(min( abs(S1 - S2), abs(oldS1 - oldS2) ))

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

using namespace std;

int main(){
	int n, i, j;
	scanf("%d", &n);
	vector<vector<double>> ans;
	for(i=0;i<=n+1;i++) ans.push_back(vector<double> ());
	double p[n+1];
	for(i = 1; i<=n; i++)
		scanf("%lf", &p[i]);

	ans[1].push_back(1 - p[1]);
	ans[1].push_back(p[1]);
	for(i=2; i<=n; i++){
		ans[i].push_back(ans[i-1][0]*(1 - p[i]));
		for(j=1; j<=i; j++)
			ans[i].push_back(ans[i-1][j-1]*p[i] + ans[i-1][j]*(1 - p[i]));
	}
	double prob = 0;
	/*for(i = 1; i<=n; i++){
		for(auto v: ans[i]) 
			printf("%f ", v);
		printf("\n");
	}*/
	for(i=n; i>=1; i--){
		if((n-i) < i)
			prob += ans[n][i];
		else
			break;
	}
	printf("%.10lf\n", prob);

}

Measured memory_bytes: 43904
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acos(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define less Less
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define KK 500
#define N 100005
#define MXN 200005
int main(){
    int n,q;
    scanf("%d %d",&n,&q);
    /*if(q==0){
        for(int i = 0;i<n;i++){
            printf("%d\n",1);
        }
        return 0;
    }*/
    vector<LL> v;
    v.pb(n);
    for(int i = 0;i<q;i++){
        LL x;
        scanf("%lld",&x);
        while(!v.empty()&&x<v.back())v.pop_back();
        v.pb(x);
    }
    //printf("%d\n",v.size());
    if(v.size()==1){
        for(int i = 0;i<n;i++){
            if(i<v[0])printf("1\n");
            else printf("0\n");
        }
        return 0;
    }
   // reverse(v.begin(),v.end());
    LL now=1;
    map<LL,LL> m;
    for(int i = v.size()-2;i>=0;i--){
        if(v[i+1]%v[i]!=0)
        m[v[i+1]%v[i]]+=now;
        now*=v[i+1]/v[i];
       // printf("%lld\n",now);
        while(!m.empty()&&m.rbegin()->x>=v[i]){
            now+=m.rbegin()->x/v[i]*m.rbegin()->y;
            if(m.rbegin()->x%v[i]!=0)
            m[m.rbegin()->x%v[i]]+=m.rbegin()->y;
            m.erase(m.rbegin()->x);
        }
       /* printf("%lld\n",now);
        for(auto it:m){
            printf("%lld %lld ",it.x,it.y);
        }
        printf("\n");*/
    }
  //  printf("%lld\n",now);
    LL ans[100005];
    MEM(ans);
    for(auto it:m){
        ans[it.x]=it.y;
    }
    ans[v[0]]=now;
    for(int i = n-1;i>=1;i--)
    ans[i]+=ans[i+1];
    for(int i = 1;i<=n;i++)
    printf("%lld\n",ans[i]);
}


Measured memory_bytes: 9332
N= int(input())
K= int(input())

from math import factorial

str_n = str(N)
len_n = len(str(str_n))

def conb(n, r):
    return factorial(n)//factorial(r)//factorial(n-r)
    
def get_num(top, k_val, depth):
    if k_val==0:
        return 1
    elif k_val>(len_n-depth+1):
        return 0
    elif top:
        if int(str_n[depth - 1])==0:
            return get_num(top, k_val, depth + 1)
        else:
            b1 = get_num(top, k_val - 1, depth + 1)
            b2 = (int(str_n[depth-1])-1) * get_num(False, k_val-1, depth+1)
            b3 = get_num(False, k_val, depth + 1)
            return b1+b2+b3
    else:
        return 9**(k_val) * conb(len_n - depth + 1, k_val)
    
    
a1 = get_num(True, K-1, 2)
a2 = (int(str_n[0])-1)*get_num(False, K-1, 2)
a3 = get_num(False, K, 2)

#print(a1, a2, a3)
print(a1+a2+a3)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;

int main() {
	long long N, A, B;
	cin >> N >> A >> B;

	long long x1, x2;
	x1 = N / (A + B);
	x2 = N % (A + B);
	if (x2 < A) {
		cout << A * x1 + x2 << endl;
	}
	else if (x2 >= A) {
		cout << A * x1 + A << endl;
	}

	return 0;
}

Measured memory_bytes: 256
# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


Measured memory_bytes: 46940
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	int n;
	int d[65000];
	while(cin>>n,n){
		long long sum=0,ans=0;
		int tmp;
		for(int i=0;i<n;i++)cin>>tmp,sum+=tmp;
		for(int i=0;i<n-1;i++)cin>>d[i];
		sort(d,d+n-1,greater<int>());
		ans=sum*n;
		for(int i=0;i<n-1;i++){
			sum+=d[i];
			ans=max(ans,sum*(n-i-1));
		}
		cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 1424
#include<iostream>
using namespace std;
int main() {
    int N,M; cin>>N>>M;
    int sum=N;
    for (int i=0; i<M; i++) {
        int tmp; cin>>tmp;
        sum -= tmp;
    }
    if (sum>=0)
        cout<<sum<<endl; 
    else
        cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define vec vector
#define ll long long
#define pii pair<long long, int>

int main(void)
{
	int w, h;
	cin >> w >> h;
	vec<pii> r(w + h);
	rep(i, w) {
		cin >> r[i].first;
		r[i].second = 0;
	}
	rep(i, h) {
		cin >> r[w + i].first;
		r[w + i].second = 1;
	}

	sort(r.begin(), r.end());

	ll ans = 0;
	ll prev0 = h + 1;
	ll prev1 = w + 1;

	rep(i, w + h) {
		if (r[i].second) {
			ans += prev1 * r[i].first;
			prev0--;
		} else {
			ans += prev0 * r[i].first;
			prev1--;
		}
	}
	cout << ans << endl;
}



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

int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    bool f = false;
    if (A == 5)
    {
        if ((B == 5 && C == 7) || (B == 7 && C == 5))
        {
            f = true;
        }
    }
    else if (A == 7)
    {
        if (B == 5 && B == C)
        {
            f = true;
        }
    }
    cout << (f ? "YES" : "NO") << endl;
}


Measured memory_bytes: 256
// Created by arvybhatt

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define p_b push_back
#define m_p make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)

using namespace std;
using ll = long long;

ll power(ll x, ll y) { ll temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } 

int main()
{
    fast;
    int k;cin>>k;
    string s;
    cin>>s;
    if(s.length()<=k)
    	cout<<s<<"\n";
    else
    {
    	string t="";
    	for(int i=0; i<k; i++)
    		t+=s[i];
    	t+="...";
    	cout<<t<<"\n";
    }

}





Measured memory_bytes: 3652
#include <stdio.h>

int main(void)
{
	int n, w;
	int a, b, dummy;
	int array[31] = {0};
	int i , j;
	char c;
	
	scanf("%d%d", &w, &n);
	for (i = 1; i <= 30; i++)array[i] = i;
	for (i = 1; i <= n; i++){
		scanf("%d%c%d", &a, &c, &b);
		dummy = array[a];
		array[a] = array[b];
		array[b] = dummy;
	}
	
	for (i = 1; i <= w; i++){
		printf("%d\n", array[i]);
	}
	
	return (0);
	
}

Measured memory_bytes: 596
#include<stdio.h>

long gozyo(long x,long y){
long r;
long i=1;

while(i>0){
r=x%y;
if(r==0){return y;}
else{x=y;y=r;}

}


}



int main(){
long a,b;
long gcm;
long lcm;

while(scanf("%ld %ld",&a,&b)!=EOF){
 if(a>b){gcm=gozyo(a,b);}
 else{gcm=gozyo(b,a);}
  lcm=a*b/gcm;
 printf("%ld %ld\n",gcm,lcm);
  
}


return 0;
}

Measured memory_bytes: 1856
function Main(input) {
	input = parseInt(input.trim());
  var output = 1; 
  var maxCount = 0;
  for(var i = 1; i <= input; i++){
    var tmp = i;
    var count = 0;
    while(tmp % 2 != 1){
       tmp = tmp / 2;
       count++;
    }
    if(maxCount < count){
       output = i;
       maxCount = count;
    }
   }
  console.log(output);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int MAX_N=262144*2;
vector<int64_t> seg(MAX_N*2-1);
int64_t qu(int a,int b,int k,int l, int r){
  if(r<=a||b<=l){
    return 0;
  }
  else if(a<=l&&r<=b){
    return seg[k];
  }
  else{
    int64_t X=qu(a,b,k*2+1,l,(l+r)/2);
    int64_t Y=qu(a,b,k*2+2,(l+r)/2,r);
    return X+Y;
  }
}
void pu(int64_t a,int b){
  int D=MAX_N-1+b;
  while(D>0){
    seg[D]+=a;
    D--;
    D/=2;
  }
  seg[0]+=a;
}

int main() {
  int N,Q;
  cin>>N>>Q;
  vector<int> p(N);
  for(int i=0;i<N;i++){
    cin>>p[i];
    p[i]--;
  }
  vector<tuple<int,int,int>> q(Q);
  for(int i=0;i<Q;i++){
    int a,b;
    cin>>a>>b;
    q[i]=make_tuple(b,a,i);
  }
  sort(q.begin(),q.end());
  vector<int> la(N,-1);
  vector<int> an(Q);
  int W=0;
  for(int i=0;i<Q;i++){
    int a,b,c;
    tie(a,b,c)=q[i];
    while(W<a){
      if(la[p[W]]!=-1){
        pu(-1,la[p[W]]);
      }
      la[p[W]]=W;
      pu(1,W);
      W++;
    }
    an[c]=qu(b-1,a,0,0,MAX_N);
  }
  for(int i=0;i<Q;i++){
    cout<<an[i]<<endl;
  }
}

Measured memory_bytes: 23668
#include<bits/stdc++.h>
#define maxn 400100
using namespace std;
struct edge{int r,nxt;}e[maxn];
int c[maxn],ptr,a[maxn],vis[maxn],head[maxn],tp,bg,tg[maxn],q[maxn],pre[maxn],esz,f[maxn],n;
void addedge(int u,int v){e[++esz].r=v;e[esz].nxt=head[u];head[u]=esz;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
int getmex(){
	sort(c+1,c+ptr+1),ptr=unique(c+1,c+ptr+1)-c-1;
	for(int i=1;i<=ptr;++i)if(c[i]!=i-1)return i-1;
	return ptr;
}
void dfs(int u){
	for(int t=head[u];t;t=e[t].nxt)
		if(!tg[e[t].r])dfs(e[t].r);
	ptr=0;
	for(int t=head[u];t;t=e[t].nxt)
		if(!tg[e[t].r])c[++ptr]=a[e[t].r];
	a[u]=getmex();
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<=n;++i){
		scanf("%d",&pre[i]);
		if(find(i)!=find(pre[i]))
			f[find(i)]=find(pre[i]),addedge(pre[i],i);//,printf("[%d->%d]",i,pre[i]);
		else bg=i,addedge(pre[i],i);
	}
	for(int i=bg;;i=pre[i]){
		q[++tp]=i,tg[i]=true;
		if(pre[i]==bg)break;
	}
	for(int i=1;i<=tp;++i)dfs(q[i]);
	int f1=-1,f2=-1;
	for(int t=head[bg];t;t=e[t].nxt)if(!tg[e[t].r])
		vis[a[e[t].r]]=true;
	for(int i=0;i<=n+10;++i)if(!vis[i]){
		if(f1<0)f1=i;
		else if(f2<0)f2=i;
	}
	a[bg]=f1;
	for(int i=2;i<=tp;++i){
		ptr=0;
		for(int t=head[q[i]];t;t=e[t].nxt)
			c[++ptr]=a[e[t].r];//,printf("<%d,%d>",q[i],e[t].r);
		a[q[i]]=getmex();
	}
//	for(int i=1;i<=tp;++i)printf("{%d,%d}",q[i],a[q[i]]);
	ptr=0;
	for(int t=head[bg];t;t=e[t].nxt)
		c[++ptr]=a[e[t].r];
	if(getmex()==a[bg])return puts("POSSIBLE"),0;
	a[bg]=f2;
	for(int i=2;i<=tp;++i){
		ptr=0;
		for(int t=head[q[i]];t;t=e[t].nxt)
			c[++ptr]=a[e[t].r];
		a[q[i]]=getmex();
	}
	ptr=0;
	for(int t=head[bg];t;t=e[t].nxt)
		c[++ptr]=a[e[t].r];
	if(getmex()==a[bg])return puts("POSSIBLE"),0;
	puts("IMPOSSIBLE");
}

Measured memory_bytes: 13824
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a, b, H, W;
    
    while (1) {
        scanf("%d%d", &H, &W);
        if (H == 0 && W == 0) {
            break;
        }
        
            for (a = 0; a < H; a++) {
                for (b = 0; b < W; b++) {
                    putchar('#');
                }
                putchar('\n');
            }
        putchar('\n');
    }
    return 0;
}



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

#define HASH 1000003

typedef struct List {
	struct List *next;
	char *s;
	int l;
} list;

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

int hash_string(char* s)
{
	int i, x = 0;
	for (i = 0; s[i] != 0; i++) x = ((x << 5) + s[i] - 'a') % HASH;
	return x;
}

int lex_smaller(char* s1, char* s2)
{
	int i;
	for (i = 0; s1[i] != 0 && s2[i] != 0; i++) {
		if (s1[i] < s2[i]) return 1;
		else if (s1[i] > s2[i]) return -1;
	}
	if (s1[i] == s2[i]) return 0;
	else if (s1[i] == 0) return 1;
	else return -1;
}

int main()
{
	int i, j, l[200001], N;
	char *S[200001], T[1000001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%s", T);
		for (l[i] = 0; T[l[i]] != 0; l[i]++);
		S[i] = (char*)malloc(sizeof(char) * (l[i] + 1));
		for (j = 0; j <= l[i]; j++) S[i][j] = T[j];
	}
	
	int h[200001];
	list *p, *hash[HASH], d[200001];
	for (i = 1; i <= N; i++) {
		h[i] = hash_string(S[i]);
		d[i].s = S[i];
		d[i].l = l[i];
		d[i].next = hash[h[i]];
		hash[h[i]] = &(d[i]);
	}
	
	int k, dp[26];
	long long ans = 0, tmp, pow[32], inv = div_mod(1, 32, HASH);
	for (k = 1, pow[0] = 32; k < 32; k++) pow[k] = pow[k-1] * pow[k-1] % HASH;
	for (i = 1; i <= N; i++) {
		if (l[i] <= 1) continue;
		for (j = 0; j <= l[i]; j++) T[j] = S[i][j];
		for (j = l[i] - 1, k = 0, tmp = 1; j > 0; j >>= 1, k++) if ((j & 1) == 1) tmp = tmp * pow[k] % HASH;
		h[i] = (h[i] - tmp * (T[0] - 'a') % HASH + HASH) % HASH;
		tmp = tmp * inv % HASH;
		h[i] = (h[i] - tmp * (T[1] - 'a') % HASH + HASH) % HASH;
		for (j = 0; j < 26; j++) dp[j] = 0;
		dp[S[i][0] - 'a'] = 1;
		for (j = 1; j < l[i]; j++) {
			dp[S[i][j] - 'a'] = 1;
			for (k = 0; k < 26; k++) {
				if (dp[k] == 0) continue;
				T[j] = 'a' + k;
				h[0] = (tmp * k + h[i]) % HASH;
				for (p = hash[h[0]]; p != NULL; p = p->next) if (p->l == l[i] - j && lex_smaller(&(T[j]), p->s) == 0) break;
				if (p != NULL) ans++;
			}
			tmp = tmp * inv % HASH;
			h[i] = (h[i] - tmp * (S[i][j+1] - 'a') % HASH + HASH) % HASH;
		}
	}
	
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 23492
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define INF_LL (ll)1e18

#define INF (int)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
using ll = long long;
using PII = pair<int, int>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

class LazySegTree{
private:
	int n;
	vector<ll> node, lazy;
	vector<bool> lazyFlag;
public:
	LazySegTree(vector<ll> v){
		int sz = v.size();
		n = 1; while(n < sz) n *= 2;
		node.resize(2*n-1, 0);
		lazy.resize(2*n-1, 0);
		lazyFlag.resize(2*n-1, false);
		REP(i, sz) node[i+n-1] = v[i];
		for(int i = n-2;i >= 0;i--) node[i] = node[2*i+1]+node[2*i+2];
	}

	void eval(int k, int l, int r){
		if(lazyFlag[k]){
			node[k] += lazy[k] * (r-l);
			if(r-l > 1){
				lazy[2*k+1] += lazy[k];
				lazy[2*k+2] += lazy[k];
				lazyFlag[2*k+1] = lazyFlag[2*k+2] = true;
			}
			lazy[k] = 0;
			lazyFlag[k] = false;
		}
	}

	void add(int a, int b, ll x, int k=0, int l=0, int r=-1){
		if(r < 0) r = n;
		eval(k, l, r);
		if(b <= l || r <= a) return;

		if(a <= l && r <= b){
			lazy[k] += x;
			lazyFlag[k] = true;
			eval(k, l, r);
		}else{
			add(a, b, x, k*2+1, l, (l+r)/2);
			add(a, b, x, k*2+2, (l+r)/2, r);
			node[k] = node[k*2+1] + node[k*2+2];
		}
	}

	ll query(int a, int b, int k=0, int l=0, int r=-1){
		if(r < 0) r = n;
		eval(k, l, r);

		if(b <= l || r <= a) return 0;
		if(a <= l && r <= b) return node[k];

		return query(a, b, k*2+1, l, (l+r)/2) + query(a, b, k*2+2, (l+r)/2, r);
	}
};

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	vector<ll> v(s.size());
	vector<int> use;
	REP(i, s.size())
		v[i] = s[i]-'0';
	vector<int> d;
	int cnt = 0;
	int now = v[0];
	REP(i, v.size()){
		if(now == v[i])
			cnt++;
		else{
			d.push_back(cnt);
			cnt = 1;
			now = 1-now;
		}
	}
	if(cnt != 0)
		d.push_back(cnt);
	if(d.size() == 1){
		cout << d[0] << endl;
		return 0;
	}
	int res = 0;
	int sum = 0;
	REP(i, d.size()){
		sum += d[i];
		if(sum <= s.size()-sum+d[i])
			res = max(res, sum);
	}
	sum = 0;
	for(int i = d.size()-1;i >= 0;i--){
		sum += d[i];
		if(sum <= s.size()-sum+d[i])
			res = max(res, sum);
	}

	cout << res << endl;
}


Measured memory_bytes: 1488
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define nn 206008
int n;
struct edge{
	int x,y,c;
};
bool operator<(edge a,edge b){
	return a.c>b.c;
}
edge e[nn];

int pa[nn];
int find(int x){
	if(pa[x]==x) return x;
	return pa[x]=find(pa[x]);
}
int w,h;int loop[nn];
int used[nn];

signed main()
{
	for(int i=0;i<nn;i++) pa[i]=i;
	scanf("%lld%lld%lld",&n,&h,&w);int ans=0;
	for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].c),e[i].y+=nn/2-1;
	sort(e+1,e+n+1);
	for(int i=1;i<=n;i++){
		int x=e[i].x,y=e[i].y;//
		if(find(x)==find(y)) {
			if(loop[find(x)]==0) loop[find(x)]=1,ans+=e[i].c;
			continue;
		}
		if(loop[find(x)]&loop[find(y)]) continue;
		loop[find(y)]|=loop[find(x)];
		pa[find(x)]=find(y);
		ans+=e[i].c;
	}
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

#define int long long
#define pb push_back
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) FOR(i, n, 0);

signed main () {
  cin.tie(0);
  cout << setprecision(10);

  int n, m; cin >> n >> m;
  int k = 1;
  REP(i, m) {
    k *= 2;
  }
  cout << k * (100 * n + 1800 * m) << endl;
}


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

using namespace std;

bool judge(string S) {
	string tmp = S;
	reverse(tmp.begin(), tmp.end());

	if (S == tmp) {
		return true;
	}
	else {
		return false;
	}

	return false;
}

int main(void) {
	string S, substr1, substr2;

	cin >> S;

	substr1 = S.substr(0, (S.size() - 1) / 2);
	substr2 = S.substr((S.size() + 3) / 2 -1, (S.size() - 1) / 2);

	if (judge(S) && judge(substr1) && judge(substr2)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}






	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<": "<<x<<endl
typedef long long ll;
const ll mod = (ll)1e9+7;
int w,d,n;
int m[59][59];
int x[59],y[59],z[59];
int myabs(int x){return x<0?-x:x;}
int main()
{
    scanf("%d%d%d",&w,&d,&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&x[i],&y[i],&z[i]);
    int flag=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(myabs(x[i]-x[j])+myabs(y[i]-y[j])<myabs(z[i]-z[j]))flag=0;
        }
    if(flag==0){
        printf("No\n");return 0;
    }
    for(int i=1;i<=w;i++)for(int j=1;j<=d;j++)m[i][j]=-100000;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=w;j++){
            for(int k=1;k<=d;k++){
                m[j][k]=max(m[j][k],z[i]-myabs(x[i]-j)-myabs(y[i]-k));
            }
        }
    }
    int ans=0;
    for(int i=1;i<=w;i++)for(int j=1;j<=d;j++)ans+=m[i][j];
    printf("%d\n",ans);
    return 0;
}
/*

*/



Measured memory_bytes: 3228
program test
implicit none

integer(8),parameter :: inf_minus = -1d10
integer(8) :: i,j,k,l,m,n
integer(8) :: a(10),b(10),dp(-100:10000)=inf_minus
integer(8) :: match_use(9) = (/2,5,5,4,5,6,3,7,6/)
integer(8) :: ans(10000)=0,rest

read(*,*) n,m
read(*,*) (a(i),i=1,m)
do i=1,m
	b(i) = match_use(a(i))
enddo

call heapsort_down(m,a(1:m),b(1:m))

dp(0) = 0

!dp(i)とは、i本のマッチを使って作成できる最大の文字数
do i=0,n
	do j=1,m
		if(i-b(j)>=0 )then
			dp(i) = max(dp(i),(dp(i-b(j))+1))
		endif
	enddo
enddo

!上の桁から、利用可能な数字か確かめていく
rest = n
do i=1,dp(n)
	do j=1,m
		if(rest-b(j)>=0 .and.dp(rest-b(j))==(dp(rest)-1))then
			rest = rest-b(j)
			ans(i) = a(j)
			goto 100
		endif
	enddo
	100 continue
enddo


write(*,'(10000(I1))') (ans(i),i=1,dp(n))

contains
subroutine heapsort_down(n,y1,y2)
 
	implicit none
	integer(8),intent(in) :: n
	integer(8),intent(inout) :: y1(1:n)
	integer(8),intent(inout) :: y2(1:n)
	integer(8) :: i,k,j,l
	integer(8) :: t1,t2
	
	l = n/2+1
	k = n
 
	do while (k /= 1)
		 if(l > 1) then
				l = l-1
				t1 = y1(l)
				t2 = y2(l)
				
		 else
				t1 = y1(k)
				t2 = y2(k)
				y1(k) = y1(1)
				y2(k) = y2(1)
				k = k-1
				if(k == 1) then
					 y1(1) = t1
					 y2(1) = t2
					 exit
				endif
		 endif
 
		 i = l
		 j = l+l
 
		 do while(j <= k)
				if(j < k) then
					 if(y1(j) > y1(j+1)) j = j+1
				endif
				
				if (t1 > y1(j)) then
					 y1(i) = y1(j)
					 y2(i) = y2(j)
					 i = j
					 j = j+j
				else
					 j = k+1
				endif
		 
		 enddo
		 
		 y1(i) = t1
		 y2(i) = t2
	
	enddo
	return
 
end subroutine heapsort_down
 
subroutine heapsort_up(n,y1,y2)
 
	implicit none
	integer(8),intent(in) :: n
	integer(8),intent(inout) :: y1(1:n)
	integer(8),intent(inout) :: y2(1:n)
	integer(8) :: i,k,j,l
	integer(8) :: t1,t2
	
	l = n/2+1
	k = n
 
	do while (k /= 1)
		 if(l > 1) then
				l = l-1
				t1 = y1(l)
				t2 = y2(l)
				
		 else
				t1 = y1(k)
				t2 = y2(k)
				y1(k) = y1(1)
				y2(k) = y2(1)
				k = k-1
				if(k == 1) then
					 y1(1) = t1
					 y2(1) = t2
					 exit
				endif
		 endif
 
		 i = l
		 j = l+l
 
		 do while(j <= k)
				if(j < k) then
					 if(y1(j) < y1(j+1)) j = j+1
				endif
				
				if (t1 < y1(j)) then
					 y1(i) = y1(j)
					 y2(i) = y2(j)
					 i = j
					 j = j+j
				else
					 j = k+1
				endif
		 
		 enddo
		 
		 y1(i) = t1
		 y2(i) = t2
	
	enddo
	return
 
end subroutine heapsort_up

end program

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  if(N==1){
    cout << 1 << endl;
    return 0;
  } 
  vector<int> P(N);
  for (int i=0; i<N; i++){
    cin >> P.at(i);
  } 
  int min=P.at(0);
  int ans=1;
  for(int i=1; i<N; i++){
    if(min>=P.at(i)){
      ans++;
      min=P.at(i);
    }
  }  
  cout << ans << endl; 
}

// int型の2次元配列(3×4要素の)の宣言
  //vector<vector<int>> data(3, vector<int>(4));

  // 入力 (2重ループを用いる)
  //for (int i = 0; i < 3; i++) {
    //for (int j = 0; j < 4; j++) {
      //cin >> data.at(i).at(j);
    //}
  //}


Measured memory_bytes: 1152
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#pragma GCC optimize("Ofast")
//#define endl '/n'
using namespace std;
typedef long long ll;
const long long INF=(1LL<<62);
const double inf=pow(10,10);
double pi=3.141592653589793;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const ll MOD = 1000000007;
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

long long gcd(long long a,long long b){
	if(a<b)swap(a,b);
	if(a%b==0)return b;
	else return gcd(a%b,b);
}

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

string myrev(string s){
	string t=s;
	reverse(t.begin(),t.end());
	return t;
}


int main(){
	init();
	string s;cin>>s;
	if(s[0]=='9'||s[1]=='9')cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
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 long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
int main(){
	ll mod=2019;
	ll l,r;
	ll ans=INF;
	cin >>l>>r;
	
	if(r-l < 2050){
		for(ll a=l; a<r;a++){
			for(ll b=a+1;b<=r;b++){
				chmin(ans,(a%mod)*(b%mod)%mod);
			}
		}
	}else{
		ans=0;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
  cin>>s;
  map<string,int>mp;
  mp["MON"]=6;mp["SUN"]=7;mp["TUE"]=5;
  mp["WED"]=4;
  mp["THU"]=3;
  mp["FRI"]=2;
  mp["SAT"]=1;
  cout<<mp[s]<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	int v[22], c[22];
	for(int i=0;i<n;i++){
		cin >> v[i];
	}
	for(int i=0;i<n;i++){
		cin >> c[i];
	}
	int ans = 0;
	for(int bit=0;bit<(1<<n);bit++){
		int sum = 0;
		for(int i=0;i<n;i++){
			if(bit>>i&1){
				sum += v[i]-c[i];
			}
		}
		ans = max(ans, sum);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
a = $stdin.gets.chomp.to_i
b = $stdin.gets.chomp.to_i
c = $stdin.gets.chomp.to_i
d = $stdin.gets.chomp.to_i
e = $stdin.gets.chomp.to_i
k = $stdin.gets.chomp.to_i

if e - a <= k
 puts "Yay!"
else
 puts ":("
end

Measured memory_bytes: 1788
N=int(input())
preorder=list(map(int,input().split()))
inorder=list(map(int,input().split()))
pre_iter=iter(preorder)
bisect_tree = [[None,None] for i in range(N+1)]

def reconst(l,r):
    global pre_iter
    if r-l <= 0:
        return
    if r-l == 1:
        next(pre_iter)
        return inorder[l]
    partial_root = next(pre_iter)
    partial_root_position = inorder.index(partial_root)
    left_child = reconst(l,partial_root_position)
    right_child = reconst(partial_root_position+1,r)
    bisect_tree[partial_root][0]=left_child
    bisect_tree[partial_root][1]=right_child
    return partial_root
ans=[]
def postorder(node):
    if bisect_tree[node] == [None,None]:
        ans.append(node)
    else:
        if bisect_tree[node][0] != None:
            postorder(bisect_tree[node][0])
        if bisect_tree[node][1] != None:
            postorder(bisect_tree[node][1])
        ans.append(node)

def root_search():
    parent=[-1]*(N+1)
    for i in range(1,N+1):
        if bisect_tree[i][0] != None:
            parent[bisect_tree[i][0]]=i
        if bisect_tree[i][1] != None:
            parent[bisect_tree[i][1]]=i
    for i in range(1,N+1):
        if parent[i] == -1:
            break
    return i

reconst(0,N)
root = root_search()
postorder(root)
print(*ans)


Measured memory_bytes: 5612
def LI(): return list(map(int,input().split()))
N,K = LI()
a = LI()
ans = float('INF')
for i in range(2**(N-1)):
    bit = [i>>j&1 for j in range(N-1)]
    if K-1!=sum(bit):
        continue
    #print("bit",bit)
    cost,kijun = 0,a[0]
    for k in range(N-1):
        if bit[k]==0:
            kijun = max(kijun,a[k+1])
            continue
        if a[k+1]>=kijun+1:
            kijun = a[k+1]
            continue
        cost += (kijun+1)-a[k+1]
        kijun += 1
    ans = min(ans,cost)
print(ans)

Measured memory_bytes: 9132
S=input()
if S.count("N")>=1 and S.count("S")==0:
    print("No")
elif S.count("S")>=1 and S.count("N")==0:
    print("No")
elif S.count("W")>=1 and S.count("E")==0:
    print("No")
elif S.count("E")>=1 and S.count("W")==0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3060
#include <stdio.h>
const int MAX = 100 + 10 ;
int main()
{
	int a[3];
	int i=0;
	scanf("%d",&a[0]);
	scanf("%d",&a[1]);
	scanf("%d",&a[2]);
	for(i=0;i<3;i++)
	{
		int j=0;
		for(j=0;j<2-i;j++)
		{
			if(a[j]>a[j+1])
			{
				int t=a[j+1];
				a[j+1]=a[j];
				a[j]=t;
			}
		}
	}
	printf("%d",a[2]-a[0]);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N,M,C;cin>>N>>M>>C;
  
  vector<int> B(M);
  for(int i=0;i<M;i++){
    cin>>B[i];
  }
  
  vector<vector<int>> A(N,vector<int>(M));
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      cin>>A[i][j];
    }
  }
  
  
  int ans=0;
  
  vector<int> sum(N);
  
  for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
      sum[i]+=A[i][j]*B[j];
    }
    if(sum[i]+C>0){
      ans++;
    }
    else{
      ans=ans;
    }
  }  
  
  cout<<ans<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll = long long;
using P = pair<int,int>;
int main(void) {
    int a, b; cin >> a >> b;
    bool ok = false;
    if(a<9 && b<9) ok = true;
    if(ok) cout << "Yay!";
    else cout << ":(";
}


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

const ll N = 1e5+5, INF = -1;
ll n, k;
ll d[4][N], dp[4][N];

int main(){
	cin >> n;
	for(ll i = 0; i < n; i++)
		for(ll j = 0; j < 3; j++)
			cin >> d[j][i];

	for(ll i = 0; i < 4; i++)
		for(ll j = 0; j < N; j++)
			dp[i][j] = INF;

	for(ll i = 0; i < 4; i++)
		dp[i][n-1] = d[i][n-1];

	for(ll i = n-2; i >= 0; i--){
		dp[0][i] = d[0][i] + max(dp[1][i+1], dp[2][i+1]);	 
		dp[1][i] = d[1][i] + max(dp[0][i+1], dp[2][i+1]);
		dp[2][i] = d[2][i] + max(dp[0][i+1], dp[1][i+1]);
	}
	cout << max({dp[0][0], dp[1][0], dp[2][0]}) << endl;
}

Measured memory_bytes: 6400
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#define MAXA 100000
#define MAX 20000000000
#define s(i) scanf("%d", &(i))
#define p(i) printf("%d", (i))
#define ps() printf(" ") 
#define rer(i,j,k) for((i)=(j);(i)<(k);++(i))
#define ret(i,j,k) for((i)=(j);(i)>=(k);--(i))
using namespace std;
int main(){
	string a, b, c;
	int num = 0, i, t = 0, is = 0;
	cin >> a >> b;
	c = a+b;
	ret(i,c.length()-1,0){
		num += (c[i]-'0')*pow(10,t);
		t++;
	}
	rer(i,1,1000000){
		if(pow(i,2)==num){
			is = 1;
			cout << "Yes" <<endl;
			break;
		}
	}
	if(!is){
		cout << "No" << endl;
	}
	return 0;
} 

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<ctype.h>
#include<string>
using namespace std;
int main(){
	int A, B;
	cin >> A >> B;
	cout << max(A, B) + max(min(A, B), max(A, B) - 1) << endl;;
	return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())

lst = [list(map(int,input().split())) for _ in range(M)]
D = [[] for i in range(N)]
#print(lst)
submit =[0]*M
for i in range(M):
    D[lst[i][0]-1].append((lst[i][1],i))

#print(D)

for i,d in enumerate(D):
    #print(i,d)
    d.sort(key=lambda x: x[0])
    #print(d)
    for k,(y,j) in enumerate(d):
        #print(i,k,y,j)
        submit[j] = str(i+1).zfill(6)+str(k+1).zfill(6)

print(*submit,sep = '\n')

Measured memory_bytes: 55580
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repR(i, n) for(int i = n; i >= 0; ++i)
#define FDS(i, n) for(int i = 0; i < n; ++i)
#define FDSR(i, n) for(int i = n; i >= 0; ++i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define FORR(i, m, n) for(int i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define itn int
#define ednl endl
using namespace std;
typedef long long ll;
int main(){
	int a,b;
	cin>>a>>b;
	if(a%b==0){
		cout<<0<<endl;
	}
	else{
		cout<<1<<endl;
	}
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

struct LazySegTree {
  vector<ll> seg, lazy;
  int size;
  LazySegTree() {}
  LazySegTree(int n) {
    init(n);
  }
  void init(int n) {
    size = 1;
    while (size < n) size *= 2;
    seg.resize(size * 2);
    lazy.resize(size * 2);
    for(int i = 0; i < size*2; i++)seg[i]=-INF;
  }
  void update(int k,ll v){
    k += size-1;
    seg[k] = v;
    while(k > 0){
      k = (k - 1)/2;
      seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }
  void push(int k, int l, int r) {
    seg[k] += lazy[k];
    if (r - l > 1) {
      lazy[k * 2 + 1] += lazy[k];
      lazy[k * 2 + 2] += lazy[k];
    }
    lazy[k] = 0;
  }
  void add(int a, int b, ll v, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      lazy[k] += v;
      push(k, l, r);
    } else {
      add(a, b, v, k * 2 + 1, l, (l + r) / 2);
      add(a, b, v, k * 2 + 2, (l + r) / 2, r);
      seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
    }
  }
  void add(int a, int b, ll v) {
    add(a, b, v, 0, 0, size);
  }
  ll query(int a, int b, int k, int l, int r) {
    push(k, l, r);
    if (r <= a || b <= l) return -INF*100; // caution
    if (a <= l && r <= b) return seg[k];
    ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl,vr);
  }
  ll query(int a, int b) {
    return query(a, b, 0, 0, size);
  }
};

ll N,M;
vector<ll> rs[200010];

int main(){
  cin>>N>>M;
  LazySegTree sgt(M+2);
  rep(i,M+2)sgt.update(i,i);
  rep(i,N){
    ll a,b;
    cin>>a>>b;
    rs[a].push_back(b);
  }

  ll res=0;
  rep(s,M){
    ll tmin=s+2;
    for(ll r : rs[s]){
      sgt.add(0,r+1,1);
    }
    ll x=sgt.query(tmin,M+2);
    maxch(res,x-(s+M+1));
  }
  maxch(res,N-M);
  cout<<res<<endl;
  return 0;
}


Measured memory_bytes: 18304
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<pair<ll,ll>> dep;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい

ll N,M;

int main(){
	cin>>N>>M;
	if(2*N>=M) cout<<M/2<<endl;
	else cout<<N+(M-2*N)/4<<endl;
	
	  return 0;
  }


Measured memory_bytes: 256
from collections import deque
from enum import Enum
import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


LIST = deque()

num_command = int(input())

for loop in range(num_command):

    input_command = input()

    if input_command == 'deleteFirst':
        LIST.popleft()
    elif input_command == 'deleteLast':
        LIST.pop();
    else:
        com,num = input_command.split()

        if com == 'insert':
            LIST.appendleft(num)
        elif com == 'delete':
            try:
                LIST.remove(num)
            except:
                pass

print(' '.join(LIST))




Measured memory_bytes: 70164
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
def lcm(a, b):
	return a * b // gcd (a, b)
  
A,B,C,D=map(int, input().split())
divC = B//C - (A-1)//C
divD = B//D - (A-1)//D
CD = lcm(C,D)
divCD = B//CD - (A-1)//CD
divsum=divC+divD-divCD
answer=B-A+1-divsum

print(answer)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


int main()
{
	string s;
	cin>>s;
	for(int i=0;i<=1;i++)
	{
		if(s[i]==s[i+1]&&s[i+1]==s[i+2])
		{
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
import math
N=int(input())

han=999999999999999999999999999999999999999999
b=0



for a in range(1,int(math.sqrt(N))+1):
    if N%a==0:
        A=N/a
        if A>a:
            gou=A-a
        else:
            gou=a-A
        b=a
        if gou<han:
            han=gou
            kot=A+a

print(int(kot)-2)


Measured memory_bytes: 9156
/*
  https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=651&page=show_problem&problem=4844
*/


#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using psi=pair<string,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
template<class T>void geti(T&a){for(auto&_:a)cin>>_;}
template<class T>void getii(T&a){for(auto&_:a)geti(_);}
void put(string d){}template<class H,class...T>void put(string d,H&h,T&...t){cout<<h;if(sizeof...(t))cout<<d;put(d,t...);}
template<class T>void puti(T&a,string d=" "){bool f=1;for(auto&_:a)cout<<(exchange(f,0)?"":d)<<_;cout<<endl;}
template<class T>void putii(T&a,string d=" "){for(auto&_:a)puti(_,d);}
#define dcl(...) ll __VA_ARGS__;get(__VA_ARGS__)
#define dclt(t,...) t __VA_ARGS__;get(__VA_ARGS__)
vs sepstr(string s,string r){vs res;regex R("[^|]+");for(auto _:r)s=regex_replace(s,regex("[\\"+string{_}+"]"),"|"+string{_}+"|");for(sregex_iterator itr(all(s),R),end;itr!=end;++itr)res.pb(itr->str());return res;}

template<class T>string bitstr(T x){return typeid(T)==typeid(int)?bitset<32>(x).to_string('_','#'):bitset<64>(x).to_string();}
template<class T>int bitcnt(T x){return typeid(T)==typeid(int)?__builtin_popcount(x):__builtin_popcountll(x);}
template<class T>int bitdig(T x){return x?typeid(T)==typeid(int)?32-__builtin_clz(x):64-__builtin_clzll(x):0;}
template<class T>int bitpow(T x){return x?typeid(T)==typeid(int)?__builtin_ctz(x):__builtin_ctzll(x):0;}

constexpr void bitswap(int &b,int p, int q){
	int f=(!!(b&(1<<p)))^!!(b&(1<<q));
	b^=(1<<p)*f;
	b^=(1<<q)*f;
}


inline int solve(int n,int b,int p){
	if(bitcnt(b)!=bitcnt(p)) return INT_MAX;
	int ans=0;
	rep(i,n-1){
		int j;
		for(j=i;(!(b&(1<<j)))!=!(p&(1<<i));j++);
		bitswap(b,i,j);
		ans+=(j-i);
	}
	return ans;
}

int main(){
	int n,m;
	while(cin>>n>>m){
		int b=0;
		int p=0;
		rep(i,n){
			dcl(t);
			b=b*2+t;
		}
		rep(i,m){
			dcl(t);
			rep(lp,t){
				p=p*2+i%2;
			}
		}
		cout<<min(solve(n,b,p), solve(n,b,(~p)&((1<<n)-1)))<<endl;
	}
	return 0;
}



Measured memory_bytes: 3200
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>
#include<functional>

using namespace std;
typedef long long int ll;

#define C cout<<
#define E <<endl

ll n,m,a,b,c,x,y,z,aa[100010],ba[100010];
bool r,ra,rb,rc;
string s,sa,sb,sc;
char ca,cb,cc[1000][1000],cd[1000][1000];
vector<ll> va,vb,vc;

int main(){
    cin>>s;
    a=s.size()*2;
    b=0;
    for(ll i=0;i<s.size();i++){
        if(s[i]=='A')a=min(a,i);
        if(s[i]=='Z')b=max(b,i);
    }
    C b-a+1 E;
}

Measured memory_bytes: 640
#include<cstdio>

int main(){
    int n;
    scanf("%d",&n);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int u;
        scanf("%d",&u);
        if(i%2 && u%2) ans++;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1728
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N;
  cin>>N;
  vector<Int>A(N);
  cin>>A;

  vector<P> H;
  Int ans = 1000;
  H.push_back(P(0, 1000));
  for(Int i=0;i<N;i++){
    P v = P(-1, -1);
    for(Int j=0;j<(Int)H.size();j++){
      Int b, x; tie(b, x) = H[j];
      Int a = 0;
      for(Int k=j;k<=i;k++) Max(a, A[k]);
      x += b * a;
      Int p = x % A[i];
      Int q = x / A[i];
      Max(v, P(q, p));
      Max(ans, x);
    }
    H.push_back(v);
  }
  //pr(H);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3660
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}
func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}
func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	h := iScan()
	ans := 0
	x := 1
	for h != 0 {
		ans += x
		x *= 2
		h /= 2
	}
	fmt.Println(ans)
}


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

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

long long gcdary(long long a[],long long n)
{
  if(n==1){
    return a[0];
  }else if(n==2){
    return (gcd(a[0],a[1]));
  }else{
    return (gcd(a[0],gcdary(&a[1],n-1)));
  }
}


int main(void)
{
  long N,X;
  long long x[200000];
  long long dist[200000];
  scanf("%ld %ld",&N,&X);
  for(long i=0;i<N;i++){
    scanf("%lld",&x[i]);
  }


  for(long i=0;i<N;i++){
    dist[i]=abs(X-x[i]);
  }

  printf("%lld\n",gcdary(dist,N));
  return 0;
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <utility>
 
#define YNUM(X) ( X < 0 ? X + 3 : X )
 
typedef std::pair<int, int> WH;
//typedef std::vector<WH> whvec;
 
int h, w;
bool map[502][502];
std::string in;
//std::vector<std::vector<whvec> > data(3, std::vector<whvec>(502));
int data[3][502][502];
int data_max = 0;
int height_sum[502][502], width_sum[502][502];
int data_pt[3][502];
WH wh;
 
int main(){
    while( std::cin >> h >> w, w + h != 0 ){
        data_max = 0;
 
        memset( data_pt, 0, sizeof(data_pt) );
        memset( height_sum, 0, sizeof(height_sum) );
        memset( width_sum, 0, sizeof(width_sum) );
 
        for( int i = 1; i <= h; ++i ){
            std::cin >> in;
            for( int l = 1; l <= w; ++l ){
                map[i][l] = ( in[l - 1] == '.' );
                if(map[i][l]){
                    width_sum[i][l] = width_sum[i][l - 1] + 1;
                    height_sum[i][l] = height_sum[i - 1][l] + 1;
                }
            }
        }
 
        for( int i = 1, n = 1; n <= h; n++, i = n % 3 ){
            for( int l = 1; l <= w; l++ ){
                //data[i][l] = 0;
 				memset( data[i][l], 0, sizeof(int) * 502 );
                if( map[n][l] ){
                    if( map[n - 1][l] && map[n][l - 1] ){
                        int x_cnt = width_sum[n][l], y_cnt = height_sum[n][l];
 
                        for( int m = 0; m < 502; ++m ){
                            if( data[YNUM(i - 1)][l][m] ){
                            	data[i][l][std::min(m, x_cnt)] = data[YNUM(i - 1)][l][m] + 1;
                            	data_max = std::max( data_max, wh.first * wh.second );
                        	}
                        }
                        for( int m = 0; m < 502; ++m ){
                            if( data[i][l - 1][m] ){
                            	data[i][l][m + 1] = std::min(data[i][l - 1][m], y_cnt);
                            	data_max = std::max( data_max, (m + 1) * data[i][l][m + 1] );
                            }
                        }
                         
                    }else if( map[n - 1][l] ){
                        for( int m = 0; m < 502; ++m ){
                            if( data[YNUM(i - 1)][l] ){
                            	data[i][l][1] = std::max( data[i][l][1], data[YNUM(i - 1)][l][m] + 1 );
                            	data_max = std::max( data_max, wh.first * wh.second );
                        	}
                    	}
 
                    }else if( map[n][l - 1] ){
                        for( int m = 1; m < 502; ++m ){
                            if( data[i][l - 1][m] ){
                            	data[i][l][m + 1] = std::max( data[i][l][m + 1], 1 );
                       	    	data_max = std::max( data_max, (m + 1) * data[i][l][1] );
                        	}
                        }
 
                    }else data[i][l][1] = std::max( data[i][l][1], 1 ), data_max = std::max( data_max, data[i][l][1] );
 
                }   
            }
        }
 
        std::cout << data_max << std::endl;
    }
    return 0;
}

Measured memory_bytes: 6384
N = int(input())
counts = dict()
for i in range(N):
    s = input()
    s_lst = list(s)
    s_lst.sort()
    s = "".join(s_lst)
    if s in counts:
        counts[s] += 1
    else:
        counts[s] = 1

ans = 0
for v in counts.values():
    ans += v * (v - 1) // 2
print(ans)

Measured memory_bytes: 17808
#include<stdio.h>

int main(){
	int w, h, x, y;
	scanf("%d%d%d%d", &w, &h, &x, &y);
	
	printf("%lf", (1.*w*h)/2.);
	if(w == 2 * x && h == 2 * y){
		printf(" 1\n");
	} else {
		printf(" 0\n");
	}
} 


Measured memory_bytes: 1748