akhauriyash/Code-Regression huggingface dataset:
s = [list(input()) for _ in range(3)]

n_row = 0

dic = {0:"A",1:"B",2:"C"}

while len(s[n_row]):
    s_num = s[n_row].pop(0)
    
    if s_num == "a":
        n_row = 0
    elif s_num == "b":
        n_row = 1
    elif s_num =="c":
        n_row = 2

print(dic[n_row])

Measured memory_bytes: 9004
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
using namespace std;

#define rep(i,a,n) for(int i=a; i<n; i++)
#define repq(i,a,n) for(int i=a; i<=n; i++)
#define repr(i,a,n) for(int i=a; i>=n; i--)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

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

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

// ?§?????????¨????????¨???????????????????¨???????????§???????
struct Edge {
    int from, to, cost;
    Edge(int s, int d) : to(s), cost(d) {}
    Edge(int f, int s, int d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

// 1??????????????????????????????????????±????????????????????????????????? vector
// Edges????????????????????????????????????????????°??????????????????
typedef vector<Edge> Edges;

// ???????????±??????????????? vector
// Graph??????????????????????????°?????????????????§??? V ??§?????????
typedef vector<Edges> Graph;

vector<int> tpsort_Kahn(const Graph &g) {
    const int V = g.size();
    vector<int> indeg(V, 0);
    stack<int> S;

    rep(i,0,V) rep(j,0,g[i].size())
        indeg[ g[i][j].to ]++;
    rep(i,0,V) if(indeg[i] == 0) S.push(i);

    vector<int> ans;
    while(S.size() > 0) {
        int u = S.top(); S.pop();
        // C++11??\???
        // ans.emplace_back(u);
        ans.pb(u);
        rep(i,0,g[u].size()) {
            indeg[ g[u][i].to ]--;
            if(indeg[ g[u][i].to ] ==  0)
                S.push( g[u][i].to );
        }
    }
    return ans;
}

signed main() {
    int V, E; cin >> V >> E;
    Graph G(V);
    int s, t;
    rep(i,0,E) {
        cin >> s >> t;
        G[s].pb(Edge(t,1));
    }
    vector<int> ans = tpsort_Kahn(G);
    rep(i,0,ans.size()) {
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 4996
# -*- coding: utf-8 -*-

import re

n = int(input())
s = input()
t = input()

idx = 0

for i in range(len(s)-1, -1, -1):
    if re.match(s[i:], t):
        matchOB = s[i:]
        idx = len(matchOB)
        
print(len(s + t[idx:]))
    

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define MOD 1000000007
typedef pair<li, li> PI;

li h[100100];
li dp[100100];

inline li cost(li from, li to) {
	return abs(h[from] - h[to]);
}

int main(void)
{
	string s;
	cin >> s;
	cout << ((s[0] == '9' || s[1] == '9') ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 256
import numpy as np
def main():
    n = int(input())
    A = np.array([list(map(lambda x: '{}'.format(x), input())) for _ in range(n)], dtype='U')
    ans = 0
    for i in range(n):
        B = np.block([A[:, i:], A[:, :i]])
        if np.array_equal(B, B.T):
            ans += n
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 28564
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
	int n;
	while ((n = nextInt()) != 0) {
	    int[][] map = new int[21][21];
	    for (int i = 0; i < n; i++) {
		map[nextInt()][nextInt()] = 1;

	    }
	    int m = nextInt();
	    int x = 10;
	    int y = 10;
	    int count = 0;
	    for (int i = 0; i < m; i++) {
		// if (count != n) {
		char c = getChar();
		int l = nextInt();
		int dx = 0;
		int dy = 0;
		if (c == 'N') {
		    dy = 1;
		} else if (c == 'E') {
		    dx = 1;
		} else if (c == 'S') {
		    dy = -1;
		} else if (c == 'W') {
		    dx = -1;
		}
		for (int j = 0; j < l; j++) {
		    count += map[x][y];
		    map[x][y] = 0;
		    x += dx;
		    y += dy;
		}
		count += map[x][y];
		map[x][y] = 0;
		// } else {
		// skip();
		// }
	    }
	    if (count == n) {
		System.out.println("Yes");
	    } else {
		System.out.println("No");
	    }
	}
    }

    private static void skip() throws IOException {
	int c = System.in.read();
	while (c != '\n') {
	    c = System.in.read();
	}

    }

    private static char getChar() throws IOException {
	int c = ' ';
	while (c < 'E' || 'W' < c) {
	    c = System.in.read();
	}
	return (char) c;
    }

    private static int nextInt() throws IOException {
	int c = System.in.read();
	while ((c < '0' || '9' < c) && c != '-') {
	    c = System.in.read();
	}
	if (c == '-') {
	    return -nextInt();
	}
	int result = 0;
	while ('0' <= c && c <= '9') {
	    result = result * 10 + (c - '0');
	    c = System.in.read();
	}
	return result;
    }
}

Measured memory_bytes: 25420
#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++)
#define dame { printf("No\n"); return 0;}
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(1e17)


signed main(){
    int n,k;
    cin >> n >> k;
    if(n == 1){
        if(k == 0){
            cout << "0 0 1 1" << endl;
            return 0;
        }
        else{
            cout << -1 << endl;
            return 0;
        }
    }
    int check = 1;
    REP(i,n) check *= 2;
    if(k >= check){
        cout << -1 << endl;
        return 0;
    }
    int ans[check * 2];
    ans[check] = k;
    int tmp = 0;
    FOR(i,1,check){
        if(tmp == k) tmp ++;
        ans[i] = tmp;
        ans[check * 2 - i] = tmp;
        tmp ++;
    }
    ans[0] = k;
    REP(i,check * 2) cout << ans[i] << " ";
    cout << endl;
}


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

int isprime(long x){
    int i;
    
    if(x==2) return 1;
    if(x<2 || (x%2)==0) return 0;
    
    for(i=3; i<=sqrt(x); i+=2){
        if(x%i==0)return 0;
    }
    
    return 1;
}


int main(void){
    long x;
    int n;
    int i,cnt=0;
    
    scanf("%d",&n);
    
    for(i=0; i<n; i++){
        scanf("%ld",&x);
        if(isprime(x)==1) cnt++;
    }
    
    printf("%d\n",cnt);
    
    return 0;
}

Measured memory_bytes: 596
#include <cstdio>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')

const int N_MAX = 100000;
const int K_MAX = N_MAX * 2;

int N;
int K;
int M;
int a[K_MAX];
int b[K_MAX];

bool C(int x) {
  // printf("x: %d\nb: ", x);
  REP(i, K) b[i] = a[i] >= x ? 1 : 0;
  // DUMP(b, K);
  int res;
  int i;
  int lv = 0, lb = -1, rv = 0, rb = -1;
  for (i = M - 1; i >= 0 && b[i] != b[i + 1]; i--) lv++;
  if (i >= 0) lb = b[i];
  for (i = M + 1; i < K && b[i] != b[i - 1]; i++) rv++;
  if (i < K) rb = b[i];
  if (lb < 0 && rb < 0) {
    res = (N % 2 > 0 ? b[M] : 1 - b[M]);
  } else if (lv == 0 || rv == 0) {
    res = b[M];
  } else if (lv < rv) {
    res = lb;
  } else {
    res = rb;
  }
  // printf("lv: %d, lb: %d, rv: %d, rb: %d, res: %d\n", lv, lb, rv, rb, res);
  return res == 1;
}

void solve() {
  int hi = K + 1;
  int lo = 1;
  while (hi - lo > 1) {
    // printf("hi: %d, lo :%d\n", hi, lo);
    int mi = (hi + lo) / 2;
    if (C(mi)) lo = mi;
    else hi = mi;
  }
  // printf("hi: %d, lo :%d\n", hi, lo);
  printf("%d\n", lo);
}

void input() {
  scanf("%d", &N);
  K = 2 * N - 1;
  M = N - 1;
  REP(i, K) scanf("%d", a + i);
}

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


Measured memory_bytes: 1664
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


int main(){

	int N,tmp,upper_2,upper_1;

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		upper_2 = upper_1 = 0;

		for(int i = 0; i < N; i++){
			scanf("%d",&tmp);
			if(tmp > 0){
				upper_1++;
				if(tmp > 1){
					upper_2++;
				}
			}
		}

		if(upper_2 == 0)printf("NA\n");
		else{
			printf("%d\n",upper_1+1);
		}
	}

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    int tmp;
    cin >> tmp;
    int cnt = 0;
    while (tmp % 2 == 0) {
      cnt++;
      tmp /= 2;
    }
    ans += cnt;
  }
  cout << ans << endl;
}


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

int main() {
	int a = 0, N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		a += i + 1;
	}
	
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N, M;
  cin >> N >> M;
  vvl graph(N + 1, vl(N + 1, 0));
  ll a, b;
  rep(i, M){
    cin >> a >> b;
    graph[a][b] = 1;
    graph[b][a] = 1;
  }

  ll cnt = 0;
  
  vl n(N);
  iota(n.begin(), n.end(), 1);

  do{
    if(n[0] == 1){
      bool path = true;

      rep2(i, 1, N){
	if(graph[ n[i - 1] ][ n[i] ] == 0){
	  path = false;
	  break;
	}
      }
      
      if(path) cnt++;
    }
  } while( next_permutation(n.begin(), n.end()) );

  cout << cnt << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

int main() {
    int n;
    cin >> n;

    int ans = 0;

    srep(i,1,n+1){
        if(i<10){
            ans++;
        }else if(100<=i&&i<1000){
            ans++;
        }else if(10000<=i&&i<100000){
            ans++;
        }
    }

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


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

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

typedef int long long ll;
using namespace std;
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const ll MOD = 1e9 + 7;
static const int MAX = 100;
static const int INF =1e9+7;

int main() {
    ll n;
    cin>>n;
    vector<pair<ll,ll>> v;
    ll lon = 0;
    ll lonp = 0;
    ll minl = 0,lp =INF;
    ll mar = 0,rq = 0;

    rep(i,n){
        ll a,b;
        cin>>a>>b;
        v.push_back({a,b});
        if(b<lp){
            lp=b;
            minl=i;
        }
        if(a>rq){
            rq=a;
            mar=i;
        }
    }

   //cout<<mar<<" "<<minl<<endl;
   int p =0;
    rep(i,n){
            if(v[i].second-v[i].first+1>lon){
                lon=v[i].second-v[i].first+1;
                p=i;

            }
    }
    ll pl=INF,pr=0;
    rep(i,n){
        if(i!=p){
            pl= min(pl,v[i].second);
            pr = max(pr,v[i].first);
        }
    }


    ll ans = 0;
   // ans=lon+max(0ll,v[minl].second-v[mar].first+1);
   ans = lon+max(0ll,pl-pr+1);

   //cout<<ans<<endl;
    vector<pair<ll,ll>> v2;

    rep(i,n){
        ll y1 = max(v[i].second - v[mar].first+1,0ll);
        ll y2 = max(v[minl].second-v[i].first+1,0ll);
        v2.push_back({y1,-y2});
    }

    //cout<<v[mar].first<<" "<<v[minl].second<<endl;

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


    ll s=0;ll t=0;
    ll w = INF;
    rep(i,n){
        ll a = v2[i].first,b=-v2[i].second;
        if(w!=INF){
            ans=max(ans,w+a);
        }
        w=min(w,b);
    }
    cout<<ans<<endl;




    return 0;
}


Measured memory_bytes: 4848
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  string s;
  cin >> s;
  if (s.back() == '3') cout << "bon\n";
  else if (s.back() == '1' or s.back() == '0' or s.back() == '6' or s.back() == '8') cout << "pon\n";
  else cout << "hon\n";
}



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

using namespace std;

int main()
{
	string str;
	cin >> str;
	
	int n = str.length();
	
	for(int i = 0; i < n; i++)
	{
		if((i - 1) >= 0 && str[i] == str[i - 1]){
			cout << (i) << " " << (i + 1);
			return 0;
		}
		
		if((i - 2) >= 0 && str[i] == str[i - 2]){
			cout << (i - 1) << " " << (i + 1);
			return 0;
		}
	}
	
	cout << "-1 -1";
	return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
 
 
int main() {
    int N,K;
    cin >> N >> K;
    vector<int> enemy(N);
    if (K >= N) {
        cout << 0 << endl;
        return 0;
    }

    long long sum = 0;
    int a = 0;
    for (int i = 0;i < N;i++) {
        cin >> a;
        sum += a;
        enemy.at(i) = a;
    }

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


    for (int i = 0;i < K;i++) {
        sum -= enemy.back();
        enemy.pop_back();
    }

    cout << sum << endl;
}


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

using namespace std;
int main(){
  string s;
  cin >> s;
  
  string s0 = "CODEFESTIVAL2016";
  int ans = 0;
  for(int i = 0; i < s0.length(); i++){
    if(s[i] != s0[i]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
string s,t;
int main(){
	ios::sync_with_stdio(0);
	cin>>s>>t;
	if(t.substr(0,sz(s))==s)
	cout<<"Yes";
	else
	cout<<"No";
	re 0;
}

Measured memory_bytes: 3640
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 2010
inline ll read()
{
	ll x=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
	return x*f;
}
inline void write(ll x)
{
	static char buf[20];
	int len=0;
	if(x<0)putchar('-'),x=-x;
	for(;x;x/=10)buf[len++]=x%10+'0';
	if(!len)putchar('0');
	else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
char mp[maxn][maxn];
int a[maxn][maxn];
int n,m,k;
int main()
{
	n=read(); m=read(); k=read();
	for(int i=1;i<=n;i++)
		scanf("%s",mp[i]+1);
	int tot=0;
	for(int i=1;i<=n;i++){
		int pos=0;
		for(int j=1;j<=m;j++)
			if(mp[i][j]=='#'){
			pos=j; break;
			}
		if(!pos)continue;
		++tot;
		for(int j=1;j<=pos;j++)
			a[i][j]=tot;
		for(int j=pos+1;j<=m;j++)
			if(mp[i][j]=='#')a[i][j]=++tot;
			else a[i][j]=a[i][j-1];
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j])a[i][j]=a[i-1][j];
	for(int i=n;i;i--)
		for(int j=1;j<=m;j++)
			if(!a[i][j])a[i][j]=a[i+1][j];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			writesp(a[i][j]);
		putchar('\n');
	}
	return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
using namespace std;
//using bint=boost::multiprecision::cpp_int;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  char c; cin>>c;
  if(c<=90) co('A');
  else co('a');
  
  return 0;
}

Measured memory_bytes: 3672
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>

int len[3], used[3], s[3][100], d, i;

void rec(int t){
	if(used[t]++>=len[t]) putchar('A'+t);
	else rec(s[t][used[t]-1]);
}

int main(){
	for(i=0;i<3;i++) while((d=getchar())!='\n') s[i][len[i]++] = d-'a';
	rec(0);
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int  dp[50][500][500];
int a[50], b[50], c[50];
int main()
{
	int N, M1, M2;
	cin >> N >> M1 >> M2;
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	for (int i = 0; i < 50; i++) {
		for (int j = 0; j < 500; j++) {
			for (int k = 0; k < 500; k++) {
				dp[i][j][k] = mod;
			}
		}
	}
	dp[0][0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 400; j++) {
			for (int k = 0; k < 400; k++) {
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				dp[i + 1][j + a[i]][k + b[i]] = min(dp[i][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);
			}
		}
	}
	int ans = mod;
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++) {
			if (i == 0 && j == 0) continue;
			if (i * M2 == j * M1) ans = min(ans, dp[N][i][j]);
		}
	}
	if (ans == mod)cout << -1 << endl;
	else cout << ans << endl;
}

Measured memory_bytes: 49152
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define dup(x,y) (((x)+(y)-1)/(y))
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const double EPS = 1e-10;
const int INF = 1e9;
const ll LINF = 1e15;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	vector<int> b(n+1, 0), w(n+1, 0);
	rep(i,n) {
		w[i+1] = w[i] + (s[i] == '.');
		b[i+1] = b[i] + (s[i] == '#');
	}

	int ans = INF;
	for(int i = 0; i < n+1; i++) {
		int lb = b[i] - b[0];
		int rw = w[n] - w[i];
		ans = min(ans, lb + rw);
	}
	cout << ans << endl;
}

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

int main()
{
  int ans=0;
  vector<char> a(3);
  vector<char> b(3);
  for(int i=0;i<3;i++)
  {
    cin>>a.at(i);
  }
  for(int i=0;i<3;i++)
  {
    cin>>b.at(i);
  }
  for(int i=0;i<3;i++)
  {
    if(a.at(i)==b.at(i))
    {
      ans++;
    }
  }
  cout<<ans<<endl;
}


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

// 1-indexed
template <class T>
struct BIT {
  vector<T> lst;
  int treesize;
  // constructor
  BIT(int newn = 0) {
    treesize = newn;
    lst.resize(treesize + 1);
    for(int i = 0; i <= treesize; ++i) lst[i] = 0;
  }
  // a_place += num
  bool add(int place, T num) {
    while(place <= treesize) {
      lst[place] += num;
      place += place & -place;
    }
    return 1;
  }
  // add wide ver.(add num between l and r)
  bool addw(int left, int right, T num) {
    while(left <= right && left >= 1 && right <= treesize)
      add(left++, num);
    return 1;
  }
  // sum between [1,place]
  T calcsum(int place) {
    T answer = 0;
    while(place > 0) {
      answer += lst[place];
      place -= place & -place;
    }
    return answer;
  }
  // sum [l,r]
  T calcsumw(int left, int right) {
    return calcsum(right) - calcsum(left - 1);
  }
};

struct data {
  long long x, h;
};
bool operator<(const data &l, const data &r) {
  return l.x < r.x;
}

long long n, d, a;
vector<data> v;
BIT<long long> bit;

long long solve();

int main() {
  cin >> n >> d >> a;
  v.resize(n);
  for(int i = 0; i < n; ++i) {
    cin >> v[i].x >> v[i].h;
    v[i].h = (v[i].h + a - 1) / a;
  }
  sort(v.begin(), v.end());
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = 0, r = 0;
  bit = BIT<long long>(n + 2);
  for(int i = 0; i < n; ++i) bit.add(i + 1, v[i].h);
  for(int i = 0; i < n; ++i) {
    long long now = bit.calcsum(i + 1);
    if(now <= 0) {
      bit.add(i + 1, -v[i].h);
      continue;
    }
    while(r < n && v[r].x <= v[i].x + 2 * d) ++r;
    res += now;
    bit.add(i + 1, -v[i].h - now);
    bit.add(r + 1, now);
  }
  return res;
}


Measured memory_bytes: 4992
//K-OS WITH THE OCDE

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <iostream>
#include <numeric>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <deque>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <climits>

using namespace std;

typedef long long int ll;
typedef long double db;


#define TEST ll t; cin>>t; while(t--)
#define vell vector<ll>
#define pl pair<ll,ll>
#define all(v) v.begin(),v.end()
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define dbg(x)  cerr << #x << ": "<< x <<endl
#define dbg2(x,y) cerr<< #x <<": "<< x <<" || "<< #y << ": " << y << endl

#define endl "\n"
#define MAX 1e18
#define MIN INT_MIN
#define mod 1000000007


ll add(ll a, ll b)  { return ((a % mod + b % mod) % mod); }
ll sub(ll a, ll b)  { return ((a % mod - b % mod) % mod); }
ll mult(ll a, ll b) { return (((a % mod) * (b % mod)) % mod); }

ll ways(ll n , ll m)
{
    ll dp[m + 1][n + 1];

    for (ll i = 0; i <= n; i++) {
        dp[1][i] = 1;
    }

    ll sum;

    for (ll i = 2; i <= m; i++) {
        for (ll j = 0; j <= n; j++) {
            sum = 0;
            for (ll k = 0; k <= j; k++) {
                sum = add(sum , dp[i - 1][k]);
            }
            dp[i][j] = sum;
        }
    }
    return dp[m][n] % mod;
}


void solve()
{
    ll n;
    cin >> n;

    ll dp[2005] = {0};

    if (n < 3) {
        cout << 0;
        return;
    }

    dp[3] = 1;
    dp[4] = 1;
    dp[5] = 1;


    for (ll i = 6 ; i <= n ; ++i) {
        for (ll j = 3 ; j <= i ; ++j) {
            if (i - j < 3) {
                dp[i]++;
                break;
            }
            else
                dp[i] = add(dp[i] , dp[i - j]);
        }
    }


    cout << dp[n] % mod;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    //TEST
    solve();
}



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

typedef long long ll ;
#define rep (i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int N;
	
	cin >> N;

	int a[N];

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

	sort(a, a+N);

	int init = 0;
	if (N % 2)
	{
		if (a[0] != 0)
		{
			cout << 0 << endl;
			return 0;
		}
		init = 1;
		
	}
	bool ve = true;
	for (int i = init; i < N;)
	{
		if (a[i] != a[i+1])
		{
			ve = false;
			break;
		}

		if (a[i] != i+1)
		{
			ve = false;
			break;
		}
		i = i+2;
	}

	if (!ve)
	{
		cout << 0 << endl;
	}
	else
	{
		//cout << pow(2, N / 2) << endl;
		ll sum = 1;
		for (int i = 0; i < N / 2;i++)
		{
			sum = (sum * 2) % MOD;
		}
		cout << sum << endl;
	}
	
	return 0;
}

Measured memory_bytes: 640
using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            bool b;
            int N = 0;

            b = int.TryParse(Console.ReadLine(), out N);        //N????????????

            if (!b)
            {
                Console.WriteLine("error.");
            }

            string[] line = Console.ReadLine().Split(' ');      //??°???????????????
            int[] array = new int[N];

            for(int i = 0; i < N; i++)
            {
                b = int.TryParse(line[i], out array[i]);        //line???????´????int??????????????????array???????´?
            }

            DisplayArray(array);
            int v = 0;
            int j = 0;

            for( int i = 1;  i <= N-1; i++)
            {
                v = array[i];
                j = i - 1;

                while (j >= 0 && array[j] > v)
                {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = v;
                DisplayArray(array);
            }
        }

        /// <summary>
        /// ??°????????¶????????¨???
        /// </summary>
        /// <param name="array"></param>
        private static void DisplayArray(int[] array)
        {
            for(int i = 0; i < array.Length; i++)
            {
                Console.Write(array[i]);
                if(i == array.Length - 1)
                {
                    Console.WriteLine();
                }
                else
                {
                    Console.Write(" ");
                }
            }
        }
    }
}

Measured memory_bytes: 9116
import math

t1,t2 = map(int,input().split())
a1,a2 = map(int,input().split())
b1,b2 = map(int,input().split())

if a1*t1+a2*t2 == b1*t1+b2*t2:
	print('infinity')
	exit(0)

if (a1*t1 < b1*t1 and a1*t1+a2*t2 < b1*t1+b2*t2) or (a1*t1 > b1*t1 and a1*t1+a2*t2 > b1*t1+b2*t2):
	print(0)
	exit(0)

m = abs(a1*t1-b1*t1)
s = abs(a1*t1+a2*t2-b1*t1-b2*t2)
if m%s == 0:
	print((m//s)*2)
else:
	print((m//s)*2+1)

Measured memory_bytes: 3064
#include<stdio.h>
#define max_n 100000
#define max_q 50000
int n,q,i,count=0;
long int S[max_n],T[max_q];
void search(void);
int main(void){
    scanf("%d", &n);
    for (i=0;i<n;i++){
        scanf("%ld",&S[i]);
    }   
    scanf("%d", &q);
    for (i=0;i<q;i++){
        scanf("%ld",&T[i]);
    }   
    search();
    printf("%d\n",count);
}
void search(void){
    int left,right,mid;
    for (i=0;i<q;i++){
        left=0,right=n-1;
        if (S[0]==T[i]||S[n-1]==T[i]){count++;continue;}
        while(right-left > 1){ 
            mid=(left+right)/2;
            if(S[mid]>T[i]) right=mid;
            else if ( S[mid]==T[i]) {count++; break;}
            else left=mid;
        }   
    }   
}

Measured memory_bytes: 3920
n = int(input())
a = list(map(int,input().split()))
s = []

for i in range (n):
    d = 0
    c = -1
    b = a[i]
    while d == 0:
        d = b % 2
        b = b / 2
        c = c + 1

    s.append(c)

res = min(s)

print(res)


Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#define ll long long
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}

ll a[100010];
ll c[100010];
ll cc[100010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%lld",a+i);
	sortup(a,n);
	int pre=-1,cnt=0;
	for(int i=0;i<n;i++){
		if(a[i]!=pre)c[cnt++]=a[i];
		pre=a[i];
		cc[cnt-1]++;
	}
	if(cnt==1){
		puts(c[0]==0?"Yes":"No");
	}else if(cnt==2){
		puts(c[0]==0&&cc[0]*2==cc[1]?"Yes":"No");
	}else if(cnt==3){
		puts((c[0]^c[1]^c[2])==0&&cc[0]==cc[1]&&cc[1]==cc[2]?"Yes":"No");
	}else{
		puts("No");
	}
}

Measured memory_bytes: 1948
a=-1,A=65,d;
char
*N="GKSOCNWLDFVTBRXHAJUPEMQI",
*E="PHLTIDOXQAGWECSUMBKVJFNR",
s[9];
main(c)
{
for(;c-48&&scanf("%s",s);a+=d/4+1)
{
if((c=*s)<A)
~a&&printf("%d\n",a),
a=d=0;
if(c=='N')d=N[d]-A;
if(c=='E')d=E[d]-A;
if(c=='W')d=E[E[E[d]-A]-A]-A;
if(c=='S')d=N[N[N[d]-A]-A]-A;
if(c=='R')d=d&28|d%4+1&3;
if(c=='L')d=d&28|d%4+3&3;
}
}

Measured memory_bytes: 0
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>

// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

/* ---------- Namespace ---------- */
using namespace std;

/* ---------- Type ---------- */
using ll = long long;
#define int ll
#define P pair<ll, ll>

/* ---------- Constants  */
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;

/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    int N;
    string S;
    cin >> N >> S;

    int height = 0;
    int min_height = 0;

    for (int i = 0; i < N ; i++) {
        if (S[i] == '(') {
            height++;
        } else {
            height--;
        }

        min_height = min(height, min_height);
    }

    int prepend_num = abs(min_height);
    int append_num = prepend_num + height;

    cout << string(prepend_num, '(') + S + string(append_num, ')');

    return 0;
}

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

int main()
{
    long long int i,lenght,sum,t;
    string  n;
    int cot=0,flag=0;
    cin>>t;
    cin>>n;
    for(i=0; i<=n.length(); i++)
    {
        if(n[i]=='A' && n[i+1]=='B' && n[i+2]=='C')
        {
            cot++;
        }
    }

    cout<<cot<<endl;


}

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

int main(){
  int n;
  cin >> n;
  string str;
  int point;
  vector<tuple<string,int,int>> guide;
  for(int i=0;i<n;i++){
    cin >> str >> point;
    guide.push_back(make_tuple(str,point*-1,i+1));
  }
  sort(guide.begin(),guide.end());
  for(tuple<string,int,int> t:guide){
    int x;
    tie(ignore,ignore,x)=t;
    cout << x << endl;
  }
}
  

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int n,a,ans=0;
	vector<char> p;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a;
		p.push_back(a);
	}
	for (int i = 1; i < p.size() - 1; i++) {
		if (p[i] > p[i - 1] && p[i] < p[i + 1]) {
			ans++;
		}
		else if (p[i] < p[i - 1] && p[i] > p[i + 1]) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int n,m,l,r,d,dist[100010];
vector<pair<int,int> > v[100010];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l,&r,&d);
		v[l].push_back(make_pair(r,d));
		v[r].push_back(make_pair(l,-d));
	}
	for(int i=1;i<=n;i++) dist[i]=INF;
	for(int i=1;i<=n;i++) if(dist[i]==INF){
	    queue<int> q;
		q.push(i);
		dist[i]=0;
		while(!q.empty())
		{
			int t=q.front();q.pop();
			for(int i=0;i<v[t].size();i++){
				pair<int,int> u=v[t][i];
				if(dist[u.first]==INF){
					dist[u.first]=dist[t]+u.second;
					q.push(u.first);
				}
				else if(dist[u.first]!=dist[t]+u.second){
					cout<<"No"<<endl;
					return 0;
				}
			}
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 9344
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define F first
#define S second
const int N = 1e5 + 87;
int fen[N];
vector<pii> a[N];
int po[N];
int qry(int i)
{
    int ret = 0;
    for (; i; i ^= i & -i)
        ret += fen[i];
    return ret;
}
void upd(int i,int x)
{
    for (; i < N; i += i & -i)
        fen[i] += x;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    for (int i = 0; i <n; ++i) {
        int l,r;
        cin >> l >> r;
        a[r - l + 1].emplace_back(l,r);
    }
    for (int i = m; i >= 1; --i)
        po[i] = a[i].size() + po[i+1];
    for (int i = 1; i <= m; ++i) {
        int ans = po[i];
        for (int j = i; j <= m; j += i)
            ans += qry(j);
        cout << ans << '\n';
        for (const pii & p : a[i]) {
            upd(p.F,1);
            upd(p.S+1,-1);
        }
    }
}


Measured memory_bytes: 8448
// Package main provides
//
// File:  main.go
// Author: ymiyamoto
//
// Created on Sun Jan 27 17:58:27 2019
//
package main

import (
	"fmt"
	"sort"
)

func min(slice ...int) int {
	sort.Ints(slice)
	return slice[0]
}

func max(slice ...int) int {
	sort.Ints(slice)
	return slice[len(slice)-1]
}

func main() {
	var A, B, C, X, Y int
	fmt.Scan(&A, &B, &C, &X, &Y)

	fmt.Println(min(A*X+B*Y, 2*C*max(X, Y), 2*C*min(X, Y)+A*(X-min(X, Y))+B*(Y-min(X, Y))))
}


Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

int main(){
  int a,b;cin>>a>>b;
  int res=(a>2*b)?a-2*b:0;
  cout<<res<<endl;
}

Measured memory_bytes: 256
using System;

namespace abc94_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array = Console.ReadLine().Split(' ');
            int cat = int.Parse(array[0]);
            int index = int.Parse(array[2]);
            int catdog = int.Parse(array[1]);
            if (cat > index)
            {
                Console.WriteLine("NO");
            }
            else if (cat + catdog >= index)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

main()
{
    fast;
    int i,tp,ans=0;
    string s;
    cin>>s;
    for (i=0;i<s.size()-2;i++)
    {
        tp=100*(s[i]-'0')+10*(s[i+1]-'0')+(s[i+2]-'0');
        if (abs(753-ans)>=abs(753-tp))
            ans=tp;
    }
    cout<<abs(753-ans)<<endl;
}

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

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n, m, ans = 2;
    cin >> n;
    m = n - 1;
    if (n == 2) return cout << 1, 0;
    for (ll i = 2; i * i <= m; i++) if (m % i == 0) {
        ans++;
        if (i * i != m) ans++;
    }
    for (ll i = 2; i * i <= n; i++) if (n % i == 0) {
        ll cp = n;
        while (cp % i == 0) cp /= i;
        if (cp % i == 1) ans++;

        if (i * i != n) {
            cp = n;
            while (cp % (n / i) == 0) cp /= (n / i);
            if (cp % (n / i) == 1) ans++;
        }
    }

    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

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

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////




int main() {
	ll K;
	cin >> K;

	while (K % 2 == 0) { K /= 2; }
	while (K % 5 == 0) { K /= 5; }

	if (K == 1) { cout << 1;}

	else {
		vector<ll> p(1, 1);
		for (ll v = 10 % K; v != 1; v = v * 10 % K) { p.push_back(v); }
		ll M = p.size();

		//rep(i, M) cout << p[i];
		//cout << endl;

		vector<ll> dis(K, -1);
		dis[1] = 1;

		queue<pair<ll, ll>> q;
		q.push({ 1,0 });

		ll ans = -1;
		while (1) {
			auto x = q.front();
			q.pop();
			for (ll j = x.second; j < M; j++) {
				ll k = (x.first + p[j]) % K;

				//cout << x.first << p[j] << k << endl;

				if (k == 0) { ans = dis[x.first] + 1; break; }
				if (dis[k] != -1) { continue; }
				dis[k] = dis[x.first] + 1;
				q.push({ k,j });
			}

			if (ans != -1) { break; }
		}

		cout << ans;
	}

	system("PAUSE");
}


Measured memory_bytes: 2808
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S=input()

A=int(S[:2])
B=int(S[2:])
mA=False
mB=False
if 1<=A<=12:
    mA=True
if 1<=B<=12:
    mB=True

if mA and mB:
    print('AMBIGUOUS')
elif mA:
    print('MMYY')
elif mB:
    print('YYMM')
else:
    print('NA')


Measured memory_bytes: 3064
n = gets.chomp.to_i
cities = Array.new
n.times do
    cities << gets.split.map(&:to_i)
end
sum = 0.0
count = 0
# puts readlines.map(&:chomp)
cities.combination(2).each do |a, b|
    sum += Math.sqrt((a[0]-b[0]) ** 2 + (a[1] - b[1]) ** 2)
    count +=1
end
ave = sum / count
puts ave * (n-1)

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




int main(void){
   int N; 
   cin>>N;
   map<string,int> a;

   for(int i=0;i<N;i++){
     string s;
     cin>>s;
     a[s]++;
   }
   int x=0;
   for(auto p : a) x=max(x,p.second);
   for(auto p : a){
      if(p.second != x) continue;
      cout<<p.first<<endl; 
   }

   return 0;
   
}




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

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

int main(){
int n;
cin>>n;
ll a[n];
vector<ll> arr;
map<ll,int>m;
rep(i,n){
  cin>>a[i];
  if(m[a[i]]==1||m[a[i]]==3){
    arr.push_back(-a[i]);
  }
  m[a[i]]++;
}
if(arr.size()<2){

  cout<<0<<endl;
  return 0;
}
sort(arr.begin(),arr.end());
//rep(i,arr.size()){
  //cout<<arr[i]<<endl;
//}
ll ans=arr[0]*arr[1];
cout<<ans<<endl;
  return 0;
}


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

int main() {
    string S;
    cin >> S;
    int res = 700;
    rep(i, 3) if(S[i]=='o') res+=100;

    cout << res << endl;
    return 0;
}

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

int main(void){
    ll x, y, z, k;
    cin >> x >> y >> z >> k;

    ll a[x], b[y], c[z];

    rep(i, x){
        cin >> a[i];
    }
    rep(i, x){
        cin >> b[i];
    }
    rep(i, x){
        cin >> c[i];
    }

    vector<ll> ab;
    rep(i, x){
        rep(j, y){
            ab.push_back(a[i] + b[j]);
        }
    }

    sort(ab.begin(),  ab.end(), greater<ll>());

    vector<ll> abc;
    rep(i, min(k, x * y)){
        rep(j, z){
            abc.push_back(ab[i] + c[j]);
        }
    }

    sort(abc.begin(), abc.end(), greater<ll>());

    rep(i, k){
        cout << abc[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 43236
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

int main()
{
    fast_io
    ll n,k;
    string s;
    cin>>n>>k;
    cin>>s;
    s[k-1]+=32;
    cout<<s<<endl;



    return 0;
}





Measured memory_bytes: 3608
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {

	H := nextInt64()
	W := nextInt64()

	if H == 1 || W == 1 {
		fmt.Println(1)
	} else if H%2 == 1 && W%2 == 1 {
		fmt.Println(H*W/2 + 1)
	} else {
		fmt.Println(H * W / 2)
	}
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store") // to restrict undesirable precision
#pragma GCC optimize ("-fno-defer-pop")// to pop argument of function as soon as it returns
#define all(a) a.begin(),a.end()
#define ll long long int
#define ld long double
ll power(ll a,ll b,ll m){ if(b==0) return 1; if(b==1) return a%m; ll t=power(a,b/2,m)%m; t=(t*t)%m; if(b&1) t=((t%m)*(a%m))%m; return t;}
ll modInverse(ll a, ll m) { return power(a, m-2, m); }
#define ps push_back
#define fs first
#define takeline cin.ignore();
#define sc second
#define N 3000005
#define endl "\n"
#define mod 1000000007
//((1.0l)*BIG MULTIPLY MAGIC?)
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
//-----------------------------------------------
int main(){
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	ll i,j,k,l,n;
	cin>>n;
	ll ar[n];
	for(i=0;i<n;i++){
		cin>>ar[i];
	}

	ll an=0;
	for(i=0;i<63;i++){
		k=power(2,i,mod);
		ll a=0,b=0;
		for(j=0;j<n;j++){
			if((ar[j]&(1LL<<i))) a++;
			else b++;
		}
		an=(an+(k*((a*b)%mod))%mod)%mod;
	}
	cout<<an;
	return 0;
}

Measured memory_bytes: 2560
import sys
sys.setrecursionlimit(10 ** 7)


def input():
    return sys.stdin.readline().strip()


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    res = 0
    for nv in g[v]:
        res = max(res, dfs(nv) + 1)
    dp[v] = res
    return res


n, m = map(int, input().split())
g = {i: set() for i in range(1, n + 1)}
for _ in range(m):
    x, y = map(int, input().split())
    g[x].add(y)

dp = [-1] * (n + 1)
for v in g:
    dp[v] = max(dp[v], dfs(v))
print(max(dp))


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

int main(){
    size_t N, X;
    cin >> N >> X;
    size_t ans{N};
    N -= X;
    while(X){
        ans += 2 * X * (N / X);
        swap(N %= X, X);
    }
    cout << ans - N << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <boost/optional.hpp>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i, n) for(int i = 0, i##_MACRO = (n); i < i##_MACRO; i++)
#define RANGE(i, a, b) for(int i = (a), i##_MACRO = (b); i < i##_MACRO; i++)
#define EACH(e, a) for(auto&& e : a)
#define ALL(a) std::begin(a), std::end(a)
#define RALL(a) std::rbegin(a), std::rend(a)
#define FILL(a, n) memset((a), n, sizeof(a))
#define FILLZ(a) FILL(a, 0)
#define INT(x) (static_cast<int>(x))

using namespace std;

using ll = long long;
using VI = vector<int>;
using VI2D = vector<vector<int>>;

constexpr int INF = 2e9;
constexpr double EPS = 1e-10;
constexpr double PI = acos(-1.0);

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

template <typename T>
constexpr int sign(T x) {
	return x < 0 ? -1 : x > 0 ? 1 : 0;
}

template <>
constexpr int sign(double x) {
	return x < -EPS ? -1 : x > EPS ? 1 : 0;
}

template <typename T, typename U>
constexpr void chmax(T& m, U x) {
	m = max(m, x);
}

template <typename T, typename U>
constexpr void chmin(T& m, U x) {
	m = min(m, x);
}

template <typename T>
constexpr T square(T x) {
	return x * x;
}

int main() {
	ll x;
	cin >> x;
	cout << (x / 500LL) * 1000LL + ((x % 500LL) / 5L) * 5L << endl;
	return 0;
}


Measured memory_bytes: 256
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Solve is
   D : Integer;
begin
   Get (D);
   if D = 25 then
      Put_Line ("Christmas");
   end if;
   if D = 24 then
      Put_Line ("Christmas Eve");
   end if;
   if D = 23 then
      Put_Line ("Christmas Eve Eve");
   end if;
   if D = 22 then
      Put_Line ("Christmas Eve Eve Eve");
   end if;
end Solve;

Measured memory_bytes: 3636