akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

using namespace std;

#define INF (100000000)

typedef pair<int, int> P;

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

    vector<int> D;
    vector<P> DPAIR(M);
    for(int i=0; i<M; ++i) DPAIR[i]=P(i,0);
    for(int i=0; i<N; ++i) {
        int temp;
        cin >> temp;
        D.push_back(temp-1);
        ++DPAIR[temp-1].second;
    }

    vector<int> DD[M];

    for(int i=0; i<M; ++i) {
        DD[i].resize(N);
        DD[i][0]=(D[0]==i?1:0);
        for(int j=1; j<N; ++j) {
            DD[i][j]=DD[i][j-1]+(D[j]==i?1:0);
        }
    }

    string ALPHA="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string istr=ALPHA.substr(0,M);
    vector<int> indx(M+1);
    map<string,P> mp;

    for(int c=1; c<=M; ++c) {
        indx[c]=M;
        for(int i=0; i<c; ++i) indx[i]=i;
        --indx[c-1];
        while(indx[0]<M-c || c==M) {
            int now=c-1;
            while(indx[0]!=M-c || c==M) {
                if(indx[now+1]-indx[now]>1) {
                    ++indx[now];
                    break;
                } else if(indx[now]-indx[now-1]>1) {
                    ++indx[now-1];
                    for(int i=now; i<c; ++i) indx[i]=indx[i-1]+1;
                    break;
                } else {
                    --now;
                }
            }

            // main
            int cnt=INF;
            int len;
            for(int i=0; i<c; ++i) { // most back position's index
                string s="";
                for(int j=0; j<c; ++j) {
                    if(j==i) continue;
                    s.push_back(istr[indx[j]]);
                }
                if(s=="") {
                    cnt=min(cnt,DPAIR[indx[i]].second-DD[indx[i]][DPAIR[indx[i]].second-1]);
                    len=DPAIR[indx[i]].second;
                } else {
                    int fst=mp[s].first;
                    int snd=mp[s].second;
                    cnt=min(cnt,fst+DPAIR[indx[i]].second-DD[indx[i]][snd+DPAIR[indx[i]].second-1]+DD[indx[i]][snd-1]);
                    len=snd+DPAIR[indx[i]].second;
                }
           }
           string s="";
           for(int i=0; i<c; ++i) {
               s.push_back(istr[indx[i]]);
           }
           mp[s]=make_pair(cnt,len);

            if(c==M) break;
        }
    }

    cout << mp[istr].first << endl;
    return 0;
}


Measured memory_bytes: 138080
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<50;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

class Network{
	private:
	int V;
	struct edge{
		int to,cap,cost,rev;
	};
	vector<vector<edge> > g;
	vi h,d,pv,pe;
	public:
	Network(int v){
		V=v;
		g=vector<vector<edge> >(v);
	}
	void add_edge(int s,int t,int cap,int cost){
		g[s].push_back(edge{t,cap,cost,(int)g[t].size()});
		g[t].push_back(edge{s,0,-cost,(int)g[s].size()-1});
	}
	int min_cost_flow(int s,int t,int f){
		int res=0;
		h=pv=pe=vi(V);
		while(f>0){
			priority_queue<P> q;
			d=vi(V,inf);
			d[s]=0;
			q.push({0,s});
			while(!q.empty()){
				P p=q.top();
				q.pop();
				int v=p.second;
				if(d[v]<-p.first) continue;
				for(int i=0;i<g[v].size();i++){
					edge &e=g[v][i];
					if(e.cap>0&&d[e.to]>d[v]+e.cost+h[v]-h[e.to]){
						d[e.to]=d[v]+e.cost+h[v]-h[e.to];
						pv[e.to]=v;
						pe[e.to]=i;
						q.push({-d[e.to],e.to});
					}
				}
			}
			if(d[t]==inf) return -1;
			for(int i=0;i<V;i++) h[i]+=d[i];
			int D=f;
			for(int i=t;i!=s;i=pv[i]) D=min(D,g[pv[i]][pe[i]].cap);
			f-=D;
			res+=D*h[t];
			for(int i=t;i!=s;i=pv[i]){
				edge &e=g[pv[i]][pe[i]];
				e.cap-=D;
				g[i][e.rev].cap+=D;
			}
		}
		return res;
	}
};

int n,m,f;

int main(){
	cin>>n>>m>>f;
	Network net(n);
	for(int i=0;i<m;i++){
		int v,u,c,d;
		cin>>v>>u>>c>>d;
		net.add_edge(v,u,c,d);
	}
	cout<<net.min_cost_flow(0,n-1,f)<<endl;
}

Measured memory_bytes: 3224
#include <iostream>

using namespace std;

int main() {
  int n, m, X, Y;
  cin >> n >> m >> X >> Y;
  int mxx = X, mny = Y;
  for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    mxx = max(mxx, x);
  }
  for (int j = 0; j < m; ++j) {
    int y;
    cin >> y;
    mny = min(mny, y);
  }
  puts(mxx<mny?"No War":"War");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MAX 100002
typedef long long ll;
ll N, A[MAX], B[MAX];

int main(){
	scanf("%lld", &N);
	for(int i = 1; i <= N; i++){
		scanf("%lld %lld", A + i, B + i);
		A[i] %= B[i];
	}
	ll add = 0;
	for(int i = N; i >= 1; i--){
		A[i] = (add + A[i]) % B[i];
		add += (B[i] - A[i]) % B[i];
	}
	printf("%lld\n", add);
	return 0;
}

Measured memory_bytes: 1792
#include"bits/stdc++.h"
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a>b)swap(a,b);
	int flag=0;
	for(int i=a;i<=b;i++){
		if(abs(a-i)==abs(b-i)){
			flag=1;
			cout<<i<<endl;
		}
	}
	if(flag==0)cout<<"IMPOSSIBLE";
}

Measured memory_bytes: 256
def s():
 n,m=map(int,input().split())
 P=[[]for _ in[0]*n]
 C=[0]*n
 k=0
 for _ in[0]*m:
  s,t=map(int,input().split());P[s]+=[t];P[t]+=[s]
 for i in range(n):
  k+=1
  if C[i]<1:
   s=[i];C[i]=k
   while s:
    u=s.pop()
    for v in P[u]:
     if C[v]<1:C[v]=k;s+=[v]
 for _ in[0]*int(input()):
  a,b=map(int,input().split())
  print(['no','yes'][C[a]==C[b]])
if'__main__'==__name__:s()


Measured memory_bytes: 23900
n = int(input())
s = []
last_a = 0
first_b = 0
cnt = 0
both = 0
for i in range(n):
    ss = input()
    s.append(ss)
    if ss[0] == 'B':
        first_b += 1
    if ss[-1] == 'A':
        last_a += 1
    if ss[0] == 'B' and ss[-1] == 'A':
        both += 1
        last_a -= 1
        first_b -= 1

    for j in range(len(ss)-1):
        if ss[j] == 'A' and ss[j+1] == 'B':
            cnt += 1

sub = abs(first_b - last_a)
sub2 = both - sub
ans = cnt
if both == 0:
    ans += min(first_b,last_a)
elif first_b == last_a == 0:
    ans += max(0,both - 1)
else:
    ans += min(first_b,last_a) + min(sub,both) + max(0,sub2)

print(ans)


Measured memory_bytes: 3700
#!/usr/bin/env python3
import sys


def solve(P: int, Q: int, R: int):
    print(sum([P,Q,R])-max([P,Q,R]))



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    P = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    solve(P, Q, R)

if __name__ == '__main__':
    main()


Measured memory_bytes: 39704
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int main() {
	std::map<int, int> mp;
	for(int i = 0; i < 12; i++) {
		int a; cin >> a;
		mp[a]++;
	}
	
	for(auto v : mp) {
		if(v.second % 4) {
			cout << "no" << endl;
			return 0;
		}
	}
	cout << "yes" << endl;
	return 0;
}



Measured memory_bytes: 3124
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	int N;
	ll K;
	cin >> N >> K;
	vector<ll> A(N);
	REP(i, N) cin >> A[i];
	ll res = 0;
	REP(i, 40) {
		if ((K + 1) & (1LL << i)) {
			ll sum = 0;
			REP(j, 40) {
				if (j <= i) {
					ll tmp = 0;
					REP(k, N) tmp += A[k] & (1LL << j);
					if (j < i) tmp = max(tmp, N * (1LL << j) - tmp);
					sum += tmp;
				}
				else {
					REP(k, N) sum += (A[k] ^ (K + 1)) & (1LL << j);
				}
			}
			res = max(res, sum);
		}
	}

	cout << res << "\n";

	return 0;
}

Measured memory_bytes: 1024
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

//const ll MOD = 998244353;
const ll MOD = 1e9+7;
 
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll a,p;
  std::cin>>a>>p;
  std::cout<<(a*3+p)/2;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
         
    int main() {
        int K, N;
        cin >> K >> N;

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

        sort(vec, vec + N);

        int dif = 0;
        for (int i = 1; i < N; i++) {
            if(dif < (vec[i] - vec[i-1]))   dif = (vec[i] - vec[i-1]);
        }

        if(dif < K -(vec[N-1] - vec[0]))  dif = K -(vec[N-1] - vec[0]);

        cout << K - dif << endl;
    }

Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
   int x,y,i;
   for (i==0;i<=3000;i++){
    scanf("%d %d",&x,&y);
    if (x==0&&y==0) break;
    else if (x<y) printf("%d %d\n",x,y);
    else if (y<x) printf("%d %d\n",y,x);
    else printf("%d %d\n",x,y);

   }

    return 0;
}

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

int main() {
	int yj[30] = {};
	int unco[28] = {};
	int a;
	for(int i = 0; i < 30 ; i++){
		yj[i] = i + 1;
	}
	for(int i = 0; i < 28 ; i++){
		cin >> unco[i];
		a = unco[i];
		yj[a - 1] = 0;
	}
	for(int i = 0; i < 30 ; i++){
		if(yj[i] != 0)
			cout << yj[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define F first
#define S second

#define ALL(x)      (x).begin(), (x).end()
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#ifndef ONLINE_JUDGE
#define DBG(x)      cout << __LINE__ << " says: " << #x << " = " << (x) << endl
#else
#define DBG(x)
#define endl "\n"
#endif

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

#define int long long

const int nmax = 2e5+7;
const int mod = 1e9+7;

template <class T>
T bm(T b, T p, T m ) /// Faster than recursive one
{
    T res = 1 % m, x = b % m;
    while ( p )
    {
        if ( p & 1 )
            res = ( res * x ) % m;
        x = ( x * x ) % m;
        p >>= 1;
    }
    return res;
}

int32_t main()
{
    optimizeIO();

    int tc = 1;

    while(tc--)
    {
        int n;
        cin>>n;

        vector<int>v(n+1);
        for(int i=1;i<=n;i++) cin>>v[i];

        vector<int>cnt(n+1,0);

        bool ok = true;

        for(int i=1;i<=n;i++)
        {
            if((n%2) == (v[i]%2))
            {
                ok = false;
                continue;
            }

            int x = (n-v[i]-1)/2;
            int y = (n+v[i]-1)/2;

            cnt[x+1]++;
            cnt[y+1]++;

        }

        for(int i=1;i<=n;i++) if(cnt[i]!=2) ok = false;

        if(ok) cout<<bm(2LL,n/2,mod)<<endl;
        else cout<<0<<endl;
    }

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}


Measured memory_bytes: 4732
# coding: utf-8
DATA = """
2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

X, Y, A, B, C = [int(i) for i in get_line().strip().split(" ")]
p = [int(i) for i in get_line().strip().split(" ")]
q = [int(i) for i in get_line().strip().split(" ")]
r = [int(i) for i in get_line().strip().split(" ")]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p = p[:X]
q = q[:Y]

ret = p + q + r
ret.sort(reverse=True)

#print (ret[:X+Y], sum(ret[:X+Y]))
print (sum(ret[:X+Y]))


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

int main(){
  string a, b, c;
  cin >> a >> b >> c;
  if(*(a.end()-1)==*(b.begin()) && *(b.end()-1)==*(c.begin())){
    cout << "YES" << endl;
  }
  else cout << "NO" << endl;

  return 0;
}


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

#define fio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(a) a.begin(),a.end()
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define bloop(i,a,b) for (int i = a ; i >= b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define ll long long
#define pb push_back
#define sz(v) v.size()
#define pln(a)  cout<<a;
#define rr return 0;
#define rr1 return 1;
#define vr return;
#define int long long 

void solve()
{
  int n; cin>>n;
  int val = 1e18;
  vector<int>v(n);
  bool zero = false;
  
  for0(i, n) {
    cin>>v[i];
    if(v[i] == 0)
      zero = true;
  }
  
  if(zero) {
    cout<<"0";
    vr;
  }
  
  int prod = 1;
  for0(i, n) {
    if(prod <= val / v[i]) {
      prod *= v[i];
    }
    else {
      cout<<"-1";
      vr;
    }
  }
  
  cout<<prod;
}

signed main() {

  fio;
  
  
  //tc(t) {
    solve();
    pln("\n");
  //}
  
  rr;
}

Measured memory_bytes: 3992
let cnt = ref 0 
let (g : int list ref) = ref []
  
let insertion_sort (a : int array) n g =
  let rec insert j v =
    if j < 0 || a.(j) <= v then a.(j+g) <- v
    else (a.(j+g) <- a.(j); incr cnt; insert (j - g) v)
  and doit i =
    if i < n then (insert (i - g) a.(i); doit (i + 1))
  in doit g 

let generate_g n =
  let rec doit i g acc =
    if g > n then acc
    else doit (i + 1) (int_of_float (4.**(float_of_int i) +. 3.*.2.**(float_of_int (i - 1)) +. 1.)) (g :: acc)
  in doit 1 1 []
  
let shell_sort (a : int array) n =
  cnt := 0;
  g := generate_g n;
  let rec doit = function
    | [] -> ()
    | hd :: tl -> (insertion_sort a n hd; doit tl)
  in doit !g

let () =
  let n = read_int () in
  let a = Array.init n (fun _ -> read_int ()) in
  shell_sort a n; 
  Printf.printf "%d\n" (List.length !g);
  List.iteri (fun i n -> if i <> 0 then print_string " "; print_int n) !g;
  print_newline ();
  Printf.printf "%d\n" !cnt;
  Array.iter (fun n -> Printf.printf "%d\n" n) a

Measured memory_bytes: 12436
n, m, l = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
b = []
for _ in range(m):
    b.append(list(map(int, input().split())))

c = [[0]*l for _ in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            c[i][j] += a[i][k]*b[k][j]

for _c in c:
    print(*_c)


Measured memory_bytes: 7048
#include<bits/stdc++.h>
using namespace std;
vector< long long > v;
long long check(long long n,long long k)
{
    while(n%k==0)   n/=k;
    return n%k==1;
}
void cal(long long n,long long old)
{
    long long sq = sqrt(n);
    for(long long i=2;i<=sq;i++)
    {
        if(n%i==0)
        {
            if(check(old,i))  v.push_back(i);
            if(check(old,n/i))v.push_back(n/i);
        }
    }
    if(n!=1)    v.push_back(n);
}
int main()
{
    long long n;
    scanf("%lld",&n);
    cal(n,n),cal(n-1,n);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    printf("%d\n",v.size());
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
  int A[100];
  int i,j,v,N;
  scanf("%d",&N);
  for(i=0;i<N;i++) scanf("%d",&A[i]);
  for(i=0;i<N;i++)
    {
      v=A[i];
      j=i-1;
      while((j>=0)&&(A[j]>v))
	{
	  A[j+1]=A[j];
	  j--;
	}
      A[j+1]=v;
      for(j=0;j<N-1;j++) printf("%d ",A[j]);
      printf("%d\n",A[j]);
    }
  return 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
int modpow(int X,int Y){
  vi A;
  int sum=X;
  for(int i=1;i<=Y;i*=2){
    A.pb(sum);
    sum*=sum;
    sum%=MOD;
  }
  int M=A.size();
  int ret=1;
  REP(i,1,M){
    if(Y>=(1ll<<M-i)){
      ret*=A[M-i];
      ret%=MOD;
      Y-=(1ll<<M-i);
    }
  }
  return ret;
}
signed main(){
  int N; cin>>N;
  vi A(N);
  map<int,int> M;
  vector<map<int,int>> B(N);
  rep(i,0,N){
    cin>>A[i];
    int X=A[i];
    REP(j,2,sqrt(X)){
      while(X%j==0){
        X/=j;
        B[i][j]++;
        M[j]=max(M[j],B[i][j]);
      }
    }
    if(X>1){
      B[i][X]++;
      M[X]=max(M[X],B[i][X]);
    }
  }
  int ans=0;
  int sum=1;
  for(auto p:M){
    sum*=modpow(p.first,p.second);
    sum%=MOD;
  }
  rep(i,0,N){
    int sum2=sum;
    for(auto p:B[i]){
      int X=modpow(p.first,MOD-2);
      sum2*=modpow(X,p.second);
      sum2%=MOD;
    }
    ans+=sum2;
    ans%=MOD;
  }
  cout<<ans<<endl;
  }




Measured memory_bytes: 3968
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <iomanip>
#include <math.h>
#include <list>
#include <numeric>
using namespace std;

int main(){    
  int N;
  cin >> N;
  int X[N],sum=0;
  for(int i=0;i<N;i++){
    cin >> X[i];
    sum+=X[i];
  }
  int av=round((double)sum/(double)N),minn=0;
  for(int i=0;i<N;i++){
    minn += pow(X[i]-av,2);
  }
  cout << minn << endl; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using iii = pair<ii, ll>;
#define vt vector
#define pq priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)
// #define multicase
const ll MOD = 1e6;
const ll INF = 2e9;
// const ll N = ;

ll need, now, cur;

void solve() {
    ll T = 1;
  #ifdef multicase
    cin >> T;
  #endif
    while(T--) {
        cin >> need;
        now = 100, cur = 0;
        while(now < need) {
            now += now / 100;
            cur++;
        }
        cout << cur << "\n";
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    solve();
    
}

Measured memory_bytes: 3616
#define _USE_MATH_DEFINES
 
#pragma GCC optimize("Ofast,no-stack-protector") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("fast-math")
  
#include <bits/stdc++.h> 
  
using namespace std;
  
#define $(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
#define x first
#define y second    
// #define int long long
#define double long double       
#define vec vector            
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double> 
#define beg begin
#define print(x) cout << (x) << endl;
  
#ifdef LOCAL
    #define dbg(x) cerr << #x << " = " << x << endl;
#else 
    #define dbg(x)
#endif 
  
template<class T> ostream& operator<<(ostream &str, vector<T> &a) {
    for (auto &i : a) {
        str << i << " ";
    }
    return str;
}
  
template<class T> istream& operator>>(istream &str, vector<T> &a) {
    for (auto &i : a) {
        str >> i; 
    }
    return str;
}
  
template<class T> ostream& operator<<(ostream &str, pair<T, T> &a) {
    str << a.first << " " << a.second;
    return str;
}
  
template<class T> istream& operator>>(istream &str, pair<T, T> &a) {
    str >> a.first >> a.second;
    return str;
}
 
void solve(); signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);                                       
    // freopen("output.txt", "w", stdout);
#endif
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout.setf(ios::fixed); cout.precision(6);
    solve();   
    return 0;
}

void solve() {
    int n; 
    cin >> n;
    string s; 
    cin >> s;
    for (int i = 0; i < $(s); ++i) {
        int ord = s[i] - 'A';
        ord = (ord + n) % 26;
        s[i] = (char)('A' + ord);
    }

    print(s);
}




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 = (1 << 23);

int main() {

    int ans=0;
    string a,b;
    cin>>a>>b;
    rep(i,3){
        if(a[i]==b[i])ans++;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  float x1,y1,x2,y2,xq,yq,xm,ym,x,y,m,n;
  
  while(1){
    scanf("%f,%f,%f,%f,%f,%f",&x1,&y1,&x2,&y2,&xq,&yq);
    if(feof(stdin))break;
    
    if(y2-y1!=0&&x2-x1!=0){
      m=(y2-y1)/(x2-x1);
      n=-((x2-x1)/(y2-y1));
      
      xm=(m*x1-n*xq-y1+yq)/(m-n);
      ym=(-m*n*xq+m*yq+n*m*x1-n*y1)/(m-n);

      x=2*xm-xq;
      y=2*ym-yq;

    }else if(x2-x1!=0&&y2-y1==0){
      y=2*y1-yq;
      x=xq;
    }else if(x2-x1==0&&y2-y1!=0){
      y=yq;
      x=2*x1-xq;
    }else{
      exit(1);
    }
    
    printf("%f %f\n",x,y);
  }
  return(0);
}

Measured memory_bytes: 0
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n, m, cnt = 0;
	cin >> n >> m;
	vector<vector<char> > a(n, vector<char>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
			if (a[i][j] == '#') ++cnt;
		}
	}
	if (cnt != n + m - 1) { cout << "Impossible"; return 0; }
	pair<int, int> pr = { 0, 0 };
	while (pr.first != n - 1 && pr.second != m - 1) {
		if (a[pr.first][pr.second + 1] == '#') pr.second++;
		else if (a[pr.first + 1][pr.second] == '#') pr.first++;
		else {
			cout << "Impossible";
			return 0;
		}
	}
	cout << "Possible";
	return 0;
}

Measured memory_bytes: 3624
from collections import Counter
n=int(input())
a=Counter(list(map(int,input().split()))).most_common()
x=[0,0]

for i in range(len(a)):
  if x[1]<=a[i][0] and x[0]<=a[i][0] and a[i][1]>=4:
    x[0],x[1]=a[i][0],a[i][0]
  elif (x[1]<=a[i][0] or x[0]<=a[i][0]) and a[i][1]>=2:
    if x[0]<x[1]:
      x[0]=a[i][0]
    else:
      x[1]=a[i][0]
print(x[0]*x[1])


Measured memory_bytes: 97708
n = int(input())
houseInfo = [[0] * 10 for _ in range(12)]

for i in range(n):
    b, f, r, v = list(map(int, input().split()))
    # list上の基準(行)を計算
    base = ((b - 1) * 3) + (f - 1)

    houseInfo[base][r - 1] += v

count = 1
index = 0
while index < len(houseInfo):
    if count % 4 == 0:
        print("#" * 20)
    else:
        print(" ", end="")
        print(*houseInfo[index])
        index += 1

    count += 1


Measured memory_bytes: 5620
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num,init) vector<ll> name((num),(init));
#define op(i) cout<<(i)<<endl;
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define mat(name,fnum,snum,init); vector<vector<ll>> name((fnum),vector<ll>((snum),(init)));

int main(){
    ll n;
    cin>>n;
    vec(t,n+1,0);
    vec(x,n+1,0);
    vec(y,n+1,0);
    repf(i,1,n+1){
        cin>>t[i]>>x[i]>>y[i];
        if((abs(x[i]-x[i-1])+abs(y[i]-y[i-1])) >t[i]-t[i-1]){
            opN;
            return 0;
        }else if((abs(x[i]-x[i-1])+abs(y[i]-y[i-1])-(t[i]-t[i-1]))%2){
            opN;
            return 0;
        }
        
    }
    opY;
    return 0;

}

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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(9);
    /*start*/
    int n;
    cin>>n;
    vector<int>h(n);
    rep(i, n)cin>>h[i];
    vector<int>dp(n);
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    ffor(i, 2, n) {
        dp[i]=min((dp[i-2]+abs(h[i-2]-h[i])), (dp[i-1]+abs(h[i-1]-h[i])));
    }
    c(dp[n-1]);
}


Measured memory_bytes: 3920
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(ll i=0; i<n; ++i)
#define FOR(i,a,b) for(ll i=a; i<=b; ++i)
#define FORR(i,a,b) for (ll i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
int main() {
    int n;
    cin >> n;
    VVI a(n, VI(n-1));

    if (n == 2){
        cout << -1 << endl;
        return 0;
    }

    if (n % 2){
        REP(i,n){
            REP(j,n-1){
                a[i][j] = (i + j + 1) % n;
            }
        }
    }else{
        REP(i,n/2){
            REP(j,n-1) a[i][j] = (i + j + 1) % n;
        }
        FOR(i,n/2,n-1){
            REP(j,n/2-1) a[i][j] = (i + j + 1) % n;
            FOR(j,n/2-1,n-3) a[i][j] = (i + j + 2) % n;
            a[i][n-2] = (i + n/2) % n;
        }
    }


    REP(i,n){
        REP(j,n-1) cout << a[i][j]+1 << " ";
        cout << endl;
    }
    return 0;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s; cin>>s;
  ll n=s.size();
  vll ans(n);
  ll gu=0, ki=0;
  rep(i,n){
    if(s[i]=='L'){
      if(i%2){
        ans[i]+=ki;
        ans[i-1]+=gu;
      }else{
        ans[i]+=gu;
        ans[i-1]+=ki;
      }
      gu=ki=0;
    }else{
      if(i%2) ki++;
      else gu++;
    }
  }
  
  gu=0, ki=0;
  rrep(i,n){
    if(s[i]=='R'){
      if(i%2){
        ans[i]+=ki;
        ans[i+1]+=gu;
      }else{
        ans[i]+=gu;
        ans[i+1]+=ki;
      }
      gu=ki=0;
    }else{
      if(i%2) ki++;
      else gu++;
    }
  }
  rep(i,n) cout<<ans[i]<<endl;
}

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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

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

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll a(n);
  rep(i,n) cin>>a[i];
  reverse(all(a));
  bool ok=true;
  rep(i,n-1){
    if(a[i]<a[i+1]){
      a[i+1]--;
      if(a[i]<a[i+1])ok=false;
    }
  }
  if(ok)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}

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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;
const int BASE = 26;

int n;
char s[MAXN];
int cc[BASE];

void init ();
void input ();
void work ();



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%s", s );
}

void work ()
{
	// main work
	
	n = strlen ( s );
	lp ( i, 0, n ) ++cc[s[i]-'a'];
	
	LL ans = SC ( LL, n ) * ( n - 1 ) >> 1;
	lp ( i, 0, BASE ) ans -= SC ( LL, cc[i] ) * ( cc[i] - 1 ) >> 1;
	
	cout << ans + 1 << endl;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

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

	string S; cin >> S;
	int N = S.size();

	int ans1 = N;
	int ans2 = N;
	F0R(i, N) {
		if (S[i] == '1') ans1 = min(ans1, max(i, N-i-1));
		if (S[i] == '0') ans2 = min(ans2, max(i, N-i-1));
	}
	print(max(ans1, ans2));
}

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

struct info{
  int x;
  int y;
  ll h;
};

int main(){
  int n;
  cin>>n;
  info a[n];
  int cur;
  rep(i,0,n){
    int x,y;
    ll h;
    cin>>x>>y>>h;
    info b={x,y,h};
    a[i]=b;
    if(h>0) cur=i;
  }
  rep(i,0,101){
    rep(j,0,101){
      bool p=true;
      ll h=a[cur].h+abs(i-a[cur].x)+abs(j-a[cur].y);
      rep(k,0,n){
        if(max(h-abs(i-a[k].x)-abs(j-a[k].y),(ll)0)!=a[k].h){
          p=false;
        }
      }
      if(p){
        cout<<i<<" "<<j<<" "<<h<<endl;
      }
    }
  }
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
const long long MOD = 1000000007;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 1;
    vector<int> RGB(3, 0);
    rep(i, N) {
        int cnt = 0;
        rep(j, 3) {
            if (RGB[j] == A[i]) cnt++;
        }
        rep(j, 3) {
            if (RGB[j] == A[i]) {
                RGB[j]++;
                break;
            }
        }
        ans *= (ll)cnt;
        ans %= MOD;
    }

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


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

char mat[30][30];

int vis[30][30];
int n,m;
int res = 0;
    

void bfs(pair<int,int> s){
    memset(vis, -1, sizeof vis);
    queue<pair<int,int> > q;
    q.push(s);
    vis[s.first][s.second] = 0;
    
    while(q.size()){
        pair<int,int> c = q.front();
        q.pop();
        for(int i = -1; i <= 1; i++){
            for(int j = -1; j <= 1; j++){
                if((i == 0 || j == 0) && i != j) {
                    int ii = i + c.first;
                    int jj = j + c.second;
                    if(ii >= 0 && ii < n && jj >= 0 && jj < m && mat[ii][jj] == '.' && vis[ii][jj] == -1 ){
                        vis[ii][jj] = vis[c.first][c.second] + 1;
                        res = max(res, vis[ii][jj]);
                        q.push(make_pair(ii,jj));
                    }
                }
            }
        }
    }
}


int main() {
    
    scanf("%d %d", &n, &m);
    
    for(int i = 0; i < n; i++){
        scanf("%s", mat[i]);
    }
    
    
    for(int i = 0; i < n ; i++) {
        for(int j = 0; j < m; j++){
            if(mat[i][j] == '.'){
                 bfs(make_pair(i,j));
            }
        }
    }
    cout<<res<<endl;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
int N,A,B,C,D;
long long fa[1001];
long long modinv(long long a, long long m);
long long power(long long b, long long p);
void setting(int n);
unsigned long long groupsplit(int n,int r,int m);


int main()
{
    cin >> N >> A >> B >> C >> D;
    vector <vector <long long>> dp(B-A+2,vector <long long> (N+1));
    for (int i=0;i<B-A+2;i++)
    {
        for (int j=0;j<N+1;j++)
        {
            dp[i][j]=0;
        }
    }
    dp[0][0]=1;
    setting(1000);
    for (int i=1;i<B-A+2;i++)
    {
        for (int j=0;j<N+1;j++)
        {
            dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                for(int group=C;group<min(D+1,j/(A+i-1)+1);group++)
                {
                  dp[i][j]=(dp[i][j]+dp[i-1][j-(A+i-1)*group]*groupsplit(N-j+(A+i-1)*group,A+i-1,group))%mod;
                }
        }
    }
    cout << dp[B-A+1][N] << endl;
return 0;
}

long long modinv(long long a, long long m) 
{
    return power(a,m-2)%mod;
}

long long power(long long b, long long p)
{
    long long res = 1, a = b;
    for(; p; p >>= 1){
      if(p&1) res = res * a % mod;
      a = a * a % mod;
    }
    return res;
}

void setting(int n)
{
  fa[0]=1;
  for (int i=1;i<n+1;i++) fa[i]=i*fa[i-1]%mod;
  return;
}

unsigned long long groupsplit(int n,int r,int m)
{
  unsigned long long s;
  s=fa[n];
  s=s*modinv(fa[n-r*m],mod)%mod;
  s=s*modinv(power(fa[r],m),mod)%mod;
  return s*modinv(fa[m],mod)%mod;
}

Measured memory_bytes: 8064
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <math.h>
#include <queue>
using namespace std;
typedef long long int lli;
const long long int MaxN=200004;
const lli mod=1e9+7;
#define fst first
#define snd second
#define mp make_pair
const float pi=3.1415926535897932384626433832795028;
	lli mcd(lli a,lli b){
		if(a==0)return b;
		return mcd(b%a,a);
	}
	bool posible[MaxN];
	void solve(){
		lli N,i,j;
		cin>>N;
		posible[100]=1;
		posible[101]=1;
		posible[102]=1;
		posible[103]=1;
		posible[104]=1;
		posible[105]=1;
		for(i=106;i<=N;i++){
			posible[i]|=posible[i-100];
			posible[i]|=posible[i-101];
			posible[i]|=posible[i-102];
			posible[i]|=posible[i-103];
			posible[i]|=posible[i-104];
			posible[i]|=posible[i-105];
		}		
		cout<<posible[N];
	}
int main(){
	cin.tie(0),ios_base::sync_with_stdio(0);
	lli i,j,t;
	t=1;
	for(i=1;i<=t;i++){
		solve();
	}
}


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

#define int long long
#define rep(i,l,r) for(int i=(int)(l);i<(int)(r);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
template<class T>bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,T b){if(a>b){a=b;return 1;}return 0;}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int inf = 1LL<<60;
const int mod = 1e9 + 7;
const double eps = 1e-9;

/*{
}*/

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

	string s[n];
	rep(i, 0, n) cin >> s[i];

	int cnt = 0, a = 0, b = 0, ab = 0;
	for(auto t : s){
		int m = t.size();
		if(t[0] == 'B') b++;
		if(t[m-1] == 'A') a++;
		if(t[0] == 'B' and t[m-1] == 'A') ab++;

		rep(i, 0, m-1){
			if(t[i] == 'A' and t[i+1] == 'B') cnt++;	
		}
	}

//	cout << a << ", " << b << ", " << ab << endl;
	int ans = cnt + min(a, b) - (max(a, b) == ab and max(a, b) != 0);
	cout << max(0LL, ans) << endl;

	return 0;
}


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

int main()
{
    int N;
    cin >> N;
    int mat[N][N] = {};

    for (int i = 0; i < N; i++)
    {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++)
        {
            int v;
            cin >> v;
            mat[u - 1][v - 1] = 1;
        }
    }

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << mat[i][j];
            if (j != N - 1)
            {
                cout << " ";
            }
        }
        cout << endl;
    }
}



Measured memory_bytes: 3092
package main

import (
	"fmt"
)

func main() {
	var (
		a     string
		count = 0
	)
	fmt.Scan(&a)
	for i := 0; i < len(a); i++ {
		if a[i] == '1' {
			count++
		}
	}

	fmt.Println(count)
}


Measured memory_bytes: 1768
#include<bits/stdc++.h>
typedef long long ll;


using namespace std;
int main()
{
    int n , m;
    cin >> n >> m;
    ll a[n];
    priority_queue< ll > pq;
    for(int i = 0 ; i < n ; i++){
    	int x;
    	cin >> x;
    	pq.push(x);
    }
    for(int i = 0 ; i < m ; i++){
    	int x = pq.top();
    	x /= 2;
    	pq.pop();
    	pq.push(x);
    }
    ll sum = 0;
    for(int i = 0 ; i < n ; i++){
    	sum += pq.top();
    	pq.pop();
    }
    cout << sum << endl;
    return 0;
}



Measured memory_bytes: 1400
n,m=map(int,input().split())
h=list(map(int,input().split()))

gooddict={i:1 for i in range(1,n+1)}

for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]<=h[b-1]:  
    gooddict[a]=0
  if h[a-1]>=h[b-1]:
    gooddict[b]=0

count=0
for i in range(1,n+1):
  if gooddict[i]==1:
    count+=1
print(count)

Measured memory_bytes: 24544
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
}

func input() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	n, err := strconv.Atoi(input())
	if err != nil {
		log.Fatalln(err)
	}

	m, err := strconv.Atoi(input())
	if err != nil {
		log.Fatalln(err)
	}

	listA := make([]int, m)
	listB := make([]int, m)

	for i := 0; i < m; i++ {
		a, err := strconv.Atoi(input())
		if err != nil {
			log.Fatalln(err)
		}
		listA[i] = a

		b, err := strconv.Atoi(input())
		if err != nil {
			log.Fatalln(err)
		}
		listB[i] = b
	}

	listC := make([]int, n)
	for i := 0; i < m; i++ {
		listC[listA[i]-1]++
		listC[listB[i]-1]++
	}

	for i := 0; i < len(listC); i++ {
		fmt.Println(listC[i])
	}
}


Measured memory_bytes: 640
#!/usr/bin/env python3
import collections


def main():
    N = int(input())
    S = input()
    RGB = ('R', 'G', 'B')
    cnt = collections.Counter(S)
    ans = cnt['R'] * cnt['G'] * cnt['B']

    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] != S[j]:
                if 2 * j - i < N:
                    if S[2 * j - i] == RGB[3 - RGB.index(S[i]) - RGB.index(S[j])]:
                        ans -= 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9444
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5, mod = 1e9 + 7;

int n, m;
vector<int> v[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int t, c;
        cin >> t >> c;
        v[t].push_back(c);
    }
    priority_queue<int> pq;
    int ans = 0;
    for(int i = 1; i <= m; i++){
        while(v[i].size()){
            pq.push(v[i].back());
            v[i].pop_back();
        }
        if(pq.size()){
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans;

    return 0;

}



Measured memory_bytes: 5632
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static class UnionFind{
	    int[] par; // 
	    
	    public UnionFind(int n){
	        par = new int[n];
	        for(int i = 0; i < n; i++){ par[i] = -1; }
	    }
	    
	    public int find(int x){
	        if(par[x] < 0){
	            return x;
	        }else{
	            return par[x] = find(par[x]);
	        }
	    }
	    
	    public boolean union(int x, int y){
	        x = find(x);
	        y = find(y);
	        
	        if(x != y){
	            if(par[y] < par[x]) {  // 多い方が根になるようにスワップする.
	                int tmp = x; x = y; y = tmp;
	            }
	            par[x] += par[y];
	            par[y] = x;
	            return true;
	        }else{
	            return false;
	        }
	    }
	    
	    public boolean same(int x, int y){
	        return find(x) == find(y);
	    }
	    
	    public int size(int x){
	        return -par[find(x)];
	    }
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		final int n = sc.nextInt();
		final int q = sc.nextInt();
		
		UnionFind uf = new UnionFind(n);
		for(int i = 0; i < q; i++){
			final int com = sc.nextInt();
			final int x   = sc.nextInt();
			final int y   = sc.nextInt();
			
			if(com == 0){
				uf.union(x, y);
			}else{
				System.out.println(uf.same(x, y) ? 1 : 0);
			}
		}
		
		sc.close();
	}
	
	public static class Scanner {
	    private BufferedReader br;
	    private StringTokenizer tok;

	    public Scanner(InputStream is) throws IOException {
	        br = new BufferedReader(new InputStreamReader(is));
	    }

	    private void getLine() throws IOException {
	        while (!hasNext()) { tok = new StringTokenizer(br.readLine()); }
	    }

	    private boolean hasNext() {
	        return tok != null && tok.hasMoreTokens();
	    }

	    public String next() throws IOException {
	        getLine(); return tok.nextToken();
	    }

	    public int nextInt() throws IOException {
	        return Integer.parseInt(next());
	    }
	    // 他のnextXXXもXXX.parseXXX()メソッドを使って作れるので省略
	    
	    public void close() throws IOException {
	        br.close();
	    }
	}
}

Measured memory_bytes: 55048
s=input()
n=len(s)

def rle(string):
    tmp = string[0]
    cnt = 1
    ans = []
    for i in range(1, len(string)):
        if tmp == string[i]:
            cnt += 1
        else:
            ans.append(tmp)
            ans.append(cnt)
            tmp = string[i]
            cnt = 1
    ans.append(tmp)
    ans.append(cnt)
    return ans

rle_s=list(rle(s))
# print(rle_s)
ans=[0]*n
sum_cnt=0

for i in range(0,len(rle_s),4):
    r_num=int(rle_s[i+1])
    l_num=int(rle_s[i+3])
    odd_num=r_num//2+(l_num+1)//2
    even_num=r_num+l_num-odd_num

    ans[sum_cnt+r_num-1]=even_num
    ans[sum_cnt+r_num]=odd_num

    sum_cnt+=(r_num+l_num)
    # print(r_num, l_num, odd_num, even_num, sum_cnt)

print(*ans)


Measured memory_bytes: 7896