akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iterator>
#include <functional>
#include <utility>
#include <algorithm>
#include <numeric>
#include <typeinfo>

using namespace std;

#define dump(n) cerr<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,n) repi(i,0,n)
#define iter(c) __typeof((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define allof(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

typedef pair<int,string> pis;

bool cmp(const pii& a,const pii& b)
{
	return a.first==b.first?a.second<b.second:a.first>b.first;
}

bool ok(vector<pii>& favs,vector<pii>& oths,int k,int l,int num)
{
	if(oths.size()<=k-num)
		return true;
	
	ll need=0;
	rep(i,num){
		if(favs[i].first>oths[k-num].first)
			continue;
		else{
			int diff=oths[k-num].first-favs[i].first;
			bool after=favs[i].second>oths[k-num].second;
			need+=diff+after;
		}
	}
	return need<=l;
}

void solve(vs& names,vi& votes,vs& fnames,int k,int l)
{
	int n=names.size(),m=fnames.size();
	
	vector<pii> favs,oths; // vote,id
	{
		map<string,int> ma;
		rep(i,n)
			ma[names[i]]=0;
		{int i=0; foreach(it,ma)
			it->second=i++;
		}
		vi isfav(n);
		rep(i,m)
			isfav[ma[fnames[i]]]=1;
		rep(i,n){
			vector<pii>& chrs=isfav[ma[names[i]]]?favs:oths;
			chrs.push_back(mp(votes[i],ma[names[i]]));
		}
	}
	
	sort(allof(favs),cmp);
	sort(allof(oths),cmp);
	
	int left=0,right=1+min(m,k);
	while(right-left>1){
		int mid=(left+right)/2;
		if(ok(favs,oths,k,l,mid))
			left=mid;
		else
			right=mid;
	}
	
	cout<<left<<endl;
}

int main()
{
	for(int n,m,k,l;scanf("%d%d%d%d",&n,&m,&k,&l),n|m|k|l;){
		vs names(n);
		vi votes(n);
		for(int i=0;i<n;i++){
			char tmp[11];
			scanf("%s%d",tmp,&votes[i]);
			names[i]=tmp;
		}
		vs favs(m);
		rep(i,m){
			char tmp[11];
			scanf("%s",tmp);
			favs[i]=tmp;
		}
		solve(names,votes,favs,k,l);
	}
	
	return 0;
}

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

int main() {
    int n, buf;
    int c, max = 0;
    int ans = 1;
    cin >> n;
    for(int i = 1; i <= n; i++){
        buf = i;
        while(true){
            if(buf % 2 == 0 && buf != 0){
                buf = buf / 2;
                c++;
            }else{
                break;
            }
        }
        if(c > max){
            max = c;
            ans = i;
        }
        c = 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main () {
	int test;
	scanf("%d", &test);
	int fizzbuzz;
	long long int jumlah = 0;
	for(int i = 1 ; i<=test ; i++){	
		if(i % 3 == 0 && i % 5 == 0){
			fizzbuzz+=i;
		}else if(i % 3 == 0 || i % 5 == 0 ){
			fizzbuzz+=i; 
		}else{
			jumlah+=i;
		}
	}
	printf("%lld\n", jumlah);
	return 0;
}

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

#define debug(x) cout << #x" = " << x;

#define st first
#define nd second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

const int MAXN = 1E5 + 10;

int n;
int a[MAXN << 1];

bool check(int limit)
{
    static int b[MAXN << 1];
    int n0 = n << 1;
    for (int i = 1; i < n0; ++i)
        b[i] = a[i] >= limit;

    int l, r;
    for (l = n; l > 1 && b[l] != b[l - 1]; --l);
    for (r = n; r < n0 - 1 && b[r] != b[r + 1]; ++r);
    if (l == 1 && r == n0 - 1)
        return b[1];
    if (l == n || r == n)
        return b[n];
    if (b[l] == b[r])
        return b[l];
    return n - l < r - n ? b[l] : b[r];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i < 2 * n; ++i)
        scanf("%d", &a[i]);
    int low = 2, high = 2 * n, mid;
    while (low < high)
    {
        mid = low + (high - low >> 1);
        if (check(mid))
            low = mid + 1;
        else
            high = mid;
    }
    printf("%d\n", low - 1);
    return 0;
}


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

int dp[2][2005];
int a[2005];

int main(){
  int n,z,w;
  cin >> n >> z >> w;
  for(int i=0;i<n;i++) cin >> a[i];
  // dp[i][j] = score when j_th card was drowed by !i. 
  if(n==1){
  	cout << abs(a[0] - w) << endl;
    return 0;
  }
  for(int i=n-1;i>=0;i--){
    if(i==n-1){
      dp[0][n-1] = abs(a[n-2]-a[n-1]);
      dp[1][n-1] = abs(a[n-2]-a[n-1]);
    }else if(i==0){
      dp[0][0] = abs(w - a[n-1]);
      for(int j=1;j<n;j++){
      dp[0][0] = dp[0][0] < dp[1][j] ? dp[1][j] : dp[0][0];
      }
      dp[1][0] = abs(z - a[n-1]);
      for(int j=1;j<n;j++){
        dp[1][0] = dp[1][0] < dp[0][j] ? dp[0][j] : dp[1][0];
      }
    }else{
      dp[0][i] = abs(a[i-1] - a[n-1]);
      dp[1][i] = abs(a[i-1] - a[n-1]);
      for(int j=i+1;j<n;j++){
        dp[0][i] = dp[0][i] < dp[1][j] ? dp[1][j] : dp[0][i];
      }
      for(int j=i+1;j<n;j++){
        dp[1][i] = dp[1][i] < dp[0][j] ? dp[1][i] : dp[0][j];
      }
    }
  }
  cout << dp[0][0] << endl;
  return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
#define ll unsigned long long int

using namespace std;
ll dp[105][100005], n, c;
ll v[100005], w[100005];

ll f(ll n, ll c)
{
    if (dp[n][c] != -1)
    {
        return dp[n][c];
    }
    if (n == 0 || c == 0)
    {
        return 0;
    }
    if (w[n] > c)
    {
        return dp[n][c] = f(n - 1, c);
    }
    return dp[n][c] = max(f(n - 1, c), v[n] + f(n - 1, c - w[n]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp, -1, sizeof dp);
    int t1, t2;
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        cin >> v[i];
    }
    cout << f(n, c) << "\n";
}

Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    x -= a;
    while (x >= b) x -= b;
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  int P[N],Q[N];
  for(int i=0;i<N;i++) cin >> P[i];
  for(int j=0;j<N;j++) cin >> Q[j];
  int M[N];
  for(int k=0;k<N;k++) M[k]=k+1;
  int count=0;
  int a,b;
  do{
    count++;
    bool an=true;
    bool bn=true;
    for(int i=0;i<N;i++){
      if(M[i]!=P[i]) an=false;
      if(M[i]!=Q[i]) bn=false;
    }
    if(an) a=count;
    if(bn) b=count;
    
  }while(next_permutation(M,M+N));
  cout << abs(a-b) << endl;
}

Measured memory_bytes: 256
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n=int(input())
    p=list(map(int,input().split()))
    q = list(map(int, input().split()))
    pn=0
    qn=0
    nn1 = [i+1 for i in range(n)]
    nn2 = [i + 1 for i in range(n)]
#    print(nn1)
    for i in range(n):
        pn+=(nn1.index(p[i]))*math.factorial(n-i-1)
        nn1.remove(p[i])
    for i in range(n):
        qn += (nn2.index(q[i])) * math.factorial(n - i - 1)
        nn2.remove(q[i])
#    print(pn,qn)
    print(abs(pn-qn))




if __name__ == "__main__":
    main()

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

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string s;
    int x, y;
    cin >> s >> x >> y;

    int i = 0;
    while (i < sz(s) && s[i] == 'F')
        i++;

    x -= i;

    bool dir = false;
    vi vert, horiz;
    while (i < sz(s)) {
        int j = i + 1;
        while (j < sz(s) && s[j] != 'T')
            j++;
        if (j-i-1) (dir ? horiz : vert).push_back(j-i-1);
        i = j;
        dir = !dir;
    }

    const int MAXV = 8008;
    bitset<2 * MAXV> v, h;
    v[MAXV] = true;
    h[MAXV] = true;

    for (int d : vert) v = (v << d) | (v >> d);
    for (int d : horiz) h = (h << d) | (h >> d);

    if (x + MAXV < 0) cout << "No\n";
    else cout << (v[y + MAXV] && h[x + MAXV] ? "Yes\n" : "No\n");

    return 0;
}



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

#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define per(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define repo(i, l, r) for(int i = l, i##end = r; i < i##end; ++i)
#define pero(i, l, r) for(int i = l, i##end = r; i > i##end; --i)
#define debug(x) cerr << "debug(" << #x << ')' << ": " << x << " " << endl
typedef long long ll;
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MAXN = 1 * 1e5 + 5;
const int MOD = 1e9 + 7;
const double PI = acos(-1);
inline ll read() {
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
//int cmpfunc (const void * a, const void * b){return ( *(int*)a - *(int*)b );}
//rise; qsort (a, n, sizeof(int), cmpfunc);

/*struct cmp{bool operator( ) (int x, int y) const {return a[x] + b[x] > a[y] + b[y];}};*/

ll a, b;
ll GEt_ans(ll n) {
	ll t = n & 3;
	if (t & 1) return t / 2 ^ 1;
	return t / 2 ^ n;
}
void solve() {
	cin >> a >> b;
	ll x = GEt_ans(a-1), y = GEt_ans(b);
	ll sum = y ^ x;
	cout << sum << endl;
}

int main() {
#ifdef ACM_LOCAL
	freopen("in.txt", "r", stdin);
#endif
//	int T; cin >> T;
//	while(T--)
	solve();
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

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

#define INF INT_MAX/3
#define MAX_N 1000
ll n,m;
ll dp[20001][256];
ll c[16],x[20000];
ll rec(ll p,ll y){
  if(dp[p][y] >= 0) return dp[p][y];

  if(p == n) return 0;

  long ret=LONG_MAX;
    for(ll i=0; i<m; ++i){ //??????????????????????????¨????????????????????°????????????
        ll ny = y+c[i];
        if(ny<0) ny=0;
        else if(ny>255) ny=255;

        ret = MIN(ret, rec(p+1,ny)+(ny-x[p])*(ny-x[p]));
    }
    return dp[p][y]=ret;
}
void solve(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  while(1){
    cin>>n>>m;
    if(n==0) break;
    rep(i,m) cin>>c[i];
    rep(i,n) cin>>x[i];
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",rec(0,128));
  }

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



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

int main() {

  int N;
  string S;
  cin >> N >> S;

  if (N % 2 == 1) {
    cout << "No" << endl;
  }
  else {
    int half = N / 2;

    string mae = S.substr(0, half);
    string ushiro = S.substr(half);
    if (mae == ushiro) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}


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

int main()
{
	char alpha;
	char moji;
	
	// 文字の入力
	scanf("%c", &alpha);
	
	// 判定
	for(moji='A'; moji<='Z'; ++moji){
	
		if(alpha == moji){
			printf("A");
		}
	}
	
	// 判定
	for(moji='a'; moji<='z'; ++moji){
	
		if(alpha == moji){
			printf("a");
		}
	}

	return 0;
}

Measured memory_bytes: 1596
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  int n, n3, n2, n1;
  scanf("%d", &n);
  n3 = n / 100;
  n2 = (n - n3*100) / 10;
  n1 = n - n3*100 - n2*10;

  if(n1 == 7 || n2 == 7 || n3 == 7){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }

  return 0;
  }


Measured memory_bytes: 1632
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  cout << n/min({a,b,c,d,e})+(n%min({a,b,c,d,e})>0)+4ll << endl;
  return 0;
}


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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A + B > C + D)
    cout << "Left" << endl;
  else if (A + B == C + D)
    cout << "Balanced" << endl;
  else
    cout << "Right" << endl;
}

Measured memory_bytes: 256
s=input()
n=len(s)
t=input()
lent=len(t)
ans=''
for i in range(n-lent+1):
    flag=0
    for j in range(lent):
        if s[i+j]!=t[j] and s[i+j]!='?':
            flag=1
    if flag==0:
        if i==0:
            ans=(t+s[lent:]).replace('?','a')
        else:
            ans=(s[:i]+t+s[lent+i:]).replace('?','a')
print(ans if ans!='' else 'UNRESTORABLE')

Measured memory_bytes: 3064
F = input().split()
stack = []

for i in F:
    try:
        stack.append(int(i))
    except ValueError:
        exec(
            f"temp = stack[-2] {i} stack[-1];"
            "stack.pop();"
            "stack.pop();"
            "stack.append(temp);"
            )

print(stack[0])



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

int main() {
	int a, b;
	cin >> a >> b;
	if (a == 1) a += 13;
	if (b == 1) b += 13;
	
	if (a > b) cout << "Alice" << endl;
	else if (a == b) cout << "Draw" << endl;
	else cout << "Bob" << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import math
n=int(input())
A=[]
xy=[[]]*n
for i in range(n):
    a=int(input())
    A.append(a)
    xy[i]=[list(map(int,input().split())) for _ in range(a)]

ans=0

for bit in range(1<<n):
    tmp=0
    for i in range(n):
        if bit>>i & 1:
            cnt=0
            for elem in xy[i]:
                if elem[1]==1:
                    if bit>>(elem[0]-1) & 1:
                        cnt+=1
                else:
                    if not (bit>>(elem[0]-1) & 1):
                        cnt+=1
            if cnt==A[i]:
                tmp+=1
            else:
                continue
    
    if tmp==bin(bit).count("1"):
        ans=max(bin(bit).count("1"),ans)
print(ans)






Measured memory_bytes: 74088
a,b,c,d=map(int,input().split())
import math
ans=b-a+1
e=(b//c)-(a-1)//c
f=(b//d)-(a-1)//d
g=(b//(c*d//math.gcd(c,d)))-((a-1)//(c*d//math.gcd(c,d)))
h=int(e+f-g)
print(ans-h)

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

using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
using P = pair<ll,ll>;
using ld=long double;

int main(){
   int n,m,k;cin >>n>>m>>k;
   bool flg=false;
    for (int i = 0; i <=n; ++i) {
        for (int j = 0; j <=m; ++j) {
            int now=n*j+m*i-2*i*j;
            if(now==k)flg=true;
        }
    }
    if(flg)puts("Yes");
    else puts("No");
}


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

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n, W;
  cin >> n >> W;
  vector<ll> w(n), v(n);
  rep(i,n) {
    cin >> w[i] >> v[i];
  }
  ll V = 100010;
  vector<vector<ll> > dp(n+5,vector<ll>(V, W+5));
  dp[0][0] = 0;
  rep(i,n) {
    for (int sumv = 0; sumv < V; ++sumv) {
      if (sumv == 0) dp[i+1][sumv] = 0;
      else if (sumv - v[i] >= 0) {
        dp[i+1][sumv] = min(dp[i][sumv], dp[i][sumv - v[i]] + w[i]);
      }
      else dp[i+1][sumv] = dp[i][sumv];
    }
  }
  int ans = 0;
  rep(i,V) {
    if (dp[n][i] <= W) ans = i;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 83328
from math import ceil

INF = int(1e18)
DP = [INF for _ in range(32)]
DP[1] = 1
DP[2] = 1
DP[3] = 2
for i in range(4, 32):
    DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3]

# print(DP[1:])
while True:
    n = int(input())
    if n == 0:
        break

    print(ceil(DP[n + 1] / 3650))


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


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

	sort(a,a+n);

	cout<< a[n-1]-a[0] <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <map>
#include <numeric>
#include <random>
#include <queue>
#include <deque>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin>>N;
  vector<int> X(N);
  for(int i=0;i<N;i++)cin>>X[i];
  vector<int> Y=X;
  sort(ALL(X));
  int med = X[N/2-1];
  for(int i=0;i<N;i++){
    if(Y[i]<=med)cout<<X[N/2]<<endl;
    else cout<<med<<endl;
  }
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v(3);
 
int main(){
	ios_base::sync_with_stdio(false);
  	cin >> v[0] >> v[1] >> v[2];
    if(!(v[0] & 1) || !(v[1] & 1) || !(v[2] & 1)){
    	cout << 0 << endl;
	      return 0;
    }
  	sort(v.begin(), v.end());
    cout << v[0] * 1LL * v[1] << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
using namespace std;

#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
#define F first
#define S second
typedef long long ll;
#define PB push_back
#define mkp make_pair

class UF{
public:
	static const int ufmax = 410;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() {init();}
	void init(){
		rep(i,ufmax){
			ufpar[i] = i;
			ufrank[i] = 0;
			ufcnt[i] = 1;
		}
	}
	int find(int x){
		return (ufpar[x] == x?(x):ufpar[x] = find(ufpar[x]));
	}
	int operator[](int x){
		return find(x);
	}
	int count(int x){
		return ufcnt[find(x)];
	}
	void unite(int x,int y){
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x] = y,ufcnt[y]+=ufcnt[x];
		else{
			ufpar[y] = x;
			ufcnt[x] += ufcnt[y];
			if(ufrank[x]==ufrank[y]) ufrank[x]++;
		}
	}
};

int main(){
	int n,m;
	while(cin>>n>>m,n||m){
		// vector<pair<int,int>> v(n);
		map<int,set<int>> ma;
		rep(i,n){
			int t;
			cin>>t;
			ma[-t].insert(i);
		}
		// sort(v.begin(),v.end());
		vector<vector<pair<int,int>>> vv(n);
		rep(i,m){
			int a,b,c;
			cin>>a>>b>>c;
			a--,b--;
			vv[a].PB(mkp(b,c));
			vv[b].PB(mkp(a,c));
		}
		int cnt = 0;
		ll ans = 0;
		vector<int> used(n,0);
		UF uf;
		for(auto x:ma){
			for(int y:x.S){
				used[y]=1;
				cnt++;
			}
			priority_queue<pair<int,pair<int,int>>> pq;
			if(ans==0) rep(i,n){
				if(!used[i]) continue;
				for(auto y:vv[i]){
					if(!used[y.F]) continue;
					pq.push(mkp(-y.S,mkp(i,y.F)));
				}
			}
			while(pq.size()){
				auto top = pq.top();
				pq.pop();
				if(uf[top.S.F]==uf[top.S.S]) continue;
				uf.unite(top.S.F,top.S.S);
				ans-=top.F;
			}
			for(int i:x.S){
				for(auto y:vv[i]){
					if(!used[y.F]) continue;
					pq.push(mkp(-y.S,mkp(i,y.F)));
				}
			}
			while(pq.size()){
				auto top = pq.top();
				pq.pop();
				if(uf[top.S.F]==uf[top.S.S]) continue;
				uf.unite(top.S.F,top.S.S);
				ans-=top.F;
			}
			rep(i,n){
				if(!used[i]) continue;
				if(uf.count(i)<cnt) ans=0;
			}
			if(ans==0) uf.init();
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 4628
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<limits.h>
#include<string>
#define int long long
using namespace std;

int a[200001];
signed main(){
	int b, c; cin >> b >> c;
	for (int d = 0; d < b; d++)cin >> a[d];
	a[b] = LLONG_MAX;
	int ans = 0;
	for (int i = 0; i < b; i++) {
		ans += min(c, a[i + 1] - a[i]);
	}
	cout << ans << endl;
}

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

using namespace std;
using ll = long long;

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007

signed main()
{
	init();
	solve();
}

int q, xl, yl;
string x, y;

void init()
{
	cin >> q;
}

int dp[1010][1010];

void reset()
{
	rep(i, xl+2) rep(j, yl+2) dp[i][j] = 0;
}


void solve()
{
	rep(cnt, q) {
		cin >> x >> y;
		xl = x.length();
		yl = y.length();
		reps(i, 1, xl+1) reps(j, 1, yl+1) {
			if (x[i-1] == y[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
			else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
		}
		cout << dp[xl][yl] << endl;
		reset();
	}
}




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

int n,k,q;
int d[100005];
int main(){
	cin >> n >> k >> q;
	for (int i = 0; i < q; ++i)
	{
		int o;
		cin >> o;
		d[o]++;
	}
	for (int i = 1; i <= n; ++i)
	{
		cout << (k-q+d[i]>0 ? "Yes" : "No") << endl;
		/* code */
	}

} 

Measured memory_bytes: 1024
void main() {
	auto ip = readAs!(int[]), N = ip[0], K = ip[1];
	auto x = readAs!(int[]);

	long res = long.max;
	foreach(i; 0..N-K+1) {
		auto l = x[i];
		auto r = x[i+K-1];
		//writefln("l: %d, r: %d", l, r);
		if((l < 0) == (r < 0)) {
			if(r < 0) {
				res = min(res, abs(l));
			} else {
				res = min(res, r);
			}
		} else {
			if(abs(l) < abs(r)) {
				res = min(res, abs(l) * 2 + abs(r));
			} else {
				res = min(res, abs(r) * 2 + abs(l));
			}
		}
	}
	res.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

#define F first
#define S second
#define pb push_back
#define ll long long
#define int long long
#define ld double

using namespace std ;

int32_t main()
{
	ios::sync_with_stdio(0) ; cin.tie(0) ; 
	int a , b; 
	cin >> a >> b; 
	if(a<=0&&b>=0) return cout << "Zero" << endl , 0 ; 
	if(a>0) return cout << "Positive" , 0  ; 
	b = min(b,-1ll) ; 
	int x = b - a + 1 ; 
	if(x&1) return cout << "Negative" << endl , 0 ; 
	cout << "Positive" << endl ; 
}

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

int main(){
 
  int N, L;
  cin >> N >> L;
  vector<string> S(N);

  for (int i = 0; i < N; i++) {
      cin >> S.at(i);
  }

  sort(S.begin(), S.end());
  for (int i = 0; i < N; i++) {
      cout << S.at(i);
  }
  cout << endl;


  
  return 0;
}
    


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return (ll)a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
const int N = 5e5+5;
int fac[N],ifac[N];
int pwn[N], pwm[N];
int nn,mm;
inline void init(int n=5e5){
	fac[0]=ifac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	ifac[n]=qpow(fac[n],mod-2);for(int i=n-1;i;i--)ifac[i]=mul(ifac[i+1],i+1);
	pwn[0]=pwm[0]=1;
	for(int i=1;i<=mm;i++)pwn[i]=mul(pwn[i-1],nn+1);
	for(int i=1;i<=nn;i++)pwm[i]=mul(pwm[i-1],mm+1);
}
inline int binom(int a,int b){
	if(b>a)return 0;
	return mul(fac[a],mul(ifac[a-b],ifac[b]));
}

int main()
{
	cin >> nn >> mm;
	init();
	int ans=0;
	for(int d=0,s=1;d<=min(nn,mm);++d,s=mod-s){
		// cout << d << ":" << mm-d << ":" << pwn[mm-d] << ":" << mul(pwn[mm-d],pwm[nn-d]) << endl;
		int sum = mul(mul(mul(binom(nn,d),binom(mm,d)),fac[d]),mul(pwn[mm-d],pwm[nn-d]));
		ans=add(ans, mul(s,sum));
	}
	cout << ans << endl;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define pb push_back
#define vi vector<int>
#define all(x) (x).begin(), (x).end()
#define pi pair<int, int>
#define int long long
using namespace std;

const int N = 2e5 + 5;

int a[N], b[N], n, k, pref[N];

signed main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    while (k--) {
        for (int i = 0; i <= n + 1; i++)
            pref[i] = 0;
        for (int i = 1; i <= n; i++) {
            int l = max(1ll, i - a[i]);
            int r = min(n + 1, i + a[i] + 1);
            pref[l]++;
            pref[r]--;
        }
        int cur = pref[0], was = 0;
        for (int i = 1; i <= n; i++) {
            cur += pref[i];
            if (cur != a[i])
                was = 1;
            a[i] = cur;
        }
        if (!was)
            break;
    }
    for (int i = 1; i <= n; i++)
        cout << a[i] << ' ';
    return 0;
}


Measured memory_bytes: 6776
import sys

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())

sys.setrecursionlimit(10 ** 9)


def main():
    X = INT()
    print("YES" if X == 3 or X == 5 or X == 7 else "NO")


if __name__ == '__main__':
    main()

Measured memory_bytes: 38256
#include <bits/stdc++.h>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long int ll;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
const int MOD=1000000007;

bool isPowerOfTwo (ll x)  
{  
    return x && (!(x&(x-1)));  
}
bool isPrime(int n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
}
int highestPowerof2(unsigned int n) 
{ 
    // Invalid input 
    if (n < 1) 
        return 0; 
  
    int res = 1;
    for (int i=0; i<8*sizeof(unsigned int); i++) 
    { 
        int curr = 1 << i; 
        if (curr > n) 
           break; 
  
        res = curr; 
    } 
  
    return res; 
} 
long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}       
////////////////////////////////////////////////////////////////////

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);  
  cout.tie(NULL);
  int t=1;
  while(t--)
  {
      string s,t;
      cin>>s>>t;
      int n=s.length();
      int m=t.length();
      int dp[n+1][m+1];
      for(int i=0;i<=n;i++)
      {
        for(int j=0;j<=m;j++)
        {
            if(i==0 || j==0)
            dp[i][j]=0;
            else if(s[i-1]==t[j-1])
            dp[i][j]=dp[i-1][j-1]+1;
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
            
        }
      }
      string ans="";
      int i=n,j=m;
      while(i>0 && j>0)
      {
          if(s[i-1]==t[j-1])
          {
              ans+=s[i-1];
              i--;j--;
          }
          else if(dp[i-1][j]>dp[i][j-1])
          i--;
          else
          {
              j--;
          }
          
      }
      reverse(ans.begin(),ans.end());
      cout<<ans;
  }  
  return 0;
}

Measured memory_bytes: 35456
mod = 1000000007
n,m = [int(x) for x in input().split()]
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]

xtot=0
ytot=0
mult=n-1
multdiff=mult-2
for i in range(1,n):
    xadd = x[i]-x[i-1]
    xadd = (xadd%mod * abs(mult)%mod)%mod
    xtot = (xtot%mod + xadd%mod)%mod

    mult+=multdiff
    multdiff-=2

mult=m-1
multdiff=mult-2
for i in range(1,m):
    yadd = y[i]-y[i-1]
    yadd = (yadd%mod * abs(mult)%mod)%mod
    ytot = (ytot%mod + yadd%mod)%mod

    mult+=multdiff
    multdiff-=2

print((xtot%mod*ytot%mod)%mod)


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

struct UnionFind{
  Int n;
  vector<Int> r,p;
  UnionFind(){}
  UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    r[x]+=r[y];
    p[y]=x;
  }
};

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  
  vector<set<Int> > G(n),H(n);
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    G[x].emplace(y);
    G[y].emplace(x);
  }
  using P = pair<Int, Int>;
  queue<P> q;
  for(Int i=1;i<n;i++){
    Int x,y;
    cin>>x>>y;
    x--;y--;
    if(G[x].count(y)) q.emplace(x,y);
    H[x].emplace(y);
    H[y].emplace(x);
  }

  UnionFind uf(n);
  while(!q.empty()){
    Int x,y;
    tie(x,y)=q.front();q.pop();
    if(uf.same(x,y)) continue;
    x=uf.find(x);y=uf.find(y);
    
    if(G[x].size()<G[y].size()) swap(x,y);
    
    uf.unite(x,y);
    
    for(auto z:H[y]){
      if(G[x].count(z)) q.emplace(x,z);
      H[x].emplace(z);
      H[z].emplace(x);
    }
    
    for(Int z:G[y]){
      if(H[x].count(z)) q.emplace(x,z);
      G[x].emplace(z);
      G[z].emplace(x);
    }
  }
  cout<<(uf.r[uf.find(0)]==n?"YES":"NO")<<endl;
  return 0;
}


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

// 섭테 긁을 목적이어도 N=100000에서 돌아가게는 해야하나보다.
// SR은 사실 필요없었다.
int N, X, T;

int main()
{
	cin >> N >> X >> T;
	cout << (N+X-1)/X*T;
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h> // {{{
// clang-format off
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define pb emplace_back
#define em emplace
#define fi first
#define se second
#define USE1(...) template <typename __VA_ARGS__> inline
#define USE2(T, ...) USE1(T, typename __VA_ARGS__)
#define mygc(c) (c) = getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
using ll = long long;
template<typename T> using vec = std::vector<T>;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE2(T=int,V=vec<T>)V reserved(int n){V v;v.reserve(n);return v;}
USE1(T=int)vec<T>in(int n){auto v=reserved<T>(n);rep(i,n)v.pb(in<T>());return v;}
USE2(T,U=std::pair<T,int>)vec<U>enume(const vec<T>&x,int s=0){int N=x.size();auto v=reserved<U>(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE2(T,U)void prif(bool b,T t,U f){if(b)pr(t);else pr(f);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
struct IoSetup { // {{{
  IoSetup() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(10);
    std::cerr.precision(10);
  }
} iosetup; //}}}
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  ll N = in(), A = in(), B = in();
  auto X = in(N);
  ll ans = 0;
  rep(i, N - 1) { ans += min<ll>((X[i + 1] - X[i]) * A, B); }
  pr(ans);
  return 0;
}


Measured memory_bytes: 640
n=gets.to_i
a=gets.split.map{|u| u.to_i}

def gcd(x,y)
    if x < y
        x,y=y,x
    end
    if y==0
        return x
    else
        return gcd(y,x%y)
    end
end

k=a[0]
n.times do |i|
    k=gcd(k,a[i])
end

puts k

Measured memory_bytes: 8452
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    double sum=0.0;
    cin>>n;
    int ar[n];
    for(int i=0;i<n;i++)
    {
        cin>>ar[i];
    }
    sort(ar,ar+n);
    sum=ar[0];
    for(int i=1;i<n;i++)
    {

        sum=(sum+ar[i])/2;
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int n;
  long long a[10001];
  a[1] = 2;
  for(int i=2;i<=10000;i++)
    a[i] = a[i-1]+i;
  while(scanf("%d",&n) != EOF)
    printf("%d\n",a[n]);
  return (0);
}

Measured memory_bytes: 2624
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define mod 1000000007

bool vis[200005];
vector<int> vec[2000005], v1;
int child[2000005];
int parent[2000005];
int div1[100005];
int min_indx[200005];
int count1 = 0;
int height = 0;
int max_indx[200005];
void dfs(int node)
{

    vis[node] = 1;

    min_indx[count1] = node;
    max_indx[node] = min(max_indx[node], count1);
    count1++;

    //  count1++;
    child[node] = height++;
    for (int i = 0; i < vec[node].size(); i++)
    {
        if (!vis[vec[node][i]])
        {
            dfs(vec[node][i]);
            min_indx[count1] = node;
            max_indx[node] = min(max_indx[node], count1);
            count1++;
        }
    }
    height--;
}
int MAXN = 200005;
int LOGMAXN = (int)log2(200005) + 1;
int M[200005][60];
int ans[200005];
void fun(int a, int b, int c)
{
    //ll val = 1;

    while (a <= b)
    {
        ans[a] += c;
        int p = -a;
        a += (a & p);
    }
}
int find1(int a)
{
    int sum = 0;
    while (a != 0)
    {
        sum += ans[a];
        int p = -a;
        a -= (a & p);
    }
    return sum;
}
void process2(int A[], int N)
{
    int i, j;

    for (i = 0; i < N; i++)
        M[i][0] = i;
    for (j = 1; 1 << j <= N; j++)
        for (i = 0; i + (1 << j) - 1 < N; i++)
            if (find1(M[i][j - 1]) < find1(M[i + (1 << (j - 1))][j - 1]))
                M[i][j] = M[i][j - 1];
            else
                M[i][j] = M[i + (1 << (j - 1))][j - 1];
}

int32_t main()
{
    int x, a, b;
    cin >> x >> a >> b;
    int to;
    cin >> to;
    int count = 0;
    for (int i = 0; i <= x; i++)
    {
        for (int j = 0; j <= a; j++)
        {
            for (int k = 0; k <= b; k++)
            {
                int p = 500 * i + 100 * j + 50 * k;
                if (p == to)
                    count++;
            }
        }
    }
    cout << count << "\n";
    return 0;
}

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


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

    string s;
    long long k;
    cin >> s >> k;
    int not_one_i = 0;
    char first_not_one = s[s.length() - 1];
    for (int i = 0; i < s.length() - 1; ++i) {
        if (s[i] != '1') {
            not_one_i = i;
            first_not_one = s[i];
            break;
        }
    }

    if (k < not_one_i + 1) {
        cout << '1' << endl;
    } else {
        cout << first_not_one << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int go[110];
int c[110];
int d[110];
int e[110];
int ret[110];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<b;i++)scanf("%d",c+i);
		for(int i=0;i<a;i++)d[i]=e[i]=-1;
		int t=0;
		int sz=0;
		int num=0;
		while(sz<b){
			for(int i=0;i<a;i++){
				if(~d[i]){
					if(go[d[i]]<=t){
						ret[sz++]=d[i];
						d[i]=-1;
						if(~e[i]&&go[e[i]]<=t){
							ret[sz++]=e[i];
							e[i]=-1;
						}else {d[i]=e[i];e[i]=-1;}
					}
				}
			}
			for(int i=num;i<=min(t/10,b-1);i++){
				bool ok=false;
				for(int j=0;j<a;j++){
					if(!~d[j]){
						go[i]=t+c[i];
						d[j]=i;
						num++;
						ok=true;break;
					}
				}
				if(ok)continue;
				int at=-1;
				int sc=88888888;
				for(int j=0;j<a;j++){
					if(!~e[j]&&go[d[j]]>=t+c[i]&&sc>go[d[j]]-(t+c[i])){
						at=j;sc=go[d[j]]-(t+c[i]);
					}
				}
				if(~at){
					go[i]=t+c[i];
					e[at]=d[at];
					d[at]=i;
					num++;
					continue;
				}
				for(int j=0;j<a;j++){
					if(!~e[j]&&sc>t+c[i]-go[d[j]]){
						at=j;sc=t+c[i]-go[d[j]];
					}
				}
				if(~at){
					go[i]=t+c[i];e[at]=d[at];d[at]=i;num++;continue;
				}
				
				break;
			}
			t++;
		}
		for(int i=0;i<b;i++){
			if(i)printf(" ");
			printf("%d",ret[i]+1);
		}
		printf("\n");
	}
}

Measured memory_bytes: 1032
import sys

NIL = -1

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = NIL
        self.left = NIL
        self.right = NIL

class Tree:
    def __init__(self):
        self.root = NIL

    def insert(self, z):
        y = NIL
        x = self.root

        while x != NIL:
            y = x

            if z.key < x.key:
                x = x.left
            else:
                x = x.right

        z.parent = y

        if y == NIL:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def inorder_walk(self, node):
        if node == NIL:
            return

        if node.left != NIL:
            self.inorder_walk(node=node.left)

        print(' ' + str(node.key), end='')

        if node.right != NIL:
            self.inorder_walk(node=node.right)

    def preorder_walk(self, node):
        if node == NIL:
            return

        print(' ' + str(node.key), end='')

        if node.left != NIL:
            self.preorder_walk(node=node.left)

        if node.right != NIL:
            self.preorder_walk(node=node.right)

    def show(self):
        self.inorder_walk(self.root)
        print()
        self.preorder_walk(self.root)
        print()


n = int(sys.stdin.readline())
T = Tree()

for i in range(n):
    line = sys.stdin.readline().split()
    
    if len(line) == 1:
        T.show()
    else:
        key = int(line[1])

        T.insert(Node(key))

Measured memory_bytes: 153884
k=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
i=int(input())
print(k[i-1])

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n;
	cin >> n;
	int sum = n*(n+1)/2;
	vector<P> ans;
	if(n%2==0){
		int x =1+n;
		for(int i = 1; i < n; i++){
			for(int j = i+1; j <= n; j++){
				if(i+j!=x){
					ans.push_back(P(i,j));
				}
			}
		}
	}else{
		for(int i = 1; i < n; i++){
			for(int j = i+1; j <= n; j++){
				if(i+j!=n){
					ans.push_back(P(i,j));
 				}
			}
		}
	}

	cout << ans.size() << endl;
	for(int i = 0; i < ans.size(); i++){
		cout << ans[i].first << " " << ans[i].second <<endl;
	}

	return 0;
}

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

int main() {
	int N;
	cin >> N;
	int answer = 0;
	for (int C = 1; C <= N; C += 2) {
		int num_of_divisors = 0;
		for (int X = 1; X <= C; ++X) {
			if (C % X == 0) {
				++num_of_divisors;
			}
		}
		if (num_of_divisors == 8) {
			++answer;
		}
	}
	cout << answer << '\n';
	return 0;
}


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

namespace AtcoderTemplateForCSharp
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ');

            var a = int.Parse(input[0]);
            var b = int.Parse(input[1]);

            Console.WriteLine((a - 1) * (b - 1));
        }
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
//void chmin(int &a, int b) { if (a > b) a = b; }
//void chmax(int &a, int b) { if (a < b) a = b; }

const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

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

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){

  int H,W;
 
  while (true){
      cin >> H >> W;
      if (H==0) break;

      for (int i=0; i< H; i++){
          switch (i%2){
              case 0 :  {
                  for (int j =0; j < (W/2) ; j++){
                      
                      cout << "#.";
                  }
                  for (int j=0; j < (W%2);j++){
                      cout <<"#";
                  }
              }  break;    //偶数行，#开头
              case 1 :  {
                  for (int j =0; j < (W/2) ; j++){
                      cout << ".#";
                  }
                  for (int j=0; j < (W%2);j++){
                      cout <<".";
                  }
              } break; //奇数行，。开头
          }
        cout << endl;
      }
      cout << endl;
  }
}


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

int main(){
	while(1){
		int n; //柿の木の数
		int w, h; //width,height
		int s, t; //土地の広さsが幅，tが高さ
		int field[100][100];
		
		scanf(" %d", &n);
		if(n==0) break;
		scanf(" %d %d", &w, &h);
		
		for(int i=0; i<h; ++i)
		for(int j=0; j<w; ++j)
		field[i][j]=0;
		
		for(int i=0; i<n; ++i){
			int x, y;
			scanf(" %d %d", &x, &y);
			field[y-1][x-1]=1;	
		}
		/*
		for(int i=0; i<h; ++i){
			for(int j=0; j<w; ++j){
				printf("%d ",field[i][j]);
			}
			printf("\n");
		}
		*/
		scanf(" %d %d", &s, &t);
		
		
		
		
		int ans=0;
		for(int i=0; i<=h-t; ++i){ //枠の左上端
			for(int j=0; j<=w-s; ++j){
				
				int tmp=0;
				for(int p=i; p<i+t; ++p){
					for(int q=j; q<j+s; ++q){
						tmp+=field[p][q];
					}
				}
				
				if(ans<tmp) {
					ans=tmp;
					//printf(" %d better::: %d, %d\n", ans, i, j);
				}
			}
		}
		printf("%d\n", ans); 
	}
	
	return 0;
}

Measured memory_bytes: 1228
main = do
    s <- getLine
    let n = length s
        a = length $ filter (== 'a') s
        b = length $ filter (== 'b') s
        c = (n - a - b)
    putStrLn $ if all (\i -> i >= n `div` 3 && i <= n `div` 3 + 1) [a,b,c] then "YES" else "NO"

Measured memory_bytes: 7164