akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef long long ll;
typedef pair<int,int> P;

int s[10];

int main(void){
    int n,m;
    cin>>n>>m;
    if(m==0){
        if(n==1)cout<<0<<endl;
        if(n==2)cout<<10<<endl;
        if(n==3)cout<<100<<endl;
        return 0;
    }
    for(int i=0;i<10;i++)s[i]=-1;
    bool flag = false;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        if(x!=1){
            if(s[x]!=-1){
                if(s[x]!=y)flag=true;
            }
            else s[x]=y;
        }
        else{
            if(s[x]!=-1){
                if(s[x]!=y)flag=true;
            }
            else{
                if(n==1){
                    s[x]=y;
                }
                else{
                    if(y==0)flag=true;
                    else s[x]=y;
                }
            }
        }
    }
    if(flag){
        cout<<-1<<endl;
        return 0;
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(i==1){
            if(s[i]==-1)ans+=(int)pow(10,n-1);
            else ans+=(int)pow(10,n-1)*s[i];
        }
        else{
            if(s[i]==-1)ans+=0;
            else ans+=(int)pow(10,n-i)*s[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
# AOJ 0501: Data Conversion
# Python3 2018.6.29 bal4u

while True:
	n = int(input())
	if n == 0: break
	tbl = {}
	for i in range(n):
		a, b = input().split()
		tbl[a] = b
	ans = ''
	m = int(input())
	for i in range(m):
		a = input()[0]
		if a in tbl: ans += tbl[a]
		else: ans += a
	print(ans)


Measured memory_bytes: 5712
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int main(){
    int n;
    cin >> n;
    for(int i=1;i<=9;i++){
        for(int j =1;j<=9;j++){
            if(i*j==n){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
return 0;
}

Measured memory_bytes: 256
from copy import copy

def change(n,a):
    temp = a[n]
    a[n] = a[n+1]
    a[n+1] = temp
    return a

while(1):
    st = 1
    n = int(input())
    if n == 0:
        break
    elif n == 1:
        st = 0
    m_ = int(input())
    m = m_ -1
    w = int(input())
    d = int(input())
    b = []
    forward = []
    for i in range(d):
        b.append([int(i) for i in list(input())])
    if st == 0:
        print("0")
        continue
    a = [i for i in range(n)]
    for i in range(d):
        for j in range(n-1):
            if b[i][j] == 1:
                a = change(j,a)
        forward.append(copy(a))
    if a[w-1] == m:
        print(0)
    else:
        state = True
        pivot = a[w-1]
        for i in range(d):
            f = forward[i]
            x = f.index(m)
            y = f.index(pivot)
            if y - x == 1:
                if b[i][x] == 0 and (x-1 < 0 or b[i][x-1] == 0) and (x+1 > n-2 or b[i][x+1] == 0):
                    print(i+1,x+1)
                    state = False
                    break
            elif x - y == 1:
                if b[i][y] == 0 and (y-1 < 0 or b[i][y-1] == 0) and (y+1 > n-2 or b[i][y+1] == 0):
                    print(i+1,y+1)
                    state = False
                    break
        if state:
            print(1)




Measured memory_bytes: 6352
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define DUMP(x) cout << #x << " = " << (x) << endl
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

int main() {
  int n, k; cin >> n >> k;
  VI a(n);
  REP(i, n) {
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  VI ans;
  REP(i, n) {
    if (ans.empty() or a[ans.back()] != a[i]) {
      ans.push_back(i);
    }
  }
  VI ansn;
  ans.push_back(n);
  FOR(i, 1, ans.size()) {
    ansn.push_back(ans[i] - ans[i - 1]);
  }
  sort(ansn.begin(), ansn.end());
  if (ansn.size() <= k) {
    cout << 0 << endl;
  } else {
    int ans = 0;
    for (int i = 0; i < ansn.size() - k; ++i) {
      ans += ansn[i];
    }
    cout << ans << endl;
  }
  return 0;
}

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

int main() {
    
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            std::cout << i << "x" << j << "=" << i*j << std::endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3076
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N;
int A[100000];
int C[16];
int D[1<<15];
vector<int> Q[100010];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N-1) {
    int u, v, a;
    cin >> u >> v >> a;
    A[u] ^= a;
    A[v] ^= a;
  }
  rep(i, N) C[A[i]]++;
  int sum = 0, st = 0;
  for (int i=1; i<16; i++) {
    sum += C[i]/2;
    if (C[i]%2) st |= 1<<(i-1);
  }
  rep(i, 1<<15) D[i] = INF;
  Q[0].pb(st);
  D[st] = 0;
  for (int v=0; v<=100000; v++) {
    for (int S : Q[v]) {
      if (D[S] < v) continue;
      rep(i, 15) if ((S>>i)&1) {
        rep(j, i) if ((S>>j)&1) {
          for (int z=1; z<=15; z++) {
            int i2 = ((i+1)^z)-1, j2 = ((j+1)^z)-1;
            int nS = S^(1<<i)^(1<<j), cost = 1;
            if (i2 != -1) nS ^= (1<<i2), cost += (S>>i2)&1;
            if (j2 != -1) nS ^= (1<<j2), cost += (S>>j2)&1;
            if (D[nS] > D[S]+cost) D[nS] = D[S]+cost, Q[v+cost].pb(nS);
          }
        }
      }
    }
    Q[v].clear();
  }
  cout << sum + D[0] << "\n";
  return 0;
}


Measured memory_bytes: 3200
c[100],n,k,a,b,x,y,M,m;Z(){for(x=a=0;a<=n-k;a++){for(y=1,b=0;b<k;b++)y*=c[a+b];if(x<y)x=y;}}
main(i,j,t){for(;scanf("%d%d",&n,&k),n;printf("%d\n",m-M)){
	for(i=0;i<n;i++)scanf("%d",c+i);
	Z();M=x;
	for(m=i=0;i<n;i++)for(j=i+1;j<n;j++){
		t=c[i],c[i]=c[j],c[j]=t;
		Z();m=m>x?m:x;
		t=c[i],c[i]=c[j],c[j]=t;
	}
}exit(0);}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define int     long long
#define F       first
#define S       second
#define _READ   freopen("input.txt","r", stdin);
#define _FAST   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
void solve()
{
    int n,k,d;
    cin>>n>>k;
    vector<int> mp(n+1,0);
    for(int i=0;i<k;i++)
    {
        cin>>d;
        for(int j=0;j<d;j++)
        {
            int input;
            cin>>input;
            mp[input]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(mp[i]==0)
            ++ans;
    }
    cout<<ans<<"\n";
}
int32_t main()
{
    _FAST  
    int t;
    t=1;
    //cin>>t;
    while(t--)
        solve();
    
    return 0;
}

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

int getmin(int N, string S){
    int i, count;
    // i-1番目の文字
    string last;
    count = 0;
    last = S.substr(0, 1);
    for(i=1; i<N; i++){
        if(last==S.substr(i, 1)){
            count++;
            last = to_string(1-stoi(S.substr(i, 1)));
        }else{
            last = S.substr(i, 1);
        }
    }
    return count;
}

int main(void){
    int N;
    string S;
    cin >> S;
    N = S.length();
    int ans1, ans2;
    ans1 = getmin(N, S);
    // 始めの文字を入れかえる
    int s;
    s = 1-stoi(S.substr(0, 1));
    S.replace(0, 1, to_string(s));
    ans2 = getmin(N, S)+1;
    cout << min(ans1, ans2) << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>
#include <set>
#include <map>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e933
#define INFL 1e18
#define MOD 1e9+7
#define pb push_back
#define MP make_pair
typedef long long int ll;
typedef std::pair<int,int> pii;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int temp[3]={1,5,10};

using namespace std;

int main() {
    //ペアに突っ込んでソートするだけで時間順。時間が重複した場合は１つしか出力しないので、uniqueをして重複を消す
    int n,m;
    cin>>n;
    vector<pair<int,int>> a(n);
    rep(i,0,n)cin>>a[i].fi>>a[i].se;
    cin>>m;
    rep(i,0,m){
        int x,y;
        cin>>x>>y;
        a.pb(MP(x,y));
    }
    Sort(a);
    a.erase(unique(all(a)),a.end());
    rep(i,0,a.size()){
        if(i)cout<<" ";
        printf("%d:%02d",a[i].fi,a[i].se);
    }
    cout<<endl;
    return 0;
}



Measured memory_bytes: 3220
import java.util.*;
import java.io.*;
import java.math.BigInteger;
 
public class Main {
	public static int count = 0;
	public static int cnd = 0;
	public static void permutation(String q, String ans, String p){
        if(q.length() <= 1) {
			count++;
			if(p.equals(ans+q)){
				cnd = count;
			}
        }
        
        else {
            for (int i = 0; i < q.length(); i++) {
                permutation(q.substring(0, i) + q.substring(i + 1),
                        ans + q.charAt(i), p);
            }
        }
    }
	
	public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	int N = s.nextInt();
	String a = "";
	String b = "";

	for(int i = 0; i < N; i++){
		a = a + s.next();
	}
	for(int i = 0; i < N; i++){
		b = b + s.next();
	}
	String first = "";
	for(int i = 1; i <= N; i++){
		first = first + String.valueOf(i);
	}
	
	int countA = 0;
	int countB = 0;
	permutation(first, "", a);
	countA = cnd;
	count = 0;
	permutation(first, "", b);
	countB = cnd;

	System.out.println(Math.abs(countA-countB));
    
  }
}

Measured memory_bytes: 59744
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i <(n); i++)
using namespace std;
using ll = long long;
const ll MOD = 2019;

int main()
{
    ll l, r;
    cin >> l >> r;

    ll ans = 2018;
    for (ll i = l; i <= min(r, l + 2019); i ++)
    for (ll j = i + 1; j <= min(r, l + 2019); j++)
        ans = min(ans, (i * j) % MOD);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
//print a Rectangle

#include<stdio.h>

int main()
{
	int i,j,k,a[100][2],count;

	i=0;	

	while(1){			//a[i][0]:hight a[i][1]:wide

		start:
		scanf("%d %d",&a[i][0],&a[i][1]);
		if ( a[i][0]>300 || a[i][1]>300)
			goto start;


		if(a[i][0]==0 && a[i][1]==0)
			break;

		i++;
	
	}
	
	count=i;
		
	for(i=0;i<count;i++){
		for(j=0;j<a[i][1];j++) printf("#");
		printf("\n");

		for(j=1;j<a[i][0]-1;j++){
			printf("#");
			for(k=1;k<a[i][1]-1;k++)
				printf(".");				
			printf("#");
			printf("\n");
		}
		for(j=0;j<a[i][1];j++) printf("#");
		printf("\n\n");
	}

	return 0;
}
	

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

using namespace std;

typedef long long ll;

#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define inn(x, y) int x,y;cin>>x>>y
#define innn(x, y, z) int x,y,z;cin>>x>>y>>z
#define bit(n) (1<<(n))

#define out(x) cout<<(x)<<endl;
#define err(x) cerr<<(x)<<endl;
#define errr(x,y) cerr<<(x)<<" "<<(y)<<endl;
#define errrr(x,y,z) cerr<<(x)<<" "<<(y)<<" "<<(z)<<endl;

#define rep(i,n) for (int i=0;i<(n);i++)
#define repp(i,n) for (int i=1;i<=(n);i++)
#define reppp(j, i, n) for (int j=i+1; j<n; j++)

#define lim5 200002
#define lim9 1000000002

#define deg(rad) (((rad)/2/M_PI)*360)
#define mid(min, max) ((min + max) / 2)

int main() {
	inn(n, k);
	ll h[lim5] = {};

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

	sort(h, h + n);

	ll cnt = 0;
	rep (i, n - k) {
		cnt += h[i];
	}

	out(cnt);

	return 0;
}


Measured memory_bytes: 1792
N,M = map(int,input().split())

l=[]
for i in range(N):
  a=list(map(int,input().split()))
  a.pop(0)
  l.append(a)
  
#print(l)

cmn=l[0]
for i in range(1,N):
  cmn = set(cmn) & set(l[i])
  
print(len(cmn))
  

Measured memory_bytes: 3060
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>

using namespace std;
using ll = long long int;

int main() {
  ll N, M, X;
  cin >> N >> M >> X;

  ll ans1 = 0;
  ll ans2 = 0;

  for (ll i = 0; i < M; i++) {
    ll ai;
    cin >> ai;
    if (X > ai) {
      ans1++;
    } else {
      ans2++;
    }
  }

  cout << min(ans1, ans2) << endl;
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

#define mk make_pair
#define inb push_back
#define X first
#define Y second
#define all(v) v.begin(), v.end()
#define sqr(x) (x) * (x)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#define y1 AYDARBOG
//continue break pop_back return

int solve();

int main()
{
    //ios_base::sync_with_stdio(0);
    //cin.tie(0);
#define TASK "lzss"
#ifndef _DEBUG
    //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
#endif
    solve();
#ifdef _DEBUG
    fprintf(stderr, "\nTIME: %.3f\n", TIME);
#endif
}

int solve()
{
    int n;
    scanf("%d", &n);
    vi a(n), ok(n);
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &a[i]);
        --a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == i)
        {
            if (i == 0)
            {
                swap(a[i + 1], a[i]);
                ++ans;
            }
            else
            {
                if (i == n - 1)
                {
                    swap(a[i], a[i - 1]);
                    ++ans;
                }
                else
                {
                    if (a[i - 1] == i)
                    {
                        swap(a[i], a[i + 1]);
                        ++ans;
                    }
                    else
                    {
                        if (a[i + 1] == i)
                        {
                            swap(a[i], a[i - 1]);
                            ++ans;
                        }
                        else
                        {
                            swap(a[i], a[i + 1]);
                            ++ans;
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

ll solve(ll h, ll w) {
    ll ret = w;
    for (int i = 1; i < w; i++) {
        vector <ll> v;
        v.push_back(i * h);
        ll y = h / 2, y1 = h - y;
        v.push_back(y * (w - i));
        v.push_back(y1 * (w - i));
        sort(v.begin(), v.end());
        ret = min(ret, v[2] - v[0]);
    }

    return ret;
}

int main() {
    ll h, w; cin >> h >> w;
    
    if (h % 3 == 0 or w % 3 == 0) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = solve(h, w);
    ans = min(ans, solve(w, h));

    cout << ans << endl;
}

Measured memory_bytes: 3604
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

h, w = map(int, input().split())
graph = np.array([list(map(int, input().split())) for _ in range(10)])

cost = floyd_warshall(graph)
cost = cost.astype(int)

arr = np.array([list(map(int, input().split())) for _ in range(h)])
arr = arr.flatten()

ans = 0
for x in arr:
    if x == -1:
        continue
    else:
        ans += cost[x][1]

print(ans)

Measured memory_bytes: 38632
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,sum=0;
    cin>>n;
    long long ar[n];
    for(int i=0;i<n;i++){
        cin>>ar[i];
        sum+=ar[i];
    }
    int avg=ceil((double)sum/(double)n),av=sum/n;
    long long ans=0,ans2=0;
    for(int i=0;i<n;i++){
        int d=abs(ar[i]-avg);
        int x=abs(ar[i]-av);
        ans+=(d*d);
        ans2+=(x*x);
    }
    cout<<min(ans,ans2)<<endl;
}


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

main(){
	int n;
	while(cin>>n){
		int ans = 0;
		for(int i=0; i<=9; ++i){
			for(int j=0; j<=9; ++j){
				for(int k=0; k<=9; ++k){
					for(int l=0; l<=9; ++l){
						if(i+j+k+l == n){
							ans++;
						}
					}
				}
			}
		}
		cout << ans << endl;
	}
}


Measured memory_bytes: 3100
#include<iostream>
#include<string>
#include<stack>/*** LIFO *** stack<type> var;
push(), top():to get data, pop():to remove, size(), empty() ***/
using namespace std;

#define Fp(I, STAT, END) for(int I = STAT; I < END; I++)
#define Fm(I, STAT, END) for(int I = STAT; I > END; I--)

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    if(A - B <= C){
        cout << C - A + B << endl;
    }else{
        cout << 0 << endl;
    }
}


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

int main()
{
    int N;
    cin >> N;
    vector<int> input(N);
    rep0(i, N)
    {
        cin >> input[i];
    }
    int res = 0;
    for (int i = 0; i < N - 2; i++)
    {
        if ((input[i] < input[i + 1] && input[i + 1] < input[i + 2]) || (input[i] > input[i + 1] && input[i + 1] > input[i + 2]))
        {
            res++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3608
using System;

class Plogram
{
    static void Main()
    {
        var line = Console.ReadLine().Split();
        int x1 = int.Parse(line[0]);
        int y1 = int.Parse(line[1]);
        int x2 = int.Parse(line[2]);
        int y2 = int.Parse(line[3]);

        int dx = x2 - x1;
        int dy = y2 - y1;

        int x3 = x2 - dy;
        int y3 = y2 + dx;
        int x4 = x1 - dy;
        int y4 = y1 + dx;

        Console.WriteLine("{0} {1} {2} {3}", x3, y3, x4, y4);

    }
}



Measured memory_bytes: 13268
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
    vector<int> W(10);
    vector<int> K(10);
    
    for(int i = 0; i < 10; i++) { cin >> W[i]; }
    for(int i = 0; i < 10; i++) { cin >> K[i]; }
    
    sort(W.begin(), W.end(), greater<int>());
    sort(K.begin(), K.end(), greater<int>());
    
    cout << W[0] + W[1] + W[2] << ' ' << K[0] + K[1] + K[2] << endl;
    
    return 0;
}

Measured memory_bytes: 1212
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}
int main(){
  int A,B; cin>>A>>B;
  if(A>2*B){
    cout<<A-2*B<<endl;
  }
  else cout<<0<<endl;
}

Measured memory_bytes: 256
def is_prime(a):
    if a == 2:
        return True
    for i in range(2, int(a**0.5)+2):
        if a%i == 0:
            return False
    return True

X = int(input())

for i in range(X, 100004):
    if is_prime(i):
        print(i)
        break

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
long double spi=3.1415926535898*5.00;
int x[200005],y[200005];
int u[200005],t[200005];
struct node
{int x,y;
}p[200005];
int cnt=0;
inline bool cmp(node a,node b)
{return a.x<b.x;}
int main (){
	int n,xs,xt,ys,yt,p1=1,p2=1,i,j;
	scanf ("%d%d%d%d",&xs,&ys,&xt,&yt);
	if (xs>xt) {xs*=(-1);xt*=(-1);p1=-1;}
        if (ys>yt) {ys*=(-1);yt*=(-1);p2=-1;}
	scanf ("%d",&n);
	for (i=1;i<=n;i++)
	{scanf ("%d%d",&x[i],&y[i]);x[i]*=p1;y[i]*=p2;}
	for (i=1;i<=n;i++)
	{if (x[i]>=xs&&x[i]<=xt&&y[i]>=ys&&y[i]<=yt)
	{p[++cnt].x=x[i];p[cnt].y=y[i];u[cnt]=y[i];}
	}
	sort(p+1,p+cnt+1,cmp);
	sort(u+1,u+cnt+1);
	for (i=1;i<=cnt;i++)
	{p[i].y=lower_bound(u+1,u+cnt+1,p[i].y)-u;}
	int ans=0;
	for (i=1;i<=cnt;i++)
	{int tp=0;
        for (j=p[i].y;j;j-=(j&(-j))) tp=max(tp,t[j]);
        tp++;
	if (tp>ans) {ans=tp;}
	for (j=p[i].y;j<=cnt;j+=(j&(-j))) t[j]=max(tp,t[j]);
	}
	long double res=(yt-ys+xt-xs)*100.00+ans*(spi-20.0);
	if (ans==min(yt-ys,xt-xs)+1) {res+=spi;}
	printf ("%.15Lf\n",res);
	return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=2001;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
int main()
{
    std::ios::sync_with_stdio(false);
    int n,sum=0;
    cin>>n;
    bitset<N*N> bi;
    bi[0]=1;
    for(int i=1;i<=n;i++)
    {
        /* Make sum=all input [ a1,a2,,,,aN]...  S^2N−1=sum. Now, set{ a1,sum-a1} , {  a2,sum-a2} ,,,,,,
        . let Xi be { a1,a2,..aN } and the remaining numbers (sum-a1 or sum-a2 or.  ...) are recorded as Yi; And make P=min (Xi,Yi), Q=max (Xi,Yi); available: P≤q,p+q=s2n−1=sum,
        from which P≤12sum,q≥12sum is introduced and can be P∈{S1,S2,⋯,S2N−1−1},Q∈{S2N−1,⋯,
        also min( of Xi's) and max(Yi's) difference is constant (for any arbitrary i/o) , it is the median /answer here .....
        */
        int c;
        cin>>c;
        sum+=c;

        /*cout<<" bef : "<<bi<<" | "<<(bi<<c)<<" -- ";/*here are 3 digits: "1 3 2", now to the ' 2 ' number,
        the front ' 1 ', ' 3 ' can be composed and has {0, 1, 3, 4}; So Bitset is now in a state of "11011"
        (the rightmost is No. 0), and if you do not use the number ' 2 ', the state is still "11011"; if the
        number of ' 2 ' is used, the status is "1101100" (i.e., previously available and all +2), and finally
        the two States or (∣) are put up , You get the new state "11111111" (that is, the 0~6 can be made up).*//*
        https://blog.csdn.net/XzzF1024/article/details/79181725*/
        bi|=bi<<c;
        ////cout<<bi<<endl;
    }
    if(n==1) return cout<<sum,0;
    for(int i=(sum+1)/2;i<=sum;i++)
    {
        if(bi[i])
        {
            cout<<i<<endl; return 0;
        }
    }

}


Measured memory_bytes: 1792
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#define FR first
#define SE second

using namespace std;

typedef pair<int,int> pr;

struct Edge {
  int t,next;
  Edge() {}
  Edge(int a,int b):t(a),next(b) {}
};

Edge e[100005];
int head[100005];

int dep[100005],fa[100005];

void dfs1(int x) {
  for(int i=head[x];i;i=e[i].next) {
  	int u=e[i].t;
  	dep[u]=dep[x]+1;
  	dfs1(u);
  }
}

bool vis[100005];

void dfs2(int x) {
  if (vis[x]) return;
  vis[x]=1;
  for(int i=head[x];i;i=e[i].next) dfs2(e[i].t);
}

pr a[100005];

int main() {
  int n,k;
  scanf("%d%d",&n,&k);
  int ans=0;
  for(int i=1;i<=n;i++) {
  	int x;
  	scanf("%d",&x);
  	if (i==1) {
  		if (x!=1) ans++;
	  }
	else {
		fa[i]=x;
		e[i]=Edge(i,head[x]);
		head[x]=i;
	}
  }
  dfs1(1);
  for(int i=2;i<=n;i++) a[i-1]=pr(dep[i],i);
  sort(a+1,a+n);
  for(int i=n-1;i>0;i--)
    if (!vis[a[i].SE]&&a[i].FR>k) {
    	ans++;
    	int p=a[i].SE;
    	for(int j=1;j<k;j++) p=fa[p];
    	dfs2(p);
	}
  printf("%d\n",ans);
  return 0;
}

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

const int N_MAX = 100000;
int N;

const int C_MAX = 30;
int C;

int c[31][100001];

int time_[100001];

int main()
{
    cin >> N;
    cin >> C;
    int s,t,ci;
    for(int i =0;i < N;i++)
    {
        cin >> s >> t >> ci;
        for(int ti = s - 1;ti < t;ti++)
        {
            c[ci][ti] = 2;
        }
    }
    for(int cha = 1;cha <= C;cha++)
    {
        for(int ti = 0;ti <= 100000;ti++)
        {
            if(c[cha][ti] == 2)
            {
                time_[ti]++;
            }
        }
    }
    int ans = -1;
    for(int i =0;i <= 100000;i++)
    {
        ans = max(time_[i],ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 12416
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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

	
	string S;
	cin >> S;

	int A = -1, Z;
	rep(i, S.size()) {
		if (S[i] == 'A' && A == -1) A = i;
		if (S[i] == 'Z') Z = i;
	}

	co(Z - A + 1);

	Would you please return 0;
}

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

long long int uriage[4000];

int main(void) {
	int n,i,num,flag;
	long long int price,cnt;
	
	while(scanf("%d",&n)){
		if(!n) break;
		
		flag = 0;
		memset(uriage,0,sizeof(uriage));
		
		for(i = 0;i < n;i++){
			scanf("%d %lld %lld",&num,&price,&cnt);
			if(uriage[num-1] < 1000000){
				uriage[num-1] += price*cnt;
				if(uriage[num-1] >= 1000000){
					printf("%d\n",num);
					flag = 1;
				}
			}
		}
		if(!flag) printf("NA\n");
	}
	
	return 0;
}

Measured memory_bytes: 648
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define inf 2e18
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define mem(a,v) memset(a,v,sizeof(a))
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
#define N 2e5+5


int32_t main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int a,b;
        cin >> a >> b;
        int x=(a+b-1)/b;
        cout << x << '\n';
        
        

}

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

long n, a[101010];

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

    long ans = 0;
    for(int i = 0; i < n; ++i) {
        ans += a[i] / 2;
        if(a[i]&1 && a[i+1] > 0) ++ans, --a[i+1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define All(obj) (obj).begin(),(obj).end()

using namespace std;


int main() {
	speed;
	string s;
	cin >> s;
	int ans = 0;
	rep(i, 4) {
		if (s.at(i) == '+')ans++;
		else {
			ans--;
		}
	}
	cout << ans;
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { cout << p.first << ' ' << p.second; return os; }

void solve() {
  int N; cin >> N;
  unordered_set<int> ma;
  rep(i, N) {
    int a; cin >> a;
    ma.insert(a);
  }
  if (ma.size() % 2 == 0) cout << ma.size() - 1 << '\n';
  else cout << ma.size() << '\n';
}


Measured memory_bytes: 4388
#include <bits/stdc++.h>
#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 FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  sort(a.begin(), a.end());
  ll ans = n, sum = 0, idx = 0;
  while (1) {
    sum += a[idx];
    idx++;
    while (sum * 2 < a[n - 1] && sum * 2 >= a[idx]) {
      sum += a[idx];
      idx++;
    }
    if (sum * 2 >= a[n - 1]) break;
    ans = n - idx;
  }
  cout << ans << '\n';






  
  return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int N; cin >> N;
  cout << (-N / 15 * 200 + 800 * N) <<"\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
vector<int>kaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
int comb(int a,int b){
    //if(!kaijo[0])init_fact(2000010);
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){
    double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
    double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
    double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
    double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
    return tc*td<0&&ta*tb<0;
}

signed main(){
    int x;
    cin>>x;
    int n=100;
    for(int i=1;;i++){
        n=n*1.01;
        if(n>=x){
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 3640
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define AU(i,x)    for(auto i=x.begin(); i!=x.end(); ++i)
# define ALL(A) A.begin(),A.end()
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){
    char ch=nc();int sum=0, f=1;
    if (ch=='-') f=-1, ch=nc();
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum*f;
}
int ps4[4][2]={0,1,0,-1,1,0,-1,0};
int ps8[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,-1,-1,1};
inline int min(int a,int b,int c) {return min(a,min(b,c));}
inline int max(int a,int b,int c) {return max(a,max(b,c));}
inline int min(int a,int b,int c,int d){return min(min(a,b,c),d);}
inline int max(int a,int b,int c,int d){return max(max(a,b,c),d);}
//struct Edge{int p, next, w;}edge[maxn];
//inline add_edge(int u, int v, int w){edge[cnt]=Edge{v,head[u],w}; head[u]=cnt++;}
const int N=100005;
///Code begin..................................................................


string a, b;

bool Check(int x){
    for (int i=x; i<x+b.length(); ++i) {
        if (a[i]!='?'&&a[i]!=b[i-x]) return false;
    }
    return true;
}
int main ()
{
    cin>>a>>b;
    int oo=a.length()-b.length();
    for (int i=oo; i>=0; --i) {
        if (Check(i)) {
            for (int j=0; j<i; ++j) if (a[j]=='?') a[j]='a';
            for (int j=i; j<i+b.length(); ++j) a[j]=b[j-i];
            for (int j=i+b.length(); j<a.length(); ++j) if (a[j]=='?') a[j]='a';
            cout<<a<<endl;
            return 0;
        }
    }
    puts("UNRESTORABLE");
    return 0;
}


Measured memory_bytes: 256
from scipy.special import comb
N = int(input())

if N == 3:
  print(1)
elif N < 3:
  print(0)
else:
  i = 1
  ans = 1
  while True:
    a = N - ((i + 1) * 3)
    if a < 0:
      print(ans)
      break
    b = comb(a + i, i, exact=True)
    ans += b 
    ans %= (10 ** 9 + 7)
    i += 1


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

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

int main() {

    int h, w; cin >> h >> w;

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

    vector<vector<int>> d(h, vector<int>(w, -1));

    d[0][0] = 0;
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));

    while (!q.empty()) {
        auto p = q.front();
        q.pop();

        for (int i = 0; i < 2; ++i) {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];

            if (nx < 0 || h <= nx || ny < 0 || w <= ny) continue;
            if (d[nx][ny] != -1) continue;
            if (a[nx][ny] == '.') continue;

            d[nx][ny] = d[p.first][p.second] + 1;
            q.push(make_pair(nx, ny));
        }
    }


    int cnt[100] = {};
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (a[i][j] == '#') {
                if (d[i][j] == -1) {
                    puts("Impossible");
                    return 0;
                }
                
                if (cnt[d[i][j]] == 1) {
                    puts("Impossible");
                    return 0;
                } else {
                    cnt[d[i][j]] = 1;
                }
            }
        }
    }

    if (d[h - 1][w - 1] == -1) {
        puts("Impossible");
    } else {
        puts("Possible");
    }
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
csum = [0 for i in range(len(A)+1)]
for i in range(len(A)):
    csum[i+1] = csum[i] + A[i]


res = 1000000000000
for i in range(len(A)-1):
    res = min(res, abs(csum[i+1] - (csum[N]-csum[i+1])))

print(res)


Measured memory_bytes: 24800
#include <bits/stdc++.h>
using namespace std;
#define fol(i,n) for(int i=0;i<n;i++)
const int lim=2001;
const int a=10000,b=5000,c=1000;
int ans[3]={-1,-1,-1};

void cyl(int n,int y){
    fol(i,n+1){
        fol(j,n+1-i){
            fol(k,n+1-i-j){
                if ((i+j+k==n)&&a*i+b*j+c*k==y){
                    ans[0]=i,ans[1]=j,ans[2]=k;
                    return;
                }
            }
        }
    }
}
int main(){
    int n,y;cin>>n>>y;
    cyl(n,y);
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
    return 0;
}


Measured memory_bytes: 384
def search_substr(S, subs):
    idx = 0
    ret = False
    for s in S:
        if s == subs[idx]:
            idx += 1
            if idx == len(subs):
                ret = True
                break
                
    return ret

def solve():
    N = int(input())
    S = input()
    
    # 愚直にやると↓だが、まあ間に合わないだろう
    # ret = len(set(for s in combination(S, 3)))
    ret = 0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                subs = '{0}{1}{2}'.format(i,j,k)
                if search_substr(S, subs):
                    ret += 1
                    
    print(ret)
    
solve()

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <stack>
#include <queue>
#include <array>
#include <random>

using namespace std;
#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef int64_t i64;
typedef uint64_t ui64;
typedef pair<int, int> pi;

template <class T, class U>
inline ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <class T, class U>
inline istream& operator>>(istream& os, pair<T, U>& p) {
    os >> p.first >> p.second;
    return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
    if (v.empty())
        return os;
    if (v.begin() != v.end())
        os << v.front();
    for (auto it = ++v.begin(); it != v.end(); ++it)
        os << ' ' << *it;
    return os;
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
    for (auto& i : v)
        is >> i;
    return is;
}

void Solve(istream& is, ostream& os) {
    vector<string> input(3);
    is >> input;
    vi counts(3, 0);
    int curr = 0;
    while (counts[curr] < sz(input[curr])) {
        int next = input[curr][counts[curr]] - 'a';
        ++counts[curr];
        curr = next;
    }
    os << static_cast<char>('A' + curr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << setprecision(20) << fixed;
    Solve(cin, cout);
    return 0;
}


Measured memory_bytes: 764
#include <stdio.h>
#include<math.h>

int mypow(int a,int b)
{
    int i,ans=1;
    for (i = 0; i < b;i++)
    {
        ans *= a;
    }
    return ans;
}

int main()
{
    int n,i,rank=1,kosu=0;
    scanf("%d", &n);
    for (i = 1; i <= n;i++)
    {
        if(i % mypow(10,rank)==0)
        {
            rank++;
            //printf("%d %d\n",i,rank);
        }
        if(rank%2==1)
        {
            kosu++;
        }
    }
    printf("%d", kosu);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define MOD7 1000000007
#define MOD9 1000000009

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

using namespace std;

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

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

vector<vector<int>> nexts;

int solve(int n) {
	int ret = 0;

	vector<int> tmp(nexts[n].size());
	rep(i, nexts[n].size()) {
		tmp[i] = solve(nexts[n][i]) + 1;
	}
	sort(all(tmp));
	reverse(all(tmp));

	rep(i, tmp.size()) {
		ret = max(ret, tmp[i] + i);
	}

	return ret;
}

signed main() {
	int N;
	cin >> N;

	nexts.resize(N + 10);

	REP(i, 2, N) {
		int a;
		cin >> a;
		nexts[a].push_back(i);
	}

	cout << solve(1) << endl;

    return 0;
}


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

typedef long long ll;
typedef long double ld;

#define n1		      "\n"
#define B                     begin()
#define E                     end()
#define F                     first
#define S                     second
#define pb                    push_back
#define pf                    push_front
#define popb                  pop_back()
#define popf                  pop_front()

const int BIG=1e5+55;
const int BIGG=1e9+7;
const ll BIGGE=1e12+55;
const double SML=(1e-7);

using namespace std;

    set <int> s;
    int x;

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cout.tie(NULL);
    cin >>x;
    s.insert(x);
    cin >>x;
    s.insert(x);
    cin >>x;
    s.insert(x);
    if (s.size() == 2)
        cout <<"Yes";
    else
        cout <<"No";



    return 0;
}


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

int main(){
  set<int> s;
  int n, a;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    s.insert(a);
  }
  bool flag = false;
  for(int i : s){
    if(flag){
      cout << " ";
    }
    cout << i;
    flag = true;
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 7776
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string a,b,c;
	cin >> a >> b >> c;
	cout << a[0] << b[1] << c[2];
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	if(a==b)
		printf("Draw\n");
	else if(a==1)
		printf("Alice\n");
	else if(b==1)
		printf("Bob\n");
	else if(a>b)
		printf("Alice\n");
	else
		printf("Bob\n");
	return 0;
}

Measured memory_bytes: 128
n = gets.to_i
arr = gets.chomp.split(' ').map(&:to_i)
personel = Array.new(n,0)
i = 0
boss = 1
while i < n - 1
  if arr[i] == boss
    personel[boss-1] += 1
  else
    boss = arr[i]
    personel[boss-1] += 1
  end
  i += 1
end
puts personel


Measured memory_bytes: 35792
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int n,a,b,c,x;
	vector<int>y;
	while(cin>>n>>a>>b>>c>>x){
		if(n+a+b+c+x==0)break;
		int cnt=0,ans=-1;
		for(int i=0;i<n;i++){
			int tmp;
			cin>>tmp;
			y.push_back(tmp);
		}
		for(int i=1;i<=10001;i++){
			//cout<<x<<endl;
			if(y[cnt]==x)cnt++;
			if(cnt==y.size()){
			ans=i-1;
			//cout<<i<<endl;
			break;
			}
			x=(a*x+b)%c;
		}
		if(x!=-1)cout<<ans<<endl;
		else cout<<-1<<endl;
		y.clear();
	}
	return 0;
}

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

int main()
{
    int N,X;
    int sum1 = 0;
    int sum2 = 0;
    int sum3 = 0;
    vector<int> g;
    
    cin >> N >> X;
    
    for(int i = 0; i < N; i++){
        int w;
        cin >> w;
        
        g.push_back(w);
    }
    
    sort(g.begin(),g.end());
    
    for(int i = 0; i < N; i++){
        sum1 += g.at(i);
    }
    
    sum2 = X - sum1;
    
    sum3 = sum2 / g.at(0);
    
    
    cout << N + sum3 << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
		int res = 0;
		for(int i = 1; i < n-1; i++){
			int[] three = new int[3];
			three[0] = arr[i];
			three[1] = arr[i-1];
			three[2] = arr[i+1];
			Arrays.sort(three);
			if(three[1] == arr[i]) res++;
		}
		System.out.println(res);
	}

}


Measured memory_bytes: 21716
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>

using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
typedef long long ll;

int dp[5005][5005];
int main()
{

    int n;
    string s;
    cin >> n;
    cin >> s;

    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = n - 1; j >= 0; --j)
        {
            if (s[i] != s[j])
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i + 1][j + 1] + 1;
        }
    }

    int ans = 0;
    REP(i, n)
    REP(j, n)
    {
        if (i >= j)
            continue;
        int now = min(dp[i][j], j - i);
        ans = max(ans, now);
    }
    cout << ans << endl;

    return 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define lcm(a, b) (a)/__gcd((a),(b))*(b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> LP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;
static const int SIZE = 200005;

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

vector<int> Div(int n) {
    vector<int> ret;
    for(int i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);

            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int n, m;
    cin >> n >> m;
    int s = 0;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
        s += v[i];

    }

    int c = 0;
    for(int i = 0; i < n; ++i) {
        if(v[i] >= double(s) / (4 * m)) {
            ++c;

        }
    }
    if(c >= m) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}



Measured memory_bytes: 256