akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline


class RollingHash:
    def __init__(self, string):
        self.n = len(string)
        self.BASE = 1234
        self.MOD = 67280421310721
        # (2 << 61) - 1
        self.hash = [0] * (self.n + 1)
        self.pow = [1] * (self.n + 1)

        for i, char in enumerate(string):
            self.hash[i + 1] = (self.hash[i] * self.BASE + ord(char)) % self.MOD
            self.pow[i + 1] = (self.pow[i] * self.BASE) % self.MOD

    def get_hash(self, l, r):
        """string[l:r]のハッシュ値を返す。O(1)"""
        res = (self.hash[r] - self.hash[l] * self.pow[r - l]) % self.MOD
        return res


n = int(input())
s = [input()[:-1] for i in range(n)]


s.sort(key=len)
str_set = set()
cnt = 0

for string in s:
    string = string[::-1]
    n = len(string)
    rh = RollingHash(string)

    for r in range(1, n + 1):
        if rh.get_hash(0, r) in str_set:
            cnt += 1

    set_char = set()
    for r in range(1, n + 1)[::-1]:
        set_char.add(string[r - 1])
        for char in set_char:
            if char == string[r - 1]:
                continue
            h = (rh.hash[r - 1] * rh.BASE + ord(char)) % rh.MOD
            if h in str_set:
                cnt += 1
    str_set.add(rh.get_hash(0, n))

print(cnt)

Measured memory_bytes: 133608
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int main(void){
    string S;
    cin >> S;
    bool flag = true;

    for(int i = 0; i < S.length(); i++){
        if(i % 2 == 0){
            if(S[i] == 'L')
                flag = false;

        }
        else{
            if(S[i] == 'R')
                flag = false;
        }
    }

    if(flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    vector<ll> d(n);
    for(i = 0; i < n; i++) {
        cin >> d[i];
    }
    sort(d.begin(), d.end());
    if(n >= 24 || d[0] == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> cnt(12, 0),tim(24,0);
    tim[0]=1;
    for(i = 0; i < n; i++) {
        cnt[d[i]]++;
        if(cnt[d[i]] > 2) {
            cout << 0 << endl;
            return 0;
        }
    }
    if(cnt[12] > 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<ll> solo;
    for(i=1;i<=12;i++){
        if(cnt[i]==2){
            tim[i] = 1;
            tim[24-i]=1;
        }else if(cnt[i]==1){
            solo.push_back(i);
        }
    }
    vector<ll> t(n, 0);
    ll ret = 0;
    for(i = 0; i < 1 << solo.size(); i++) {
        t = tim;
        for(j = 0; j < solo.size(); j++) {
            if((i >> j) & 1) {
                t[solo[j]] = 1;
            } else {
                t[24-solo[j]] = 1;
            }
        }
        ll now = INF, cur = 0;
        for(j = 1; j < 24; j++) {
            if(t[j] == 1){
                now = min(now, abs(cur - j));
                cur = j;
            }
        }
        now = min(now,min(cur,24-cur));
        ret = max(ret, now);
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=2002;
bitset<maxn*maxn+10>s;
int main()
{
    int N,x,ans;
    while (~scanf("%d",&N)) {
        s.reset();ans=0;
        s[0]=1;
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&x);
            s|=(s<<x);
            ans+=x;
        }
        for(int i=(ans+1)/2;;i++)
        {
            if(s[i]){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

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

#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define rep(i,n) reps(i,0,n)
#define rrep(i,n) for(int i=n-1; i>=0: i--)
#define X first
#define Y second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const ll INF = 1e9;

const string bo = "aiueo";

int main(){
	int n;
	while(cin >> n, n){
		string s[105];
		rep(i,n) cin >> s[i];
		int len=0;
		rep(i,n) len = max<int>(len, s[i].length());

		int l=0, r=len+1;
		while(r-l>1){
			int m = (r+l) / 2;
			
			set<string> st;
			rep(i,n){
				string t;
				t += s[i][0];
				rep(j,s[i].length()-1){
					for(auto b: bo){
						if( t.size() >= m ) break;
						if( s[i][j] == b ){
							t += s[i][j+1];
						}
					}
				}
				st.insert(t);
			}
			if( st.size() == n ){
				r = m;
			}else{
				l = m;
			}
		}
		cout << (r>len ? -1 : r) << endl;
	}
	return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
	cin>>n>>s;
	for(int i=0;i<s.size();i++)
	{
		int num=s[i]-'A';
		num+=n;
		num%=26;
		s[i]=(char)num+'A';
	}
	cout<<s<<endl;
}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
#define r(i,a,n) for(int i=a;i<(int)(n);i++)
typedef long long ll;
int main(){
    string S;
    int memo=0;
    int c_point;
    cin>>S;
    if(S[0]!='A'){
        cout<<"WA"<<endl;
        return 0;
    }
    r(i,2,S.size()-1){
        if(S[i]=='C'){
            memo++;
            c_point=i;
        }
    }
    if(memo!=1){
        cout<<"WA"<<endl;
        return 0;
    }
    r(i,1,S.size()){
        if(i!=c_point){
            if(S[i]>='A'&&S[i]<='Z'){
                cout<<"WA"<<endl;
                return 0;
            }
        }
    }
    cout<<"AC"<<endl;
    return 0;
}

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int n = s.size();
    ll ans = 0;
    for (int m = 0; m < (1 << (n - 1)); m++) {
        string t;
        vector <string> r;
        for (int i = 0; i < n; i++) {
            t += s[i];
            if ((m >> i) & 1) {
                r.push_back(t);
                t.clear();
            }
        }
        r.push_back(t);
        for (auto to : r) {
            ll x = stoll(to);
            ans += x;
        }
    }  
    cout << ans << '\n';
    return 0;
} 

Measured memory_bytes: 256
#0が来るまで回数の入力を繰り返す
while True:
    j = int(input())
    if j == 0:break

    #点数を合計し、一番小さいかずと、一番大きい数を出力する
    else:
        num_list = []
        for _ in range(j):
            line = list(map(int,input().split()))
            num_list.append(sum(line))
        print(str(max(num_list)) + " " + str(min(num_list)))


Measured memory_bytes: 5616
def s():
 n=int(input())+1
 e=[input().split()for _  in[0]*~-n]
 p=[int(e[0][0])]+list(int(x[1])for x in e)
 m=[[0]*n for _ in[0]*n]
 for i in range(n):
  for r in range(n-i-1):
   c=r+i+1
   for j in range(r+1,c):
    x=m[r][j]+m[j][c]+p[r]*p[j]*p[c]
    if not 0<m[r][c]<x:m[r][c]=x
 print(m[r][c])
if'__main__'==__name__:s()


Measured memory_bytes: 5712
unittest
{
	assert( [ "2 2" ].parse.expand.solve == 25 );
	assert( [ "8 10" ].parse.expand.solve == 100 );
	assert( [ "19 99" ].parse.expand.solve == -1 );
	
	assert( [ "80 100" ].parse.expand.solve == 1000 );		// 追加ケース
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

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

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ab = input.front.split.to!( long[] );
	return tuple( ab[ 0 ], ab[ 1 ] );
}

auto solve( long a, long b )
{
	auto ans = 0L;
	foreach( i; 1L .. 1001L )
	{
		if( cast( long )( i * 0.08 ) == a && cast( long )( i * 0.1 ) == b ) return i;
	}
	return -1;
}


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

using namespace std;

int main()
{
    int x, y ;
    cin >> x >> y;
    if(y<=x*4 && y>= x*2 && y%2==0)
    {
        cout << "Yes";
        return 0;
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
struct edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<int>>;
using dou =long double;
string Yes="Yes";
string YES="YES";
string NO="NO";
string No="No";
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(int i = m; i < (int)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ffor for(;;)
#define ub upper_bound
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define res resize
#define as assign
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout << "Case #" <<qqq+1<<": "
 
typedef long long ll;
//typedef long long T;
const int INF = 2000000000;
const ll INF64 = 922337203685477580ll;
//const int mod = 1000000007ll;
const ll  MOD = 1000000007LL;
int main(){
    int a,b,c,x,y;
    std::cin >> a>>b>>c>>x>>y;
    int ans=INF;
    ans=min(ans,x*a+y*b);
    ans=min(ans,max(x,y)*c*2);
    int m=min(x,y);
    x-=m,y-=m;
    ans=min(ans,m*2*c+x*a+y*b);
    std::cout << ans << std::endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100;
int main()
{
    int N,flag = 1,sum=0;
    cin>>N;
    int a[maxn];
    for(int i=0;i<N;i++)
        cin>>a[i];
    sort(a,a+N);
    for(int i=N-1;i>=0;i--)
    {
        sum+=flag*a[i];
        flag = -flag;
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int haiku[5] = {5,7,5,7,7};
  int n;
  while(cin>>n,n){
    vector<string> vs(n);
    FOR(i,0,n) cin >> vs[i];
    FOR(i,0,n) {
      int j = 0;
      int k = i;
      while(k < n && j < 5) {
        int len = 0;
        while(len < haiku[j] && k < n) {
          len += vs[k].length();
          k++;
        }
        if(len != haiku[j]) break;
        j++;
      }
      if(j == 5) {
        cout << i + 1 << endl;
        break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3128
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <random>
#include <utility>
#include <map>
#include <vector>
#include <queue>
#include <bitset>
#include <sstream>
#define REP(i,x) for(int i=0; i<(x); i++)
typedef long long ll;

using namespace std;

int main(int argc, const char * argv[]) {
    string n,m;
    cin >> n >> m;

    if(m=="100"){
        m="101";
    }
    
    string out;
    if(n=="0"){
        out = m;
    }else if(n=="1"){
        out = m+"00";
    }else if(n=="2"){
        out = m+"0000";
    }

    cout << out << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

typedef pair<int, int> P;

int main(){
   int n, w, d;
   while (1){
      cin >> n >> w >> d;
      if (n==0 && w==0 && d==0) return 0;
      if (n == 0){
         cout << w * d << endl;
         continue;
      }
      int p[n], s[n];
      vector<P> v;
      for (int i = 0; i < n; i++){
         cin >> p[i] >> s[i];
      }

      v.push_back(P(w, d));
      for (int i = 0; i < n; i++){
         int ww = v[p[i]-1].first, dd = v[p[i]-1].second;
         v.erase(v.begin()+p[i]-1, v.begin()+p[i]);
         int len = s[i]%(ww+dd);
         if (len < ww){
            v.push_back(P(min(len, ww-len), dd));
            v.push_back(P(max(len, ww-len), dd));
         }
         else {
            v.push_back(P(ww, min(len-ww, ww+dd-len)));
            v.push_back(P(ww, max(len-ww, ww+dd-len)));
         }
      }

      int sq[n+1];
      for (int i = 0; i <= n; i++){
         sq[i] = v[i].first * v[i].second;
      }
      sort(sq, sq+n+1);
      for (int i = 0; i <= n; i++){
         cout << sq[i] << (i==n?"\n":" ");
      }
   }
}



Measured memory_bytes: 3072
n = int(input())
a = list(map(int, input().split()))
d = [0 for _ in range(10 ** 5 + 10)]

for i in range(n):
    d[max(a[i] - 1, 0)] += 1
    d[a[i] + 2] -= 1
for i in range(1, n + 1):
    d[i] += d[i - 1]

# print(d[:10])
print(max(d))


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

int is_number(char c) {
    int res = c - '0';
    if (0 <= res && res < 10) return res;
    else return -1;
}

int main ()
{
    string str;
    int res = 0;
    while (cin >> str) {
        int i = 0;
        while (i < str.size()) {
            int tmp = 0;
            int sum = 0;
            while (i < str.size() && (tmp = is_number(str[i])) >= 0) {
                sum = sum * 10 + tmp;
                i++;
            }
            if (sum == 0) i++;
            res += sum;
        }
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1184
#include <iostream>
#include <algorithm>
using namespace std;
int p[105];
int m[110][110];
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i - 1];
		cin >> p[i];
		m[i][i] = 0;
	}
	for (int l = 2; l <= n; l++) {
		for (int i = 1; i <= n - l + 1; i++) {
			int j = i + l - 1;
			m[i][j] = (i << 21);
			for (int k = i; k <= j - 1; k++) {
				m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
			}
		}
	}
	cout << m[1][n] << "\n";
	return 0;
}

Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(void){
    int h, w;
    
    while(1){
        cin >> h >> w;
        if(h == 0 && w == 0)
            break;
        else{
            for(int i=0; i < h; i++){
                for(int j=0; j < w; j++){
                    cout << "#";
                }
                cout << endl;
            }
            cout << endl;
        }
    }
    
    return 0;
}



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

using namespace std;
typedef long long ll;

int main(){
	ll r,d,x[15];
	cin >> r >> d >> x[0];
	for(int i=1; i<=10; i++){
		x[i] = x[i-1] * r - d;
		cout << x[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<list>
#include<stack>
//#include<unordered_map>
using namespace std;
#define ll long long
#define dd cout<<endl
#define lll __int128
const int mod=1e9+7;
const int inf=1e9+7;

//const int maxn=

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    double n;
    
    cin>>n;
    
    if((int)n&1)
    	cout<<((n+1)/2/n)<<endl;
    else
    	cout<<1.0/2<<endl;

    return 0;
}

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



using namespace std;

typedef vector<int> VI;
typedef vector<string> VS;


//container util
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

long long N;
long long ans = 0;

void dfs(long long v, int a, int b, int c){

	if(v > N) return ;
	else if(v >= 1 and v <= N and a > 0 and b > 0 and c > 0){
		ans++;
	}

	dfs(10*v+7,a+1, b, c);
	dfs(10*v+5, a, b+1, c);
	dfs(10*v+3, a, b, c+1);

	return ;

}


int main(void){


	cin >> N;
	dfs(0,0,0,0);
	cout << ans << endl;


	return 0;

}


Measured memory_bytes: 256
N = int(input())
S = list(input())

w_cnt = [0]
w = 0
for s in S:
    if s == '.':
        w += 1
    w_cnt.append(w)

b_cnt = [0]
b = 0
for s in S[::-1]:
    if s == '#':
        b += 1
    b_cnt.append(b)
b_cnt.reverse()


ans = float('inf')
i = 0
for b, w in zip(b_cnt, w_cnt):
    ww, bb = i, N - i
    ans = min(ans, abs(b - bb) + abs(w - ww))
    i += 1
print(ans)


Measured memory_bytes: 16192
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(a, b, c) for(ll c=a;c<b;c++)
#define re(b, c) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

vvl G = vv(100001, 0, 0, ll);
vector<set<ll>> T(100001);
vll per(100001, 0);
deque<vll> q;
void bfs(ll now, ll from){
  if(T[now].size()==1||from==0){
    per[now] = from;
    for(int i=0;i<G[now].size();i++){
      q.push_back(vll{G[now][i], now});
    }
  }else{
    T[now].erase(from);
  }
}
int main(int argc, char const *argv[]) {
  ll x, y, n, m;std::cin >> n >> m;
  for(int i=0;i<n-1+m;i++){
    std::cin >> x >> y;
    G[x].push_back(y);
    T[y].insert(x);
  }
  ll root=-1;
  for(int i=1;i<=n;i++) if(T[i].size()==0&&root==-1) root = i;

  q.push_back(vll{root, 0});
  while(!q.empty()){
    vll t = q.front();q.pop_front();
    bfs(t[0], t[1]);
  }
  for(int i=1;i<=n;i++) std::cout << per[i] << '\n';
  return 0;
}


Measured memory_bytes: 17268
#include<bits/stdc++.h>
using namespace std;
int main() {
  int h,m,i,j;
  cin>>h>>m;
  vector<int> x(m),y(m),dp(h+1,1e8);
  dp[0]=0;
  for(i=0;i<m;i++) cin>>x[i]>>y[i];
  for(i=0;i<m;i++){
    for(j=1;j<=h;j++){
      dp[j]=min(dp[j],dp[max(0,j-x[i])]+y[i]);
    }
  }
//  for(j=0;j<=h;j++) cout<<dp[j]<<' ';
  cout<<dp[h]<<endl;
}

Measured memory_bytes: 3648
c=[]
s=[]
e=[]
while True:
    try:
        t=input()
        if not t:break
    except:break
    c.append(int(t))

for i in c:
    if i==0:
        e.append(s.pop(-1))
    else:
        s.append(i)
[print(i) for i in e]


Measured memory_bytes: 5600
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
  long long int N;
  long long int a,b,n=10;
  cin >> N;
  long w = sqrt(N);
  for(long i=1;i<=w;i++){
    if(N%i==0){
      a=i;
      b=N/i;
    }
  }
  for(long i=1;;i++){
    if(a%n==a){
      a=i;
      break;
    }
    n *=10;
  }
  n=10;
  for(long i=1;;i++){
    if(b%n==b){
      b=i;
      break;
    }
    n *=10;
  }
  cout << max(a,b);
}

Measured memory_bytes: 256
# A - Sharing Cookies

# A,B,A+Bのいずれかが3の倍数かどうか判定する


A,B = map(int,input().split())

if A % 3 == 0\
or B % 3 == 0\
or (A+B) % 3 == 0:
    print('Possible')
else:
    print('Impossible')


Measured memory_bytes: 9164
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static void Main() {
        var xs = ReadInts();
        Array.Sort(xs);
        bool yes = xs.SequenceEqual(new[] { 5, 5, 7 });
        Console.WriteLine("{0}", yes ? "YES" : "NO");
    }
}

Measured memory_bytes: 3160
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include <cassert>
#include <functional>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(...) ;
#else
#define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl;

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v);

template<typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}

void _tostr_rec(ostringstream &oss) {
  oss << "\b\b \b";
}

template<typename Head, typename... Tail>
void _tostr_rec(ostringstream &oss, Head &&head, Tail &&... tail) {
  oss << head << ", ";
  _tostr_rec(oss, forward<Tail>(tail)...);
}

template<typename... T>
string _tostr(T &&... args) {
  ostringstream oss;
  int size = sizeof...(args);
  if (size > 1) oss << "{";
  _tostr_rec(oss, forward<T>(args)...);
  if (size > 1) oss << "}";
  return oss.str();
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

struct Trie;

Trie *memo[SIZE];
int memoIdx = 0;

/* Trie */

struct Trie {
  int val;
  int depth;
  Trie *next[2];

  Trie(): val(0), depth(0) { memset(next, 0, sizeof(next)); }

  void insert(char *s, bool countPrefix = true, int d = 0) {
    if (countPrefix) val++; //接頭辞のカウント[default]
    depth = d;

    if (*s) {
      int al = *s - '0';
      if (next[al] == NULL) {
        next[al] = new Trie;
        memo[memoIdx++] = next[al];
      }
      next[al]->insert(s + 1, countPrefix, d + 1);
    } else {
      if (!countPrefix) val++; //終端のカウント
    }
  }

  int find(char *s) {
    if (*s) {
      int al = *s - '0';
      return next[al] ? next[al]->find(s + 1) : 0;
    }
    return val;
  }
};

int main() {
  int N;
  ll L;
  char S[SIZE];

  Trie trie;
  memo[memoIdx++] = &trie;

  scanf("%d%lld", &N, &L);

  for (int i = 0; i < N; i++) {
    scanf("%s", S);
    trie.insert(S, false);
  }

  map<ll, int> counter;
  for (int i = 0; i < memoIdx; i++) {
    if (memo[i]->val) continue;
    ll d = L - memo[i]->depth;
    int v = 0;
    v += memo[i]->next[0] == NULL;
    v += memo[i]->next[1] == NULL;
    counter[d] += v;
  }

  map<int, int> Xor;

  for (auto p : counter) {
    ll i = p.first;
    int pow2 = 0;
    while (i >= 2 && i % 2 == 0) {
      i /= 2;
      pow2++;
    }
    Xor[pow2] += p.second;
  }

  bool ok = false;
  for (auto p : Xor) {
    ok |= p.second % 2;
  }

  if (ok) {
    puts("Alice");
  } else {
    puts("Bob");
  }

  return 0;
}

Measured memory_bytes: 13840
/*
    हॉंजी । की हाल चाल?
    बड़ीया सब?
*/

#include<bits/stdc++.h>
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             unordered_map<int,int>
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define MOD             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define EPS             1e-9

void gogeta()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
    gogeta();
    string s; cin >> s;
    if (s.back() == 's') s.push_back('e');
    s.push_back('s');
    cout << s << endl;
}


Measured memory_bytes: 3640
#!/usr/bin/env python3
#ABC62 C

import math
h,w = map(int,input().split())

def solve(H,W):
    mid = math.floor(W/2)
    ans = float('inf')
    for i in range(1,H):
        Smin = min(i*W,mid*(H-i),(W-mid)*(H-i))
        Smax = max(i*W,mid*(H-i),(W-mid)*(H-i))
        ans = min(ans,Smax-Smin)
    return min(ans,H)
if h % 3 == 0 or w % 3 == 0:
    print(0)
else:
    print(min(solve(h,w),solve(w,h)))


Measured memory_bytes: 41836
<?php
$stdins = []; 
while (true) {
    $stdin = trim(fgets(STDIN));
    if ($stdin === '') {
        break;
    }
    $stdins[] = $stdin;
}
$num = $stdins[0]; 
$lengths = explode(' ',$stdins[1]);
rsort($lengths);

$skip = true;
$total = 0;
foreach ($lengths as $length) {
    if ($skip) {
        $skip = false;
    } else {
        $total = $total + $length;
        $skip = true;
    }
}
print($total);


Measured memory_bytes: 3828
// includes
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <functional>
#include <cmath>
#include <climits>
#include <bitset>
#include <list>
#include <random>

// macros
#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())

using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
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;}

bool flag = false;

struct Graph{
  int n;
  vector<vector<int> > edge;
  vector<int> in_deg;
  Graph(int n_){
    n = n_;
    edge.resize(n);
    in_deg.resize(n, 0);
  }
  void adde(int at, int to){
    edge[at].push_back(to);
    in_deg[to]++;
  }
  vector<int> topological_sort(){
    stack<int> st;
    for(int i = 0; i < n; i++){
      if(in_deg[i] == 0)st.push(i);
    }
    vector<int> res;
    while(st.size()){
      if(st.size() > 1)flag = true;
      int at = st.top(); st.pop();
      res.push_back(at);
      for(int j: edge[at]){
        in_deg[j]--;
        if(in_deg[j] == 0)st.push(j);
      }
    }

    return res;
  }
};

int main(int argc, char const* argv[])
{
  int n, m;
  cin >> n >> m;
  Graph graph(n);
  rep(i, m){
    int a, b;
    cin >> a >> b;
    a--; b--;
    graph.adde(a, b);
  }
  vector<int> ts = graph.topological_sort();
  rep(i, n)cout << ts[i] + 1 << endl;
  if(flag)cout << 1 << endl;
  else cout << 0 << endl;
	return 0;
}



Measured memory_bytes: 3788
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>

bool judge2(std::vector<int> &a, std::vector<int> &b){
	for (int i=0; i<a.size(); i++){
		std::cout << "-";
		if(a[i]!=b[i]) return false;
		else std::cout << "一致\n";
	}
	return true;
}

bool judge(std::vector< std::vector<int> > &abc_s, std::vector< std::vector<int> > &abc_t){
	int first_s, first_t;
	for (int i=0; i < 26; i++){
		if(abc_s[i].size()==0) continue;
		first_s = abc_s[i][0];
		for (int j=0; j < 26; j++){
			if(abc_t[j].size()==0) continue;
			first_t = abc_t[j][0];
			if (first_s == first_t){
				if(abc_s[i]!=abc_t[j]){
				//if(judge2(abc_s[i], abc_t[j])==false){
					return false;
				}
			}
		}
	}
	return true;
}

int main(){
	std::string S, T;
	std::cin >> S >> T;
	int n = S.size();
	int pos;
	std::vector< std::vector<int> > abc_s(26), abc_t(26);
	for (int i=0; i < n; i++){
		pos = S[i] - 'a';
		abc_s[pos].push_back(i);
		pos = T[i] - 'a';
		abc_t[pos].push_back(i);
	}
	if(judge(abc_s, abc_t)) std::cout << "Yes\n";
	else std::cout << "No\n";	
	return 0;
}


Measured memory_bytes: 3080
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
const int MAX=1e6;
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline int GCD(int a,int b){return !b?a:GCD(b,a%b);}
typedef struct{int SPF[1000001],Primes[168],sz;}Template;
Template P;
static inline void ready(void)
{
  *P.SPF=1,*P.Primes=2,P.sz=1;
  rep(i,MAX/2)P.SPF[2*(i+1)]=2,P.SPF[2*(i+1)-1]=2*(i+1)-1;
  rep(i,MAX/2-1)
  {
    int x=2*(i+1)+1;if(P.SPF[x]==x){P.Primes[P.sz++]=x;}if(x*x>MAX)break;
    rep(j,P.sz){if(P.Primes[j]<=P.SPF[x]&&x*P.Primes[j]<=MAX)P.SPF[x*P.Primes[j]]=P.Primes[j];else break;}
  }
}
const char common[]="not coprime",disjoint[]="pairwise coprime",several[]="setwise coprime";
char esc[1000000];
static inline int Divise(int x)
{
  if(!x){return 0;}
  rep(i,168)
  {
    if(P.Primes[i]*P.Primes[i]>x)break;
    if(x%P.Primes[i]==0)
    {
      if(esc[P.Primes[i]-1])return 0;
      esc[P.Primes[i]-1]=1;
      while(x%P.Primes[i]==0&&x)x/=P.Primes[i];
    }
  }
  if(x>1){if(esc[x-1])return 0;esc[x-1]=1;}
  return 1;
}
int main(void)
{
  int N=IN(),A=0,flag=0,g=0;ready();
  rep(i,N){A=IN();g=GCD(g,A);if(i&&g!=1){flag=1;}if(!Divise(A)){flag=1;}}
  if(g>1)return puts(common),0;
  if(flag)return puts(several),0;else return puts(disjoint),0;
}

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

typedef vector< vector<int> > vvi;
typedef vector< vector<bool> > vvb;
typedef vector< vector<char> > vvc;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef long long ll;

int main(){
    int n, y;
    cin >> n >> y;
    for(int i=0;i<=n;i++){
        for(int j=n-i;j>=0;j--){
            if(10000*i+5000*j+1000*(n-i-j)==y){
                cout << i << " " << j << " " << n-i-j << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;
    return 0;
}

Measured memory_bytes: 3520
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int P = 0, W = 0, G = 0, Y = 0;
    int N;
    cin >> N;
    string S;
    for (int i = 0; i < N;i++){
        cin >> S;
        if (S=="P")
        {
            P = 1;
        }
        if (S == "W")
        {
            W = 1;
        }
        if (S == "G")
        {
            G = 1;
        }
        if (S == "Y")
        {
            Y = 1;
        }
    }
    int ans = P + W + G + Y;
    if (ans==3)
        cout << "Three";
    else
        cout << "Four";
    cout << endl;
}

Measured memory_bytes: 256
N, M, X = list(map(int, input().split()))
c_a_list = [list(map(int, input().split())) for _ in range(N)]

min_money = 1e10
for i in range(2**N):
    buy_list = [0] * N
    skill = [0] * M
    money = 0
    
    for j in range(N):
        if i % 2 == 0:
            buy_list[j] = 1
        i //= 2
    for buy_idx, ca in enumerate(c_a_list):
        if buy_list[buy_idx] == 1:
            for a_idx, a in enumerate(ca[1:]):
                skill[a_idx] += a
            money += ca[0]
    for s_idx, s in enumerate(skill):
        if s < X:
            break
        if s_idx == M-1:
            min_money = min(min_money, money)
if min_money == 1e10:
    print(-1)
else:
    print(min_money)

Measured memory_bytes: 9168
#16:50
n,m = map(int,input().split())
a = []
for _ in range(m):
  x,y = list(map(int,input().split()))
  x -= 1
  y -= 1
  a.append([x,y])
a.reverse()
scr = n * (n-1) // 2
pre = [-1 for _ in range(n)]
cnt = [1 for _ in range(n)]
ans = []
for i in range(m):
  ans.append(scr)
  X,Y = a[i]
  while pre[X] != -1:
    X = pre[X]
  while pre[Y] != -1:
    Y = pre[Y]
  x,y = min(X,Y), max(X,Y)
  if x != y:
    scr -= cnt[x] * cnt[y]
    pre[y] = x
    cnt[x] = cnt[x] + cnt[y]
  #print(pre)
  #print(cnt)
ans.reverse()
for i in range(m):
  print(ans[i])

Measured memory_bytes: 84584
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	if(n > 9 || m > 9){
		printf("%d", -1);
		return 0;
	}else{
		printf("%d", n * m);
	}
	return 0;
 } 

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

//GCD,LCM
ll gcd(ll a, ll b){ return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){ return a/gcd(a,b)*b;}

int main()
{
    double N,A[110]={},sum=0,d[110]={},ave,m=10000;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>A[i];
        sum+=A[i];
    }

    ave = sum/N;

    for(int i=0;i<N;i++){
        d[i] = abs(A[i]-ave);
        m = min(m,d[i]);
    }

    for(int i=0;i<N;i++){
        if(d[i] == m){
            cout<<i<<endl;
            return 0;
        }
    }

    return 0;
}

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

int main(){
    int a,b,c;
    while(cin >> a >> b >> c){
        int s = c*3;
        int x[3][3];
        x[0][0] = a;
        x[0][1] = b;
        x[1][1] = c;
        x[0][2] = s - x[0][0] - x[0][1];
        x[2][1] = s - x[0][1] - x[1][1];
        x[2][0] = s - x[0][2] - x[1][1];
        x[2][2] = s - x[0][0] - x[1][1];
        x[1][0] = s - x[0][0] - x[2][0];
        x[1][2] = s - x[1][0] - x[1][1];
        rep(i,3) printf("%d %d %d\n", x[i][0], x[i][1], x[i][2]);
    }
}


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

while a >= b and k != 0:
    b *= 2
    k -= 1
while b >= c and k != 0:
    c *= 2
    k -= 1

if a < b and b < c:
    print('Yes')
else:
    print('No')

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

int main() {
	int i, n, a = 0, b = 0;
	string sa, sb;
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> sa >> sb;
		if (sa.compare(sb) > 0)a += 3;
		else if (sa.compare(sb) < 0)b += 3;
		else {a++;b++;}
	}
	cout << a << " " << b << endl;
	return 0;
}

Measured memory_bytes: 1208
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CStones solver = new CStones();
        solver.solve(1, in, out);
        out.close();
    }

    static class CStones {

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            String s = in.next();
            int white = 0;
            int black = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '.') {
                    white++;
                } else {
                    black++;
                }
            }
            int curWhite = 0;
            int curBlack = 0;

            int ans = Math.min(white, black);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '.') {
                    curWhite++;
                } else {
                    curBlack++;
                }
                int curCost = curBlack + (white - curWhite);
                if (curCost < ans) {
                    ans = curCost;
                }
            }
            out.println(ans);
        }
    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}



Measured memory_bytes: 25064
n, k = map(int, input().split())
h = list(map(int,input().split()))

def calc():
  dp = [0]*n
  for i in range(n):
    tmp = []
    for j in range(1,k+1):
      if i-j >= 0:
          tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min(tmp) if len(tmp) != 0 else 0
  return dp[n-1]

print(calc())

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; i++)
    cin >> a.at(i);
  b.at(n / 2) = a.at(0);
  for(int i = 2 - n % 2; i < n; i += 2)
    b.at(n / 2 + (i + 1) / 2) = a.at(i);
  for(int i = 1 + n % 2; i < n; i += 2)
    b.at(n / 2 - (i + 1) / 2) = a.at(i);
  for(int i = 0; i < n; i++)
    cout << b.at(i) << ' ';
  cout << '\n';
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define fi first
#define se second
#ifdef CX_TEST
#define Debug printf
#else
#define Debug(...)
#endif
#define LL long long
using namespace std;
typedef pair<int, int> P;
const int maxn = 605;
const int mod = 1e9 + 7;

void add(int &x, int y) {
    x += y;
    if(x >= mod) x -= mod;
}

int mul(int x, int y) {
    LL z = 1LL * x * y;
    return z - z / mod * mod;
}

int g[maxn], f[maxn][maxn], d[maxn][maxn], c[maxn];

int main() {
#ifdef CX_TEST
    freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
    int n, m, i, j, k, l, w = 0;
    scanf("%d%d", &n, &m);
    n *= 2;
    for(i = 0; i < m; i++) {
        scanf("%d%d", &j, &k);
        c[j] = k;
        c[k] = j;
    }
    m = n - m * 2;
    g[0] = 1;
    for(i = 2; i <= n; i += 2) g[i] = mul(g[i - 2], i - 1);
    for(i = 1; i <= n; i++) {
        for(j = i; j <= n; j++) d[i][j] = d[i][j - 1] + (c[j] == 0);
    }
    for(l = 2; l <= n; l++) {
        for(i = 1; i <= n; i++) {
            j = i + l - 1;
            if(j > n) break;
            for(k = i; k <= j; k++) {
                if(c[k] && c[k] < i || c[k] > j) break;
            }
            if(k <= j || (d[i][j] & 1)) continue;
            f[i][j] = g[d[i][j]];
            for(k = i + 1; k < j; k++) add(f[i][j], mod - mul(f[i][k], g[d[k + 1][j]]));
            add(w, mul(f[i][j], g[m - d[i][j]]));
        }
    }
    cout << w << endl;
    return 0;
}


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

//define
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long

//constant
const int MOD = 1000000007;

//typedef
typedef vector<int> vi;
typedef vector<vector<int>> vvi;


const long long int mod = 1e9 + 7;

//return gcd(a,b), ax+by=1
//O(log max(a,b))
long long int extgcd(long long int a, long long int b, long long int& x, long long int& y) {
	long long  d = a;
	if (b != 0) {
		d = extgcd(b, a%b, y, x);
		y -= (a / b)*x;
	}
	else {
		x = 1; y = 0;
	}
	return d%mod;
}

//return a^(-1) (mod m) if gcd(a,m)==1
//O(log m)
long long int mod_inverse(long long int a, long long int m) {
	long long int x, y;
	extgcd(a, m, x, y);    //ax+my=1
	return (m + x%m) % m;   //return positive integer
}




long long int fac[1000000];
long long int com(long long int n, long long int k) {
	return (fac[n]*mod_inverse((fac[n-k]*fac[k])%mod,mod)) % mod;
}

int main() 
{
	fac[0] = 1;
	for (long long int i = 0; i < 1000000-1; i++) {
		fac[i + 1] =( fac[i] * (i + 1)) % mod;
	}
	long long int n, m, k;
	cin >> n >> m >> k;
	long long int res = 0;
	for (long long int i = 0; i <= k; i++) {
		long long int d = i;
		long long int l = k - i;
		long long int u = n + i;
		long long int r = m + k-i;

		if(d>0&&l>0)
			res = (res + (((com(n + m + 2*k, u + d)*((com(u + d, d) - com(u + d, d- 1)) )% mod)*((com(r + l, l) - com(r + l, l - 1))) % mod)%mod)%mod )% mod;
		if (d == 0 && l == 0)
			res = (res + com(n + m +2*k, u + d)) % mod;
		if (d == 0 && l > 0)
			res = (res + (com(n + m + 2*k, u + d)*(com(l + r, l) - com(l + r, l - 1)))%mod)%mod;
		if (d > 0 && l == 0)
			res = (res +( com(n + m +2* k, u + d)*((com(u + d, d) - com(u + d, d - 1)%mod))) % mod) % mod;

	}
	cout << (res+mod)%mod << endl;
	return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using P = pair<int, int>;

void Main() {
    int n;
    cin >> n;
    vi a(3);
    rep(i, 3) cin >> a[i];

    vi ans;

    vector<P> q;
    rep(i, n){
        string s; cin >> s;
        if(s == "BC") q.eb(1, 2);
        else if(s == "AC") q.eb(0, 2);
        else q.eb(0, 1);
    }
    
    auto add = [&](int x, int y){
        a[x]++;
        a[y]--;
        ans.pb(x);
    };
    
    q.eb(0, 1); // 番兵
    
    rep(i, n){
        int x = q[i].fi;
        int y = q[i].se;
        if(!a[x] && !a[y]){
            puts("No");
            return;
        }
        if(!a[x]) add(x, y);
        else if(!a[y]) add(y, x);
        else{
            int nx = q[i+1].fi;
            int ny = q[i+1].se;
            if(x == nx || x == ny){
                add(x, y);
            }else{
                add(y, x);
            }
        }
    }
    
    cout << "Yes" << endl;
    for(auto i : ans) cout << char('A' + i) << endl;
	return;
}

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

Measured memory_bytes: 4780
#include<stdio.h>
long long int n, a, b;
long long int h[100005];
int f(long long int x)
{
	long long int count = 0;
	int i;
	for (i = 0; i < n; i++)
		if (h[i] - x * b > 0)
			count += (h[i] - x * b + a - b - 1) / (a - b);
	if (count <= x)
		return 1;
	else
		return 0;
}
int main()
{
	scanf("%lld %lld %lld", &n, &a, &b);
	int i;
	for (i = 0; i < n; i++)
		scanf("%lld", &h[i]);
	long long int min, mid, max;
	max = 1000000009;
	min = 0;
	while (max - min > 1)
	{
		mid = (max + min) / 2;
		if (f(mid) == 0)
			min = mid;
		else
			max = mid;
	}
	printf("%lld\n", max);
	return 0;
}

Measured memory_bytes: 896
def gcd(x,y):
    if x < y:
        x,y = y,x
    
    while x%y != 0:
        x,y = y,x%y

    return y
    
N,X = map(int,input().split())

x=list(map(int,input().split()))
x=sorted(x)

l=[abs(i - X) for i in x]
ans=l[0]

if len(l) == 1:
    print(ans)
    exit()
    
for i in range(1,len(l)):
    ans = gcd(ans,l[i])
    
print(ans)   

Measured memory_bytes: 14224
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H,W;
  string sharp = "##";
  cin >> H >> W;
  vector<string> picture(H);
  for(int j=0;j<W;j++){
    sharp += "#";
  }
  for(int i=0;i<H;i++){
    cin >> picture.at(i);
    picture.at(i) = "#" + picture.at(i) + "#";
  }
  cout << sharp << endl;
  for(int k=0;k<H;k++){
    cout << picture.at(k) << endl;
  }
  cout << sharp << endl;
  return 0;
}

Measured memory_bytes: 256
def resolve():
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b, c = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    cnt=0
    judge=True
    while judge == True:
        for i in range(len(A)):
            if A[i] % 2 == 1:
                judge = False
            else:
                A[i] = A[i] /2

        if judge == True:
            cnt += 1

    print(cnt)


resolve()

Measured memory_bytes: 38512
/*بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيم*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mx=1e5+5;
const int MOD=1e9+7;
ll ara[mx];
int main ()
{
    ll n,m;
    scanf ("%lld %lld",&n,&m);
    ll sum1=0;
    for (int i=0;i<n;i++) {
        scanf ("%lld",&ara[i]);
        if (i) {
            ll x=ara[i]-ara[i-1];
            sum1+=x*i*(n-i);
            sum1%=MOD;
        }
    }
    ll sum2=0;
    for (int i=0;i<m;i++) {
        scanf ("%lld",&ara[i]);
        if (i) {
            ll x=ara[i]-ara[i-1];
            sum2+=x*i*(m-i);
            sum2%=MOD;
        }
    }
    ll ans=(sum1*sum2)%MOD;
    printf ("%lld\n",ans);

    return 0;
}


Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;

int main(void) {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0;i < s.length();i++) {
		int num = 0;
		for (int j = i;j < s.length();j++) {
			if (s[j] == 'A')num++;
			else {
				if (s[j] == 'T')num++;
				else {
					if (s[j] == 'C')num++;
					else {
						if (s[j] == 'G')num++;
						else break;
					}
				}
			}
		}
		ans = max(ans, num);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
using namespace std;
int dp[501][10][3][2][500];
char a[502],b[502],*s;
int alen,blen,slen,m;
int solve(int n,int pv,int ud,int ok,int md) {
	if(n==slen)return !md;
	if(dp[n][pv][ud][ok][md]>=0)return dp[n][pv][ud][ok][md];
	int ret=0;
	for(int i=0;i<=(ok?9:s[n]-'0');i++) {
		if(ud==0 && pv<=i)continue;
		if(ud==1 && pv>=i)continue;
		if(ud==2 && pv!=0 && pv==i)continue;
		int u;
		if(ud==2) {
			if(pv==0)u=2;
			else if(pv>i)u=1;
			else u=0;
		}else{
			u=ud^1;
		}
		ret+=solve(n+1,i,u,ok||(i!=(s[n]-'0')),(md*10+i)%m);
	}
	return dp[n][pv][ud][ok][md]=ret%10000;
}
int main() {
	scanf("%s",a);
	alen=strlen(a);
	for(int i=alen-1;i>=0;i--) {
		if(a[i]>='1') {
			a[i]--;
			for(int j=i+1;j<alen;j++)a[j]='9';
			break;
		}
	}
	if(alen>=2&&a[0]=='0') {
		for(int i=1;i<=alen;i++)a[i-1]=a[i];
		alen--;
	}
	scanf("%s",b);
	blen=strlen(b);
	scanf("%d",&m);
	int aa,bb;
	s=b,slen=blen;
	memset(dp,-1,sizeof(dp));
	bb=solve(0,0,2,0,0);
	s=a,slen=alen;
	memset(dp,-1,sizeof(dp));
	aa=solve(0,0,2,0,0);
	printf("%d\n",(bb+10000-aa)%10000);
}

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

int main() {
	int W, H, N;
	cin >> W >> H >> N;

	int ldx = 0, ldy = 0, rux = W, ruy = H;

	for (int i = 0; i < N; i++) {
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1) {
			if (x > ldx) ldx = x;
		}
		else if (a == 2) {
			if (x < rux) rux = x;
		}
		else if (a == 3) {
			if (y > ldy) ldy = y;
		}
		else {
			if (y < ruy) ruy = y;
		}
	}
	if (rux < ldx || ruy < ldy) cout << 0 << endl;
	else cout << (rux - ldx) * (ruy - ldy) << endl;
}

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

int a;

int check(ll n){
	ll res = 0;
	if(n > a) return 0;

	string s = to_string(n);
	if(s.find('3')!=string::npos and s.find('5')!=string::npos and s.find('7')!=string::npos){
		res++;
		for(int i = 0; i < s.size(); i++){
			if(s[i]!='3' and s[i]!='5' and s[i]!='7'){
				res--;
				break;
			}
		}
	}

	res += check(n*10 + 3);
	res += check(n*10 + 5);
	res += check(n*10 + 7);

	return res;
}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> a;
	cout << check(0) << endl;

	return 0;
}

Measured memory_bytes: 256