akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	vl v(5),det(5);
	rep(i,5){
		cin>>v[i];
		det[i]=10*((v[i]-1)/10+1);
	}
	int ans=INF;
	rep(i,5){
		int sum=0;
		rep(j,5){
			if(j==i)sum+=v[j];
			else sum+=det[j];
		}
		chmin(ans,sum);
	}
	cout<<ans<<endl;

}


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

using namespace std;

ll n;
ll sum;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    ll ans = 0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            for (int k=1;k<=n;k++)
            {
                int g = __gcd(i,j);
                g = __gcd(g , k);
                ans += g;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug" << x << endl;
using namespace std;
 
int main(){
    int h,w;
    while(cin >> h >> w, h||w){
        rep(i,h){
            rep(j,w){
                cout << '#';
            }
            cout << endl;
        }
        cout << endl;
    }
}



Measured memory_bytes: 3072
#include <stdio.h>
//??¢??°?¨????
void EV (int m, int f, int r){
	if(m>=0 && f>=0 && 80<=m+f) putchar('A');
	if(m>=0 && f>=0 && 65<=m+f && m+f<80) putchar('B');
	if(m>=0 && f>=0 && 50<=m+f && m+f<65) putchar('C');
	if(m>=0 && f>=0 && 30<=m+f && m+f<50 && r<50) putchar('D');
	if(m>=0 && f>=0 && 30<=m+f && m+f<50 && 50<=r) putchar('C');
	if(m>=0 && f>=0 && m+f<30) putchar('F');
	if(m==-1 || f==-1) putchar('F');
}
int main(void){
	int m,f,r;
	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if(m==-1 && f==-1 && r==-1) break;
		EV(m,f,r);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 572
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		
		if (a < b && b < c){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		scan.close();
	}
}


Measured memory_bytes: 26184
import java.util.Scanner;

public class Main {

	public static void main(String args[]){

		Scanner scan = new Scanner(System.in);
		
		int a = scan.nextInt();
		int b = scan.nextInt();
		
		int ax = a, bx = b;
		for(int i = 1; i < b; i++){
			ax *= 10;
			ax += a;
		}

		for(int i = 1; i < a; i++){
			bx *= 10;
			bx += b;
		}
		
		System.out.println(ax >= bx ? ax : bx);
		
	}
}


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

using namespace std;

main(){
	int x,y,z;
	cin >> x >> y >> z;
	if(x==1&&y==0&&z==0){
		printf("Close\n");
	}else if(x==0&&y==1&&z==0){
		printf("Close\n");
	}else if(x==1&&y==1&&z==0){
		printf("Open\n");
	}else if(x==0&&y==0&&z==1){
		printf("Open\n");
	}else{
	printf("Close\n");}
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  if (S.size() > 3){
    if (S.at(0)=='Y' && S.at(1)=='A' && S.at(2)=='K' && S.at(3)=='I'){
      cout << "Yes";
    } else {
      cout << "No";
    }
  } else {
    cout << "No";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define  re(i,j,n) for(li i=(j);i<(n);i++)
#define  rep(i,n) re(i,0,(n))
#define  red(i,n) for(li i=n;i>0;i--)
#define  all(a) begin(a),end(a)
#define  pb(a) push_back(a)
using namespace std;
//namespace mp = boost::multiprecision;
typedef long int li;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<li> vli;
typedef vector<string> vs;


int main()
{
    int n;
    cin>>n;
    cout<<n*(n+1)/2<<endl;
    
    return 0;
}


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

using namespace std;

#define int long long 
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

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

    string s, t;
    cin >> s >> t;
    for(int i = s.size() - 1; i >= t.size() - 1; --i) {
        if(s[i] == t[t.size() - 1] || s[i] == '?') {
            int count = i - 1;
            bool flag = true;
            for(int j = t.size() - 2; j >= 0; --j) {
                if(s[count] != t[j] && s[count] != '?') {
                    flag = false;
                    break;
                }
                --count;
            }
            if(flag) {
                int index = count + t.size() + 1;
                string res = s;
                for(int j = 0; j < s.size(); ++j) {
                    if(res[j] == '?') res[j] = 'a';
                }
                int cnt = 0;
                for(int j = count + 1; j < index; ++j) {
                    res[j] = t[cnt++];
                }
                cout << res << endl;
                return 0;
            }
        }
    }
    cout << "UNRESTORABLE" << endl;
    return 0;
}


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

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int k, x;
	cin >> k >> x;

	for(int i = x - k + 1; i < x + k; i++) {
		cout << i << ' ';
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int main(){
  int n, x1, x2, y1, y2, z1, z2, w1, w2;
  while(scanf("%d", &n) && n){
    rep(i, n){
      scanf("%d%d%d%d%d%d%d%d", &x1, &y1, &z1, &w1, &x2, &y2, &z2, &w2);
      int rx, ry, rz, rw;
      rx = x1*x2 - y1*y2 - z1*z2 - w1*w2;
      ry = y1*x2 + x1*y2 + z1*w2 - w1*z2;
      rz = x1*z2 - y1*w2 + z1*x2 + w1*y2;
      rw = x1*w2 + y1*z2 - z1*y2 + w1*x2;
      printf("%d %d %d %d\n", rx, ry, rz, rw);
    }
  }
  return 0;
}

Measured memory_bytes: 1188
N = int(input())
l = list(map(int,input().split()))
for n in range(N):
    if l[n] % 2 == 0:
        if l[n] % 3 == 0 or l[n] % 5 == 0:
            pass
        else:
            print('DENIED')
            exit()
print('APPROVED')

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

ll n, a, b;

signed main(){
  cin >> n >> a >> b;
  if(abs(a - b) % 2 == 0){
    cout << abs(a - b) / 2 << endl;
  }else{
    ll res1 = min(a, b) + ((abs(a - b) - 1) / 2);
    ll res2 = n - max(a, b) + 1 + ((abs(a - b) - 1) / 2);
    cout << min(res1, res2) << endl;
  }
  //return 0;
}


Measured memory_bytes: 256
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <functional>
#include <map>

using namespace std;
 
typedef long long ll;

int ch[400][400];
int bw[400][400]; 
ll h , w; 
ll black , white;

    void dfs(ll a, ll b , int c) {
        if(ch[a][b] != 0){
            return;
        }
        if(bw[a][b] == c){
            return;
        }
        ch[a][b] = 1;
        if(bw[a][b] == -1){
            white += 1;
        }else{
            black += 1;
        }
        if(a+1 < h ){
            dfs(a+1 , b , bw[a][b]);
        }
        if(a-1 >= 0 ){
            dfs(a-1 , b , bw[a][b]);
        }
        if(b+1 < w ){
            dfs(a , b + 1 , bw[a][b]);
        }
        if(b-1 >= 0 ){
            dfs(a , b - 1 , bw[a][b]);
        }
        return;
    }

int main()
{
    //ll h , w;
    cin >> h >> w;
    string s;
    for(ll i = 0 ; i < h ; i++){
        cin >> s;
        for(ll j = 0 ; j < w ; j++){
            if(s[j] == '.'){
                bw[i][j] = -1;
            }else{
                bw[i][j] = 1;
            }
            ch[i][j] = 0;
        }
    }
    ll ans = 0;
    for(ll i = 0 ; i < h ; i++){
        for(ll j = 0 ; j < w ; j++){
            //cout << i  << ":" << j << endl;
            if(ch[i][j] == 0){
                black = 0;
                white = 0;
                dfs(i , j , (bw[i][j]) * -1 );
                ans += black * white; 
                //cout << ans << endl;
            }
        }
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11520
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ff first
#define ss second
typedef long long ll;
ll power(ll a, ll b){//a^b
    ll res=1;
    a=a%MOD;
    while(b>0){
        if(b&1){res=(res*a)%MOD;b--;}
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
ll fermat_inv(ll y){return power(y,MOD-2);}
ll gcd(ll a, ll b){return (b==0)?a:gcd(b,a%b);}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--){
        int a,b,c;
        int k;
        cin>>a>>b>>c>>k;
        int ctr=0;
        while(b<=a){
            b*=2;
            ctr++;
        }
        while(c<=b){
            c*=2;
            ctr++;
        }
        if(ctr<=k)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))

#define ll long long

using namespace std;
using Graph = vector<vector<int> >;

int main() {
  ll N;
  cin >> N;
  map<string, ll> ALL;
  vector<string> V;
  for (ll i = 0; i < N; i++) {
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    ALL[S]++;
  }

  ll cnt = 0;

  for (auto St : ALL) {
    cnt += St.second * (St.second -1) / 2;
  }

  cout << cnt << endl;
  // for (auto St : ALL) {
  //   ll acc = 0;
  //   for (auto Vt: V) {
  //     if (St == Vt) {
  //       acc++;
  //     }
  //   }
  //   if (acc != 1 ){
  //     cnt += acc * (acc - 1) / 2;
  //   }
  // }

  // cout << cnt << endl;
}


Measured memory_bytes: 11136
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#define FILE_NAME "a"


string s;

bool read() {
	cin >> s;
	return 1;
}

string apply(const string& s, char ch) {
	assert(sz(s) >= 2);
	string t;
	forn(i, sz(s) - 1) {
		if  (s[i] == ch || s[i + 1] == ch) {
			t.pb(ch);
		} else {
			t.pb(s[i]);
		}
	}
	return t;
}

bool same(const string& s) {
	forn(i, sz(s)) {
		if  (s[i] != s[0]) {
			return 0;
		}
	}
	return 1;
}

int solve() {
	int mn = sz(s);
	for (char ch = 'a'; ch <= 'z'; ++ch) {
		string cur = s;
		int res = 0;
		while (!same(cur)) {
			cur = apply(cur, ch);
			++res;
		}
		mn = min(mn, res);
	}
	return mn;
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

	while (read()) {
		cout << solve() << endl;

		break;
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


Measured memory_bytes: 256
length = int(input())
mochi = [int(input()) for i in range(length)]
sorted_mochi = sorted(mochi,reverse=True)
stage = 1
for i in range(0,length-1):
  if sorted_mochi[i] > sorted_mochi[i+1]:
    stage +=1
  else:
    pass
print(stage)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 1e5 + 5;

int a[N] , b[N] , c[N] , n;
long long ans , c1[N] , c2[N];

int main(void) {
	scanf("%d" , &n);
	for(int i = 1;i <= n;++ i) scanf("%d" , &a[i]);
	for(int i = 1;i <= n;++ i) scanf("%d" , &b[i]);
	for(int i = 1;i <= n;++ i) scanf("%d" , &c[i]);
	sort(a + 1 , a + n + 1); sort(b + 1 , b + n + 1); sort(c + 1 , c + n + 1);
	int it = 1;
	for(int i = 1;i <= n;++ i) {
		while(c[it] <= b[i] && it <= n) it ++;
		c2[i] = n - it + 1;
	}
	for(int i = n;i >= 1;-- i) c2[i] += c2[i + 1];
	it = 1;
	for(int i = 1;i <= n;++ i) {
		while(b[it] <= a[i] && it <= n) it ++;
		ans += c2[it];
	}
	printf("%lld\n" , ans);
}

Measured memory_bytes: 2176
def is_good(mid, key):
    S = list(map(int, str(mid)))
    N = len(S)
    dp = [[[0] * 11 for _ in range(2)] for _ in range(N + 1)]
    dp[1][1][10] = 1
    for k in range(1, S[0]):
        dp[1][1][k] = 1
    dp[1][0][S[0]] = 1
    for i in range(1, N):
        for k in range(1, 11):
            dp[i + 1][1][k] += dp[i][0][10] + dp[i][1][10]
        for is_less in range(2):
            for k in range(10):
                for l in range(k - 1, k + 2):
                    if not 0 <= l <= 9 or (not is_less and l > S[i]):
                        continue
                    dp[i + 1][is_less or l < S[i]][l] += dp[i][is_less][k]
    return sum(dp[N][0][k] + dp[N][1][k] for k in range(10)) >= key


def binary_search(bad, good, key):
    while good - bad > 1:
        mid = (bad + good) // 2
        if is_good(mid, key):
            good = mid
        else:
            bad = mid
    return good


K = int(input())
print(binary_search(0, 3234566667, K))


Measured memory_bytes: 9240
import collections
num = int(input())
hm = collections.Counter()
for _ in range(num):
  temp = input()
  hm[temp] += 1
most = hm.most_common(1)[0][1]
ret = []
for k, v in hm.items():
  if v == most:
    ret.append(k)
ret.sort()
for i in ret:
  print(i)

Measured memory_bytes: 32468
import numpy as np
n = int(input())
*a, = map(int, input().split())
x = 0
for i in range(n):
  if i % 2 == 0:
    x += a[i]
  else:
    x -= a[i]
ans = np.zeros(n,dtype='i8')
ans[0] = x//2

for j in range(n-1):
  ans[j+1] = a[j] - ans[j]

def db(y):
  return y*2
ans = db(ans)
print(' '.join(map(str,ans)))


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

struct UnionFind {
    vector<int> data;
    int sz;
    UnionFind(int sz) : data(sz, -1), sz(sz) { }
    bool unionSet(int x, int y) {
        if ((x = root(x)) == (y = root(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y]; data[y] = x; sz--;
        return true;
    }
    bool findSet(int x, int y) { return root(x) == root(y); }
    int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
    int size(int x) { return -data[root(x)]; }
    int size() { return sz; }
};

int main() {
    int n, k, l; cin >> n >> l >> k;
    UnionFind uf(n * 2);
    while (l--) {
        int p, q; cin >> p >> q; p--, q--;
        uf.unionSet(p * 2, q * 2);
    }
    while (k--) {
        int r, s; cin >> r >> s; r--, s--;
        uf.unionSet(r * 2 + 1, s * 2 + 1);
    }
    map<pair<int, int>, int> cnt;
    for (int i = 0; i < n; i++) cnt[{uf.root(i * 2), uf.root(i * 2 + 1)}]++;
    for (int i = 0; i < n; i++) {
        cout << cnt[{uf.root(i * 2), uf.root(i * 2 + 1)}] << " \n"[i == n - 1];
    }
    return 0;
}

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

int x, y;

int main() {
	cin >> x >> y;
	
	for (int a = 0; a <= x; a++) {
		int b = x - a;
		if (a * 2 + b * 4 == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3632
/*
 * atcoder/abc126_2nd/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

/*
 * 単純化して表が出たらスコア+1するとする
 * サイコロのそれぞれの目が出る確率1/N
 * K以上が出る確率 max(N-K+1, 0)/N
 * K未満が出る場合
 * K-1) 1/N * 1/2   ---- 一度表が出れば良い
 * K-2) 1/N * pow(1/2, 2)  ---- 二度表が出れば良い
 * K-M) 1/N * pow(1/2, M) ---- M回表
 *
 * 話を戻して表でスコアが2倍になるとすると
 * K-i) 1/N * pow(1/2, M) ---- K-iをM回2倍してK以上となる
 */
int N, K;
void solve() {
  cin >> N >> K;
  double total = max(N-K+1, 0)/(double)N;
  // cout << "k>=N) " << total << endl;
  for (int k=1; k<=min(K-1,N); k++) {
    int k_ = k;
    int count = 0;
    while (k_ < K) count++, k_ *= 2; // 何回2倍する必要があるか
    double d = 1/(double)N * pow(0.5, count);
    total += d;
    // cout << "k=" << k << ") " << d << endl;
  }
  cout << total << endl;
}
int main() {
  cout.precision(15);
  cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int N;
vector <int> G[100005];
int DP[2][100005];
void Read()
{
    cin >> N;
    for(int i = 1; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        ++x;++y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int node, int father)
{
    int sum = 0;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        DFS(neighb, node);
        sum += DP[1][neighb];
    }
    DP[1][node] = sum;
    for(int i = 0; i < G[node].size(); i++)
    {
        int neighb = G[node][i];
        if(neighb == father)
            continue;
        if(DP[0][neighb] == 0)
            DP[1][node] = min(DP[1][node], sum - DP[1][neighb]);
    }
    DP[1][node] = max(DP[1][node], 1);
    /*if(DP[1][node] > 0)
        DP[0][node] = -1;
    else
        DP[0][node] = 0;*/
    if(G[node].size() == 1)
    {
        DP[0][node] = 0;
        DP[1][node] = 1;
    }
    else
    {
        if(G[node].size() == 2)
        {
            if(father == G[node][0])
                DP[0][node] = DP[0][G[node][1]];
            else
                DP[0][node] = DP[0][G[node][0]];
        }
        else
            DP[0][node] = -1;
    }
}
int main()
{
    Read();
    int root = 0;
    for(int i = 1; i <= N; i++)
    {
        if(G[i].size() > 2)
            root = i;
    }
    if(root == 0)
        cout << "1\n";
    else
    {
        DFS(root, 0);
        cout << DP[1][root] << "\n";
    }
    return 0;
}


Measured memory_bytes: 11776
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define fi first
#define se second
#define mp make_pair
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define MOD llong(1e9+7)
#define MAX int(2 * 1e5 +5)
#define debug(x)  cout << #x << " = " << (x) << endl;
#define pi acos(-1.0)
#define int llong
#define INF llong(1e18 + 3)
template<class T> bool chmax(T &a,  T b) {if(a<b){a=b; return 1;} return 0;}
template<class T> bool chmin(T &a,  T b) {if(a>b){a=b; return 1;} return 0;}
bool Add(int &a,int b){a = (a + b) % MOD;}
void myprint(int* A,int A_num){
   REP(i,A_num) cout << A[i] << " ";
   cout << endl;
}

signed main(){
    int a,b,c,d;

    cin >> a >> b >> c >> d;
    cout << c - a << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, M;
    cin >> N >> M;
    int cntAC = 0, cntWA = 0;
    vector<int> isAC(N+1, 0);
    vector<int> WA(N+1, 0);
    for (int i = 0; i < M; i++) {
        int num;
        string S;
        cin >> num >> S;
        if (isAC[num]) continue;
        if (S == "AC") {
            cntAC++;
            isAC[num] = 1;
            cntWA += WA[num];
        }
        else WA[num]++;
    }
    cout << cntAC << ' ' << cntWA << '\n';
}


Measured memory_bytes: 4032
//#pragma GCC optimize("Ofast")
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define bql 2147483647
#define ll long long
#define ull unsigned long long
using namespace std::tr1;
using namespace std;
const int N=2e5+5;
const int mod=998244353;
const int fx[5]={0,-1,0,1,0};
const int fy[5]={0,0,-1,0,1};
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=(x<<3)+(x<<1);x+=(ch-'0');ch=getchar();}
    return x*f;
}

void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x>10) write(x/10);
    putchar(x%10+'0');
}

ll n,k,a[N];
ll f(ll mid)
{
	ll ret=0;
	for (int i=0;i<n;i++)
  {
		if (a[i]==0)
    {
			if (mid>=0)
          ret+=n-1;
			continue;
		}
		if (a[i]<0)
    {
			ll target=mid/a[i];
			if (target*a[i]>mid)
          target++;
			int idx=lower_bound(a,a+n,target)-a;
			ret+=n-idx;
			if (idx<=i)
          ret-=1;
		}
		else
    {
			ll target=mid/a[i];
			if (target*a[i]>mid)
          target--;
			int idx=upper_bound(a,a+n,target)-a-1;
			if (idx<0)
          continue;
			ret+=idx+1;
			if (idx>=i)
          ret-=1;
		}
	}
	return ret/2;
}

int main()
{
	cin>>n>>k;
	for (int i=0;i<n;i++)
      cin>>a[i];
	sort(a,a+n);
	ll lo=-1e18,hi=1e18;
	while (lo<hi)
  {
		ll mid=lo+(hi-lo)/2;
		if (f(mid)>=k)
        hi=mid;
		else
        lo=mid+1;
	}
	cout<<lo<<endl;
	return 0;
}


Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String []args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s.equals("ABC"))
            System.out.println("ARC");
        else
            if(s.equals("ARC"))
                System.out.println("ABC");
    }
}


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

// for loop
#define rep(i,a,n) for(int i=(a);i<(n);++i)
#define repe(i,a,n) for(int i=(a);i<=(n);++i)
#define rrep(i,n,a) for(int i=(n);n>(a);--i)
#define rrepe(i,n,a) for(int i=(n);n>=(a);--i)

// abbreviati
#define PB(v) push_back(v)
#define MP make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ENDL << "\n"

using ll = long long;
using P = pair<int,int>;
using itn = int;

// constant
const int INF = 1<<30;
const ll INFLL = 1LL << 60;
const ll MOD = 1000000007;
const long double PI =(acos(-1));

/***Snippet***************************************************
ifelse, isprime, torad, todeg, lcm, bfs,chmin,chmax
**************************************************************/

// adjacency list
vector<int> to[100005];

// Graph
using Graph = vector<vector<int>>;

// Grid
int H,W;
vector<vector<int>> field;

// 4方向への移動ベクトル
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector<int> p(n);
    rep(i,0,n){
        cin >> p[i];
    }

    int cnt=0;
    rep(i,1,n-1){
        if(p[i-1] < p[i] && p[i] < p[i+1]) cnt++;
        if(p[i-1] > p[i] && p[i] > p[i+1]) cnt++;
    }
    cout << cnt ENDL;
    return 0;
}

Measured memory_bytes: 5940
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const ll MOD = 1000000007;
// const int INF = 2000000000;

vector<ll> divisor(ll n) {
  vector<ll> res;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      res.push_back(i);
      if (i != n / i) {
        res.push_back(n / i);
      }
    }
  }
  return res;
}

ll N;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N;
  vector<ll> ds = divisor(N);

  ll ans = 0;
  for (auto &e : ds) {
    if (e == 1 || e == 2) {
      continue;
    }

    ll d = N / e; // 商 かつ あまり
    if ((N - d) % d == 0) {
      ll m = (N - d) / d;
      if ((N / m) == (N % m)) {
        ans += m;
      }
    }
  }

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

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

int main() {
	long long N,M;cin>>N>>M;

	vector<pair<long long,long long>>sorted;
	for (int i = 0; i < N; i++)
	{
		long long a,b;cin>>a>>b;
		sorted.push_back(make_pair(a,b));
	}
	sort(sorted.begin(), sorted.end());

	long long ans = 0;
	long long a = 0;
	for(int i=0;i<sorted.size();i++)
	{
		if(sorted[i].second + a < M)
		{
			ans += sorted[i].first * sorted[i].second;
			a += sorted[i].second;
		}
		else
		{
			ans += sorted[i].first * (M - a);
			break;
		}
	}

	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>

ll n, x, y, d, dl[110000], f, ans = 0;
bool used[110000];
vector<ll> g[110000];
bool dfs(ll a) {
	used[a] = true;
	if (a == x) {
		dl[0] = a;
		return true;
	}
	REP(i, g[a].size()) {
		if (!used[g[a][i]]) {
			if (dfs(g[a][i])) {
				d++;
				dl[d] = a;
				return true;
			}
		}
	}
	return false;
}

void dfs2(ll a, ll b) {
	//cout << a + 1 <<" a " << endl;
	used[a] = true;
	if (b == (d - 1) / 2) return;
	REP(i, g[a].size()) {
		if (g[a][i] == dl[b - 1]) dfs2(g[a][i], b - 1);
	}
}
void dfs3(ll a, ll b) {
	used[a] = true;
	ans = max(ans, b);
	REP(i, g[a].size()) {
		if (!used[g[a][i]]) dfs3(g[a][i], b + 1);
	}
}


int main() {
	cin >> n >> x >> y;
	x--;
	y--;
	REP(i, n - 1) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(y);
	REP(i, 110000)used[i] = false;
	f = dl[(d - 1) / 2];
	//cout << d << " d" << endl;
	dfs2(y, d);
	dfs3(f, 0);
	if (d % 2 == 0)ans++;
	cout << (d - 1) / 2 + ans << endl;
}



Measured memory_bytes: 9856
using static System.Math;
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var L = int.Parse(line[0]);
        var n = int.Parse(line[1]);
        var s = Console.ReadLine().Trim();
        var count = 0;
        for (int i = 0; i < L -1; i++)
            if (s[i] == 'o' && s[i + 1] == 'o') count++;
        var ans = ((long)Pow(2, n) - 1) * 3 * count + L;
        Console.WriteLine(ans);
    }
}



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

int check(int);

int a[8],b[8];
int c1[15],c2[15];
int chess[8][8];

int main(){
  int i,j,k,r,c;

  for(i=0;i<8;i++){
    a[i]=0;
    b[i]=0;
  }

  for(i=0;i<15;i++){
    c1[i]=0;
    c2[i]=0;
  }

  for(i=0;i<8;i++){

    for(j=0;j<8;j++){
      chess[i][j]=0;
    }

  }

  scanf("%d",&k);
  for(i=0;i<k;i++){
    scanf("%d%d",&r,&c);
    chess[r][c]=1;
  }

  check(0);

  return 0;
}

int check(int x){
  int y,i,j;

  if(x==8){

    for(i=0;i<8;i++){

      for(j=0;j<8;j++){
        if(chess[i][j]==1){
	  if(a[i]!=j) return;
        }

      }

    }

    for(i=0;i<8;i++){

      for(j=0;j<8;j++){

        if(a[i]==j) printf("Q");
        else printf(".");
      }
      printf("\n");
    }
    return 0;
  }

  for(y=0;y<8;y++){

    if(b[y]==1 || c1[x+y]==1 || c2[x-y+7]==1){
      continue;
    }

    a[x]=y;
    b[y]=1;
    c1[x+y]=1;
    c2[x-y+7]=1;
    check(x+1);
    a[x]=0;
    b[y]=0;
    c1[x+y]=0;
    c2[x-y+7]=0;
  }
  return 0;
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s == "ABC"){
    	cout << "ARC" << endl;
    }else{
    	cout << "ABC" <<endl;
    }
    return 0;
}


Measured memory_bytes: 3648
#include<stdio.h>

#define K 10000

int A[20000001];
int B[20000001];
int C[K];

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

  scanf("%d",&n);

  for(i=0;i<K;i++) C[i]=0;

  for(j=1;j<=n;j++){
    scanf("%d",&A[j]);
    C[A[j]]++;
  }

  for(i=1;i<=K;i++) C[i]=C[i]+C[i-1];
  
  for(j=n;1<=j;j--){
    B[C[A[j]]]=A[j];
    C[A[j]]--;
  }

  for(i=1;i<=n;i++){
    if(i!=1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
    return 0;
}

Measured memory_bytes: 16984
N = int(input())
A, B, C = [list(map(int, input().split())) for _ in range(3)]

satisfaction = sum(B)

before_i = float("Inf")
for i in range(N - 1):
    if A[i] + 1 == A[i+1]:
        satisfaction += C[A[i] - 1]
        
print(satisfaction)

Measured memory_bytes: 3060
N, Y = map(int, input().split())
flag = False
res = []
for x in range(N + 1):
    for y in range(N + 1 -x):
        z = N - x -y
        sum_m = (10000*x) + (5000*y) + (1000*z)
        if sum_m == Y:
            flag = True
            res = [x, y, z]

if flag == False:
    print(-1, " ", -1, " ", -1)
else:
    print(res[0]," " ,res[1]," ", res[2])

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

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 ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}

int main(){
  ll n, m;
  cin >> n >> m;
  vector<ll> ac_list(n,0);
  vector<ll> wa_conter(n,0);
  ll score = 0;
  ll error = 0;
  rep(i,m){
    ll p;
    string s;
    cin >> p >> s;
    p--;
    if(s=="AC"){
      if(!ac_list[p]){
        score++;
        error += wa_conter[p];
        ac_list[p] = 1;
      }
    }else{
      wa_conter[p]++;
    }
  }

  cout << score << " " << error << endl;

  return 0;
}

Measured memory_bytes: 1792
package main

import "fmt"

var n, m int
var arr []int
var par []int

func main() {
	fmt.Scan(&n, &m)
	arr = make([]int, n)
	par = make([]int, n)
	for i := 0; i < n; i++ {
		var j int
		fmt.Scan(&j)
		arr[i] = j - 1
		par[i] = i
	}
	for i := 0; i < m; i++ {
		var a, b int
		fmt.Scan(&a, &b)
		union(a-1, b-1)
	}
	ans := 0
	for i := 0; i < n; i++ {
		ra, rb := root(i), root(arr[i])
		if ra == rb {
			ans += 1
		}
	}
	fmt.Println(ans)
}

func root(x int) int {
	if x == par[x] {
		return x
	}
	xx := root(par[x])
	par[x] = xx
	return xx
}

func union(a, b int) {
	if a > b {
		a, b = b, a
	}
	ra, rb := root(a), root(b)
	if ra != rb {
		par[ra] = rb
	}
}


Measured memory_bytes: 5504
n = int(input())
a = [ int(x) for x in input().split() ]

ans1, ans2 = 0, 0
sum_v = 0

# 最初が負の時
for i in range(len(a)):
    sum_v += a[i]
    # sumv := minus
    if i % 2 == 0:
        if sum_v >= 0:
            ans1 += abs(sum_v)+1
            sum_v = -1
    # sumv := plus
    else:
        if sum_v <= 0:
            ans1 += abs(sum_v)+1
            sum_v = 1

sum_v = 0

# 最初がplus
for i in range(len(a)):
    sum_v += a[i]
    # sumv := minus
    if i % 2 == 0:
        if sum_v <= 0:
            ans2 += abs(sum_v)+1
            sum_v = 1
    # sumv := plus
    else:
        if sum_v >= 0:
            ans2 += abs(sum_v)+1
            sum_v = -1

print (min(ans1, ans2))


Measured memory_bytes: 14644
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(s[i]==','){
      cout << ' ';
    }else{
      cout << s[i];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000)


def dfs(x,graph,seen,nxt):
    seen[x]=1
    if x in nxt:
        nxt.remove(x)
    nxt+=[y for y in graph[x] if not seen[y] and y not in nxt]
    while nxt :
        dfs(nxt.pop(-1),graph,seen,nxt)


def island_count(w,h):
    lst=[list(map(int,input().split())) for _ in range(h)]
    graph={}
    for i in range(h):
        for j in range(w):
            if not lst[i][j] : continue
            graph[(i,j)]=[]
            for k in range(-1,2):
                for l in range(-1,2):
                    if k==0 and l==0 : continue
                    if i+k<0 or j+l<0 : continue
                    try:
                        if lst[i+k][j+l]:
                            graph[(i,j)].append((i+k,j+l))
                    except IndexError:
                        continue
    #print(graph)
    seen={x:0 for x in graph}
    sm=0
    nxt=[]
    for x in seen:
        if seen[x] : continue
        if not seen[x]:
            dfs(x,graph,seen,nxt)
            sm+=1

    print(sm)






while 1 :
    w,h=map(int,input().split())
    if (w,h)==(0,0) : break
    island_count(w,h)


Measured memory_bytes: 10360
m, f = 0, 0
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(40, -1, -1):
  _sum = sum(map(lambda x: (x >> i) & 1, a))
  s = 0 if _sum > n//2 else 1 << i
  if not s or s > k - m:
    f += _sum << i
  else:
    f += n-_sum << i
    m += s
print(f)

Measured memory_bytes: 14620
import math

a = input()
hour_length, minute_length, hours, minutes = [int(s) for s in a.split()]

hour_degrees = (hours + minutes / 60) * 360 / 12
hour_radians = math.radians(hour_degrees)
hour_x, hour_y = hour_length * math.sin(hour_radians), hour_length * math.cos(hour_radians)


minute_degrees = minutes * 360 / 60
minute_radians = math.radians(minute_degrees)
minute_x, minute_y = minute_length * math.sin(minute_radians), minute_length * math.cos(minute_radians)

distance = math.sqrt((hour_x - minute_x) ** 2 + (hour_y - minute_y) ** 2)
print(distance)

Measured memory_bytes: 9592
#include<stdio.h>
int S(long long int X,long long int Y)
{
	int num = 0;
	while (X <= Y)
	{
		num++;
		X *= 2;
	}
	return num;
}
int main()
{
	long long int X,Y;
	scanf("%lld %lld", &X, &Y);
	printf("%d", S(X,Y));
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define lli long long
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define rep0(i,j) for(int i=0;i<j;i++)
#define rep1(i,j) for(int i=1;i<=j;i++)
#define rep0d(i,j) for(int i=j-1;i>=0;i--)
#define MOD 1000000007
 
using namespace std;
 
bool cmpf(const pair<lli, lli> left, const pair<lli, lli> right) {
  	return left.first< right.first;
}
bool cmps(const pair<lli, lli> left, const pair<lli, lli> right) {
  	return left.second < right.second;
}
 
void dfs(lli ed, lli num, vector<map<lli,lli>>& vec){
    lli n=1;
    for(auto e: vec[num]){
        if(n == ed)n++;
        if(e.second != -1)continue;
        vec[num][e.first] = n;
        vec[e.first][num] = n;   
        dfs(n, e.first, vec);
        n++;
    }
}
 
lli gcd(lli a, lli b){
    if(a < b)return gcd(b, a);
    lli temp;
    while((temp = a%b)){
        a=b;
        b=temp;
    }
    return b;
}

struct nCr{
  vector<lli> f, rf;
  lli count=0;
  nCr(lli num): f(num), rf(num){
      count = num;
      f[0] = 1;
      rep1(i, num) f[i] = (f[i - 1] * i) % MOD;
      rep0(i, num+1) rf[i] = inv(f[i]);
  }
    
  lli inv(lli x) {
      lli res = 1;
      lli k = MOD - 2;
      lli y = x;
      while (k) {
          if (k & 1) res = (res * y) % MOD;
          y = (y * y) % MOD;
          k /= 2;
      }
      return res;
  }
  lli C(lli n, lli k) {
      lli a = f[n];
      lli b = rf[n-k];
      lli c = rf[k];
   
      lli bc = (b * c) % MOD;
   
      return (a * bc) % MOD;
  }
};

struct UF{
    vector<int> par,size;

    UF(int N) : par(N), size(N, 1){
        rep0(i,N)par[i] = i;
    }

    int root(int x){
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y){
        int rx = root(x);
        int ry = root(y);
        if(rx == ry) return;
        par[rx] = ry;
        size[rx] += size[ry];
    }

    bool same(int x, int y){
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int getSize(int x){
        return size[x];
    }
};
int main(){
  queue<string> q;
  int k;
  cin >> k;
  for(int i=0;i<10;i++) q.push(to_string(i));
  int s=0;
  string num;
  while(s!=k){
    num = q.front();
    q.pop();
    
    if(num.back()=='0'){
      q.push(num+'0');
      q.push(num+'1');
    }
    else if(num.back()=='9'){
      q.push(num+'8');
      q.push(num+'9');
    }else{
      q.push(num + (char)(num.back()-1));
      q.push(num + num.back());
      q.push(num + (char)(num.back()+1));
    }
    if(num[0]!='0')s++;
  }
  cout << num;
}


Measured memory_bytes: 14976
#include "bits/stdc++.h"
using namespace std;

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	while (true) {
		string s;
		cin >> s;

		if (s == "-") break;

		int n;
		cin >> n;

		rep(i, n) {
			int m;
			cin >> m;

			rep(j, m) {
				s += s[0];
				s.erase(0, 1);

			}
		}
		cout << s << endl;
	}
}


Measured memory_bytes: 3216
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A.reverse()

def binary_search(lis,i):
    ng = 0
    ok = len(lis)-1
    while abs(ok-ng) > 1:
        #print(ok,ng)
        mid = (ok + ng) // 2
        if lis[mid] > i:
            ok = mid
        else:
            ng = mid
    return ok

#print(A)
d = [-1,1000000007]
for i in range(N):
    p = binary_search(d,A[i])
    if p == len(d)-1:
        d.append(A[i])
        d[-1],d[-2] = d[-2],d[-1]
    else:
        d[p] = A[i]
    #print(p)
    #print(d)
print(len(d)-2)


Measured memory_bytes: 83916
#include<iostream>
#include<cmath>
#include<vector>
#include<bitset>
#include<bitset>
#include<string>
#include<utility>
#include<queue>

using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    for(int i=1;i<=1000;i++){
        if((i*8/100==a) && (i*10/100==b)){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}

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

int solve(int a, int b, int c, int k) {
	int ans = 0;
	while (k--) {
		if (a != 0) {
			ans += 1;
			a--;
		}
		else if (b != 0) {
			b--;
		}
		else if(c != 0) {
			ans -= 1;
			c--;
		} 
	}
	return ans;
}

int main() {
	vector<int> vars(4, 0);
	for (int i=0; i<4; i++) {
		cin >> vars[i];
	}
	cout << solve(vars[0], vars[1], vars[2], vars[3]);
	return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define all(x) x.begin(),x.end()

#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion

int main()
{
	int n, m, l; cin >> n >> m >> l;
	ll INF = 1e10;
	vector<vector<ll>> g(n, vector<ll>(n, INF));
	rep(i, n)g[i][i] = 0;
	rep(i, m)
	{
		int a, b; ll c; cin >> a >> b >> c;
		--a, --b;
		g[a][b] = c;
		g[b][a] = c;
	}
	rep(k, n)rep(i, n)rep(j, n)chmin(g[i][j], g[i][k] + g[k][j]);
	vector<vector<ll>> x(n, vector<ll>(n, INF));
	rep(i, n)rep(j, n)
	{
		if (g[i][j] <= l)x[i][j] = 1;
		x[i][i] = 0;
	}
	rep(k, n)rep(i, n)rep(j, n)chmin(x[i][j], x[i][k] + x[k][j]);

	int q; cin >> q;
	rep(i, q)
	{
		int s, t; cin >> s >> t;
		--s, --t;
		if (x[s][t] == INF)cout << -1 << endl;
		else cout << x[s][t] - 1 << endl;
	}
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;  //これで"std::cout"が"cout"と書ける

//MACRO
typedef long long ll;                  //64bit以上を表現可能な型
#define INF 100000000                  //ほぼ無限
#define itn int                        //タイポ対策
#define ALL(x) (x).begin(), (x).end()  //sort(all(x))などとする
#define SZ(x) ((int)(x).size())        //size()簡略化
//repetition
#define FOR(i, p, b) for (int i = (p); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define repR(i, n) for (int i = n; i >= 0; i--)
//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \<< " " << __FILE__ << endl;
template <class T>
bool chMAX(T &a, const T &b) {  //aよりbが大きければaに代入
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chMIN(T &a, const T &b) {  //aよりbが小さければaに代入
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

//
//
//

int main() {
    int h, w;
    bool flag = false;
    cin >> h >> w;

    bool H[h] = {false};
    bool W[w] = {false};

    string a[h];

    rep(i, h) {
        cin >> a[i];
    }

    rep(i, h) {
        rep(j, w) {
            if (a[i][j] == '#') {
                H[i] = true;
                W[j] = true;
            }
        }
    }

    rep(i, h) {
        if (H[i]) {
            rep(j, w) {
                if (W[j]) {
                    cout << a[i][j];
                }
            }
            cout << endl;
        }
    }

}

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

int main()
{
	int n, check, cnt = 0, arr[8] = { 0, 9, 0, 900, 0, 90000 };

	scanf("%d", &n);

	for (int i = 1; i <= 6; i++)
	{
		check = (int)pow(10.0, i);

		if (n < check)
		{
			check /= 10;

			if(i % 2 == 1)
				cnt += n - check + 1;

			break;
		}
		else
			cnt += arr[i];
	}

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

	return 0;
}

Measured memory_bytes: 256
let _ =
	let n = Scanf.scanf "%d\n" (fun n -> n) in
    (
    match n with
    | 1 -> "Hello World"
    | 2 ->
    	let a, b = Scanf.scanf "%d\n%d\n" (fun a b -> a, b) in
        string_of_int @@ a + b
    | _ -> failwith "hoge"
    ) |> print_string

Measured memory_bytes: 384
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] lbl=br.readLine().split(" ");
		Dice d1=new Dice(lbl);
		int n=Integer.parseInt(br.readLine());
		for (int i=0;i<n;i++){
			String[] a=br.readLine().split(" ");
			boolean fb=true;
			while(!d1.getTop().equals(a[0])){
				if(fb){
					lbl=d1.throwDice('S');
					fb=false;
				}else{
					lbl=d1.throwDice('E');
					fb=true;
				}
			}
			while(!(d1.getTop().equals(a[0])&&d1.getFront().equals(a[1]))){
				lbl=d1.throwDice('S');
				lbl=d1.throwDice('E');
				lbl=d1.throwDice('N');
			}
			System.out.println(d1.getRight());
		}
	}
	
	static class Dice {
		private String[] label;
		public Dice(String[] num){
			this.label=num;
		}
		public String[] throwDice(char ori){
			String t;
			switch(ori) {
	        case 'E':
	            t=label[0];label[0]=label[3];label[3]=label[5];label[5]=label[2];label[2]=t;
	            break;
	        case 'N':
	            t=label[0];label[0]=label[1];label[1]=label[5];label[5]=label[4];label[4]=t;
	            break;
	        case 'S':
	            t=label[0];label[0]=label[4];label[4]=label[5];label[5]=label[1];label[1]=t;
	            break;
	        case 'W':
	            t=label[0];label[0]=label[2];label[2]=label[5];label[5]=label[3];label[3]=t;
	            break;
			}
			return label;
		}
		public String getTop() {
	        return label[0];
	    }
		public String getFront() {
	        return label[1];
	    }
		public String getRight() {
	        return label[2];
	    }
	}
}

Measured memory_bytes: 16928