akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <limits>
using namespace std;

struct node {
    int key;
    struct node *left, *right;
    node(int k):key(k),left(NULL),right(NULL){}
};

class bintree {
    node dummy;
    node *&root;
    bool first;
    void inorder(node *t) {
        if(t) {
            inorder(t->left);
            cout<<' '<<t->key;
            inorder(t->right);
        }
    }
    void preorder(node *t) {
        if(t) {
            cout<<' '<<t->key;
            preorder(t->left);
            preorder(t->right);
        }
    }
    public:
    bintree():dummy(numeric_limits<int>::min()), root(dummy.right){}
    void insert(int key)
    {
        node *n = new node(key);
        node *y=&dummy;
        node *x=root;
        while(x!=NULL) {
            y=x;
            if(key<x->key) x=x->left;
            else x=x->right;
        }
        if(y==&dummy) {
            root=n;
        } else {
            if(key<y->key) y->left=n;
            else y->right=n;
        }
    }
    node *find(int key) {
        node *n=root;
        while(n) {
            if(n->key==key) return n;
            if(key<n->key) n=n->left;
            else n=n->right;
        }
        return NULL;
    }
    void del(int key) {
        node *p=&dummy;
        node *z=root;
        while(z && z->key!=key) {
            p=z;
            if(key<z->key) z=z->left;
            else z=z->right;
        }
        if(z->left==NULL && z->right==NULL) {
            if(key<p->key) p->left=NULL;
            else p->right=NULL;
            delete z;
        } else if(z->left==NULL) {
            if(key<p->key) p->left=z->right;
            else p->right=z->right;
            delete z;
        } else if(z->right==NULL) {
            if(key<p->key) p->left=z->left;
            else p->right=z->left;
            delete z;
        } else {
            node *y = z->right;
            p=z;
            while(y->left) {
                p=y;
                y=y->left;
            }
            z->key=y->key;
            if(p == z) z->right=y->right;
            else p->left=y->right;
            delete y;
        }
    }
    void inorder(){
        inorder(root);
        cout<<'\n';
    }
    void preorder(){
        preorder(root);
        cout<<'\n';
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    bintree t;
    int n;
    string com;
    int key;
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>com;
        switch(com[0]) {
        case 'i':
            cin>>key;
            t.insert(key);
            break;
        case 'f':
            cin>>key;
            if(t.find(key)) cout<<"yes\n";
            else cout<<"no\n";
            break;
        case 'd':
            cin>>key;
            t.del(key);
            break;
        case 'p':
            t.inorder();
            t.preorder();
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 13720
#include <iostream>
#include <stdio.h>

using namespace std;

int main(void){
  int a, b;
  int d;
  int r;
  double f;
  cin >> a >> b;
  d = a / b;
  r = a - b * d;
  f = (double)a / (double)b;
  // output: d r f
  //cout << d << " " << r << " " << f << endl;
  printf("%d %d %1.8lf\n", d, r, f);
  return 0;
}


Measured memory_bytes: 3200
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
cnt = 0
s = -A[0]
for i in range(N // 2):
    cnt = i
    s += 2 * A[i]
if N % 2 == 1:
    s += A[cnt + 1]
print(s)


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

using namespace std;
int a,b,c,d;
int n;

int main()
{
    scanf("%d%d%d%d%d",&a,&b,&c,&d,&n);
    long long res;
    int i,j;
    if(8*a<=4*b&&8*a<=2*c&&8*a<=d)res = 4*(long long)a*(long long)n;
    else {
        if(8*a>=4*b&&4*b<=2*c&&4*b<=d)res = 2*(long long)b*(long long)n;
        else {
            if(8*a>=2*c&&4*b>=2*c&&2*c<=d)res = (long long)c*(long long)n;
            else{
                res = (long long)d*((long long)n/2);
                if(n%2){
                    long long ans;
                    ans = min(4*a,2*b);
                    ans = min(ans,(long long)c);
                    res += ans;
                }
            }
        }
    }
    printf("%lld",res);
    return 0;
}


Measured memory_bytes: 256
a, b, c, d = map(int, input().split())

i = 0
while True:
    if 0 == i % 2:
        c -= b
    else:
        a -= d

    if a <= 0:
        print("No")
        break
    elif c <= 0:
        print("Yes")
        break
    i += 1


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

using namespace std;
using ll = long long;
using v1 = vector<int>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;


int main(){
	stack<int> a;
	stack<pair<int, int>> b;
	int S = 0;
	int left = 0;
	string s;
	cin >> s;
	rep(i, s.size()){
		if(s.at(i) == '\\'){
			a.push(i);
		}else if(s.at(i) == '/'){
			if(a.empty()) continue;
			int d = a.top();
			int as =(i-d);
			S += as;
			a.pop();
			if(b.empty()){
				b.push(make_pair(d, i-d));
			}else{
				while(!b.empty() && b.top().first > d){
					as += b.top().second;
			    	b.pop();
					}
				b.push(make_pair(d, as));
			}
		}
	}

	cout << S << endl;
	vector<int> L(0);
	int c = 0;
	while(!(b.empty())){
		L.push_back(b.top().second);
		b.pop();
		c++;
	}
	cout << c;
	if(c == 0){
		cout << endl;
	}else{
		cout << " ";
	}
	reverse(L.begin(), L.end());
	rep(i, c){
		cout << L.at(i);
		if(i == c-1){
			cout << endl;
		}else{
			cout << " ";
		}
	}
}



Measured memory_bytes: 3228
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
using namespace std;

int read(); ll readll();

int n,mod,dp[6009][2009];
int main(){
	scanf("%d%d",&n,&mod);
	int i,j;
	dp[0][0]=1;
	for (i=0; i<(3*n); i++)
		for (j=0; j<=n; j++) if (dp[i][j]){
			if (i+3<=3*n && j<n) ad(dp[i+3][j+1],(ll)dp[i][j]*(i+1)%mod*(i+2));
			if (i+2<=3*n && j<n) ad(dp[i+2][j+1],(ll)dp[i][j]*(i+1));
			ad(dp[i+1][j],dp[i][j]);	
		}
	int ans=0;
	for (i=0; i<=n; i++) ad(ans,dp[3*n][i]);
	printf("%d\n",ans);
	return 0;
}

int read(){
	int x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}
ll readll(){
	ll x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}


Measured memory_bytes: 46960
#include <bits/stdc++.h>
#define il inline
#define ri register int
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define mid ((l+r)>>1)
#define MAXN 105
#define MAXM
#define mod
#define inf (1<<30)
#define eps (1e-6)
#define alpha 0.75
#define rep(i, x, y) for(ri i = x; i <= y; ++i)
#define repd(i, x, y) for(ri i = x; i >= y; --i)
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
typedef pair <int, ll> pil;
typedef pair <ll, ll> pll;
template <typename T> il bool chkmin(T &x, T y) {return x > y ? x = y, 1 : 0;}
template <typename T> il bool chkmax(T &x, T y) {return x < y ? x = y, 1 : 0;}
template <typename T> il void read(T &x) {
	char ch = getchar(); int f = 1; x = 0;
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = x*10+ch-'0', ch = getchar();
	x *= f;
}
template <typename T, typename... Args> il void read(T &x, Args &...args) {
	read(x), read(args...);
}
int n, a[MAXN << 1], ans;
int main() {
	read(n);
	rep(i, 1, 2*n) read(a[i]);
	sort(a+1, a+2*n+1);
	rep(i, 1, n) ans += a[i*2-1];
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
import sys

s = sys.stdin.readline().rstrip()
n = len(s)

def c(n):
    return pow(2, max(0, n - 1))
  
def main():
    res = 0
    for l in range(n):
        for r in range(l, n):
            res += int(s[l:r+1]) * c(l) * c(n - 1 - r)
    print(res)

if __name__ ==  '__main__':
    main()

Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

 
public class Main {
 
    void solve() throws IOException {
        int N = ni();
        int[] x = new int[N];
        int[] y = new int[N];
        for (int i = 0; i < N; i++) {
            x[i] = ni();
            y[i] = ni();
        }
        ArrayList<Integer> pp = new ArrayList<>();
        ArrayList<Integer> pn = new ArrayList<>();
        ArrayList<Integer> np = new ArrayList<>();
        ArrayList<Integer> nn = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            pp.add(x[i] + y[i]);
            pn.add(x[i] - y[i]);
            np.add(-x[i] + y[i]);
            nn.add(-x[i] - y[i]);
        }
        long ans = 0;
        ans = Math.max(ans, Collections.max(pp)-Collections.min(pp));
        ans = Math.max(ans, Collections.max(pn)-Collections.min(pn));
        ans = Math.max(ans, Collections.max(np)-Collections.min(np));
        ans = Math.max(ans, Collections.max(nn)-Collections.min(nn));
        out.println(ans);
    }

    final int mod = 1000000007;
    final BigInteger MOD = BigInteger.valueOf(mod);

    int mul(int x, int y){
        int val = (int)((x * 1L * y) % mod);
        return val>=0 ? val : val+mod;
    }
    int add(int x, int y) {
        x += y;
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    int sub(int x, int y){
        x = add(x,mod-y);
        if(x < 0) x += mod;
        if(x>=mod) x -= mod;
        return x;
    }
    String ns() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine(), " ");
        }
        return tok.nextToken();
    }
 
    int ni() throws IOException {
        return Integer.parseInt(ns());
    }
 
    long nl() throws IOException {
        return Long.parseLong(ns());
    }
 
    double nd() throws IOException {
        return Double.parseDouble(ns());
    }
 
    String[] nsa(int n) throws IOException {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = ns();
        }
        return res;
    }
 
    int[] nia(int n) throws IOException {
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = ni();
        }
        return res;
    }
 
    long[] nla(int n) throws IOException {
        long[] res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = nl();
        }
        return res;
    }
 
    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer tok;
 
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        tok = new StringTokenizer("");
        Main main = new Main();
        main.solve();
        out.close();
    }
}

Measured memory_bytes: 69352
from collections import Counter
n=int(input())
l=list(map(int,input().split()))
s=[l[0]]+[0]*(n-1)
for i in range(1,n):
  s[i]=s[i-1]+l[i]
S=Counter(s);ans=0
for i in S.values():
  ans+=(i*(i-1))//2
ans+=s.count(0)
print(ans)

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

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

int N, M;
int a[100005], b[100005];
int cnt[100005];
int main() {
    cin >> N >> M;
    rep(i, M) cin >> a[i] >> b[i];
    rep(i, M) {
        cnt[a[i]]++;
        cnt[b[i]]++;
    }
    string ans = "YES";
    rep(i, 100005) {
        if (cnt[i] % 2 == 1) ans = "NO";
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1408
#include<iostream>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

ll tate[100000], yoko[100000];

int main() {

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> yoko[i];
	for (int i = 0; i < m; i++)cin >> tate[i];
	ll w = 0, h = 0;
	for (int i = 0; i < n; i++) {
		w += (i * yoko[i] - (n - i - 1) * yoko[i]);
		w %= MOD;
	}
	for (int i = 0; i < m; i++) {
		h += ((i * tate[i]) - (m - i - 1) * tate[i]);
		h %= MOD;
	}

	cout << h * w % MOD << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>                                             
using namespace std;                                            
                                                                
int main(void) {                                                
  int a, b;                                                     
  cin >> a >> b;                                                
  int S = a*b;                                                  
  int R = 2*(a+b);                                              
  cout << S << " " << R << endl;                                
  return 0;                                                     
}                                                               
                         

Measured memory_bytes: 3000
#include <stdio.h>

int main() {
 long long int x;
  int yrs = 0;
  long long int y = 100;
  scanf("%lld", &x);
  while(y < x) {
  	yrs++;
    y = (long long int)(y*1.01);
  }
  printf("%d\n", yrs);
  return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
const ll mod = 1000000007;
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
ll F[20000005],R[20000005];
void make(){
	F[0] = 1;
	for(int i=1;i<20000005;i++) F[i] = F[i-1]*i%mod;
	R[20000004] = modpow(F[20000004],mod-2);
	for(int i=20000003;i>=0;i--) R[i] = R[i+1]*(i+1)%mod;
}
ll C(int a,int b){
	return F[a]*R[b]%mod*R[a-b]%mod;
}

int h,w,k;
ll ans;

int main(){
	cin >> h >> w >> k;
	make();
	
	//face
	ans += C(h+w,k) * F[k] % mod * k % mod;
	
	//edge
	ans += C(h+w,k) * F[k] % mod * k % mod * (k+1) % mod * modpow(2,mod-2) % mod;
	
	//crosspoint
	if(k >= 2){
		for(int t=2;t<=k;t++){
			ans += 2LL * h * w % mod * C(h+w-2,k-2) % mod * (t-1) % mod * F[k-2] % mod * (k+1-t) % mod;
		}
	}
	cout << (ans%mod+mod)%mod << endl;
}

Measured memory_bytes: 312704
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const int INF= 1e9+5;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
int main(){
  int n;cin>>n;
  vl v(n);
  rep(i,n)cin>>v[i];
  map<ll,ll>M1;
  map<ll,ll>M2;
  rep(i,n){
    if(i%2==0)M1[v[i]]++;
    else M2[v[i]]++;
  }
  ll max1=0;
  vector<P>vec1;
  vector<P>vec2;
  for(auto p:M1){
    vec1.push_back(make_pair(p.second,p.first));
  }
  for(auto p:M2){
    vec2.push_back(make_pair(p.second,p.first));
  }
  sort(vec1.begin(),vec1.end());
  reverse(vec1.begin(),vec1.end());
  sort(vec2.begin(),vec2.end());
  reverse(vec2.begin(),vec2.end());
  vec1.push_back(make_pair(0,-1));
  vec2.push_back(make_pair(0,-2));
  if(vec1[0].second!=vec2[0].second){
    cout<<n-vec1[0].first-vec2[0].first<<endl;
  }
  else cout<<n-vec1[0].first-max(vec1[1].first,vec2[1].first)<<endl;
}
  
  
    

Measured memory_bytes: 9592
import collections
from collections import OrderedDict
count=0
N,K=map(int,input().split())
ball=list(map(str,input().split()))
c=sorted(collections.Counter(ball).values())
n=len(c)-K
if n==0:
    print(count)
else:
    for i in range(n):
        count+=c[i]
    print(count)

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

using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;

#define rep(i,b) for(i=0;i<b;++i)
#define repp(i,a,b) for(i=a;i<b;++i)

int main() {
    ll n;
    int mx = -1;
    cin >> n;
    string s;
    map<string, int> mp;
    std::vector<string> v;
    for(int i = 0; i < n; i++){
        cin >> s;
        mp[s]++;
    }
    for(auto i : mp){
        int x = i.second;
        mx = max(mx, x);
    }
    for(auto i : mp){
        if(i.second == mx){
            v.push_back(i.first);
        }
    }
    for(auto i:v)cout << i << endl;
    return 0;
}
/*
         ,--"""",--.__,---[],-------._
       ,"   __,'            \         \--""""""==;-
     ," _,-"  "/---.___     \       ___\   ,-'',"
    /,-'      / ;. ,.--'-.__\  _,-"" ,| `,'   /
   /``""""-._/,-|:\       []\,' ```-/:;-. `. /
             `  ;:::      ||       /:,;  `-.\
                =.,'__,---||-.____',.=
                =(:\_     ||__    ):)=
               ,"::::`----||::`--':::"._
             ,':::::::::::||::::::::::::'.
    .__     ;:::.-.:::::__||___:::::.-.:::\     __,
       """-;:::( O )::::>_|| _<::::( O )::::-"""
   =======;:::::`-`:::::::||':::::::`-`:::::\=======
    ,--"";:::_____________||______________::::""----.          , ,
         ; ::`._(    |    |||     |   )_,'::::\_,,,,,,,,,,____/,'_,
       ,;    :::`--._|____[]|_____|_.-'::::::::::::::::::::::::);_
      ;/ /      :::::::::,||,:::::::::::::::::::::::::::::::::::/
     /; ``''''----------/,'/,__,,,,,____:::::::::::::::::::::,"
     ;/                :);/|_;| ,--.. . ```-.:::::::::::::_,"
    /;                :::):__,'//""\\. ,--.. \:::,:::::_,"
   ;/              :::::/ . . . . . . //""\\. \::":__,"
   ;/          :::::::,' . . . . . . . . . . .:`::\
   ';      :::::::__,'. ,--.. . .,--. . . . . .:`::`
   ';   __,..--'''-. . //""\\. .//""\\ . ,--.. :`:::`
   ;    /  \\ .//""\\ . . . . . . . . . //""\\. :`::`
   ;   /       . . . . . . . . . . . . . . . . .:`::`
   ;   (          . . . . . . . . . . . . . . . ;:::`
   ,:  ;,            . . . . . . . . . . . . . ;':::`
   ,:  ;,             . . . . . . . . . . . . .;`:::
   ,:   ;,             . . . . . . . . . . . . ;`::;`
    ,:  ;             . . . . . . . . . . . . ;':::;`
     :   ;             . . . . . . . . . . . ,':::;
      :   '.          . . . . . . . .. . . .,':::;`
       :    `.       . . . . . . . . . . . ;::::;`
        '.    `-.   . . . . . . . . . . ,-'::::;
          `:_    ``--..___________..--'':::::;'`
             `._::,.:,.:,:_ctr_:,:,.::,.:_;'`
________________`"\/"\/\/'""""`\/"\/""\/"____________________________

*/


Measured memory_bytes: 26868
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define p(x) cout<<(x)<<endl;

int main() {
  int N; cin >> N;
  int dig, sum; sum = 0;

  int num = N;

  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
}

  if ( N%sum == 0) {
    p("Yes");
  } else {
    p("No");
  }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 2005

using namespace std;

vector <int> vec[SIZE];
int dp[SIZE][SIZE];
int nxt[SIZE];
int mx[SIZE],nd[SIZE];
int n,K;
int ret;

void dfs(int v=0,int p=-1)
{
	mx[v]=0;
	nd[v]=1;
	for(int j=1;j<SIZE;j++) dp[v][j]=SIZE;
	dp[v][0]=0;
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(to!=p)
		{
			dfs(to,v);
			for(int j=0;j<SIZE;j++) nxt[j]=SIZE;
			for(int j=0;j<=mx[v];j++)
			{
				for(int k=0;k<=mx[to];k++)
				{
					if(j+k>K) break;
					nxt[max(j,k)]=min(nxt[max(j,k)],dp[v][j]+dp[to][k]);
				}
			}
			for(int j=0;j<SIZE;j++) dp[v][j]=nxt[j];
			mx[v]=max(mx[v],mx[to]);
			nd[v]+=nd[to];
		}
	}
	for(int j=0;j<=K;j++) ret=min(ret,dp[v][j]+n-nd[v]);
	mx[v]++;
	for(int j=mx[v];j>=1;j--) dp[v][j]=dp[v][j-1];
	dp[v][0]=nd[v];
}
int main()
{
	scanf("%d %d",&n,&K);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--;b--;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	ret=SIZE;
	dfs();
	printf("%d\n",ret);
	return 0;
}


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

using namespace std;

int main() {
  int N, Y;
  cin >> N >> Y;

  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N - i; ++j) {
      if ((10000 * i + 5000 * j + 1000 * (N - i - j)) == Y) {
        cout << i << " " << j << " " << N - i - j << endl;
        return 0;
      }
    }
  }
  cout << "-1 -1 -1" << endl;

  return 0;
}

Measured memory_bytes: 3580
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<iomanip>

using namespace std;


int main(void) {
	int c[3][3];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> c[i][j];
		}
	}
	int rev;
	for (int i = 0; i < 3; i++) {
		if (i < 2) {
			rev = c[i][0] - c[i + 1][0];
		}
		else {
			rev = c[i][0] - c[0][0];
		}
		for (int j = 0; j < 3; j++){
			if (i < 2) {
				if (c[i][j] - c[i + 1][j] != rev) {
					cout << "No";
					return 0;
				}
			}
			else {
				if (c[i][j] - c[0][j] != rev) {
					cout << "No";
					return 0;
				}
			}
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni();
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int a = -in.ni();
            map.put(a,map.containsKey(a)?map.get(a)+1:1);
        }
        long e1 = 0, e2 = 0;
        for(Integer key: map.keySet()){
            if(map.get(key)>=4){
                if(e1==0){
                    e1 = -key;
                    e2 = -key;
                }else{
                    e2 = -key;
                }
                break;
            }else if(map.get(key)>=2){
                if(e1==0) e1 = -key;
                else if(e2==0){
                    e2 = -key;
                    break;
                }
            }
        }
        out.println(e1*e2);
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 46060
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vb vector<bool>

void solve()
{
  int n;
  cin>>n;
  if(n%1000 == 0)
    cout<<0<<'\n';
  else
    cout<<(1000-(n%1000))<<'\n';
}

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

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define maxn 100009
#define ll long long
int N;
int depth[maxn];
struct node{
    int x,y;
    int next;
}line[maxn*4];
int tot,head[maxn];
ll ans=0;
void insert(int x,int y)
{
    tot++;line[tot].x=x;line[tot].y=y;
    line[tot].next=head[x];
    head[x]=tot;
}
ll Hash[maxn];
ll p=1000000007;
ll mod=998244353;
map<ll,ll>Map;
map<ll,ll>::iterator it;
void dfs(int u,int fa)
{
    int k;
    depth[u]=depth[fa]+1;
    Hash[u]=1;
    for(k=head[u];k;k=line[k].next)
    {
        if(line[k].y==fa)continue;
        dfs(line[k].y,u);
        Hash[u]=(Hash[u]+Hash[line[k].y]*p)%mod;
    }
    Map[Hash[u]]++;
}
int main()
{
    while(scanf("%d",&N)!=EOF)
    {
        int i,j,k;
        int a,b;
        for(i=1;i<N;i++)
        {
            scanf("%d%d",&a,&b);
            insert(a,b);
        }
        dfs(1,0);
        ans=0;
        for(it=Map.begin();it!=Map.end();it++)
        {
            ll p=it->second;
            ans+=p*(p-1)/2;
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

int main(void){
  long long N, A[5];
  cin >> N;
  rep(i, 5)
    cin >> A[i];
  //ここまで入力

  //10^16
  long long min = 10000000000000000;
  long long min_n;
  rep(i, 5)
    if(A[i] < min){
      min = A[i];
      min_n = i;
    }

  //初期値は，律速な交通機関にたどり着くまでの時間
  long long ans = min_n;
  //min_t分後から数えて，全員を律速な交通機関で運び終えるまでの時間
  long long tmp;
  if(N%min == 0)
    tmp = N/min;
  //割り切れないときは，余分にもう一回運ぶ必要がある
  else
    tmp = N/min+1;

  //カウントに足し込む
  ans += tmp;

  //律速な交通機関より後にかかる時間
  ans += (5-min_n-1);

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define inf 1000000005
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define mod 1000000007
#define sz(a) ((int)(a).size())

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcount(s);}
#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --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)

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define eps 1e-9
typedef pair<int, int> II;
template<class T> T gcd(T a, T b){ T r; while (b != 0) { r = a % b; a = b; b = r; } return a;}
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define PI 2 * acos(0)

#define maxn 600006

int test;
ll a, b;

void solve(int itest){
	cin >> a >> b;
	if(a > b) swap(a, b);
	if(a == b) {
		cout << a + a - 2 << endl;
		return;
	}
	ll res = a - 1;
	ll l = a, r = b, mid;
	while(l < r){
		mid = (l + r) >> 1;
		if(mid * mid < a * b) l = mid + 1;
		else r = mid;
	}
	l--;
	res += l - a + l - 1;
	if(l * (l + 1) < a * b) res++;
	cout << res << endl;
}

int main(){
	srand(1412);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);

	cin >> test;
	For(itest, 1, test){
		solve(itest);
	}

    return 0;
}


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

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

static const int INF = 1E8;
struct Edge{int A, B, D, E;};
int N, M, L;
int A, B, D, E;
vector<Edge> g[111];
int d[111][111];
vector<int> tmp(3);

int main()
{
  while(cin >> N >> M >> L, N){
    rep(i, 111) g[i].clear();
    rep(i, M){
      cin >> A >> B >> D >> E;
      g[A - 1].push_back((Edge){A - 1, B - 1, D, E});
      g[B - 1].push_back((Edge){B - 1, A - 1, D, E});
    }

    rep(i, 111) rep(j, 111) d[i][j] = INF;
    d[0][0] = 0;
    priority_queue<vector<int>, vector<vector<int> >, greater<vector<int> > > que;
    tmp[0] = 0,  tmp[1] = 0,  tmp[2] = 0;
    que.push(tmp);
    while(!que.empty()){
      vector<int> top = que.top();  que.pop();
      int cnt = top[0];
      int cost = top[1];
      int h = top[2];
      if(d[h][cost] < cnt) continue;
      rep(i, g[h].size()){
        Edge e = g[h][i];
        tmp[2] = e.B;
        if(cost <= L && d[e.B][cost] > cnt + e.E) {
          d[e.B][cost] = cnt + e.E;
          tmp[0] = cnt + e.E;
          tmp[1] = cost;
          que.push(tmp);
        }
        if(cost + e.D <= L && d[e.B][cost + e.D] > cnt){
          d[e.B][cost + e.D] = cnt;
          tmp[0] = cnt;
          tmp[1] = cost + e.D;
          que.push(tmp);
        }
      }
    }
    int res = INF;
    rep(i, 111) res = min(res, d[N - 1][i]);
    printf("%d\n", res);
  }

  return 0;
}

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

using namespace std;

int main() {

    int N, M;
    cin >> N;
    cin >> M;

    int count = 0;
    if(N != 0)count += N*(N-1)/2;
    if(M != 0)count += M*(M-1)/2;
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
struct Node{
    int u,v,opt;
}p[maxn];
int fa[maxn];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    ll n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].opt);
        p[i].u++;
        p[i].v++;
        if(p[i].opt==0){
            int fu=find(p[i].u),fv=find(p[i].v);
            if(fu!=fv)
                fa[fu]=fv;
        }
    }
    ll c=0;
    for(int i=1;i<=n;i++){
        if(find(i)==i)
            c++;
    }
    ll huan=0;
    for(int i=1;i<=q;i++){
        if(p[i].opt==1){
            huan++;
            if(find(p[i].u)==find(p[i].v)){
                printf("No\n");
                return 0;
            }
        }
    }
    ll temp=m-(n-c);
    ll l,r;
    l = huan?max(3ll,(ll)c):c-1ll,r = 1ll*c*(c-1ll)/2ll;
    if(l<=temp&&temp<=r)
        printf("Yes\n");
    else printf("No\n");
}
 

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;



int main() {
    int n,k; cin >> n >> k;
    int ans = 0;
    for(int i = 0;i < n;i++){
        int x; cin >> x;
        if(x >= k) ans++;
    }
    cout << ans;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
#include <math.h>
#define PI 3.14159265358979323846

using namespace std;

int main() {
  double A,B,H,M,S,L;
  cin >> A >> B >> H >> M;
  S=(H*60-11*M)*PI/360;
  double C=A*B*cos(S);
  A*=A;
  B*=B;
  L=sqrt(A+B-2*C);
  cout << fixed << setprecision(20) << L << endl;
}

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

typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
#define rrep(i, m, n) for(int (i)=(m); (i)<(n);  (i)++)
#define erep(i, m, n) for(int (i)=(m); (i)<=(n); (i)++)
#define  rep(i, n)    for(int (i)=0; (i)<(n);  (i)++)
#define rrev(i, m, n) for(int (i)=(n)-1; (i)>=(m); (i)--)
#define erev(i, m, n) for(int (i)=(n); (i)>=(m); (i)--)
#define  rev(i, n)    for(int (i)=(n)-1; (i)>=0; (i)--)
#define vrep(i, c)    for(__typeof((c).begin())i=(c).begin(); i!=(c).end(); i++)
#define  ALL(v)       (v).begin(), (v).end()
#define mp            make_pair
#define pb            push_back
template<class T, class S> inline bool minup(T& m, S x){ return m>(T)x ? (m=(T)x, true) : false; }
template<class T, class S> inline bool maxup(T& m, S x){ return m<(T)x ? (m=(T)x, true) : false; }

const int    INF = 1000000000;
const ll     MOD = 1000000007LL;
const double EPS = 1E-12;

struct Point : public complex<double>
{
public:
  Point() { this->real(0);  this->imag(0); }
  Point(const double& x, const double& y) { this->real(x);  this->imag(y); }
  Point(const complex<double> w)  { this->real(w.real());  this->imag(w.imag()); }
  inline double dot(Point p){ return (conj(*this) * p).real(); }
  inline double det(Point p){ return (conj(*this) * p).imag(); }
};

namespace std
{
  bool operator < (const Point& a, const Point& b)
  {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if(b.det(c) > 0.0)    return  1;
  if(b.det(c) < 0.0)    return -1;
  if(b.dot(c) < 0.0)    return  2;
  if(norm(b) < norm(c)) return -2;
  return 0.0;
}

double x[3], y[3];
double px, py;

int main()
{
  while(cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> px >> py){
    Point A = Point(x[0], y[0]);
    Point B = Point(x[1], y[1]);
    Point C = Point(x[2], y[2]);
    Point P = Point(px, py);
    Point AB = B - A, BC = C - B, CA = A - C;
    Point AP = P - A, BP = P - B, CP = P - C;

    bool ok = false;
    if(AB.det(BP) > 0 && BC.det(CP) > 0 && CA.det(AP) > 0) ok = true;
    if(AB.det(BP) < 0 && BC.det(CP) < 0 && CA.det(AP) < 0) ok = true;

    puts(ok ? "YES" : "NO");
  }

  return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string S;
    cin >> S;
    int N = (int)S.size();
    int Ans1 = 0, Ans2 = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == '1') {
            if (i % 2 == 0) {
                Ans1++;
            } else {
                Ans2++;
            }
        } else {
            if (i % 2 == 1) {
                Ans1++;
            } else {
                Ans2++;
            }
        }
    }
    cout << min(Ans1, Ans2);
    return 0;
}



Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>

using namespace std;
typedef pair<int,int> pii;
int h,w,s;
pii dp[32][32][32][32];
int field[32][32];
int sumTbl[32][32];
int fSum[32][32][32][32];
int allSum;

pii dfs(int minx,int miny,int maxx,int maxy){
	if(dp[minx][miny][maxx][maxy].first!=-1)return dp[minx][miny][maxx][maxy];
	// »ÝÌé`Ìùva
	int sum=fSum[minx][miny][maxx][maxy];
	pii res(1,sum);
	// yÌÇ±©Åª
	for(int i=miny;i<maxy;i++){
		// ªµ½ç»ê¼êÌÌæÌaðßA»ê¼êÌaªðð½·©²×é
		int sum1=fSum[minx][miny][maxx][i];
		int sum2=fSum[minx][i+1][maxx][maxy];
		// ðð½·
		if(allSum-sum1<=s&&allSum-sum2<=s){
			// »ê¼êÌßèlðæ¾
			pii p1=dfs(minx,miny,maxx,i);
			pii p2=dfs(minx,i+1,maxx,maxy);
			if(res.first<p1.first+p2.first){
				res.first=p1.first+p2.first;
				res.second=min(p1.second,p2.second);
			}
			else if(res.first==p1.first+p2.first)res.second=max(res.second,min(p1.second,p2.second));
		}
	}
	for(int i=minx;i<maxx;i++){
		// ªµ½ç»ê¼êÌÌæÌaðßA»ê¼êÌaªðð½·©²×é
		int sum1=fSum[minx][miny][i][maxy];
		int sum2=fSum[i+1][miny][maxx][maxy];
		// ðð½·
		if(allSum-sum1<=s&&allSum-sum2<=s){
			// »ê¼êÌßèlðæ¾
			pii p1=dfs(minx,miny,i,maxy);
			pii p2=dfs(i+1,miny,maxx,maxy);
			if(res.first<p1.first+p2.first){
				res.first=p1.first+p2.first;
				res.second=min(p1.second,p2.second);
			}
			else if(res.first==p1.first+p2.first)res.second=max(res.second,min(p1.second,p2.second));
		}
	}
	dp[minx][miny][maxx][maxy].first=res.first;
	dp[minx][miny][maxx][maxy].second=res.second;
	return res;
}

int main(){
	while(cin>>h>>w>>s&&(h|w|s)){
		allSum=0;
		for(int i=0;i<32;i++)
			for(int j=0;j<32;j++)
				for(int k=0;k<32;k++)
					for(int l=0;l<32;l++)dp[i][j][k][l].first=dp[i][j][k][l].second=-1;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin>>field[i][j];
				allSum+=field[i][j];
			}
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(j==0)sumTbl[i][j]=field[i][j];
				else sumTbl[i][j]=sumTbl[i][j-1]+field[i][j];
			}
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				for(int k=i;k<h;k++){
					for(int l=j;l<w;l++){
						fSum[j][i][l][k]=0;
						// s²ÆÉÁZ
						for(int m=i;m<=k;m++){
							if(j!=0)fSum[j][i][l][k]+=sumTbl[m][l]-sumTbl[m][j-1];
							else fSum[j][i][l][k]+=sumTbl[m][l];
						}
					}
				}
			}
		}
		pii res=dfs(0,0,w-1,h-1);
		cout<<res.first<<" "<<s-(allSum-res.second)<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int const INF = 1001001001;


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

int n,k;
cin >> n >> k;
vi a(n);
rep(i,n) cin >> a[i];

int now = a[0];
int M = a[0];
for(int i = 1;i < n;++i){
    M = max(M,a[i]);
    now = gcd(now,a[i]);
}

if(k % now == 0 && k <= M) cout << "POSSIBLE" << endl;
else cout << "IMPOSSIBLE" << endl;

return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<vector>
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>
#define rep(i,N) for(int i=0;i<N;i++)
#define MOD 1000000007

using namespace std;


int main(void){
    string s,t;
    cin>>s>>t;
    int n=s.size(),m=t.size();
    VVI is(26);
    rep(i,n)is[s[i]-'a'].push_back(i);
    rep(i,n)is[s[i]-'a'].push_back(i+n);
    long long ans=0;
    int p=0;
    rep(i,m){
        int c=t[i]-'a';
        if(is[c].size()==0){
            cout<<-1<<endl;
            return 0;
        }
        p=*lower_bound(is[c].begin(),is[c].end(),p)+1;
        if(p>=n){
            p-=n;
            ans+=n;
        }
    }
    ans+=p;
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1724
//include---------------------------------------------------------------------------
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cctype>
#include<vector>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<bitset>
#include<map>
#include<algorithm>


//using namespace-------------------------------------------------------------------
using namespace std;

//define,const----------------------------------------------------------------------
#define rep(i, n) for(int i = 0; i < n; i++){
const int INF = 1 << 25;

//global----------------------------------------------------------------------------
stack<int> cars;
int numbar;

//function--------------------------------------------------------------------------
int main(){
	while(scanf("%d", &numbar) != EOF){
		if(numbar == 0){
			printf("%d\n", cars.top());
			cars.pop();
			continue;
		}
		cars.push(numbar);
	}
	return 0;
}

Measured memory_bytes: 1036
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {h: usize, w: usize, k:usize, c:[String;h]}

    let mut buf: Vec<Vec<char>> = Vec::new();

    for line in c {
        let mut char_line = Vec::new();
        for ch in line.as_str().chars() {
            char_line.push(ch);
        }
        buf.push(char_line);
    }

    let mut count = 0;
    let mut l: Vec<usize> = vec![0usize; h + w];

    println!("{}", dfs(h, w, k, &buf, &mut l, 0));
}

fn dfs(h: usize, w: usize, k: usize, c: &Vec<Vec<char>>, l: &mut Vec<usize>, i: usize) -> usize {
    let mut count: usize = 0;
    if i == l.len() {
        let mut sharp_count = 0;
        let mut h_buf = Vec::new();
        let mut w_buf = Vec::new();
        for j in 0..l.len() {
            if j < h {
                h_buf.push(l[j])
            } else {
                w_buf.push(l[j])
            }
        }

        for ch_h in 0..h {
            if h_buf[ch_h] == 1 {
                continue;
            }
            for ch_w in 0..w {
                if w_buf[ch_w] == 1 {
                    continue;
                }
                if sharp_count > k {
                    break;
                }
                if c[ch_h][ch_w] == '#' {
                    sharp_count += 1;
                }
            }
        }

        if sharp_count == k {
            count += 1;
        } else {
            count = 0;
        }
    } else {
        for j in 0..2 {
            l[i] = j;
            count += dfs(h, w, k, c, l, i + 1);
        }
    }
    count
}


Measured memory_bytes: 2312
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		String S = sc.next();

		sc.close();

		System.out.println(
			S.substring(0, K-1) +
			(char)(S.charAt(K-1) - 'A' + 'a') +
			S.substring(K)
		);
	}

}


Measured memory_bytes: 39252
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

N = 10**9+7
R = 10**5+10
modfact = [0]*(R+1)
def modfact_memo(n,N):
    r = 1
    modfact[0] = 1
    for i in range(1,n+1):
        r = r % N * i % N
        modfact[i] = r
modfact_memo(R,N)

# ax ≡ 1 (mod m)
modinv=[0]*(R+1)
def modinv_memo(a,m):
    for i in range(a+1):
        j = modfact[i]
        (inv, q, gcd_val) = egcd(j, m)
        modinv[i] = inv % m
modinv_memo(R,N)

def modconb(n,r,N):
    p = modfact[n]
    q1 = modinv[r]
    q2 = modinv[n-r]
    return p*q1%N*q2%N


n = int(input())
a = list(map(int,input().split()))
b=[0]*n
for i in range(n+1):
    b[a[i]-1] += 1
w = b.index(2)+1
index = []
for i in range(n+1):
    if a[i] == w:
        index.append(i)
l = index[0]
r = n - index[1]

for i in range(n+1):
    ans = modconb(n+1,i+1,N)
    if l+r >= i:
        ans -= modconb(l+r,i,N)
        ans %= N
    print(ans)

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

int main(){
    int N,M;
    cin >> N >> M;
    
    int A[N],sum=0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        sum += A[i];
    }

    int selectedProduct = 0;
    for(int i=0;i<N;i++){
        if(A[i] >= (double) sum / (4*M)){
            selectedProduct++;
        }
    }
    if(selectedProduct >= M){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 256
N,m = map(int,input().split())
s = [0]*m
for i in range(m):
    s[i] = list(map(int,input().split()))
p = list(map(int,input().split()))

case = 0

for i in range(2**N):
    TF=[0]*N
    for j in range(N):
        if ((i>>j)&1):
            TF[N-j-1]=1
    
    #print("\n")
    #print(TF)
    #print("↑今これ")

    c = [0]*m #スイッチ数は最初全部0
    for k in range(m): #k番目の電球に対応するスイッチ数を見ていく

        for l in range(1,len(s[k])): #対応するスイッチ数を合計していく
            c[k] += TF[s[k][l]-1] #cにその合計値を吐く
           
    #print(c)
    for k in range(m):
        if c[k]%2 != p[k]:
            #print("だめ")
            break
    else:
        case += 1
        #print("おｋ")
    
print(case)

Measured memory_bytes: 42736
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    string s; cin>>s;
    map<char,int>mp;
    rep(i,s.size()){
        mp[s[i]]++;
    }
    for(char c='a';c<='z';c++){
        mp[c]++;
        if(mp[c]==1){
            cout<<s+c<<endl;
            return 0;
        }
    }
    if(s=="zyxwvutsrqponmlkjihgfedcba"){
        cout<<-1<<endl;
        return 0;
    }
    int change;
    for(int i=s.size()-1;0<i;i--){
        if(s[i-1]>s[i])continue;
        else{
            change=i-1;
            break;
        }
    }
    char mn='z';
    char kaeru=s[change];
    for(int i=change+1;i<s.size();i++){
        if(s[i]<=kaeru)continue;
        mn=min(mn,s[i]);
    }
        rep(i,change){
        cout<<s[i];
    }
    cout<<mn<<endl;
}


Measured memory_bytes: 256
L = [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]
K = int(input())

print(L[K-1])

Measured memory_bytes: 3060
#include"bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
	int N, H, W;
	cin >> N >> H >> W;
	int ans = 0;
	rep(i, N) {
		int A, B;
		cin >> A >> B;
		if (A >= H && B >= W) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
unittest
{
	assert( [ "5", "2 2 3 5 5" ].solve == 2 );
	assert( [ "9", "1 2 3 4 5 6 7 8 9" ].solve == 0 );
	assert( [ "6", "6 5 4 3 2 1" ].solve == 18 );
	assert( [ "7", "1 1 1 1 2 3 4" ].solve == 6 );
}



import std.algorithm;
import std.conv;
import std.math;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	input.popFront;
	auto as = input.front.split.to!( long[] );
	
	// 式変形：abs( as[i] - ( b + ( i + 1 ) ) ) == abs( as[i] - ( i + 1 ) - b )
	foreach( i, ref a; as )
	{
		a -= 1 + i.signed;
	}
	
	// 各aからの距離の合計を最小にするにはbをasの中央値にすればいい
	auto ans = 0L;
	as.sort();
	if( n % 2 )
	{
		auto t = 0L;
		auto b = as[ $ / 2 ];
		foreach( ref a; as )
		{
			t += abs( a - b );
		}
		ans = t;
	}
	else
	{
		auto t1 = 0L;
		auto t2 = 0L;
		auto b1 = as[ $ / 2 - 1 ];
		auto b2 = as[ $ / 2 ];
		foreach( ref a; as )
		{
			t1 += abs( a - b1 );
			t2 += abs( a - b2 );
		}
		ans = min( t1, t2 );
	}
	return ans;
}


Measured memory_bytes: 11768
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;


int main()
{
  int x;
  cin >> x;
  string s;
  for(int i=x;i<1000;i++) {
    s = to_string(i);
    if(s[0] != s[1]) continue;
    if(s[1] != s[2]) continue;
    break;
  }
  cout << s;
  
  return 0;
}

Measured memory_bytes: 256
def f(n):
    a=[]
    while n%2==0:
        a.append(2)
        n=n//2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n=n//f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return(a)
    
n=int(input())
a=f(n)
b=[str(i) for i in a]
A=" ".join(b)
print(f"{n}: {A}")


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

int main() {
    int N, A=0, B=0;
    cin >> N;
    vector<int> a(N);
    for(int i=0; i<N; i++) cin >> a.at(i);
    
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    
    for(int i=0; i<N; i++){
        if(i % 2 == 0) A += a.at(i);
        else B += a.at(i);
    }
    cout << A - B << endl;
}

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

using namespace std;

void nextRand(int *x,int a,int b,int c){
	*x = (a * (*x) + b) % c;
}

int main(){
	while(true){
		int n;//リールの数(止める回数)
		int a,b,c;//乱数生成用定数
		int x;//シード(乱数の初期値)
		cin >> n >> a >> b >> c >> x;
		if(n==0){
			break;
		}
		int *reels = new int[n];//特殊な絵柄で止めるための乱数
		for(int i=0;i<n;i++){
			cin >> reels[i];
		}
		int reelidx = 0;
		int frame = -1;//最終的にかかったフレーム数
		for(int i=0;i<10001;i++){//[0,10000] iはフレーム数に対応
			if(x == reels[reelidx]){
				reelidx++;
			}
			nextRand(&x,a,b,c);//ループの最後に呼び出す
			if(reelidx == n){//終わり
				frame = i;
				break;
			}
		}
		cout << frame << endl;
		delete[] reels;
	}
	return 0;
}

Measured memory_bytes: 1196