akhauriyash/Code-Regression huggingface dataset:
n = int(input())
l = []
flag = 0
for i in range(n):
    w = input()
    l.append(w)
for k in range(1,n):
    if  l[k-1][-1] != l[k][0]:
        flag =1
        break

    for j in range(k):
        if l[k] == l[j]:
            flag = 1
            break
        
if(flag == 1):
    print('No')
else:
    print('Yes')

Measured memory_bytes: 8976
#include <stdio.h>
int main(){
	int N;
  	char S[50];
  	int cnt=0;
  	scanf("%d",&N);
  	scanf(" %c",&S[0]);
  	for(int i=1;i<N;i++){
      scanf("%c",&S[i]);
  	}
  	for(int i=0;i<=N-3;i++){
    	if(S[i]=='A'&&S[i+1]=='B'&&S[i+2]=='C'){
        	cnt++;
        }
    }
  	printf("%d\n",cnt);
  	return 0;
}

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b && a != c){
        cout << "Yes" << endl;
    }
    else if(b == c && b!= a){
        cout << "Yes" << endl;
    }
    else if(c == a && c != b){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 504
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
int main()
{
    int a, b, c, x;
    long cnt = 0;
    std::cin >> a >> b >> c >> x;
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int h = 0; h <= c; h++) {
                if (500 * i + 100 * j + 50 * h == x) {
                    cnt++;
                }
            }
        }
    }
    std::cout << cnt << std::endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007 

map <ll,ll>a;
int main() {
	ll n;
	cin>>n;
	for(ll i=1;i<=n;i++){
		ll x;
		cin>>x;
		a[x]=i;
	}
    for(auto itr = a.begin(); itr != a.end(); ++itr) {
        ll vale= itr->second ;    // 値を表示
        cout << vale<< " ";
    }	
	// your code goes here
	return 0;
}

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

using namespace std;

int main() {
    int T;
    cin >> T;
    for (int n_case = 1; n_case <= T; ++n_case) {
        int n;
        cin >> n;
        long long total = 0;
        vector<pair<int, int>> left;
        vector<pair<int, int>> right;
        for (int i = 0; i < n; ++i) {
            int k, l, r;
            cin >> k >> l >> r;
            if (l > r) {
                left.emplace_back(k, l - r);
                total += r;
            } else if (r > l) {
                right.emplace_back(n - k, r - l);
                total += l;
            } else {
                total += l;
            }
        }
        sort(left.begin(), left.end());
        sort(right.begin(), right.end());
        function<void(const vector<pair<int, int>>&)> process = [&](const vector<pair<int, int>>& a) {
            multiset<int> vals;
            for (auto p: a) {
                vals.insert(p.second);
                if (vals.size() > p.first)
                    vals.erase(vals.begin());
            }
            for (int v: vals)
                total += v;
        };
        process(left);
        process(right);
        cout << total << "\n";
    }
    return 0;
}


Measured memory_bytes: 9528
import os
import heapq

N,M = (int(x) for x in input().split())
list = [-int(i) for i in input().split()]

heapq.heapify(list)
ans = 0
for i in range(0,M):
    a = heapq.heappop(list)
    heapq.heappush(list,-((-a)//2))
for j in list:
    ans += j*(-1)
print(ans)


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
int hs[110];

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

    std::cin >> N;

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

    int t = 0;
    while(true){
        if(*std::max_element(hs, hs + N) == 0){
            break;
        }

        for(int i=0;i<N;){
            if(hs[i] == 0){
                i += 1;
                continue;
            }

            int j = i + 1, mn = hs[i];
            while(j < N && hs[j] > 0){
                mn = std::min(mn, hs[j]);
                j += 1;
            }

            t += mn;
            
            while(i < j){
                hs[i] -= mn;
                i += 1;
            }
        }
    }

    std::cout << t << std::endl;
}


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

int main(){
	int h, r;
	cin >> h >> r;
	
	if(h + r == 0) cout << 0 << endl;
	else if(h + r > 0) cout << 1 << endl;
	else cout << -1 << endl;
	
	return 0;
}


Measured memory_bytes: 3104
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}



int main() {
	ll N;
	cin >> N;
	vector<ll> A(N);

	rep(i, N)
		cin >> A[i];

	rep(i, N - 1) {
		if (A[i] > A[i + 1] || i == 0 || A[i-1] < A[i])
			A[i]--;
	}

	bool flag = true;
	rep(i, N - 1) {
		if (A[i] > A[i + 1])
			flag = false;
	}

	if (flag == false)
		cout << "No" << endl;
	else
		cout << "Yes" << endl;


	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,dian[1001][1001],ans,D;
bool check(int i,int j){
	int dis=0;
	for(int k=1;k<=D;k++){
		dis+=(dian[i][k]-dian[j][k])*(dian[i][k]-dian[j][k]);
	}
	int a=sqrt(dis);
	if(a*a==dis)return true;
	else return false;
}
signed main(){
	scanf("%lld %lld",&n,&D);
	for(int i=1;i<=n;i++)for(int j=1;j<=D;j++)scanf("%lld",&dian[i][j]);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(check(i,j))ans++;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define fst() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define f(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define endl '\n'
#define maxn ((int)1e7)
typedef long long ll;
typedef long double ld;
const int m=132000;

int main()
{ 
  fst();
  int a,b,c,k;
  cin>>a>>b>>c>>k;
  cout<<(a+b+c)-max(a,max(b,c))+(1<<k)*max(a,max(b,c))<<endl;
  return 0;
}

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

int main(){
  int n, max_c = 1;
  cin >> n;
  for(int i = 1; i * i <= n; i++){
    max_c = max(max_c, i*i);
  }
  cout << max_c << endl;
  return 0;
}


Measured memory_bytes: 256
from copy import *
import sys
S=sys.stdin.readlines()

def init(N,node,unit,func):
  n=1
  while n<N:
    n<<=1
  for i in range(n*2-1):
    if len(node)<=i:
      node.append(deepcopy(unit))
    else:
      node[i]=deepcopy(unit)
  node.append(func)
  node.append(unit)
  node.append(n)

def upd(node,x,a):
  y=node[-1]+x
  node[y-1]=a
  while y>1:
    y=y>>1
    node[y-1]=node[-3](node[(y<<1)-1],node[y<<1])

def query(node,l,r):
  x,y=l,r
  z=node[-1]-1
  r=node[-2]
  while True:
    if x==y:
      return r
    if x&1:
      r=node[-3](r,node[x+z])
      x+=1
    if y&1:
      r=node[-3](r,node[y+z-1])
    x>>=1
    y>>=1
    z>>=1
    if z==0:
      return r

def bis_min_k(node,k,cond):
  x=k+1
  while True:
    if node[-1]<=x:
      return x-node[-1]
    if cond(node[(x<<1)-1]):
      x=x<<1
    else:
      x=(x<<1)+1

def bis_min(node,l,r,cond):
  x,y=l,r
  z=node[-1]-1
  for i in range(30):
    if x+(1<<i)>y:
      break
    if x&(1<<i):
      if cond(node[z+(x>>i)]):
        return bis_min_k(node,z+(x>>i),cond)
      x+=(1<<i)
    if z==0:
      break
    z>>=1
  for i in range(29,-1,-1):
    if i and ((node[-1]-1)>>(i-1))==0:
      continue
    if x+(1<<i)>y:
      continue
    if (y-x)&(1<<i):
      if cond(node[((node[-1]-1)>>i)+(x>>i)]):
        return bis_min_k(node,((node[-1]-1)>>i)+(x>>i),cond)
      x+=(1<<i)
  return node[-1]

N,Q=map(int,S[0].split())
A=list(map(int,S[1].split()))
X=[]
init(N+1,X,0,lambda x,y:x+y)
for i in range(N):
  upd(X,i,A[i])
a,b,c=0,0,0
for i in range(Q):
  a,b,c=map(int,S[i+2].split())
  if a:
    print(query(X,b,c))
  else:
    upd(X,b,X[X[-1]+b-1]+c)

Measured memory_bytes: 228160
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 10100000000000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

priority_queue<int> que;
signed main() {
  int n,m;cin>>n>>m;
  rep(i,n){
    int a;cin>>a;que.push(a);
  }
  rep(i,m){
    int t = que.top();que.pop();que.push(t/2);
  }
  int ans = 0;
  while(!que.empty()){
    ans += que.top();que.pop();
  } 
  cout << ans << endl;
}



Measured memory_bytes: 1400
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
s=input()
ns=s

def check_even_string(ss):
  l=int(len(ss)/2)
  return ss[l:]==ss[:l]

while True:
  ns=ns[:-2]
  if check_even_string(ns):
    break

print(len(ns))


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl


/*--------------------template--------------------*/

int main()
{
	cin >> n;
	vi v(n);
	REP(i, n) cin >> v[i];
	sort(ALL(v));
	ll a[100005] = { 0 };
	REP(i, n)
	{
		a[v[i]]++;
	}
	REP(i, 100000)
	{
		ans = max(ans, a[i] + a[i + 1] + a[i + 2]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cstdlib>

const long long MOD = 10e9 + 7;

using namespace std;

long long f(long long i){
	long long n=i;
	int mul=1;
	while(i/10!=0){
		int i1 = i%10;
		int i2 = (i/10)%10;
		if(i1==i2){
			n=n-i1*mul;
		}	
		i=i/10;
		mul*=10;
	}	
	return n;
}

int main(){
	int N,n,t;
	vector<int> h;
	cin>>N;
	n=N;
	while(N--){
		cin>>t;
		h.push_back(t);	
	}
	int x,y;
	x=abs(h[1]-h[0]);
	if(n==2){
		cout<<x<<endl;return 0;	
	}
	y=min(abs(h[2]-h[0]), x + abs(h[2]-h[1]));
	if(n==3){
		cout<<y<<endl;return 0;	
	}
	int cur=3;
	while(cur!=n){
		//cout<<cur<<endl;
		int z = min( x + abs(h[cur] -h[cur-2]) , y + abs(h[cur] -h[cur-1]) );
		x=y;
		y=z;
		cur++;
	}
	cout<<y<<endl;;
}

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

typedef long long ll;

int main(){
    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;

    ll sing = min(q*4, min(2*h, s));
    ll doub = min(q*8, min(4*h, min(2*s, d)));

    cout << n/2*doub + (n%2)*sing << endl;

    return 0;
}

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

int main(){
	int a, b, C;

	cin >> a >> b >> C;

	double PI = acos(-1);
	double rad = PI * C/180;

	double S, L, h;

	S = a * b * (sin(rad))/2;
	L = a + b + sqrt(a*a + b*b - 2*a*b*cos(rad));
	h = b*sin(rad);

	printf("%lf\n%lf\n%lf\n", S, L, h);

	return 0;
}


Measured memory_bytes: 3516
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines 

def nCr(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
  
MOD = 10**9+7  
N, A, B = map(int, input().split())

ans = pow(2, N, MOD)-1
ans -= nCr(N, A)
ans -= nCr(N, B)
print(ans%MOD)





Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> p2;
ll arr[205][205];
void solve(){
	ll n,res=0;
	cin>>n;
	for(ll i=1;i<=n;i++)
	for(ll j=1;j<=n;j++){
		ll g=__gcd(i,j);
		for(ll k=1;k<=n;k++)
		res+=arr[g][k];
	}
	cout<<res;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for(ll i=1;i<=200;i++)
	for(ll j=1;j<=200;j++)
	arr[i][j]=__gcd(i,j);
	ll qc=1;
	for(ll i=1;i<=qc;i++)
	solve();
}


Measured memory_bytes: 3984
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define PI 3.1415926535
#define EPS (1e-10)

int main()
{
    ll x;
    cin >> x;
    ll ans = 0;
    ll a = x / 500;
    ans += a * 1000;
    x = x % 500;
    x = x / 5;
    ans += x * 5;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
using namespace std;

using VI = vector <int>;
using VVI = vector <VI>;

int main() {
    int N;
    int K;

    cin >> N >> K;

    vector <int> intensity(N);

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

    int nowTurn = 0;

    while (nowTurn < K) {
        vector <int> newIntensity(N);
        vector <int> intAcc(N+1);

        for (int i = 0; i < N; ++i) {
            int minInt = max(0, i - intensity[i]);
            int maxInt = min(N, i + intensity[i] + 1);


            ++intAcc[minInt];
            --intAcc[maxInt];
        }

        int now = 0;
        bool converged = true;
        for (int i = 0; i < N; ++i) {
            now += intAcc[i];
            newIntensity[i] = now;
            if (newIntensity[i] != N) {
                converged = false;
            }
        }

        ++nowTurn;
        intensity = newIntensity;

        if (converged) {
            break;
        }
    }

    for (int i = 0; i < N; ++i) {
        if (i) {
            cout << " ";
        }
        cout << intensity[i];
    }

    cout << endl;

    return 0;
}

Measured memory_bytes: 5632
#include <iostream>
using namespace std;
int main(void){
    int W,H,x,y,r;
    cin >>W;cin >>H;cin >>x;cin >>y;cin >>r;
if(x-r >= 0 && x+r <= W && y-r >= 0 && y+r <= H){
    cout << "Yes" << endl;
    }else{
    cout << "No" << endl;    
    }

}

Measured memory_bytes: 3096
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#include <assert.h>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int n;
ll a[100005];
vector <ll> vec;
vector <int> pos;
vector <bool> b;
ll sumabs[100005];

int main()
{
	ios_base::sync_with_stdio(false);
//	freopen("input.txt","r",stdin);
	cin>>n;
	char x;
	cin>>a[0];
	for(int i=1;i<n;i++)
	{
		cin>>x;
//		while(x!='+' && x!='-') x=getchar();
		cin>>a[i];
//		scanf("%d",a+i);
		if(x=='-') a[i]=-a[i];
//		x=getchar();
	}
	ll res=0;
	for(int i=0;i<n;)
	{
		ll sum=0;
		while(a[i]>0 && i<n)
		{
			sum+=a[i];
			i++;
		}
		vec.push_back(sum);
		while(a[i]<0 && i<n)
		{
			vec.push_back(a[i]);
			i++;
		}
	}
//	for(int i=0;i<10;i++)
//	{
//		cout<<vec[i]<<' ';
//	}
//	cout<<endl;
	while(vec.back()==0) vec.pop_back();
	n=vec.size();
	memset(a,0,sizeof(a));
	memset(sumabs,0,sizeof(sumabs));
	for(int i=0;i<n;i++)
	{
		a[i]=vec[i];
		res+=a[i];
	}
	sumabs[n]=0;
	for(int i=n-1;i>=0;i--)
	{
		sumabs[i]=sumabs[i+1]+abs(a[i]);
	}
	ll now=0;
	for(int i=0;i<n;i++)
	{
		now+=a[i];
		if(a[i]<0)
		{
			res=max(res,now-a[i+1]+sumabs[i+2]);
//			cout<<now-a[i+1]+sumabs[i+2]<<endl;
		}
//		cout<<now<<' '<<a[i+1]<<' '<<sumabs[i+2]<<endl;
	}
	cout<<res<<endl;
//	ll res=0;
//	for(int i=0;i<n;i++)
//	{
//		if(vec[i]>0) pos.push_back(i);
//	}
//	int nn;
//	for(int i=0;i<n-1;i++)
//	{
//		if(vec[i]<0 && vec[i+1]<0)
//		{
//			nn=i;
//			break;
//		}
//	}
//	
//	ll res=0;
//	for(int i=0;i<pos.size();i++)
//	{
//		int p=pos[i];
//		bool tb=false;
//		if(p!=0 && p!=n-1)
//		{
//			if(-vec[p+1]>vec[p])
//			{
//				tb=true;
//			}
//		}
//		b.push_back(tb);
//	}
//	for(int i=0;i<n;i++)
//	{
//		cout<<vec[i]<<' ';
//	}
//	cout<<endl;
//	int l=0;
//	for(int i=0;i<pos.size();i++)
//	{
//		ll block=0;
//		for(int j=pos[i]+2;j<(i==(int)pos.size()-1?n:pos[i+1]);j++)
//		{
//			block+=abs(a[j]);
//		}
//		if(i==(int)pos.size()-1 && pos[i]==n-1)
//		{
//			block+=abs(a[pos[i]]);
//		}
//		else
//		{
//			if(!b[i]) block+=a[pos[i]]+a[pos[i]+1];
//			else block+=-a[pos[i]]-a[pos[i]+1];
//		}
//		res+=block;
//		cout<<i<<' '<<block<<endl;
//	}
//	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 2676
ma = lambda :map(int,input().split())
n,m = ma()
st = [False]*(n+1)
goal = [False]*(n+1)
for i in range(m):
    a,b = ma()
    if a==n:
        goal[b] =True
    if b==n:
        goal[a] =True
    if a==1:
        st[b] = True
    if b==1:
        st[a] = True
f = False
for i in range(1,n+1):
    if st[i] and  goal[i]:
         f=True
print("POSSIBLE") if f else print("IMPOSSIBLE")
  


Measured memory_bytes: 6260
A,B,C,D,E,F=map(int,input().split())

water=set()
for a in range(0,F+1,100*A):
  for b in range(0,F+1,100*B):
    if a+b<=F: water.add(a+b)
water=sorted(list(water))

suger=set()
for c in range(0,F+1,C):
  for d in range(0,F+1,D):
    if c+d<=F: suger.add(c+d)
suger=sorted(list(suger))

ans,answater,anssuger=0,0,0
for w in water:
  for s in suger:
    if (w//100)*E<s or w+s>F: break
    if w+s!=0:
      if ans<=(100*s)/(w+s):
        answater,anssuger=w+s,s
        ans=(100*s)/(w+s)
print(answater,anssuger)


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

typedef long long ll;

ll N,M;

bool check( ll h ){
  ll x = max( 0LL,h-N );
  ll m = M-2*x;
  if( m < 0 ) return false;
  return 2*h<=m;
}

int main(){
  cin >> N >> M;
  ll st = 0, ed = N+M;
  ll res = 0;
  while( st <= ed ){
    ll h = (st+ed)/2;
    if( check( h ) ){
      res = h; st = h+1;
    } else
      ed = h-1;
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順
//cout << fixed << setprecision(10) << ans << endl;
//int gcd(int a,int b){return b?gcd(b,a%b):a;}


vector<int> x;
int ans[300000];

int n2[300000];
int n3[300000];
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        int ne = 0;
        int i2 = i;
        while(i2>0){
            ne += i2%2;
            i2/=2;
        }
        ans[i] = ans[i%ne] + 1;
    }

    int wa = 0;
    REP(i,n){
        char x3;
        cin >> x3;
        int x1 = x3 - '0';
        x.pb(x1);
        wa += x1;
    }
    int ans1 = 0;
    int ans2 = 0;
    n2[n-1] = 1;
    REP(i,n){
        if(i!=0){
            n2[n-1-i] = n2[n-i] *2 % (wa+1);
        }
        ans1 += x[n-1-i] * n2[n-1-i] % (wa+1);
        ans1 %= (wa+1);
    }
    if(wa==1){

    }
    else{
        n3[n-1] = 1;
        REP(i,n){
            if(i!=0){
                n3[n-1-i] = n3[n-i] *2 % (wa-1);
            }
            ans2 += x[n-1-i] * n3[n-1-i] % (wa-1);
            ans2 %= (wa-1);
        }
    }
    REP(i,n){
        if(x[i]==1){
            if(wa==1){
                cout << 0 << endl;

            }
            else{
                cout << ans[((wa-1)+ans2 - n3[i]%(wa-1))%(wa-1)] + 1 << endl;
            }           
        }
        else{
            cout << ans[((ans1 + n2[i])%(wa+1))%(wa+1)] + 1 << endl;
        }

    }


    



    



    return 0;
}

Measured memory_bytes: 9444
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
#define ll long long
int n,a[N],b[N],c[N];
ll dp[3][N],sum[N],ans;
inline void rd(int& x){
	static char ch;while(!isdigit(ch=getchar()));
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
}

int main(){
	rd(n);
	for(int i=1;i<=n;++i)rd(a[i]);
	for(int i=1;i<=n;++i)rd(b[i]);
	for(int i=1;i<=n;++i)rd(c[i]);
	sort(a+1,a+n+1),sort(b+1,b+n+1),sort(c+1,c+n+1);
	for(int i=1;i<=n;++i)dp[1][i]=i;
	for(int i=1;i<=n;++i){
		dp[2][i]=dp[1][lower_bound(a+1,a+n+1,b[i])-a-1];
		sum[i]=dp[2][i]+sum[i-1];
	}
	for(int i=1;i<=n;++i)ans+=sum[lower_bound(b+1,b+n+1,c[i])-b-1];
	printf("%lld",ans);
}


Measured memory_bytes: 3712
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
using namespace std;

#define int long long
#define INF 1e18
#define EPS 1e-9
#define NIL -1
#define N 100

signed main() {
    int n; cin >> n;
    vector<int> v(5); for(int i = 0; i < 5; i++) cin >> v[i];

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

    if(v[0] >= n) {
        cout << v.size() << endl;
    } else if(n % v[0] == 0) {
        cout << (n / v[0] + 4) << endl;
    } else {
        cout << (n / v[0] + 5) << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#coding: utf-8
import sys
input = sys.stdin.readline
def main(N, K, h):
    dp = [float("inf")] * N
    dp[0] = 0
    for i in range(1, N):
        dp[i] = min(dp[i], min([dp[i-k] + abs(h[i] - h[i-k]) for k in range(1, min(i, K)+1)]))
    print(dp[N-1])
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    main(N, K, h)


Measured memory_bytes: 55132
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n * 3);
    for (int i = 0; i < n * 3; i++) {
        scanf("%d", &a[i]);
    }

    sort(a.begin(), a.end());
    int64_t r = 0;
    for (int i = n; i < n * 3; i += 2) {
        r += a[i];
    }

    cout << r << endl;

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,i;
  cin >> n;
  int a[n];
  for(i=0;i<n;i++){
    cin >> a[i];
  }
  int m=0,mm=0,im=0;
  bool max2=false;
  for(i=0;i<n;i++){
    if(m==a[i]){
      max2=true;
    }
    if(a[i]>=m){
      m=a[i];
      im=i;
    }
  }

  for(i=0;i<n;i++){
    if(i!=im){
      mm=max(mm,a[i]);
    }
  }
  
  for(i=0;i<n;i++){
    cout << (i!=im ? m : mm) <<endl;
  }  
  return 0;
}


Measured memory_bytes: 2432
N, M, X, Y = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
max_x = max(x)
min_y = min(y)
ans = 'War'
for i in range(-99, 101):
    if max_x < i and min_y >= i and X < i <= Y:
        ans = 'No War'
        break
print(ans)

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

using namespace std;

#define min3(a, b, c)           min((a), min((b), (c)))
#define max3(a, b, c)           max((a), max((b), (c)))
#define lcm(a,b)                (a / __gcd(a,b) ) *b
#define gcd(a,b)                __gcd(a,b)
#define dist(x1,y1,x2,y2)       sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
#define distl(x1,y1,x2,y2)      sqrtl((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1))
#define sqr(a)                  ((a)*(a))
#define FOR(a, b)               for(int i=a; i<b; i++)
#define fRead(x)                freopen(x,"r",stdin)
#define fWrite(x)               freopen (x,"w",stdout)
#define pb                      push_back
#define mk                      make_pair
#define ff                      first
#define ss                      second
#define lb                      lower_bound
#define ub                      upper_bound
#define all(a)                  a.begin(),a.end()
#define FASTIO                  ios_base::sync_with_stdio(0);cin.tie(NULL);

int main()
{
    FASTIO

    int n;
    cin >> n;

    vector <int> monstar, hero;

    FOR (0, n+1)
    {
        long long buf;
        cin >> buf;
        monstar.push_back(buf);
    }

    FOR (0, n)
    {
        long long buf;
        cin >> buf;
        hero.push_back(buf);
    }

    long long ans = 0;

    FOR (0,n)
    {

        if (hero[i] >= monstar[i])
        {
            ans += monstar[i];
            hero[i] -= monstar[i];
            monstar[i] = 0;
            if (hero[i] >= monstar[i+1])
            {
                ans += monstar[i+1];
                monstar[i+1] = 0;
            }
            else
            {
                ans += hero[i];
                monstar [i+1] = monstar[i+1] - hero[i];
            }
        }
        else
        {
            ans += hero[i];
        }
    }

    cout << ans;

}



Measured memory_bytes: 4264
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int n = Integer.parseInt(sc.next());
        int[] x = new int[n];
        int[] y = new int[n];
        int[] h = new int[n];
        for(int i = 0; i < n; i++){
            x[i] = Integer.parseInt(sc.next());
            y[i] = Integer.parseInt(sc.next());
            h[i] = Integer.parseInt(sc.next());
        }
        
        int xt = 0;
        int yt = 0;
        int ht = 0;
        for(int i = 0; i < n; i++){
            if(h[i] > 0){
                xt = x[i];
                yt = y[i];
                ht = h[i];
                break;
            }
        }
        
        for(int cy = 0 ; cy <= 100; cy++){
            for(int cx = 0; cx <= 100; cx++){
                int height = ht + Math.abs(cx-xt) + Math.abs(cy-yt);
                boolean stop = true;
                for(int i = 0; i < n; i++){
                    if(h[i] != Math.max(height - Math.abs(x[i]-cx) - Math.abs(y[i]-cy), 0)){
                        stop = false;
                        break;
                    }
                }
                if(stop){
                    System.out.println(cx + " " + cy + " " + height);
                    return;
                }
            }
        }
    }
}

Measured memory_bytes: 21844
#![allow(unused_imports)]

use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::{i32, i64, i128, u32, u64, u128, f64};
use std::io::{stdout, Write, BufWriter};
use std::mem::{swap};
use proconio::marker::{Isize1, Usize1, Bytes, Chars};

#[proconio::fastout]
fn main() {
    proconio::input!(
        n: usize,
        mut ls: [u32; n],
    );
    let mut counter = HashMap::new();
    for &l in &ls { *counter.entry(l).or_insert(0) += 1; }
    ls.sort();
    ls.dedup();
    if counter.len() < 3 {
        println!("0");
        return;
    }
    let n = ls.len();
    let mut ans = 0;
    for i in 0..n - 2 {
        for j in i + 1..n - 1 {
            for k in j + 1..n {
                let (a, b, c) = (ls[i], ls[j], ls[k]);
                if a + b > c { ans += counter[&a] * counter[&b] * counter[&c]; }
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 2196
a=[]
b=[]
n=int(input())
for i in range(n):
    j,k=map(int,input().split())
    a.append(j)
    b.append(k)
x=0
for i in range(n-1,-1,-1):
    n,m=a[i],b[i]
    y=(n+x)%m
    if y!=0:x+=m-y
print(x)

Measured memory_bytes: 11096
import numpy as np
N, M = map(int, input().split(' '))
A = []
B = []
for i in range(N):
    Ai, Bi = map(int, input().split(' '))
    A.append(Ai)
    B.append(Bi)
A, B = zip(*(sorted(zip(A, B))))
A = np.array(A)
B = np.array(B)
temp_B = 0
for i, num in enumerate(B):
    temp_B += num
    if(temp_B >= M):
        break
ans = 0
ans += sum(A[:i+1]*B[:i+1])
ans -= A[i] * (temp_B - M)
print(ans)

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

#define int long long 

const int N = 1e5+10;
const int mod = 1e9 + 7;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string s;
	cin >> s;
	int n = s.length();
	int dp[n+1][13];
	for(int i =0; i <= n; ++i)
	{
		for(int j = 0; j < 13; ++j) 
		{
			dp[i][j] = 0;
		}
	}
	
	dp[0][0] = 1;
	
	for(int i = 0; i < n; ++i)
	{
		for(int j = 0 ; j < 10; ++j)
		{
			int nxt = (s[i] - '0');
			if(s[i] == '?')
			{
				nxt = j;
			}
		
		
			for(int k = 0; k < 13; ++k)
			{
				int rem = (10*k + nxt)%13;
				dp[i+1][rem] += dp[i][k];
				dp[i+1][rem] %= mod;
			}
		if(s[i] != '?') break;
		}
	}
	
	cout << dp[n][5] << '\n';
	
	return 0;
}



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

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-12;

void header() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

int n;
bool vis[15];
char s[15];

void dfs(int x) {
    if (x == 0) {
        for (int i = n; i > 0; i--) cout << s[i];
        cout << endl;
        return;
    }
    for (int i = 1; i <= 26; i++) {
        if (vis[i]) {
            s[x] = 'a' + i - 1;
            dfs(x - 1);
        } else if (vis[i - 1]) {
            s[x] = 'a' + i - 1;
            vis[i] = true;
            dfs(x - 1);
            vis[i] = false;
            break;
        }
    }
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) s[i] = 'a';
    vis[0] = 1;
    dfs(n);
}

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


Measured memory_bytes: 1536
#include <iostream>
#include <algorithm>
#include <set>
#include <deque>
#include <queue>
#include <list>
using namespace std;

int main(){
    string s, t, x;
    cin >> s >> t;
    int a, b;
    cin >> a >> b >> x;
    if(s == x) a--;
    else b--;
    cout << a << ' ' << b << '\n';
}


Measured memory_bytes: 256
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    l = list(iss())
    print('Yes' if len(set(l)) == 2 else 'No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;

int main(int argc, char* argv[]) {
  int n;
  cin >> n;
  vector<int> h(n);
  rep(i, n) cin >> h[i];

  vector<int> dp(n - 1);
  dp[n - 2] = abs(h[n - 1] - h[n - 2]);

  for (int i = n - 3; i >= 0; i--) {
    dp[i] =
        min(abs(h[i + 1] - h[i]) + dp[i + 1], abs(h[i + 2] - h[i]) + dp[i + 2]);
  }
  cout << dp[0] << endl;
}


Measured memory_bytes: 1024
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int N = scanner.nextInt();
    int M = scanner.nextInt();
    Node[] nodes = new Node[N];
    for (int i = 0; i < N; i++) nodes[i] = new Node(i);
    for (int i = 0; i < M; i++) {
      int x = scanner.nextInt() - 1;
      int y = scanner.nextInt() - 1;
      nodes[x].to.add(nodes[y]);
    }

    for (int i = 0; i < N; i++) {
      List<Node> tsort = new ArrayList<>();
      dfs(nodes[i], tsort);

      for (Node node : tsort) for (Node t : node.to) node.len = Math.max(node.len, t.len + 1);
    }
    int max = 0;
    for (int i = 0; i < N; i++) max = Math.max(max, nodes[i].len);
    System.out.println(max);
  }

  private static void dfs(Node n, List<Node> comp) {
    if (n.visited) return;
    for (Node t : n.to) dfs(t, comp);
    n.visited = true;
    comp.add(n);
  }

  private static class Node {
    final int id;
    final List<Node> to = new ArrayList<>();
    boolean visited = false;
    int len = 0;

    private Node(int id) {
      this.id = id;
    }

    @Override public String toString() {
      return Integer.toString(id);
    }
  }
}


Measured memory_bytes: 102732
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES
using namespace std;
// 型シノニム
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
// 定数
constexpr ll INF   = 1e16;
constexpr ll INM   = 114514;
constexpr ll MOD   = 1e9 + 7;
constexpr ld EPS   = 1e-12;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
// 便利関数
void IOS() { ios::sync_with_stdio(false), cin.tie(0); }
template <typename T>
void dump(T x) { cout << x << endl; }
void dumpf(ld x, ll t) { cout << setprecision(t) << fixed << x << endl; }
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
	fill((T *)array, (T *)(array + N), val);
}
inline ll mod(ll a, ll mod) {
	if (a > 0) return a % mod;
	if (a % mod == 0) return 0;
	ll x = -a / mod + 1;
	a += x * mod;
	return a % mod;
}
ll powm(ll a, ll b, ll m) {
	if (b == 0) {
		return 1;
	} else if (b % 2 == 0) {
		ll d = powm(a, b / 2, m);
		return (d * d) % m;
	} else {
		return (powm(a, b - 1, m) * a) % m;
	}
}
// 本体

int main() {
	IOS();
	ll n;
	cin >> n;
	ll k = 1;
	ll keta = 1;
	while (1) {
		k *= 26;
		if(k < n) {
			n -= k;
			keta++;
		}else {
			break;
		}
	}
	k = 1;
	n--;
	string ans = "";
	for (int i = 0; i < keta; i++) {
		int j = n % 26;
		ans	  = (char)(j + 'a') + ans;
		n /= 26;
	}
	dump(ans);
}

Measured memory_bytes: 3652
import sys
s = input()

#for i in range(len(s)):
# print(s[len(s)-7:len(s)])

while len(s) > 0:
    sevenLast = s[len(s)-7:len(s)]
    sixLast = s[len(s)-6:len(s)]
    fiveLast = s[len(s)-5:len(s)]

    if sevenLast == 'dreamer':
        s = s[:len(s)-7]
    elif sixLast == 'eraser':
        s = s[:len(s)-6]
    elif fiveLast == 'dream':
        s = s[:len(s)-5]
    elif fiveLast == 'erase':
        s = s[:len(s)-5]
    else:
        print('NO')
        sys.exit()

print('YES')


Measured memory_bytes: 133880
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
      	//数値の入力
		int a = sc.nextInt();
      	int b = sc.nextInt();
      	//ハイフン入り
        String str = sc.next();
      	//正規表現のパターンを作成
      	Pattern p = Pattern.compile("[0-9]{"+a+"}-[0-9]{"+b+"}");
      	Matcher m = p.matcher(str);
       if (m.find()) {
            System.out.println("Yes");
        }
		else{
			System.out.println("No");
    	}
        }
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using namespace std;

const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};

int main(void){
	int a,b;
	cin >> a >> b;
	if(a<=0&&0<=b){
		cout << "Zero" << endl;
	}else if(0<a){
		cout << "Positive" << endl;
	}else if((b-a)%2==1){
		cout << "Positive" << endl;
	}else{
		cout << "Negative" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
    int s[5][5];
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
        {
            cin>>s[i][j];
        }
    }
    int n;
    int b[5][5]= {0};
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        for(int i=1; i<=3; i++)
        {
            int ff=0;
            for(int j=1; j<=3; j++)
            {
                if(s[i][j]==x&&b[i][j]==0)
                {
                    b[i][j]=1;
                    ff=1;
                    break;
                }
            }
            if(ff==1)
                break;
        }
    }
    int flag=0;
    for(int i=1;i<=3;i++)
    {
        if(b[i][1]==1&&b[i][2]==1&&b[i][3]==1)
        {flag=1;break;}
        if(b[1][i]==1&&b[2][i]==1&&b[3][i]==1)
        {flag=1;break;}
    }
    if(b[1][1]==1&&b[2][2]==1&&b[3][3]==1)
        flag=1;
    if(b[1][3]==1&&b[2][2]==1&&b[3][1]==1)
        flag=1;
    if(flag==1)
        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

using namespace std;

int main() {
    string s;
    getline(cin, s);
    if (s.back() == 's') {
        s += "es";
    } else {
        s += "s";
    }
    for (auto ch : s) cout << ch;
    return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int top=0,S[1000];
void push(int x){
S[++top]=x;
}
int pop(){
top--;
return S[top+1];
}
int main(){
int a,b;
char s[100];
while(cin>>s){
if(s[0]=='+'){
a = pop();
b = pop();
push(a+b);
}else if(s[0]=='-'){
b = pop();
a = pop();
push(a-b);
}else if(s[0]=='*'){
a = pop();
b = pop();
push(a*b);
}else{
push(atoi(s));
}
}
cout<<pop()<<endl;
return 0;
}

Measured memory_bytes: 1152
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << min(b / a, c) << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


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

using namespace std;
typedef long long ll;
typedef pair<long long,long long> P;
#define rep(n) for(ll i=0; i<n; i++)
#define MAX_V 100001
const ll INF = 1e+9;
const ll MOD = 1000000007;


int main()
{
  ll n;
  cin >> n;
  
  vector<ll> A;
  vector<ll> B;

  for (ll i = 0; i < n; i++)
  {
    ll a, b;
    cin >> a >> b;
    if(n%2==0)
    {
      a *= 2;
      b *= 2;
    }
    A.push_back(a);
    B.push_back(b);
  }

  sort(A.begin(), A.end());
  sort(B.begin(), B.end());

  ll right, left;
  if(n%2==0)
  {
    left = (A[(n/2)-1] + A[n/2])/2; 
    right = (B[(n/2)-1] + B[n/2])/2;
  } else {
    left = A[(n-1)/2];
    right = B[(n-1)/2];
  }

  cout << right - left + 1 << endl;

  

  return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, n) for(int (i)=0; (i)<(n); (i)++)
#define FOR1(i, n) for(int (i)=1; (i)<=(n); (i)++)
#define FORI(i, n) for(int (i)=n-1; (i)>=0; (i)--)

int main(int argc, char** argv) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(15);
    if (argc == 2 && atoi(argv[1]) == 123456789) {
        freopen("d:\\code\\cpp\\contests\\stdin", "r", stdin);
        //freopen("d:\\code\\cpp\\contests\\stdout", "w", stdout);
    }

    int h, w, a, b;
    cin >> h >> w >> a >> b;
//    vector<vector<int>> v(h, vector<int>(w));
    FOR(i, h){
        FOR(j, w){
            cout << ((int)(j < a) ^ (int)(i < b));
        }
        cout << endl;
    }

    if (argc == 2 && atoi(argv[1]) == 123456789)        cerr << clock()*1.0/CLOCKS_PER_SEC << " sec\n";
    return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> a(100001,0);
  long long sum=0;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    a[x]++;
    sum+=x;
  }
  int q;
  cin>>q;
  for(int i=0;i<q;i++){
    int b,c;
    cin>>b>>c;
    sum+=(c-b)*a[b];
    a[c]+=a[b];
    a[b]=0;
    cout<<sum<<endl;
  }
}

Measured memory_bytes: 3796
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Duelist
    {
        public string name;
        public int hp;
        public int attack;
    }
    class Program
    {
        static void Main(string[] args)
        {
            Duelist no1 = new Duelist();
            Duelist no2 = new Duelist();
            no1.name = "takahashi";
            no2.name = "aoki";
            string[] input = Console.ReadLine().Split();
            no1.hp = int.Parse(input[0].ToString());
            no1.attack = int.Parse(input[1].ToString());
            no2.hp = int.Parse(input[2].ToString());
            no2.attack = int.Parse(input[3].ToString());
            Console.WriteLine(battle(no1.hp, no1.attack, no2.hp, no2.attack));
            Console.Read();
        }
        public static string battle(int a, int b, int c, int d)
        {
            int round = 1;
            string kekka = "";
            while (true)
            {
                if (round % 2 == 1)
                {
                    c = c - b;
                    if (c <= 0)
                    {
                        break;
                    }
                }
                else
                {
                    a = a - d;
                    if (a <= 0)
                    {
                        break;
                    }
                }
                round++;
            }
            if (a <= 0)
            {
                kekka = "No";
            }
            else
            {
                kekka = "Yes";
            }
            return kekka;
        }
    }
}


Measured memory_bytes: 27536
import scala.io.StdIn._
import scala.util.control.Breaks._

object Main extends App {
  val s = readInt()

  require(1 <= s && s <= 100)

  var i    = 1
  var j    = 0
  var a    = s
  var list = Seq(a)
  breakable {
    while (i <= 1000000) {
      i = i + 1
      val b = if (a % 2 == 0) a / 2 else 3 * a + 1
      if (list.contains(b)) {
        println(i)
        break()
      }
      list = list.appended(b)
      a = b
    }
  }
}


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

#define ll long long



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	t=1;
	//cin >> t;

	while(t--)
	{
		

		ll x;
		cin >> x;
		ll hcf = __gcd(x,(ll)360);
		ll lcm = x*360;
		lcm /= hcf;

		cout << lcm/x << endl;


	}
	return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(N * A, B) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#define ll long long int
using namespace std;


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int r;
	int n,m;
	ll sum=0;
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int num;
		cin>>num;
		sum+=num;
	}
	if(sum>n)
		cout<<-1;
	else
		cout<<(n-sum);
		
	return 0; 
}

Measured memory_bytes: 3604
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(ALL(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 1e5 + 5;
vector<int> g[N];
int vis[N];
int par[N];
void bfs(int src){
    queue<int> q;
    q.push(src);
    vis[src] = 1;
    while(SZ(q)){
        int cur = q.front();
        q.pop();
        for(auto to : g[cur]){
            if(vis[to]) continue;
            vis[to] = 1;
            par[to] = cur;
            q.push(to);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        g[x].PB(y);
        g[y].PB(x);
    }
    bfs(1);
    bool ok = true;
    for(int i = 1; i <= n; i++){
        ok &= (vis[i]);
    }
    if(ok){
        cout << "Yes\n";
        for(int i = 2; i <= n; i++){
            cout << par[i] << nl;
        }
    }else{
        cout << "No";
    }
    return 0;
}
/*
    *** Most Impo.. -> check base case always
    1. Overflow Check (*, +)
    2. Index check (0 - based or 1 - based)
    3. Check for n = 1, 2, 3, 4....
    4. Corner Cases
*/

Measured memory_bytes: 11016
#include<bits/stdc++.h>
using namespace std;
int main()
{int n;
  cin>>n;int a=0;int y=n;
 for(int i=0;i<y;i++)
  {
   int m=n;
   int d=0;
   while(n>0)
   {n=n/10;d++;}n=m+0;
   if(d%2!=0)
     a++;
   n--;
  }cout<<a;
}

Measured memory_bytes: 256