akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
using ll = long long;

struct Edge{
    int to, id;
};

int n;
vector<vector<Edge>> G;
vector<int> ans;

void dfs(int v, int pre = -1, int p = -1){
    int color = 1;
    for(int i = 0; i < G[v].size(); i++){
        int u = G[v][i].to;
        int ei = G[v][i].id;
        if(u == p) continue;
        if(pre == color) color++;
        
        ans[ei] = color;
        color++;
        dfs(u, ans[ei], v);
    }
}

int main()
{
    cin >> n;
    G.resize(n);
    ans.resize(n-1);
    for(int i = 0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back((Edge){b, i});
        G[b].push_back((Edge){a, i});
    }
    dfs(0);

    int an = 0;
    for(int i = 0; i< n; i++){
        int tmp = G[i].size();
        an = max(an, tmp);
    }
    cout << an << endl;
    for(int i = 0; i < n-1; i++){
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 10928
/* AUTHOR :  SHIVANK JAIN */

#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false)
#define itt cin.tie(0)
#define now cout.tie(0)

using namespace std;

#define ll long long
#define li long int

#define pb push_back
#define rep(i,a,n) for(int i=a;i<n;i++)
#define reprev(i,n,a) for(int i=n;i>=a;i--)
#define endl "\n"

#define vi vector<int>
#define vll vector<ll>
#define vpi vector< pair<int , int> >
#define mapi map<int , int>
#define mapll map<ll ,ll >
#define seti set<int> 

#define fr first
#define se second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define mp make_pair
#define sort(v) sort(v.begin() , v.end())

#define BIG 1000000007
int gcd(int a, int b) 
{ // builtin function __gcd(a,b)
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
int main(){

     fast;itt;now;
 
//    #ifndef ONLINE_JUDGE
//    // for getting input from input.txt
//    freopen("input.txt", "r", stdin);
//    // for writing output to output.txt
//     freopen("output.txt", "w", stdout);
//    #endif
    
     string s , t;  cin>>s>>t;
     
     int n = min(s.size() , t.size());
     int f = 0;
     for(int i = 0 ; i < n ; i++)
      if(s[i] != t[i])
       f = 1;
       
      if(f == 1)
	   cout<<"No"<<endl;
	  else
	   cout<<"Yes"<<endl;  
     
return 0;
}

Measured memory_bytes: 3644
#input
n, a, b = map(int, input().split())

#output
mod = pow(10, 9) + 7

def cmb(n, k):
    numerator = 1
    denominator = 1

    for i in range(k):
        numerator *= n-i
        numerator %= mod
        denominator *= i+1
        denominator %= mod
    return numerator*pow(denominator, mod-2, mod) % mod


answer = pow(2, n, mod) - 1 - cmb(n, a) - cmb(n, b)
print(answer % mod)

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

int n;
double r[500];
double ans[500];
double ans2=0;

int main(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>r[i];
    double maxm=r[i];
    for(int j=0;j<i;j++){
      double A=r[i]+r[j];
      double B=r[i]-r[j];
      double C=sqrt(A*A-B*B);
      maxm=max(maxm,ans[j]+C);
    }
    ans[i]=maxm;
    ans2=max(ans2,ans[i]+r[i]);
  }
  printf("%.8f\n",ans2);
  return 0;
}

Measured memory_bytes: 1252
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <ctype.h>
#include <deque>
#include <queue>
#include <cstring>
#include <set>
#include <list>
#include <map>
#include <random>
#include <unordered_map>
#include <stdio.h>

using namespace std;

typedef long long ll;
typedef std::vector<int> vi;
typedef std::vector<bool> vb;
typedef std::vector<string> vs;
typedef std::vector<double> vd;
typedef std::vector<long long> vll;
typedef std::vector<std::vector<int> > vvi;
typedef vector<vvi> vvvi;
typedef vector<vll> vvll;
typedef std::vector<std::pair<int, int> > vpi;
typedef vector<vpi> vvpi;
typedef std::pair<int, int> pi;
typedef std::pair<ll, ll> pll;
typedef std::vector<pll> vpll;

const long long mod = 1000000007;

#define all(c) (c).begin(),(c).end()
#define sz(c) (int)(c).size()
#define forn(i, a, b) for(int i = a; i < b; i++)

#define pb push_back
#define mp make_pair

char incaa[505000];

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

int main()
{

//    gets(incaa);
//    string s(incaa);
    string s;
    getline(cin, s);
    int n = s.size();
    bool f1=true;
    forn(i,0,n) {
        if(s[i]!=s[0]) f1=false;
    }
    if(f1) {
        cout<<n<<endl;
        cout<<1<<endl;
        return 0;
    }
    vi pf1 = prefix_function(s);
    reverse(all(s));
    vi pf2 = prefix_function(s);
    
    int l1 = n;
    int sl1 = pf1[n-1];
    int dl1 = n-sl1;
    if(sl1 == 0 || l1%dl1 !=0) {
        cout<<1<<endl<<1<<endl;
        return 0;
    }
    
    cout<<2<<endl;
    
    
    
    int cnt =0 ;
    forn(i,1,n) {
        int l = i;
        int r = n-i;
        int sl = pf1[l-1];
        int sr = pf2[r-1];
        int dl = l - sl;
        int dr = r - sr;
        if((l%dl == 0 && sl>0)|| (r%dr ==0 &&sr>0)) continue;
        cnt++;
    }
    cout<<cnt<<endl;
    
    
    
    
    
}



Measured memory_bytes: 5148
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int maxn = 200005;
int num[2][maxn];
int mm[maxn];
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	int len1 = 0, len2 = 0;
	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if (a == 1)
		{
			num[0][len1++] = b;
		}
		if (a == n){
			num[1][len2++] = b;
		}
		if (b == n){
			num[1][len2++] = a;
		}
		if (b == 1){
			num[0][len1++] = a;
		}
	}
	bool flag = 0;
	for (int i = 0; i < len1; ++i)
	{
		mm[num[0][i]] = 1;
		if (num[0][i] == n){
			flag = 1;  break;
		}
	}
	if (!flag)
	for (int j = 0; j < len2;++j)
	if (mm[num[1][j]]){ flag = 1; break; }


	if (flag){
		printf("POSSIBLE\n");
	}
	else
	{
		printf("IMPOSSIBLE\n");
		}
}

Measured memory_bytes: 1792
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = list(input())

Ts = [[] for _ in range(K)]
for i, x in enumerate(T):
    k = i % K
    Ts[k].append(x)


def solve(t):
    r, s, p = 0, 0, 0   # player の現時点の手ごとの最大得点

    for x in t[::-1]:   # 相手の手を逆順にして、最終手から探索
        if x == 'r':
            r, s, p = max(s, p), max(p, r), max(r, s) + P
            # 現時点で
            # 現時点で r を出す場合、次時点で s または p を出す。現時点では引き分けのため、無加点
            # 現時点で s を出す場合、次時点で p または r を出す。現時点では負けのため、無加点
            # 現時点で p を出す場合、次時点で r または s を出す。現時点では勝ちのため、P 加点
        elif x == 's':
            r, s, p = max(s, p) + R, max(p, r), max(r, s)
        elif x == 'p':
            r, s, p = max(s, p), max(p, r) + S, max(r, s)

    return max(r, s, p)


answer = sum(solve(t) for t in Ts)
print(answer)

Measured memory_bytes: 14116
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define YN(x) cout<<(bool x?"Yes":"No")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " ";
#define INF 10000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(int i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    lli n, k;
    cin >> n >> k;
    out(n - k+1);
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ll n, d;
	cin >> n >> d;
	ll count = 0;
	while (n--) {
		ll x, y;
		cin >> x >> y;
		if (sqrt(pow(x, 2) + pow(y, 2)) <= d) {
			count++;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 3612
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from math import sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


n = int(data())
s = list(data())
r = s.count('R')
cnt = 0
for i in range(r):
    if s[i] != 'R':
        cnt += 1
out(cnt)


Measured memory_bytes: 78076
#include<stdio.h>

int main(){
    int n,a,b,c,d;
    int i=0;
    while(~scanf("%d",&n)){
    	i=0;
    for(a=0;a<=9;a++){
    	for(b=0;b<=9;b++){
    		for(c=0;c<=9;c++){
    			for(d=0;d<=9;d++){
    				if(a+b+c+d==n){
    					i++;
    				}
    			}
    		}
    	}
    }
        printf("%d\n",i);
    }

    return 0;
}

Measured memory_bytes: 596
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){
    string a,b,c; cin >> a >> b>> c;
    cout << "A" << b[0] << "C" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void)
{
	char moji1[1000], moji2[1000], moji3[1000];
	
	scanf("%s%s", moji1, moji2);
	
	strcpy(moji3, moji1);
	strcat(moji1, moji3);
	
	if(strstr(moji1, moji2) != NULL) printf("Yes\n");
	else printf("No\n");
	
	return 0;
}

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

int main(){
  int N;
  cin >> N;
  if(N >= 100){
    int h = N/100;
    N -= 100*h;
  }
  if(N >= 10){
    int t = N/10;
    N -= 10*t;
  }
  if(N == 3){
    cout << "bon" << endl;
  }else if( (N == 0) || (N == 1) || (N == 6) || (N == 8) ){
    cout << "pon" << endl;
  }else{
    cout << "hon" << endl;
  }
}


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

#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int N; cin >> N;
    int A[N]; rep(i, N) cin >> A[i];
    int mincost = pow(10, 9);
    for(int i = -100; i <= 100; i++){
        int acc = 0;
        for(int j = 0; j < N; j++) acc += (A[j]-i)*(A[j]-i);
        if(acc < mincost) mincost = acc;
    }
    cout << mincost << endl;
    return 0;
}

void solve(){}

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

int main()
{
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; ++i){
        cin >> A[i];
    }
    int cnt = -1;
    bool flag = false;
    do {
        ++cnt;
        for (int i = 0; i < N; ++i){
            if (A[i] % 2 == 1) {
                flag = true;
            }
            A[i] /= 2;
        }
    } while (! flag);
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<limits>
//include<bits/stdc++.h>
using namespace std;
int main()
{
	int num;
	cin >> num;
	int arr[50];
	for (int i = 0; i < num; i++)
	{
		cin >> arr[i];
	}
	int sum = 0;
	for (int i = 0; i < num; i++)
	{
		for (int j = i + 1; j < num; j++)
		{
			sum += arr[i] * arr[j];
		}
	}
	cout << sum << endl;
}


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

const ll mod = 1e9 + 7;
int main(){
    ll W, H;
    cin >> W >> H;
    ll x, y;
    cin >> x >> y;
    if(W%2 == 0 && W/2 == x && H%2 == 0 && H/2 == y){
        cout << W*H/2 << ".000000000" << " " << "1" << endl;
        return 0;
    }

    if(W%2 == 1 && H%2 == 1){
        cout << W*H/2 << ".500000000" << " " << "0" << endl;
    }else{
        cout << W*H/2 << ".000000000" << " " << "0" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>

double zenka(double q){
   double x=q/2;
     while(x*x*x-q>=0.00001*q || x*x*x-q<=-0.00001*q)   {
       x=x-((x*x*x)-q)/(3*x*x);   
}     

return x;
}

int main(void){
   int q;
     while(1)   {
       scanf("%d",&q);
       if(q==-1) break;
       else       {
           printf("%.7f\n",zenka(q));
       }   
}     

return 0;
}


Measured memory_bytes: 2024
#include <bits/stdc++.h>
using namespace std;
int solve(const vector<int>& v){
    map<int,int> odd,even;
    vector<pair<int,int>> oddv,evenv;
    for(unsigned int i=0;i<v.size()-1;i+=2){
        odd[v[i]]++;
    }
    for(unsigned int i=1;i<v.size();i+=2){
        even[v[i]]++;
    }
    for(auto i:odd){
        oddv.push_back(make_pair(i.second,i.first));   
    }
    oddv.push_back(make_pair(0,100010));
    sort(oddv.begin(),oddv.end());
    reverse(oddv.begin(),oddv.end());
    for(auto i:even){
        evenv.push_back(make_pair(i.second,i.first));
    }
    evenv.push_back(make_pair(0,100010));
    sort(evenv.begin(),evenv.end());
    reverse(evenv.begin(),evenv.end());
    int a;
    if(oddv[0].second!=evenv[0].second){
        a=(int)v.size()-evenv[0].first-oddv[0].first;
    }
    else{
    	int m=(int)v.size()-evenv[1].first-oddv[0].first;
    	int n=(int)v.size()-evenv[0].first-oddv[1].first;
    	a=min(m,n);
    }
    return a;
}
int main(){
    int n;
    cin>>n;
    vector<int> v;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        v.push_back(a);
    }
    cout<<solve(v)<<endl;
}

Measured memory_bytes: 6520
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
using namespace std;

int t = 1;
int first[101] = {0};
int last[101] = {0};
void dfs(vector<vector<int> > &graph, int v, set<int> &seen){
	seen.insert(v);
	first[v] = t;
	t++;
	for (int i=0;i<graph[v].size();i++){
		int nxt = graph[v][i];
		if (seen.count(nxt)) continue;
		dfs(graph, nxt, seen);
	}
	last[v] = t;
	t++;
}



int main(){
	int n; cin >> n;
	vector<vector<int> > graph(n+1);
	for (int i = 0; i < n; i++){
		int v, k; cin >> v >> k;
		for (int j = 0; j < k; j++) {
			int in; cin >> in;
			graph[v].push_back(in);
		}
	}

	set<int> seen;
	for (int i=1;i<n+1;i++){
		if (seen.count(i)) continue;
		dfs(graph,i,seen);
	}


	for (int i=1;i<n+1;i++){
		cout << i << " " << first[i] << " " << last[i] << endl;
	}

	return 0;
}




Measured memory_bytes: 3148
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int, int >
#define F first
#define S second
#define int  long long int
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
using namespace std;
/// age ye mosh dp ro baze dashti dp tedad baz shodeye baste nashode yadet nare !!
/// joooob zadam
const int N=2e5+100;
ll a[N];
ll b[N];
vector <int> g[N];
int32_t main(){
    ll n;
    cin >> n;
    vector <pii> u,v;
    for (int i=0;i<n;i++){
        cin >> a[i];
        u.pb({a[i],i});
        //v.pb({b[i],i});
    }
    for (int i=0;i<n;i++){
        cin >> b[i];
        v.pb({b[i],i});
    }
    sort(u.begin(),u.end());
    sort(v.begin(),v.end());
    ll p1=0;
    for (int i=0;i<n;i++){
        //cout << i << endl;
        if (u[i].F>v[i].F){
            //cout << i << " " << u[i].F << " " << v[i].F << endl;
            p1=1;
        }
        g[u[i].S].pb(v[i].S);
    }
    if (p1){
        cout << "No" ;
        return 0;
    }
    ll p2=0;
    for (int i=1;i<n;i++){
        swap(u[i],u[i-1]);
      //  cout << i << " " << p2 << endl;
        if (u[i].F<=v[i].F && u[i-1].F<=v[i-1].F){
            p2=1;
        }
        swap(u[i],u[i-1]);

    }
    ll q=g[1][0];
    ll t=0;
    while(q!=1){
        t++;
        q=g[q][0];
    }
    if (t!=n-1 || p2==1){
        cout << "Yes";
    }
    else{
        cout << "No";
    }


}


Measured memory_bytes: 13424
from numpy import*;B,I=searchsorted,lambda:int32(input().split());input();a,b=I(),I();c=0
for k in range(29):l=2**k;h=2*l;y=sort(b%h);y=hstack((y-h,y));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

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

int solve(int a, int b, int c) {
    for (int i = 0; i < 100; i++) {
        if (a & 1 || b & 1 || c & 1) return i;
        int na = b / 2 + c / 2;
        int nb = c / 2 + a / 2;
        int nc = a / 2 + b / 2;
        a = na, b = nb, c = nc;
    }
    return -1;
}

int main() {
    int a, b, c; cin >> a >> b >> c;
    cout << solve(a, b, c) << endl;
    return 0;
}


Measured memory_bytes: 256
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll int n,k;
		cin>>n>>k;
		double ans;
		for(ll int i=1;i<=n;i++)
		{
			double p1=1/(1.0*n);
			double p2;
			if(i>=k) p2=1;
			else
			{
				p2=1;
				ll int k1=i;
				while(k1<k)
				{
					k1*=2;
					p2*=.5;
				}
			}
			ans+=p1*p2;
		}
		cout<<setprecision(10)<<ans;
	}
	return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [0]
A.extend(list(map(int, input().split())))
A.append(0)

C = [[0, 0] for i in range(N)]

C_all = 0
for i in range(N):
    C[i][0] = abs(A[i + 1] - A[i])
    C[i][1] = abs(A[i + 2] - A[i])
    C_all += C[i][0]

C[N - 1][0] = abs(A[N] - A[N - 1])
C[N - 1][1] = abs(A[N+1] - A[N - 1])
C_all +=  abs(A[N])

for i in range(1, N):
    print(C_all - (C[i - 1][0] + C[i][0]) + C[i - 1][1])

print(C_all - (C[N - 1][0] + abs(A[N])) + C[N - 1][1])

Measured memory_bytes: 24616
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;
#define REP(i,n) for(int i=0; i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)

int dp[3005][3005];
vector<int> v(3005),w(3005);
int n;
int W;

void solve(){
    REP(i,3005)REP(j,3005)dp[i][j]=0;
    REP(i,n){
        REP(j,W+1){
            if(j<w[i]){
                dp[i+1][j]=dp[i][j];
            }else{
                dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
            }
        }
    }
}
int main(){
    cin>>n>>W;
    REP(i,n)cin>>w[i]>>v[i];
    solve();
    priority_queue<int> que;
    int x=W-1;
    int y=n;
    while(y>0 && x>0){
        if(x>=w[y-1] && dp[y][x]==dp[y-1][x-w[y-1]]+v[y-1]){
            x-=w[y-1];
        }else{
            que.push(v[y-1]);
        }
        y--;
    }
  	REP(i,y)que.push(v[i]);
    if(!que.empty()){
        int u=que.top();
        cout<<max(dp[n][W-1]+u,dp[n][W])<<endl;
    }else{
        cout<<dp[n][W]<<endl;
    }
    return 0;
}

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

using namespace std;

#define fastio cin.tie(NULL);cout.tie(NULL);ios_base::sync_with_stdio(0);
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define MAXN 200005
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define pb push_back
#define endl '\n'
#define int long long

typedef long long ll;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vii;
typedef vector <vi> matriz;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// auto timer_start = chrono::steady_clock::now().time_since_epoch().count();

int a, b, c, n, m, k;
string s, t, u;
int q;
int v[MAXN];

int32_t main(){
    fastio
    cin >> n >> k >> q;
    int aux;
    for(int i = 1; i <= q; i++){
        cin >> aux;
        v[aux]++;
    }
    for(int i = 1; i <= n; i++){
        if(k - (q - v[i]) > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <deque>
#include <string.h>
using namespace std;

#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

// ford-fulkerson O(FE) F:Flow
// maximum flow problem
// 1. init G[V] by add_edge
// 2. max_flow(s, t) return the max flow

const int MAX_V = 100000;

struct edge{int to, cap, rev;};

vector<edge> G[MAX_V];
bool used[MAX_V];

void add_edge(int from, int to, int cap){
  G[from].push_back((edge){to, cap, int(G[to].size())});
  G[to].push_back((edge){from, 0, int(G[from].size() -1)});
}

int dfs(int v, int t, int f){
  if(v == t) return f;
  used[v] = true;
  for (int i = 0; i < G[v].size(); i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to, t, min(f, e.cap));
      if (d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int max_flow(int s, int t){
  int flow = 0;
  for(;;){
    memset(used, 0, sizeof(used));
    int f = dfs(s, t, INFi);
    if(f == 0) return flow;
    flow += f;
  }
}

const int MAX_N = 100;
int n;
int a[MAX_N], b[MAX_N], c[MAX_N], d[MAX_N];

int main(){
  cin >> n;
  REP(i, n) cin >> a[i] >> b[i];
  REP(i, n) cin >> c[i] >> d[i];

  int src = 2 * n;
  int dst = 2 * n + 1;

  REP(i, n) add_edge(src, i, 1);
  REP(i, n) add_edge(n + i, dst, 1);

  REP(i, n) {
    REP(j, n) {
      if(a[i] < c[j] && b[i] < d[j]) add_edge(i, n + j, 1);
    }
  }

  cout << max_flow(src, dst) << endl;

  return 0;
}


Measured memory_bytes: 2816
def counting_sort(A, B, n, k):
    C = [0] * (k+1)
    for ai in A:
        C[ai] += 1
    for i in range(1, k+1):
        C[i] = C[i] + C[i-1]
    for j in range(n)[::-1]:
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
    return B
n = int(input())
A = list(map(int, input().split(' ')))
k = max(A)
B = [0] * n
sorted_A = counting_sort(A, B, n, k)
print(" ".join(map(str, sorted_A)))


Measured memory_bytes: 239620
/*
 * atcoder/dp_3rd/f.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

string S, T;
int N, M;
ll dp[3100][3100];

void input() {
  cin >> S >> T;
  N = S.size(); M = T.size();
}

ll rec(int n = 0, int m = 0) {
  ll &cc = dp[n][m];
  if (~cc) return cc;
  if (n == N || m == M) return cc = 0;
  ll max_ = 0;
  chmax(max_, (S[n] == T[m]) + rec(n + 1, m + 1));
  chmax(max_, rec(n + 1, m));
  chmax(max_, rec(n, m + 1));
  return cc = max_;
}

void printLcs() {
  ll count = dp[0][0];
  vector<char> lcs(count+1);
  ll n = 0, m = 0;
  while (n < N && m < M) {
    if (S[n] == T[m]) {
      lcs[dp[n][m]] = S[n];
      n++;m++;
      continue;
    }

    if (dp[n+1][m] > dp[n][m+1]) n++;
    else m++;
  }
  for (int i=count; i>=1; i--) cout << lcs[i];
  cout << endl;
}

void solve() {
  memset(dp, -1, sizeof(dp));
  rec();
  printLcs();
}

int main() {
  // cout.precision(15);
  input();
  solve();
  return 0;
}


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

int main() {
	// your code goes here
	int n,x,count=0;
	unordered_map<int,int> mp;
	cin>>n;
	for(int i=0;i<n;i++){
	    cin>>x;
	    if(mp.find(x)!=mp.end()){
	        mp.at(x)=mp.at(x)+1;
	    }
	    else
	        mp[x]=1;
	}
	for(auto &a : mp){
	    if(a.first == a.second)
	    continue;
	    if(a.first<a.second)
	    count += a.second - a.first;
	    else
	    count += a.second;
	    
	    
	}
	
	cout<<count;
	
	return 0;
}


Measured memory_bytes: 4260
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
set<int>s;
struct Node {
  int x, y, color;
  inline bool operator < (const Node & rhs) const {return x < rhs.x;}
}Node[300];
int n, ans;
int main(void){
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i) scanf("%d%d", &Node[i].x, &Node[i].y), Node[i].color = 1;
  for(int i = 1; i <= n; ++i) scanf("%d%d", &Node[i+n].x, &Node[i+n].y), Node[i+n].color = 2;
  sort(Node+1, Node+1+n*2);
  for(int i = 2*n; i >= 1; --i) {
    if (Node[i].color == 2) s.insert(Node[i].y);
    else  {
      auto it = s.lower_bound(Node[i].y);
      if (it != s.end()) s.erase(it), ans++;
    }
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
//fr u gotta do it
//get up and solve
//CMON
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(r, aa, bb) for (int r = (aa)-1; r >= (bb); r--)
#define be(x) (x.begin(), x.end())
#define pb(t) push_back(t)
#define ll long long
#define mp(a, b) make_pair(a, b)
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	ll h, w;
	cin>>h>>w;
	if(h==1||w==1){
		cout<<1<<"\n";
		return 0;
	}
	cout<<((w+1)/2)*((h+1)/2)+(w/2)*(h/2)<<"\n";
}


Measured memory_bytes: 256
package main

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

func main() {
	var (
		n, a, b int
		s       string
	)
	fmt.Scan(&n, &a, &b, &s)

	x, y := 0, 0
	var wr = bufio.NewWriter(os.Stdout)
	for _, v := range s {
		switch v {
		case 'a':
			if x+y < a+b {
				x++
				wr.WriteString("Yes")
			} else {
				wr.WriteString("No")
			}
		case 'b':
			if x+y < a+b && y < b {
				y++
				wr.WriteString("Yes")
			} else {
				wr.WriteString("No")
			}
		case 'c':
			wr.WriteString("No")
		}
		wr.WriteString("\n")
	}
	wr.Flush()
}


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

#define fi first
#define se second
#define be begin
#define en end
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)        //repeat n times
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++)   //repeat from s to n 
#define REPD(i,n) for(int (i)=(n);(i)>=0;(i)--)      //repeat from n to 0
#define REPD2(i,s,e) for(int (i)=(s);(i)>=(e);(i)--) //repeat from s to e
#define RANGE(i,v) for(auto &(i):v)                  //repeat range
#define ASIZE(a) (sizeof(a) / sizeof(a[0]))          //array size

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;
using Vs = V<string>;

template<typename T1,typename T2> using P = pair< T1, T2 >;
using Pii = P<int,int>;

template<typename T>
T MIN(V<T> v){return *min_element(ALL(v));}

int main(){
    LL n;
    cin>>n;
    Vll abcde(5);
    REP(i,5) cin>>abcde[i];

    LL min_move = MIN(abcde);

    cout<<((n%min_move==0)?n/min_move:n/min_move+1)+4<<endl;

    return 0;
}

Measured memory_bytes: 256
import numpy as np

n = int(input())
abs = np.array([list(map(int, input().split())) for _ in range(n)])

updated = 0
ans = 0
for i in range(n-1, 0-1, -1):
    mod = (updated + abs[i,0]) % abs[i,1]
    push = 0 if mod==0 else abs[i,1]-mod
    ans += push
    updated += push

print(ans)

Measured memory_bytes: 43928
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int main()
{
	ll n;
	while(cin>>n,n){
		int a[30],na=0;
		for(;n;n/=-10){
			if(n%10<0)n-=10;
			a[na++]=(n%10+10)%10;
		}
		reverse(a,a+na);
		rep(i,na)cout<<a[i]; cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include "iostream"
using namespace std;

int main() {
  char a[2], b[2];
  cin >> a[0] >> a[1] >> a[2] >> b[0] >> b[1] >> b[2];
  cout << (a[0] == b[2] && a[1] == b[1] && a[2] == b[0] ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

int main(void)
{
   int n, m;
   cin >> n >> m;

   vector<int> a(n);
   rep(i, n) a[i] = -1;

   rep(i, m)
   {
       int s, c;
       cin >> s >> c;
       s--;
       if(a[s] != -1 and a[s] != c){
           cout << -1 << endl;
           return 0;
       }
       a[s] = c;
   }

   if(n != 1 && a[0] == 0)
   {
       cout << -1 << endl;
       return 0;
   }

   rep(i, n)
   {
       if(a[i] != -1) continue;
       if(i == 0 and n != 1) a[i] = 1;
       if(i != 0 or n == 1) a[i] = 0;
   }

   rep(i, n)
   {
       cout << a[i];
   }
   cout << endl;



    
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do { cout << "\033[32;1m " << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
    print(v[i],i==(int)(v.size())-1?suc:2);
}
const int maxn=1e5+7;
vi G[maxn];
int dis[maxn][2];
void dfs(int u,int tp,int d=0,int fa=-1)
{
    dis[u][tp]=d;
    for(auto v:G[u])if(v!=fa)
    {
        dfs(v,tp,d+1,u);
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=1,u,v;i<n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    dfs(n,1);
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i][0]<=dis[i][1])
            cnt1++;
        else cnt2++;
    }
    if(cnt1>cnt2) cout<<"Fennec\n";
    else cout<<"Snuke\n";
}

Measured memory_bytes: 12800
A, B, C = map(int, input().split())
K = int(input())
flag = False

for i in range(K):
  if A>=B:
    B = B*2
    continue
  if B>=C:
    C = C*2
    continue

if A<B<C:
  flag = True
    
print("Yes") if flag else print("No")

Measured memory_bytes: 9172
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	n := nextInt()
	d := make([]int, n)
	for i := 0; i< n; i++ {
		d[i] = nextInt()
	}

	total := 0
	for i := 0; i< n - 1; i++ {
		for j := i + 1; j< n; j++ {
			total += d[i] * d[j]
		}
	}
	fmt.Printf("%d", total)
}


Measured memory_bytes: 640
//abc139_c.cpp
//Sun Sep  1 20:53:28 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

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

	int ans = 0;
	int temp = 0;
	int prevh = h[0];
	for (int i=1;i<n;i++){
		if (prevh>=h[i]){
			temp++;
			prevh = h[i];
		}else {
			ans = max(ans,temp);
			temp = 0;
			prevh = h[i];
		}
	}
	ans = max(ans,temp);

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 640
/*------------
Name: Mohamed Anas
Program Description: Dp implementation of frog jumping
-----*/
#include<stdio.h>
#define LARGE 1000000000;
int* h;
int* dp;
int N;
int K;
int min(int a,int b){
	if(a<b)return a;
	else return b;
}
int absolute(int a){
	if(a<0)return -a;
	else return a;
}
int min_cost(int n){
	
		for (int i = 1; i<=N; ++i)
		{ for (int j = i+1; j<=i+K; ++j)
		{
			//if(i-j>0)dp[i]=min(dp[i],dp[i-j]+absolute(h[i]-h[i-j]));
			if(j<=N)dp[j]= min(dp[j],dp[i]+absolute(h[i]-h[j]));
		}
		//printf("dp[%d] = %d\n",n,dp[n] );
		}
		return dp[n];
	
}

int main(){
	scanf("%d",&N);
	scanf("%d",&K);
	h = (int*)malloc(sizeof(int)*(N+2));
	dp = (int*)malloc(sizeof(int)*(N+2));
	for (int i = 0; i < N+2; ++i)
	{	dp[i]=LARGE;
		/* code */
	}
	dp[1]=0;
	for (int i = 1; i < N+1;++i)
	{
		scanf("%d",&h[i]);

	}
	h[0]=0;
	//printtall();
	printf("%d",min_cost(N));
}

Measured memory_bytes: 896
#include <stdio.h>
#include <string.h>

int main(void)
{
	
	int i;
	int min;
	int count_0 = 0;
	int count_1 = 0;
	char str[100001];
	int s;
	
	scanf("%s", str);
	
	for(i = 0; i < strlen(str); i++) {
		if(str[i] == '0') {
			count_0++;
		} else {
			count_1++;
		}
	}
	
	if(count_0 > count_1) {
		min = count_1;
	} else {
		min = count_0;
	}
	
	printf("%d", 2 * min);
	
	return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll a, b;
    cin >> a >> b;

    if(a == 0 || b == 0) PR("Zero");
    else {
        if(a > 0 && b > 0) PR("Positive");
        else if(a < 0 && b > 0) PR("Zero");
        else {
            if((b-a+1) % 2 == 0) PR("Positive");
            else PR("Negative");
        }
    }


    return 0;
}

/*



*/

Measured memory_bytes: 3556
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	public static int gcd(int x, int y){
		if(y == 0){
			return x;
		}else{
			return gcd(y, x % y);
		}
	}
	
	public static int dfs(int p, int q, int a, int n, int cur_pro, int prev_d){
		if(n < 0){
			return 0;
		}
		
		if(p == 0 && cur_pro <= a){
			//
			return 1;/*
		}else if(n == 1 && p == 1 && prev_d <= q && cur_pro * q <= a){
			//System.out.println("[" + n + "]" + " " + p + " / " + q + " [" + (cur_pro * q) + "]");
			return 1;
		*/}else if(n == 0){
			return 0;
		}
		
		
		int sum = 0;
		
		int divide = /* a */ a / cur_pro + 1;
		while(p * divide >= q){
			//System.out.println("[" + n +"]" + " 1 / " + divide);
			if(divide * cur_pro > a){
				divide--;
				continue;
			}else if(n * q < p * divide){
				divide--;
				continue;
			}else if(divide < prev_d){
				break;
			}
			
			final int upper = p * divide - q;
			final int downer = q * divide;
			
			final int common = gcd(upper, downer);
			
			if(n == 1 && upper != 0){
				divide--;
				continue;
			}else if(n == 2 && upper / common > 1){
				divide--;
				continue;
			}
			
			sum += dfs(upper / common, downer / common, a, n - 1, cur_pro * divide, divide);
			
			
			divide--;
		}
		
		return sum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//int[][][] DP = new int[801][801][];
		
		while(true){
			StringTokenizer tok = new StringTokenizer(br.readLine());
			final int p = Integer.parseInt(tok.nextToken());
			final int q = Integer.parseInt(tok.nextToken());
			final int a = Integer.parseInt(tok.nextToken());
			final int n = Integer.parseInt(tok.nextToken());
			
			if(p == 0 && q == 0 && a == 0 && n == 0){
				break;
			}
			/*
			for(int i = 0; i <= 800; i++){
				for(int j = 0; j <= 800; j++){
					Arrays.fill(DP[i][j], -1);
				}
			}
			*/
			int sum = dfs(p, q, a, n, 1, 0);
			
			System.out.println(sum);
		}
		
	}

}

Measured memory_bytes: 21324
x = input().split()

a = int(x[0])
b = int(x[1])
c = int(x[2])
count = 0

x = [a,b,c]

Max = max(x)
x.remove(max(x))

if x[0]%2 != x[1]%2:
	Max += 1
	x[0] += 1
	count += 1

x = [Max - x[0], Max - x[1]]


count += sum(x)/2
print(int(count));

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

int main()
{
	ll K, A, B;
	cin >> K >> A >> B;
	if (A <= B && A < K) {
		cout << -1 << endl;
	}
	else if (A <= B) {
		cout << 1 << endl;
	}
	else {
		cout << min((K + A - B - 1) / (A - B) * 2, (K - A + A - B - 1) / (A - B) * 2 + 1) << endl;
	}
	return 0;
}


Measured memory_bytes: 256
(* Vicfred
 * https://atcoder.jp/contests/abc077/tasks/abc077_a
 * implementation
 * *)
Scanf.scanf "%s\n%s\n" ( fun a b ->
    if a.[0] = b.[2] && a.[1] = b.[1] && a.[2] = b.[0] then "YES"
    else "NO"
) |> Printf.printf "%s\n"



Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0 ; i < (int)n ; ++i)
#define fi first
#define se second
#define for1(i,n) for(int i=1; i<= (int)n; ++i)
#define fore(i,l,r) for(int i=(int)l; i<= (int)r; ++i)
#define ford(i,n) for(int i=(int)(n) - 1; i>= 0; --i)
#define fored(i,l,r) for(int i=(int)r; i>= (int)l; --i)
#define pb push_back
#define el '\n'
#define d(x) cout<< #x<< " " << x<<el
#define ri(n) scanf("%d",&n)
#define __USE_MINGW_ANSI_STDIO 0
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<char,int> pci;
typedef tuple<int, int, int> tiii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;

//const ll INF = LONG_LONG_MAX;
const double PI = acos(-1);
const int MAXN = 1e5+200;
const double EPS= 1e-10;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int n;
    cin>>n;
    int dp[n];
    int a[n];
    forn(i,n){
        cin>>a[i];
    }
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
  //  dp[2]=abs(a[0]-a[2]);
    for(int i = 2 ; i < n ; ++i){
        dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]),dp[i-2]+abs(a[i-2]-a[i]));
    }
    cout<<dp[n-1];

}


Measured memory_bytes: 1024
N,M = [int(i) for i in input().split()]
a = [0]*N
b = [0]*N
c = [0]*M
d = [0]*M

for i in range(N):
    a[i], b[i] = [int(i) for i in input().split()]

for i in range(M):
    c[i], d[i] = [int(i) for i in input().split()]

for n in range(N):
    near_point = 0
    shortest = 10**9
    for m in range(M):
        manhattan = abs(a[n] - c[m]) + abs(b[n] - d[m])
        if manhattan < shortest:
            shortest = manhattan
            near_point = m + 1
    print(near_point)

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

int main() {
	int n ; cin >> n; vector<long long>readiness(n); vector<long long>requirement(n); vector<long long>decider(n); long long sum = 0;
	
	int k = n;
	int chg = 0;

	for (int i = 0; i < n; i++) {
		cin >> readiness[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> requirement[i];
	}

	for (int i = 0; i < n; i++) {
		decider[i] = readiness[i] - requirement[i];
	}

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

	for (int i = 0; i < n; i++) {
		sum = decider[i] + sum;
	}
	
	if (sum < 0) {
		cout << -1;
	}
	else {
		for (int i = 0; i < n; i++) {
			if (decider[i] < 0) {
				if (i == 0) {
					chg++;
				}
				chg++;
				while (decider[i] < 0) {
					if (decider[k - 1] > abs(decider[i])) {
						decider[k - 1] = decider[k - 1] + decider[i];
						decider[i] = 0;
						
					}
					else if (decider[k - 1] < abs(decider[i])) {
						decider[i] = decider[i] + decider[k - 1];
						decider[k - 1] = 0;
						
						k--;
						chg++;
					}
				}
			}
			
		}

		cout << chg;
	}
}


Measured memory_bytes: 2560
//By Krishna Yadav
#pragma GCC optimize("-O2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define forstl(i, v) for (auto &i : v)
#define forn(i, e) for (int i = 0; i < e; i++)
#define ln "\n"

#define dbg(x) cout << #x << " = " << x << ln
#define dbg2(x, y) cout << #x << " = " << x << " & " << #y << " = " << y << ln
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> p32;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef map<int, int> m32;
const int LIM = 2e5 + 5, MOD = 1e9 + 7;
int t, n, m, k, x, y;

int main()
{
	int x, n, ans;
	cin >> x >> n;
	int A[n];
	forn(i, n) cin >> A[i];
	set<int> s;
	forn(i, n) s.insert(A[i]);
	int m = x - 1, M = x + 1;
	if (s.count(x) == 0)
		ans = x;
	else
	{
		while (true)
		{
			if (s.count(m) == 0)
			{
				ans = m;
				break;
			}
			else
				m--;
			if (s.count(M) == 0)
			{
				ans = M;
				break;
			}
			else
				M++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)

                    
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const ll mod = 1e9+7;
void chmod(ll &M){
  if(M >= mod) M %= mod;
  else if(M < 0){
     M += (abs(M)/mod + 1)*mod;
    M %= mod;
}
}
ll modpow(ll x, ll n){
   if(n==0) return 1;
  ll res=modpow(x, n/2);
 if(n%2==0) return res*res%mod;
else return res*res%mod*x%mod;
}
int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };
long long GCD(long long a, long long b) {
  if (b == 0) return a;
  else return GCD(b, a % b);
}

using namespace std;
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
int main()
{
    int r;
    cin >> r;
    cout << 3 * r * r << endl;
}

Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int i, k, searched, search;
		int[][] data = new int[N][3];
		int[] point = new int[N];

		for(i = 0; i < N; i++){
			for(k = 0; k < 3; k++){
				data[i][k] = sc.nextInt();
			}
		}

		for(i = 0; i < N; i++){
			for(k = 0; k < 3; k++){
				search = data[i][k];
				for(searched = 0; searched < N; searched++){
					if(i == searched)continue;
					if(search == data[searched][k])search = 0;
					if(search == 0)break;
				}
				point[i] += search;
			}
		}


		for(i = 0; i < N; i++){
			System.out.println(point[i]);
		}
	}
}

Measured memory_bytes: 28528