akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    string t ; cin >> t;
    ll n = t.size();

    if(t[0] == '?'){

        if(t[1] == 'D'){
            t[0] = 'P';
        }
        else if(t[1] == '?'){
            t[0] = 'P';
            t[1] = 'D';
        }
        else{
            t[0] = 'D';
        }

    }

    rep(i,n){
        if(i == 0) continue;
        if(i == n-1) continue;

        if(t[i] == '?'){
            if(t[i-1] == 'P'){
                t[i] = 'D';
                continue;
            }
            else if(t[i+1] == '?'){
                t[i] = 'P';
                t[i+1] = 'D';
                i++;
                continue;
            }
            else{
                t[i] = 'D';
            }
        }

    }

    if(t[n-1] == '?') t[n-1] = 'D';

    cout << t << endl;

}

Measured memory_bytes: 3752
def main():
    a,b,c,d=map(int,input().split())
    while a>0 or c>0:
        c-=b
        if c<=0:
            print('Yes')
            exit()
        a-=d
        if a<=0:
            print('No')
            exit()

if __name__ == '__main__':
    main()

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

using namespace std;
typedef long long ll;

const int N=100005;
const ll inf=1e18;

void gi(int&x){static char c;for(c=getchar();c<'0'||c>'9';c=getchar());for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);}
void gc(char&c){for(c=getchar();c!='+'&&c!='-';c=getchar());}

int n,a[N];
char op[N];
ll f0,f1,f2;

int main(){
	gi(n),gi(a[0]);
	for(int i=1;i<n;i++)gc(op[i]),gi(a[i]);
	f0=a[0],f1=f2=-inf;
	for(int i=1;i<n;i++){
		if(op[i]=='-'){
			f2-=a[i],f1+=a[i],f0-=a[i];
			if(f1>f2)f2=f1;if(f0>f1)f1=f0;
		}else f2+=a[i],f1-=a[i],f0+=a[i];
		if(f2>f1)f1=f2;if(f1>f0)f0=f1; 
	}
	printf("%lld\n",f0);
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = 1; i <= (int)(n); i++)
#define drep(i, n) for(int i = (n)-1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

// Mod int
const int mod = 1000000007;
// const int mod = 998244353;
struct mint {
  ll x;
  mint():x(0){}
  mint(ll x):x((x%mod+mod)%mod){}
  // mint(ll x):x(x){}
  mint& fix() { x = (x%mod+mod)%mod; return *this;}
  mint operator-() const { return mint(0) - *this;}
  mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  mint operator+(const mint& a)const{ return mint(*this) += a;}
  mint operator-(const mint& a)const{ return mint(*this) -= a;}
  mint operator*(const mint& a)const{ return mint(*this) *= a;}
  bool operator<(const mint& a)const{ return x < a.x;}
  bool operator==(const mint& a)const{ return x == a.x;}
};
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
//



int main() {
  int n, k;
  cin >> n >> k;
  vi a(n);
  rep(i, n) cin >> a[i];
  int l=0, r = 1e9;
  while (r - l > 1) {
    int x = (l+r)/2;
    auto f = [&](int x) {
      ll now = 0;
      rep(i, n) now += (a[i] - 1)/x;
      return now <= k;
    };
    if (f(x)) r = x; else l = x;
  }
  cout << r << endl;
  return 0;
}

Measured memory_bytes: 3988
#include<stdio.h>

int gcd(int i, int j);

int main(){
  int i,j;
  int gcd_num;

  scanf("%d %d", &i,&j);

  gcd_num=gcd(i,j);

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

  return 0;

}

int gcd(int i, int j)
{
  int n;

  if(i==0||j==0){
    fprintf(stderr, "引数エラーです。\n");
    return 0;
  }

  while((n=i%j)!=0)
    {
      i=j;
      j=n;
    }
  return j;
}

Measured memory_bytes: 596
#AtCoder Beginner Contest 083 B Some Sums
#n, a, b = map(int,[input().split()])
list = input().split()
n = int(list[0])
a = int(list[1])
b = int(list[2])

sums = 0

def sumStr(x):
    tmp = 0
    for i in range(len(str(x))):
        tmp += int((str(x))[i:i+1])
    return tmp

for i in range(n):
    sum = sumStr(i+1)
    if a <= sum  and sum <= b:
        sums = sums + i + 1


print(sums)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  int N;
  cin >> N;
  vector<int> T(N);
  int sum_time = 0;
  rep(i, N)
  {
    cin >> T[i];
    sum_time += T[i];
  }
  int M;
  cin >> M;
  vector<int> ans(M);
  rep(i, M)
  {
    int P, X;
    cin >> P >> X;
    ans[i] = sum_time - T[P - 1] + X;
  }
  printVector(ans);
  return 0;
}

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

typedef long long ll;

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

    int S; cin >> S;
    int h = S/3600;
    int a = 3600*h;
    a = S - a;
    int m = a/60;
    int b = 60*m;
    int s = a - b;
    cout << h << ':' << m << ':' << s << endl;
    return 0;
}


Measured memory_bytes: 3152
#include <iostream>
#include <math.h>
#include<iomanip>
using namespace std;

int main(){
  int n, i = 1;
  cin >> n;
  while(++i <= n){
    int x = i;
    if(x % 3 == 0){
      cout << " " << i;
      continue;
    }
    while(x){
      if(x % 10 == 3){
        cout << " " << i;
        break;
      }
      x /= 10;
    }
  }
  cout << endl;
}



Measured memory_bytes: 3108
fn main() {
    proconio::input! {
        n: usize,
        mut cs: proconio::marker::Chars,
    }
    // W..R to R..W
    let mut count = 0usize;
    let mut i = 0;
    let mut j = n - 1;
    while i < j {
        if cs[i] == 'W' && cs[j] == 'R' {
            cs.swap(i, j);
            count += 1;
            i += 1;
            if j == 0 {
                break;
            } else {
                j -= 1;
            }
        } else if cs[i] == 'W' {
            // cs[j] != 'R'
            if j == 0 {
                break;
            } else {
                j -= 1;
            }
        } else if cs[j] == 'R' {
            i += 1;
        } else {
            i += 1;
            if j == 0 {
                break;
            } else {
                j -= 1;
            }
        }
    }
    println!("{}", count);
}


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

int main() {
	int w, h, n;
	cin>>w>>h>>n;
	int i=0, j=0;
	int x,y,a;
	while(n--){
		
		cin>>x>>y>>a;
		if(a==1){
			if(x>i){
				i=x;
			}
		}
		else if(a==2){
			if(x<w){
				w=x;
			}
			
		}
		else if(a==3){
			if(y>j){
				j=y;
			}
			
		}
		else{
			if(y<h){
				h=y;
			}

	}
	}
	if(w<=i | h<=j) cout<<0;
	else cout<<(h-j)*(w-i);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    string s;
    cin >> s;

    if(s[0] == 'a' && s[1] == 'b' && s[2] == 'c')
        cout << "Yes" << endl;
    else if(s[0] == 'a' && s[1] == 'c' && s[2] == 'b')
        cout << "Yes" << endl;
    else if(s[0] == 'b' && s[1] == 'a' && s[2] == 'c')
        cout << "Yes" << endl;
    else if(s[0] == 'b' && s[1] == 'c' && s[2] == 'a')
        cout << "Yes" << endl;
    else if(s[0] == 'c' && s[1] == 'a' && s[2] == 'b')
        cout << "Yes" << endl;
    else if(s[0] == 'c' && s[1] == 'b' && s[2] == 'a')
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


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

int main(){
	int a,b,c,d;
	cin >> a>>b>>c>>d;

	int l = a+b;
	int r = c+d;
	if (l>r) cout << "Left" << endl;
	else if (l<r) cout << "Right"<<endl;
	else cout << "Balanced" << endl;

	return 0;
}


Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
class Tree:
    __slots__ = ['id', 'p', 'sibling', 'degree', 'depth', 'height', 'type', 'c']
    def __init__(self, id):
        self.id = id
        self.p = -1
        self.sibling = -1
        self.degree = 0
        self.depth = 0
        self.height = 0
        self.type = "leaf"
        self.c = []
    def __str__(self):
        return f"node {self.id}: parent = {self.p}, sibling = {self.sibling}, degree = {self.degree}, depth = {self.depth}, height = {self.height}, {self.type}"
n = int(input())
tree = tuple(Tree(i) for i in range(n))
for _ in range(n):
    id, *c = (i for i in map(int, readline().split()) if i != -1)
    if c != []:
        tree[id].type = "internal node"
        tree[id].c = c
        for j in c:
            tree[j].p = id
        len_c = len(c)
        tree[id].degree = len_c
        if len_c == 2:
            tree[c[0]].sibling = c[1]
            tree[c[1]].sibling = c[0]
root = 0
while tree[root].p != -1:
    root = tree[root].p
tree[root].type = "root"
def depth_height_check(id, d):
    d += 1
    height = 0
    for i in tree[id].c:
        tree[i].depth = d
        if tree[i].type != "leaf":
            tree[i].height = depth_height_check(i, d)
            height = max(height, tree[i].height)
    return height + 1
tree[root].height = depth_height_check(root, 0) if n > 1 else 0
print("\n".join(map(str, tree)))



Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e18 + 10ll;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cerr << #x << " = " << (x) << endl; \
    }
#define overload4(_1, _2, _3, _4, name, ...) name
#define FOR1(n) for (ll i = 0; i < (n); ++i)
#define FOR2(i, n) for (ll i = 0; i < (n); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < (b); ++i)
#define FOR4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
template <class T>
bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return 1;
    } else
        return 0;
}
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    } else
        return 0;
}
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
//#define S set<int>
#define itn int
bool dbg = false;

int N, A, B;

void solve() {
    int ans = INF;
    if ((A - B) % 2 == 0) {
        ans = abs((A - B) / 2);
    } else {
        int t1 = (A + B - 1) / 2;
        int t2 = (2 * N - A - B + 1) / 2;
        chmin(ans, t1);
        chmin(ans, t2);
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> N >> A >> B;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
string s;
int q,t,u,flag;
char c;
int main()
{
    cin>>s>>q;
    while(q--)
    {
        cin>>u;
        if(u==1)    flag++;
        else
        {
            cin>>t>>c;
            if(flag%2==0)
            {
                if(t==1) s.insert(s.begin(),c);
                else s.insert(s.end(),c);
            }
            else
            {
                if(t==1) s.insert(s.end(),c);
                else s.insert(s.begin(),c);
            }
        }
    }
    if(flag%2==1)   reverse(s.begin(),s.end());
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 900
# pragma GCC optimize("O3")
# include <bits/stdc++.h>
# define maxn 100005
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

int32_t main(){_
    //freopen("input","r",stdin);
    string s;
    cin >> s;
    if(sz(s) < 4) rc("No");
    if(s.substr(0,4) == "YAKI") rc("Yes");
    rc("No");
}


Measured memory_bytes: 384
n[M];main(i,j){n[0]=0;n[1]=-1;for(i=2;i<M;i++)if(!n[i])for(j=i*2;j<M;j+=i)n[j]=-1;for(i=1;i<M;i++)n[i]+=n[i-1]+1;for(;~scanf("%d",&i);printf("%d\n",n[i]));return 0;}

Measured memory_bytes: 0
import sys
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

n, W = na()
dp = [[0] * (W+1) for _ in range(n)]

w, v = na()
dp[0][w] = v

for i in range(1, n):
    w, v = na()
    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[n-1]))

Measured memory_bytes: 120428
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define INF 1145141919
typedef pair<int, int> P;
typedef pair<int, P> E;

int N, M, K, Q;
int U[18][200000], C[200000], D[200000], T[200000];
int A[200000];
vector<int> L[200000];
vector<P> G[200000];

int find(int x) {
  if (A[x] == x) return x;
  return A[x] = find(A[x]);
}

int lca(int a, int b) {
  if (D[a] > D[b]) swap(a, b);
  for (int k=0; k<17; k++) {
    if ((D[a] - D[b]) >> k & 1) {
      b = U[k][b];
    }
  }
  if (a == b) return a;
  for (int k=17; k>=0; k--) {
    if (U[k][a] != U[k][b]) {
      a = U[k][a];
      b = U[k][b];
    }
  }
  return U[0][a];
}

void unite(int x, int y, int r) {
  x = find(x), y = find(y);
  if (x == y) return;
  int p = N++;
  L[p].push_back(x), L[p].push_back(y);
  U[0][x] = p, U[0][y] = p;
  A[x] = p, A[y] = p;
  T[p] = r;
}

int main() {
  cin >> N >> M >> K >> Q;
  for (int i=0; i<M; i++) {
    int a, b, l;
    cin >> a >> b >> l;
    G[a-1].push_back(P(l, b-1));
    G[b-1].push_back(P(l, a-1));
  }
  for (int i=0; i<2*N; i++) {
    C[i] = INF;
    A[i] = i;
    T[i] = -1;
    U[0][i] = -1;
  }

  priority_queue< P, vector<P>, greater<P> > q;
  for (int i=0; i<K; i++) {
    int x;
    cin >> x;
    q.push(P(0, x-1));
    C[x-1] = 0;
  }
  while (!q.empty()) {
    int s = q.top().second, r = q.top().first; q.pop();
    for (auto p : G[s]) {
      int t = p.second, l = p.first;
      if (C[t] > C[s] + l) {
        C[t] = C[s] + l;
        q.push(P(C[t], t));
      }
    }
  }


  vector<E> g;
  for (int i=0; i<N; i++) {
    for (auto p : G[i]) {
      int t = p.second;
      g.push_back(E(min(C[i], C[t]), P(i, t)));
    }
  }
  sort(g.begin(), g.end(), greater<E>());

  for (auto e : g) {
    int r = e.first, s = e.second.first, t = e.second.second;
    unite(s, t, r);
  }
  int root = find(0);

  queue<P> bfs;
  bfs.push(P(root, 1));
  D[root] = 1;
  while (!bfs.empty()) {
    int s = bfs.front().first, r = bfs.front().second; bfs.pop();
    for (int t : L[s]) {
      D[t] = r + 1;
      bfs.push(P(t, r+1));
    }
  }
  for (int k=0; k<17; k++) {
    for (int v=0; v<N; v++) {
      if (U[k][v] == -1) U[k+1][v] = -1;
      else U[k+1][v] = U[k][U[k][v]];
    }
  }

  for (int i=0; i<Q; i++) {
    int s, t;
    cin >> s >> t;
    s--, t--;
    cout << T[lca(s, t)] << "\n";
  }
  return 0;
}

Measured memory_bytes: 43372
import sys
from typing import NamedTuple, List


def fast_input():
    return sys.stdin.readline()[:-1]


class Position(NamedTuple):
    t: int
    x: int
    y: int

    def _calc_diff_move(self, position) -> int:
        diff_x = self.x - position.x
        diff_y = self.y - position.y
        return abs(diff_x) + abs(diff_y)

    def can_move_from(self, prev) -> bool:
        diff_t = self.t - prev.t
        diff_move = self._calc_diff_move(prev)
        if not diff_t % 2 == diff_move % 2:
            return False
        return diff_t >= diff_move


def result_format(b: bool) -> str:
    return "Yes" if b else "No"


def solve(positions: List[Position]) -> bool:
    positions = [Position(t=0, x=0, y=0)] + positions
    for p_ind in range(len(positions) - 1):
        p_curr = positions[p_ind]
        p_next = positions[p_ind + 1]
        if not p_next.can_move_from(p_curr):
            return False
    return True


def main():
    n = int(fast_input())
    positions = []
    for _ in range(n):
        t, x, y = list(map(int, fast_input().split()))
        positions.append(Position(t=t, x=x, y=y))
    result = solve(positions)
    print(result_format(result))


main()


Measured memory_bytes: 94336
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
	int q;
	while(cin>>q,q!=-1){
		double x=q/2.0;
		while(fabs(x*x*x-q)>=0.00001*q)x-=(x*x*x-q)/(3*x*x);
		printf("%.6f\n", x);
	} 
	return 0;
}

Measured memory_bytes: 1192
@S=map$|++,@p=@i=0..10**5;$\-=<>;sub f{my$U=pop;$p[$U]=$U-$p[$U]?f($p[$U]):$U}/ />${*a=-$'}||(($v=f$`)-(f$a)and$S[$p[$v]=f$a]+=$S[$v]),$a=$`for<>;$\+=$S[f${-$_}]for@i;print

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll;
const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; const double eps=1e-12;
void tostr(ll x,string& res){while(x)res+=('0'+(x%10)),x/=10; reverse(ALL(res)); return;}
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; }
//template end

typedef pair<int,int> P;
typedef pair<P,int> T;
int h,w,k,dx[]={1,-1,0,0},dy[]={0,0,1,-1};
char c[810][810]; bool used[810][810]={};
int dist(int x,int y){return min({x,h-1-x,y,w-1-y});}

int main(){
   scanf("%d%d%d",&h,&w,&k);
   rep(i,0,h)cin>>c[i]; P s;
   rep(i,0,h)rep(j,0,w)if(c[i][j]=='S'){s={i,j}; continue;}
   queue<T> que; que.push({s,0}); used[s.first][s.second]=1;
   while(que.size()){
      auto t=que.front(); que.pop();
      int x=t.first.first,y=t.first.second,d=t.second;
      if(d==k)continue;
      rep(i,0,4){
         int tx=x+dx[i],ty=y+dy[i];
         if(tx<0||tx>=h||ty<0||ty>=w||c[tx][ty]=='#'||used[tx][ty])continue;
         used[tx][ty]=1; que.push({{tx,ty},d+1});
      }
   } int ans=inf;
   rep(i,0,h)rep(j,0,w)if(used[i][j])chmin(ans,(dist(i,j)+k-1)/k+1);
   printf("%d\n",ans);
   return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

/*
 for(i=0; i<N; i++)
   cin >> a[i];
*/

struct Edge {
  ll s, t, w;
  Edge(ll s, ll t, ll w): s(s), t(t), w(w){}
};

ll N, M;
vector<Edge> es;
ll d[1111];

ll bellmanFord(ll r) {
  ll i;
  for(i=0; i<N; i++) d[i]=INF;
  d[r]=0;
    
  for(ll cnt=0; cnt<=N; cnt++) {
    for(i=0; i<es.size(); i++) {
      Edge e=es[i];
      if(d[e.s]!=INF && d[e.t]>d[e.s]+e.w) {
        d[e.t]=d[e.s]+e.w;
      }
    }
  }
  
  ll p=d[N-1];
  for(i=0; i<es.size(); i++) {
    Edge e=es[i];
    if(d[e.s]!=INF && d[e.t]>d[e.s]+e.w) {
      d[e.t]=d[e.s]+e.w;
    }
  }
  
  if(d[N-1]!=p) return 1;
  else return 0;
}


int main(void) {
  ll i, j, k;
  cin >> N >> M;
  
  for(i=0; i<M; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    es.push_back(Edge(a, b, -c));
  }
  
  if(bellmanFord(0))
    pt("inf");
  else
    pt(-d[N-1]);
  
  
}



Measured memory_bytes: 384
def gcd(a, b):

	while b:

		a, b = b, a % b

	return a

def lcm(a, b):

	return a * b // gcd (a, b)

# print(lcm(2,3))


a, b, c, d = map(int, input().split())
l = []
cnt_c = 0
cnt_d = 0
n = b+1-a
# print("n",n)


# print(a//c)
# print(a//d)
# print(b//c)
# print(b//d)

lcm = lcm(c, d)

x = b//c - (a-1)//c
y = b//d - (a-1)//d
z = b//lcm - (a-1)//lcm
# print(x)
# print(y)
print(n-x-y+z)




# for i in range(a, b+1):
#     if i%c == 0:
#         cnt_c += 1
#     if i%d == 0:
#         cnt_d += 1
    
    # if i%c == 0 and i%d != 0:
    #     l.append(i)
# print(cnt_c)
# print(cnt_d)


Measured memory_bytes: 3060
s = input()
for i in range(1 << 3):
    S = list(s)
    total = int(s[0])
    for j in range(len(s)-1):
        if (i >> j) & 1:
            total += int(s[j+1])
            S.insert(2*j+1,"+")
        else:
            total -= int(s[j+1])
            S.insert(2*j+1,"-")
    if total == 7:
        print("".join(map(str,S))+"=7")
        break

Measured memory_bytes: 3064
#include <bits/stdc++.h>  // ver2.2.6
#define int long long
#define endl "\n"
#define ALL(v) (v).begin(),(v).end()
#define COUNT(a,i) upper_bound(ALL(a),i)-lower_bound(ALL(a),i)
#define Vi vector<int>
#define VVi vector<Vi>
#define Vs vector<string>
#define Pii pair<int,int>
#define VPii vector<Pii>
#define Tiii tuple<int,int,int>
#define PQi priority_queue<int>
#define PQir priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define itos to_string
#define stoi stoll
#define FI first
#define SE second
#define cYES cout<<"YES"<<endl
#define cNO cout<<"NO"<<endl
#define cYes cout<<"Yes"<<endl
#define cNo cout<<"No"<<endl
#define cyes cout<<"yes"<<endl
#define cno cout<<"no"<<endl
#define _ <<' '<<
#define sortr(v) sort(v,greater<>())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repeq(i,a,b) for(int i=a;i<=b;i++)
#define repreq(i,a,b) for(int i=a;i>=b;i--)
#define leng(n) (int)(log10(n)+1)
#define dem(a,b) ((a+b-1)/(b))
#define Vin(a) rep(iI,0,a.size())cin>>a[iI]
#define Vout(a) rep(lZ,0,a.size()-1)cout<<a[lZ]<<' ';cout<<a.back()<<endl
#define VVout(a) rep(lY,0,a.size()){Vout(a[lY]);}
#define VPout(a) rep(lX,0,a.size())cout<<a[lX].FI<<' '<<a[lX].SE<<endl
#define Verr(a) rep(iZ,0,a.size()-1)cerr<<a[iZ]<<' ';cerr<<a.back()<<endl
#define VVerr(a) rep(iY,0,a.size()){Verr(a[iY]);}
#define VPerr(a) rep(iX,0,a.size())cerr<<a[iX].FI<<' '<<a[iX].SE<<endl
#define INF 3000000000000000000  //  3.0*10^18(MAXの1/3くらい)
#define MAX LLONG_MAX
#define MOD 1000000007  //  10^9 + 7
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm
void press(auto &v){v.erase(unique(ALL(v)),v.end());}  //  圧縮
int mypow(int x, int n, int m){  //  累乗x^n(mod m)  O(log(n))
if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}



signed main() {
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(12);
  int n,m,q,qw;
  cin >> n >> m >> q;
  Vi a(0),b(0);
  
  a.pb(-INF);
  rep(i,0,n){
    cin >> qw;
    a.pb(qw);
  }
  a.pb(INF);
  
  b.pb(-INF);
  rep(i,0,m){
    cin >> qw;
    b.pb(qw);
  }
  b.pb(INF);
  
  int now,ap,am,bp,bm;
  int q1,q2,q3,q4,q5,q6,q7,q8;
  
  
  rep(i,0,q){
    cin >> now;
    
    ap = *lower_bound(ALL(a), now);
    am = a[upper_bound(ALL(a), now)-a.begin()-1];
    
    bp = *lower_bound(ALL(b), now);
    bm = b[upper_bound(ALL(b), now)-b.begin()-1];
    
    //cerr << ap _ am _ bp _ bm <<endl;
    
    q1 = abs(now - ap) + abs(ap - bp);
    q2 = abs(now - ap) + abs(ap - bm);
    q3 = abs(now - am) + abs(am - bp);
    q4 = abs(now - am) + abs(am - bm);
    q5 = abs(now - bp) + abs(bp - ap);
    q6 = abs(now - bp) + abs(bp - am);
    q7 = abs(now - bm) + abs(bm - ap);
    q8 = abs(now - bm) + abs(bm - am);
    
    cout << min({q1,q2,q3,q4,q5,q6,q7,q8}) << endl;
  }
  return 0;
}

Measured memory_bytes: 3060
N=int(input())
la=list(map(int,input().split()))
lb=list(map(int,input().split()))
lc=list(map(int,input().split()))
ans=0
for i in range(N-1):
    ans+=lb[la[i]-1]
    #print("ans",ans)
    if la[i]+1==la[i+1]:
        ans+=lc[la[i]-1]
        #print("ans1",ans)
ans+=lb[la[N-1]-1]
print(ans)


Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
typedef struct{
        double x;
        double y;
}coordinate;
int cx1, cy1, r1, cx2, cy2, r2;
void ssort(coordinate*, int);
main()
{
        double len, s, f1, f2;
        coordinate tc[4];
        scanf("%d %d %d%*c%d %d %d", &cx1, &cy1, &r1, &cx2, &cy2, &r2);
        len = sqrt(pow(cx1 - cx2, 2) + pow(cy1 - cy2, 2));
        s = atan2(cy2 - cy1, cx2 - cx1);
        f1 = acos((r1 + r2) / len);
        f2 = acos((r1 - r2) / len);
        tc[0].x = r1 * cos(s + f1);
        tc[0].y = r1 * sin(s + f1);
        tc[1].x = r1 * cos(s - f1);
        tc[1].y = r1 * sin(s - f1);
        tc[2].x = r1 * cos(s + f2);
    tc[2].y = r1 * sin(s + f2);
    tc[3].x = r1 * cos(s - f2);
    tc[3].y = r1 * sin(s - f2);
        if(len > (r1 + r2)){
                ssort(tc, 4);
        }else if(len == (r1 + r2)){
                ssort(tc, 3);
        }else if(len > abs(r1 - r2)){
                ssort(tc, 2);
        }else if(len == abs(r1 - r2)){
                printf("%.6f %.6f\n", tc[3].x + cx1, tc[3].y + cy1);
        }
}
void ssort(coordinate *t, int n)
{
        int i, j;
        for(i = 4 - n; i < 4; i++){
                int min = i;
                for(j = i + 1; j < 4; j++){
                        if(t[j].x < t[min].x || (t[j].x == t[min].x && t[j].y < t[min].y)){
                                min = j;
                        }
                }
                printf("%.6f %.6f\n", t[min].x + cx1, t[min].y + cy1);
                t[min] = t[i];
        }
}

Measured memory_bytes: 2168
N, M = map(int, input().split())
G = []
for _ in range(M):
    a, b, c = map(int, input().split())
    G.append((a, b, -c))

inf = float('inf')
d = [inf]*(N+1)
d[1] = 0
for i in range(N+1):
    for v, nv, cost in G:
        if d[v] != inf and d[nv] > d[v]+cost:
            d[nv] = d[v]+cost
            if i == N-1:
                tmp = d[N]
            if i == N and d[N] != tmp:
                print('inf')
                exit()
print(-d[N])


Measured memory_bytes: 45672
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector<int> as(n);
  vector<int> bs(n);
  rep(i, n) {
    cin >> as[i];
    bs[i] = as[i];
  }
  sort(bs.begin(), bs.end());
  rep(i, n) {
    if (as[i] == bs[n - 1]) {
      cout << bs[n - 2] << endl;
    } else {
      cout << bs[n - 1] << endl;
    }
  }

  return 0;
}


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

int caluc(int a, int b, int t){
    return t/a * b;
}

int main(int argc, char *argv[])
{
    int a, b, t;

    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&t);

    printf("%d", caluc(a,b,t));
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

priority_queue<ll, vector<ll>, greater<ll> > fo[100005];
priority_queue<ll, vector<ll>, greater<ll> > all_node;

void init(void);
ll root(ll x);
void unite(ll x, ll y);

ll get_id(ll x);

ll n, m;
ll a[100005];
ll id[100005];
ll num;

ll parent[100005];

ll ans = 0;

int main()
{
    init();
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < m; i++) {
        ll x, y;
        
        cin >> x >> y;
        unite(x, y);
    }

    for (int i = 0; i < n; i++) {
        int idx = get_id(i);
        fo[idx].push(a[i]);
    }

    if (num == 1) {
        puts("0");
        return 0;
    }

    for (int i = 0; i < n; i++) {
        int idx = get_id(i);

        if (!fo[idx].empty()) {
            ans += fo[idx].top();
            fo[idx].pop();

            while(!fo[idx].empty()) {
                all_node.push(fo[idx].top());
                fo[idx].pop();
            }
        }
    }

    int li = (num - 1) * 2 - num;
    for (int i = 0; i < li; i++) {
        if (all_node.empty()) {
            puts("Impossible");
            return 0;
        }
        else {
            ans += all_node.top();
            all_node.pop();
        }
    }

    cout << ans << endl;

    return 0;
}

void init(void)
{
    for (int i = 0; i <= 100000; i++) {
        parent[i] = -1;
    }
}

ll root(ll x)
{
    if (parent[x] < 0) {
        return x;
    }

    return parent[x] = root(parent[x]);
}

void unite(ll x, ll y)
{
    x = root(x);
    y = root(y);

    if (x == y) return;

    parent[x] += parent[y];
    parent[y] = x;

    return;
}

ll get_id(ll x)
{
    x = root(x);

    if (id[x] > 0) {
        return id[x];
    }
    else {
        num++;
        return id[x] = num;
    }
}

Measured memory_bytes: 8832
#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

int main() {
    string n; cin >> n;

    REP(0, i, n.length()) {
        if (n[i] == '1') {
            n[i] = '9';
        } else {
            n[i] = '1';
        }
    }

    cout << n << endl;

    return 0;
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::cmp::max;

fn div(a: usize, b: usize) -> usize {
    if a % b == 0 {
        a / b
    } else {
        a / b + 1
    }
}

#[allow(dead_code)]
fn solve(t: &[(usize, usize)]) -> usize {
    let (mut a, mut b) = (0, 0);
    for &(at, bt) in t {
        let ratio = if a == 0 && b == 0  {
            1
        } else {
            max(div(a, at), div(b, bt))
        };
        a = at * ratio;
        b = bt * ratio;
    }
    a + b
}


fn main() {
    input! {
    n: usize,
    t: [(usize, usize); n],
    };

    println!("{}", solve(&t));
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const long long INF = 1LL << 60;
const double PI = 3.14159265358979323846;
typedef long long ll;

int main(void) {
  int X, N;
  cin >> X >> N;
  if (N == 0) {
    cout << X << endl;
    return 0;
  }
  vector<int> p(N), notP(102);
  for (int i = 0; i <= 101; i++) notP[i] = 1;
  for (int i = 0; i < N; i++) {
    cin >> p[i];
    notP[p[i]] = 0;
  }
  int dist = 100000;
  int ans = 100000;
  for (int i = 0; i <= 101; i++) {
    if (notP[i] == 1) {
      if (dist > abs(X - i)) {
        dist = abs(X - i);
        ans = i;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

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

#define INF 1000010000
#define nl '\n'
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pdd pair<double,double>
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define sz(c) (c).size()
#define rep(i,n) for( int i = 0; i < n; ++i )
#define repi(i,n) for( int i = 1 ; i <= n; ++i )
#define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
#define repf(j,i,n) for( int j = i ; j < n ; ++j )
#define die(s) {std::cout << s << nl;}
#define dier(s) {std::cout << s; return 0;}
#define vi vector<int>
typedef long long ll;

using namespace std;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(0); 
	int k;
	string s;
	cin >> s >> k;
	rep(i , sz(s) - 1){
		if('z' - s[i] < k && s[i] != 'a'){
			k -= 'z' - s[i] + 1;
			s[i] = 'a';
		}
	}
	s[sz(s) - 1] = 'a' + (k % 26 + (s[sz(s) - 1] - 'a')) % 26;
	cout << s << nl;
	return 0;
}

Measured memory_bytes: 592
#include<stdio.h>
char a[110], b[110],c[110];

int main(){
    char d='a';
    int e1=0,e2=0,e3=0;
    scanf("%s",a);
    scanf("%s",b);
    scanf("%s",c);
    while(1){
        if(d=='a'){
            if(a[e1]!='\0'){
                d=a[e1++];
            }else{
                printf("A");
                return 0;
            }
        }else if(d=='b'){
            if(b[e2]!='\0'){
                d=b[e2++];
            }else{
                printf("B");
                return 0;
            }
        }else{
            if(c[e3]!='\0'){
                d=c[e3++];
            }else{
                printf("C");
                return 0;
            }
        }
    }
}

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

int main()
{
    int n, k; cin >> n >> k;
    ll sum = 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {cin >> a[i]; sum += a[i];}

    set<ll> div;
    for (int i = 1; i * i <= sum; i++) {
        if (sum % i == 0) {
            div.insert(i);
            div.insert(sum / i);
        }
    }

    ll ans = 0;
    for (auto& x : div) {
        vector<ll> r(n);
        ll rsum = 0;
        for (int i = 0; i < n; i++) {
            r[i] = a[i] % x;
            rsum += r[i];
        }
        sort(r.begin(), r.end());

        int pos = n - rsum / x;
        ll num = 0;
        for (int i = 0; i < pos; i++) num += r[i];
        if (num <= k) ans = max(ans, x);
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

void solve()
{
	string digit[10] = {"0111111",
						"0000110",
						"1011011",
						"1001111",
						"1100110",
						"1101101",
						"1111101",
						"0100111",
						"1111111",
						"1101111"};
	int n;
	while(cin >> n)
	{
		if(n == -1)
		{
			break;
		}
		string state = "0000000";
		while(n--)
		{
			int num;
			cin >> num;
			string str = digit[num];
			for(int i = 0; i < 7; ++i)
			{
				if(state[i] != str[i])
				{
					state[i] = '1';
				}
				else
				{
					state[i] = '0';
				}
			}
			cout << state << endl;
			state = digit[num];
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 0
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<complex>
#include<unordered_map>
#define deg(x) cout<<#x<<"="<<x<<endl;
#define fd(x) for(int i=0;i<x;i++)
#define fdd(a,x) for(int i=a;i<x;i++)
#define fx(x,n) for(int i=n-1;i>=x;i--)
#define mst(x) memset(x,0,sizeof(x));
#define fi first
#define se second
#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define ok "ok"
#define HH puts("");
#define ls rt<<1
#define rs rt<<1|1
#define pb(a,b) a.push_back(b);
#define FIN  freopen("1.in","r",stdin);
#define FOUT freopen("1.out","w",stdout);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<string,int> pss;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=1e18;
const long double eps=1e-8;
ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
const double pi=acos(-1);

int a[203040];
int main(){
	TB
	int n,k;
	cin>>k>>n;
	fd(n) cin>>a[i];
	sort(a,a+n);
	int ans=(k+a[0])-a[n-1];
	for(int i=1;i<n;i++){
        ans=max(ans,a[i]-a[i-1]);
	}
	cout<<k-ans<<'\n';
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll i, j, k, n, ans = 0, h;
  scanf("%lld", &n);
  char s[n + 10];
  scanf("%s", s);
  for(i = 0; i < n; ++i) {
    ll t[n + 1];
    t[i] = -1, t[i + 1] = 0;
    for(j = i + 2; j < n; ++j) {
      if(s[i + t[j - 1]] == s[j - 1]) t[j] = t[j - 1] + 1;
      else t[j] = 0;
    }
    h = i + 1;
    for(j = i + 1; j < n; ++j) {
      while((h != j + 1 && s[j - h + i] != s[j]) || i + j >= 2 * h) 
        h = j - t[j - h + i];
      if(j - h + 1 > ans) ans = j - h + 1;
    }
  }
  printf("%lld", ans);
  return 0;
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;
const long long MOD = (long long)1e9 + 7;

int main(){
    int n, ans = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i += 2){
        if(a[i] % 2 == 1){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;
ll roundd(ll x,ll n){
  if(x>n){return x%n;}
  else if(x<0){return x%n+n;}
  else return x;
}
vll kosuu(55,1);
ll dfs(ll n,ll x){
  if(n==0&&x==1){return 1;}
  if(x<=1){return 0;}
  else if(x==kosuu[n+1]-1){return kosuu[n];}
  else if(x==kosuu[n+2]-3){return kosuu[n+1]-1;}
  else{
    if(1<x&&x<kosuu[n+1]-1){
      return dfs(n-1,x-1);
    }
    else return dfs(n-1,x-kosuu[n+1]+1)+kosuu[n];
  }
}
int main(){
  ll n,x;cin>>n>>x;
  rep(i,1,55){
    kosuu[i]=kosuu[i-1]*2;
  }
  ll ans=dfs(n,x);
  cout<<ans<<endl;
}



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

using namespace std;

int main() {
  string s[2];
  cin >> s[0] >> s[1];
  int n = s[0].length() + s[1].length();
  int j = 0, k = 0;
  for(int i = 0; i < n; i++) {
    if(i % 2 == 0) {
      cout << s[i % 2][j];
      j++;
    }
    else {
      cout << s[i % 2][k];
      k++;
    }
  }
  puts("");
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	cout << (a / b) << " " << (a % b) << " " << fixed << setprecision(15) << ((double)a / b) << endl;
	return 0;
}



Measured memory_bytes: 3264
h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))
mod = 10**9+7
dp = [[0]*w for _ in range(h)]
dp[0][0] = 1
for i in range(h):
    for j in range(w):
        if i+1<h and m[i+1][j]==".":
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
        if j+1<w and m[i][j+1]==".":
            dp[i][j+1] += dp[i][j]
            dp[i][j+1] %= mod

print(dp[-1][-1] % mod)

Measured memory_bytes: 88944
N=int(input())
X=[0]*10001
for i in range(1,102):
  for j in range(1,102):
    for k in range(1,102):
      if i*i+j*j+k*k+i*j+j*k+k*i<10001:
        X[i*i+j*j+k*k+i*j+j*k+k*i]+=1
for i in range(N):
  print(X[i+1])

Measured memory_bytes: 69368
#include<stdio.h>

int main(){
	
	int n, i, count=0;
	fscanf(stdin, "%d", &n);
	int a[n];
	for(i=0; i<n; i++){
		fscanf(stdin, "%d", &a[i]);
		while(a[i]%2==0){
			count++;
			a[i] /= 2;
		}
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define _rep(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
#define ll long long 
#define N 200005
const int mod=1e9+7,inv=mod+1>>1;
int a[N],sum,n;
inline void reduce(int&x){x+=x>>31&mod;}
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0),std::cout.tie(0);
	std::cin>>n;
	rep(i,1,n) std::cin>>a[i],reduce(sum+=a[i]-mod);
	int ret=0;
	rep(i,1,n) reduce(ret+=1ll*a[i]*sum%mod-mod);
	rep(i,1,n) reduce(ret-=1ll*a[i]*a[i]%mod);
	std::cout<<1ll*ret*inv%mod<<'\n';
	return 0;
}

Measured memory_bytes: 4360
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

a,b,x = II()

h = (x-a**2*b/2)*2/(a**2)
if h>=0:
    if b-h==0:
        print(0)
    else:
        r = math.degrees(math.atan(a/(b-h)))
        print(90-r)
else:
    z = 2*x/(a*b)
    r = math.degrees(math.atan(z/b))
    print(90-r)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (int i = a; i < b; i++)
static lld l,x,y,n,m,i,z,p,j,k,c,d,s,t;string s1,s2;
int sum(int i)
{
    p=i;z=0;
    while(i>0)
    {
       p=i%10;
       z=z+p;
       i=i/10;
    }
    return z;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>x>>y;
    rep(i,1,n+1)
    {
        if(sum(i)<=y&&sum(i)>=x)
            {
                s=s+i;
            //    cout<<i;
            }
    }
    cout<<s;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n,m,k,i,j;
  scanf("%d %d %d",&n,&m,&k);
  for(i=0;i<=n;i++){
    for(j=0;j<=m;j++){
      if(i*j+(n-i)*(m-j)==k){
	printf("Yes\n");
	return 0;
      }
    }
  }
  printf("No\n");
  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};
vector<vector<ll> > G;
vector<bool> seen;

void dfs(ll v){
    seen[v]=1;
    rep(i,G[v].size()){
        if(seen[G[v][i]] == 0){
            dfs(G[v][i]);
        }
    }

}
struct edge {
    ll from; //出発点
    ll to;   //到達点
    ll cost; //移動コスト
};

int main() {
    ll MAX_V =1200;
    ll V; //頂点の数
    ll side; //辺の数
    ll S; //始点
   
    ll d[MAX_V]; //始点から添え字の頂点に行くのにかかるコスト
    vector<edge> edges2; //移動の情報を保存する

    cin>>V>>side;
    S=0;
   

    G.resize(V);
    seen.resize(V);
    fill(d, d+V+5, INF); //すべての頂点をINFにする
    d[S] = 0; //始点を0にする

    for (int i = 0; i < side; i++) {
        struct edge add;

        cin >> add.from;

        cin >> add.to;
        add.from--;add.to--;
        G[add.from].pb(add.to);
        cin >> add.cost;
        add.cost*=-1;
        edges2.push_back(add);
    }

    vector<ll>ban;
    rep(i,V){
        seen.clear();
        seen.resize(V);
        dfs(i);
        if(seen[V-1]==0){
            ban.pb(i);
        }
    }
    /*rep(i,ban.size()){
        cout<<ban[i]<<endl;
    }*/
    vector<edge> edges;

    rep(i,edges2.size()){
        rep(j,ban.size()){
            if(edges2[i].from==ban[j] || edges2[i].to==ban[j]){
                break;
            }
            if(j==ban.size()-1){
                edges.push_back(edges2[i]);
            }
        }
    }
    if(ban.size()==0){
        edges=edges2;
    }
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < (ll)edges.size(); j++) {

            struct edge e = edges[j];

            if (d[e.to] > d[e.from] + e.cost) {  //移動した後のコストが小さいと、頂点のコストを更新
                d[e.to] = d[e.from] + e.cost;
                if (i == V-1) {         //頂点の数と同じ回数ループすると、負の閉路があるのでループをぬける
                    cout << "inf" << endl;
                    return 0;
                } 
            }
        }
    }

    cout<<-d[V-1]<<endl;


    return 0;
    

}

Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int h,w;
string s;
int main(void){
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>s;
            if(s=="snuke"){
                char ans='A'+j;
                cout<<ans<<i+1<<endl;
                return 0;
            }
        }
    }
    
}


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	int n,a,b;
	cin>>n;

	int c=0,ans;
	for (int i = 0; i < n; i++){
		cin>>a>>b;
		if(a>c){
			ans=a+b;
			c=a;
		}
	}

	cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

int main()
{
	int K, X;

	std::cin >> K >> X;

	for (int i = std::max(-1000000, X - K + 1); i <= std::min(1000000, X + K - 1); ++i) {
		std::cout << i;
		if (i != std::min(1000000, X + K - 1))
			std::cout << " ";
	}
	std::cout << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define ll long long
#define ull unsigned long long
using namespace std;

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

	ll n, w;
	cin >> n >> w;
	vector<ll> V(n);
	vector<ll> W(n);
	for (ll i = 0; i < n; i++){
		cin >> V.at(i) >> W.at(i);
	}

	vector<vector<ll>> DP(n, vector<ll>(w + 1, -1));
	for (ll i = 0; i < n; i++){
		DP.at(i).at(0) = 0;
	}

	for (ll i = V.at(0); i <= w; i++){
		DP.at(0).at(i) = W.at(0);
	}

	for (ll i = 1; i < n; i++){
		for (ll j = 0; j <= w; j++){
			DP.at(i).at(j) = DP.at(i - 1).at(j);
		}
		for (ll j = V.at(i); j <= w; j++){
			DP.at(i).at(j) = max(DP.at(i).at(j), max(DP.at(i).at(j - 1), DP.at(i - 1).at(j - V.at(i)) + W.at(i)));
		}
	}

	cout << DP.back().back();

	return 0;
}


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n,wi;
  cin >> n >> wi;
  vector<int> w(n);
  vector<int> v(n);
  for(int i = 0; i<n;i++){
    cin >> w[i] >> v[i];
  }
  long long m[n+1][wi+1] = {0};
  for(int i = 0; i<=n;i++){
    for(int j = 0; j<=wi;j++){
      if(i ==0 || j==0){
	m[i][j] = 0;
      }else if(w[i-1]<=j){
	m[i][j] = max(v[i-1]+m[i-1][j-w[i-1]],m[i-1][j]);
      }else{
	m[i][j] = m[i-1][j];
      }
    }
  }
  cout << m[n][wi];
  return 0;
}


Measured memory_bytes: 79232
/*Allah Vorosha*/
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define n_p next_permutation
#define p_p prev_permutation
#define in insert
#define rev reverse
#define pf push_front
#define pob pop_back
#define uniq(v)         v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define all(x) (x).begin(),(x).end()
#define pof pop_front
#define ios ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define scn scanf
#define prt printf
#define rep(i, a, n) for(int i = a; i < n; i++)
#define mod 720720
#define yes cout << "Yes\n"
#define no cout << "No\n";
#define take for(auto &it : a) cin >> it;
#define out cout << a << "\n";
#define l_b lower_bound
#define u_b upper_bound
#define Max 100005
template<typename T> T mymax(T x, T y) {
    return (x > y ? x : y);
}

using namespace std;

const int N = 100005;
int cnt[N];
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(q);
    take;
    for(int x : a) {
        cnt[x]++;
    }
    for(int i = 1; i <= n; i++) {
        int p = q - cnt[i];
        if(k - p <= 0) {
            no;
        }
        else yes;
    }
    return;
}

int main() {
    /*int tc;
    scanf("%d", &tc);
    while(tc-- > 0)*/
    solve();
    return 0;
}


Measured memory_bytes: 4008