akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int N,M;
vector<int> L,R,X;

ll dp[2][303][303];
vector<pair<int,int>> v[303];

ll add(ll &a,ll b){
    a=(a+b)%MOD;
}

int main(){
  cin>>N>>M;
  L.resize(M);
  R.resize(M);
  X.resize(M);
  for(int i=0;i<M;i++) cin>>L[i]>>R[i]>>X[i];

  for(int i=0;i<M;i++) v[R[i]].push_back(mkp(L[i],X[i]));

  dp[0][0][0]=1;
  int t=0;
  for(int i=0;i<N;i++){
      for(int r=0;r<=i;r++){
          for(int g=0;g<=i;g++){
              if(dp[t][r][g]==0) continue;
              {//keep
                  int nr=r,ng=g;
                  bool ok=true;
                  for(int j=0;j<v[i+1].size();j++){
                      int l=v[i+1][j].first;
                      int x=v[i+1][j].second;
                      if(x==1&&ng<l) continue;
                      else if(x==2&&nr<l&&ng>=l) continue;
                      else if(x==3&&nr>=l) continue;
                      else{
                          ok=false;
                          break;
                      }
                  }
                  if(ok) add(dp[1-t][nr][ng],dp[t][r][g]);
              }
              {//r->i+1
                  int nr=g,ng=i;
                  bool ok=true;
                  for(int j=0;j<v[i+1].size();j++){
                      int l=v[i+1][j].first;
                      int x=v[i+1][j].second;
                      if(x==1&&ng<l) continue;
                      else if(x==2&&nr<l&&ng>=l) continue;
                      else if(x==3&&nr>=l) continue;
                      else{
                          ok=false;
                          break;
                      }
                  }
                  if(ok) add(dp[1-t][nr][ng],dp[t][r][g]);
              }
              {//g->i+1
                  int nr=r,ng=i;
                  bool ok=true;
                  for(int j=0;j<v[i+1].size();j++){
                      int l=v[i+1][j].first;
                      int x=v[i+1][j].second;
                      if(x==1&&ng<l) continue;
                      else if(x==2&&nr<l&&ng>=l) continue;
                      else if(x==3&&nr>=l) continue;
                      else{
                          ok=false;
                          break;
                      }
                  }
                  if(ok) add(dp[1-t][nr][ng],dp[t][r][g]);
              }
          }
      }
      for(int j=0;j<=i;j++) for(int k=0;k<=i;k++) dp[t][j][k]=0;
      t=1-t;
  }

  ll ans=0;
  for(int i=0;i<=N;i++) for(int j=0;j<=N;j++) add(ans,dp[t][i][j]);
  cout<<ans<<endl;

  return 0;
}


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

int Fib(int n) {

	long a[50] = { 1, 1 };

	if (n > 1) {
		for (int i = 2; i <= n; i++)
			a[i] = a[i - 1] + a[i - 2];
		return a[n];
	}
	else
		return 1;
}

int main()
{
	int n = 0;

	cin >> n;

	cout << Fib(n) << endl;

	return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define int long long
#define for1(i, n) for(int i = 1; i <= (n);i++)
using namespace std;
int d, c[30], l[30], s[400][30];
signed main() {
	cin >> d;
	for1(i, 26)cin >> c[i];
	for1(i, d)for1(j, 26)cin >> s[i][j];
	for1(i, d) {
		int p = 0, k = -100000007;
		for1(j, 26) {
			int kj = s[i][j] + c[j] * (i - l[j]) * 6.2 + c[j] * 5.2;
			if (kj > k) { p = j; k = kj; }
			else if (kj == k && c[j] > c[p])p = j;
		}
		cout << p << "\n"; l[p] = i;
	}
}

Measured memory_bytes: 3720
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
D=get_i
kind=Hash.new(0)
D.each do|d|
    kind[d]+=1
end
M=gets.to_i
T=get_i
T.each do|t|
    if kind[t]>0
        kind[t]-=1
    else
        puts "NO"
        exit
    end
end
puts "YES"

Measured memory_bytes: 53040
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
		tree_order_statistics_node_update> ordered_set;

#define el				'\n'
#define sz(v)			((int)((v).size()))
#define all(v)          ((v).begin()),((v).end())
#define clr(v, d)		memset(v, d, sizeof(v))

double const EPS = 1e-8, PI = acos(-1);
const int N = 3e5 + 9, M = 1e4 + 9, OO = (int) 2e9 + 1;
const long long MOD = 1e9 + 7, INF = 1e18 + 9;

typedef long long ll;

void OUTPUT() {
	cout << fixed << setprecision(0);
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

void INPUT() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
}

int n;
ll ans, arr[N];
ll zeroCnt[109], binRep[109];

int getBit(ll num, ll idx) {
	return ((num >> idx) & 1) == 1;		// 110100, idx = 4  -->  110 & 1 = 0
}

ll POW(ll a, ll k, ll M) {
	if (k == 0)
		return 1;
	ll r = POW(a, k / 2, M);
	r = (r * r) % M;
	if (k % 2)
		r = (r * a) % M;
	return r;
}

int main() {
//	INPUT();
	OUTPUT();
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		for (int j = 0; j < 61; j++) {
			if (!getBit(arr[i], j))
				zeroCnt[j]++;
		}
	}

	for (int i = 0; i < 100; i++) {
		ll x = zeroCnt[i] * (n - zeroCnt[i]);
		for (int j = 0; j < 61; j++) {
			if (getBit(x, j)) {

				binRep[j + i] = (1 + binRep[j + i] % MOD) % MOD;
			}
		}
	}
	for (int i = 0; i < 100; i++) {
		if (binRep[i]) {
			ll vvvv = (POW(2, i, MOD) % MOD * binRep[i] % MOD) % MOD;
			ans = (ans % MOD + vvvv % MOD) % MOD;
		}
	}
	cout << ans % MOD << el;

	return 0;

}

Measured memory_bytes: 2560
#include<iostream>
#include<cmath>
#include<map>
#include<deque>
#include<string>
#include<algorithm>

#define all(x) (x).begin(),(x).end()
#define puts(x) cout<< x << endl;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define fore(i,a) for(auto i:a)
#define ll long long
using namespace std;
int n;
int p[8],q[8];
int v[8];
int pcount,qcount;
int pcountf,qcountf;
int main(){
    cin>>n;
    rep(i,0,n)cin>>p[i];
    rep(i,0,n)cin>>q[i];
    rep(i,0,n)v[i]=i+1;
    
    do{
        int pfrag=0;
        int qfrag=0;
        rep(i,0,n){
          if(v[i]!=p[i]){
            pfrag=1;
          }
          if(v[i]!=q[i]){
            qfrag=1;  
          }
        }
        
        
        if(pfrag==0){
            pcountf=1;
        }else if(pcountf==0){
            pcount++;
        }
        
        if(qfrag==0){
            qcountf=1;
        }else if(qcountf==0){
            qcount++;
        }
    }while(next_permutation(v,v+n));
    
    
    //puts(pcount);
    puts(abs(pcount-qcount));
}

Measured memory_bytes: 256
s = raw_input().strip()
N = len(s)
l = [int(c) for c in s]

nl = []
i = 0
while i < N:
    if len(nl) > 0:
        a = nl[-1]
        b = l[i]

        if a + b == 1:
            nl.pop()
            i += 1
        else:
            nl.append(l[i])
            i += 1
    else:
        nl.append(l[i])
        i += 1

print N - len(nl)

Measured memory_bytes: 38556
#include <iostream>

using namespace std;

int main()
{

    int p=0;
    int q=0;
    int r=0;
    int v=0;
    int b=0;
    int m=0;
    int l=0;
    cin>>p;
    cin>>q;
    cin>>r;
    if((p==q)&&(p==r)){
    l=p+q;
    goto me;
}
else if(((p==q)&&(p!=r))&&p>r){

    l=p+r;
    goto me;
}
else if(((p==q)&&(p!=r))&&p<r){
    l=p+q;
    goto me;
}
else if(((p==r)&&(p!=q))&&p>q){
    l=p+q;
    goto me;
}
else if(((p==r)&&(p!=q))&&p<q){
    l=p+r;
    goto me;
}
else if(((r==q)&&(r!=p))&&r>p){
l=p+r;
    goto me;
}
else if(((r==q)&&(r!=p))&&r<p){
   l=r+q;
    goto me;
    }



        else if(p<q&&p<r){
            m=p;
         }

         else if(q<p&&q<r){
            m=q;
         }

          else if(r<p&&r<q){
            m=r;
         }
        if((p<q&&p>r)||(p<r&&p>q)){

            b=p;
         }
         else if((q<p&&q>r) || (q<r&&q>p)){
            b=q;
         }
         else if((r<q&&r>p) || (r<p&&r>q)){
            b=r;
         }



l=m+b;
me:
cout << l;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define vll vector<ll>
#define uset unordered_set<string>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll n, k, ans = 0, diff;
    cin >> n >> k;
    
    diff = n-k;
    ans = abs(diff)%k;
    ll temp = abs(ans - k);
    if(temp < ans){
        ans = abs(ans-k);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
n=int(input())
t,a=map(int,input().split())
h = list(map(int,input().split()))

min=abs(t-h[0]*0.006-a)
ans=1
for i in range(n):
  x=abs(t-h[i]*0.006-a)
  if x<min:
    min = x
    ans=i+1
print(ans)

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

int main() {
  string s, t;
  cin >> s;
  cin >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if (s < t) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 888
A = list(input().split())


if __name__ == '__main__':
    stack = []
    for item in A:
        if str.isdecimal(item):
            stack.append(int(item))
        else:
            b = stack.pop()
            a = stack.pop()
            if item == "+":
                sum = a + b
                stack.append(sum)
            elif item == "-":
                diff = a - b
                stack.append(diff)
            elif item == "*":
                multi = a * b
                stack.append(multi)
            else:
                print("invalid item")
    print(stack.pop())


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

using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> adj[n+1];
	vector<int> indegree(n+1, 0);

	for(int i=0;i<m;i++){
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		indegree[v]++;
	}
	
	vector<int> dist(n+1, INT_MIN);
	vector<bool> visited(n+1, false);
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(indegree[i]  == 0){
			q.push(i);
			dist[i] = 0;
		}
	}

	while(!q.empty()){
		int cur = q.front();
		q.pop();
		visited[cur] = true;

		for(int i: adj[cur]){
			if(!visited[i]){
				if(dist[i] < dist[cur] + 1){
					dist[i] = dist[cur] + 1;
				}
				if(--indegree[i] == 0){
					q.push(i);
				}
			}
		}
	}
	
	cout << *max_element(dist.begin(), dist.end());
	return 0;
}

Measured memory_bytes: 9348
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        if(a+b > c+d){
            System.out.println("Left");
        }else if(a+b == c+d){
            System.out.println("Balanced");
        }else{
            System.out.println("Right");
        }
        
    }
}

Measured memory_bytes: 21844
/*dismint|jjc*/
#include <bits/stdc++.h>
using namespace std;
#define forl(V, S, E) for(int V = S; V < E; V++)
#define ford(V, S, E) for(int V = S; V >= E; V--)
#define fore(E, X) for(auto &E:X)
#define println(X) cout << X << endl
#define printe(X) for(auto &E:X) cout << E << " "; cout << endl
typedef unordered_map<int, unordered_set<int>> graph;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s; cin >> s;
	if(s == "ABC") println("ARC");
	else println("ABC");
}


Measured memory_bytes: 3652
import numpy as np
n=int(input())
a=list(map(int, input().split()))

if np.gcd.reduce(a) != 1:
    print('not coprime')
    exit()

m=max(a)
cnt=[0]*(m+1)

for i in range(len(a)):
    cnt[a[i]]+=1
#print(cnt)
for i in range(2, m + 1):
    #print(cnt[i::i])
    if sum(cnt[i::i]) > 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')


Measured memory_bytes: 145256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
#include <cstdio>

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



int main(){
    string s;
    cin>>s;
    
    int ans=0;
    sort(all(s));
    
    int i=0;
    while(1){
        int c=1;
        char ch = s[i];
        s[i] = '*';
        rep(j,s.size()){
            if(s[j]==ch+1){
                c++;
                ch = s[j];
                s[j] = '*';
            }
        }
        if(c>=3){
            ans+=3;
        }
        else ans+=c;
        bool f=true;
        rep(j,s.size()){
            if(s[j]!='*')f=false;
        }
        if(f)break;
        i++;
        while(i<s.size() && s[i]=='*')i++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1204
# coding=utf-8


def all_equal(num_list):
    return all([num_list[0] == num for num in num_list])


def self_injure(num_list):
    if all_equal(num_list):
        return num_list[0]
    if 1 in num_list:
        return 1
    hp_min = min(num_list)
    num_list2 = [hp_min if num % hp_min == 0 else num % hp_min for num in num_list]
    return self_injure(num_list2)


if __name__ == '__main__':
    N = int(input())
    monsters_hp = list(map(int, input().split()))
    hps = monsters_hp[:]

    print(self_injure(hps))


Measured memory_bytes: 14228
#include <bits/stdc++.h>
using namespace std;
using Int = long long unsigned;
typedef pair<int,int> P;
typedef priority_queue<int> Pr;
Int const MOD = 1000000007;
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; }


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

    Int n,k; Int ans=0; cin>>n>>k; int a[n]; Int b[n]={},c[n]={};
    for (int i = 0; i < n; i++)cin>>a[i];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(j<i&&a[i]>a[j])b[i]++;
            else if(j>i&&a[i]>a[j])c[i]++;
        }
    }
    Int kb=((k*(k-1))/2)%MOD,kc=(((k+1)*k)/2)%MOD;
    for (int i = 0; i < n; i++)ans=(ans+b[i]*kb+c[i]*kc)%MOD;
    cout<<ans<<'\n';
}

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

using namespace std;

typedef long long LL;

const int mod = 998244353;

struct Matrix{
    LL x[2][2];
    Matrix operator * (Matrix A){
        Matrix C;
        for(int i=0; i<2; i++){
			for(int j=0; j<2; j++){
				LL &t = C.x[i][j];
				t = 0;
				for(int k=0; k<2; k++){
					t = t + x[i][k] * A.x[k][j] % mod;
				}
				t %= mod;
			}
        }
        return C;
    }
};

Matrix pow(Matrix A, LL p){
    Matrix S;
    for(int i=0; i<2; i++){
		for(int j=0; j<2; j++){
			S.x[i][j] = i==j?1:0;
		}
    }
    while(p){
		if(p & 1)	S = S * A;
		A = A * A;
		p >>= 1;
    }
    return S;
}

LL Fab(LL p){
	if(p == 0){
		return 0;
	}
    if(p <= 2){
		return 1;
    }
    Matrix A;
    A.x[0][0] = A.x[0][1] = A.x[1][0] = 1;
    A.x[1][1] = 0;
    A = pow(A, p - 2);
    return (A.x[0][0] + A.x[1][0]) % mod;
}

LL rev(LL x){
    int p = mod - 2;
    LL s = 1;
    while(p){
		if(p & 1)	s = s * x % mod;
		x = x * x % mod;
		p >>= 1;
    }
    return s;
}

int n;
LL m;

int main(){
    while(~scanf("%d %lld", &n, &m)){
        LL sum = Fab(2 * (n - 1));
        int k = n - 2;
        LL g = 1;
        for(int i=1; i<=k; i++){
			g = (m + i - 1) % mod * g % mod * rev(i) % mod;
            sum = sum + g * Fab(2 * (k - i + 1)) % mod;
            sum = sum % mod;
        }
        sum = Fab(m + 2*(n - 1)) - sum;
        sum = (sum % mod + mod) % mod;
        printf("%lld\n", sum);
    }
	return 0;
}


Measured memory_bytes: 256
c1=list(map(int,input().split()))
c2=list(map(int,input().split()))
c3=list(map(int,input().split()))

if(c1[0]-c2[0]==c1[1]-c2[1] and c1[1]-c2[1]==c1[2]-c2[2] and c3[0]-c2[0]==c3[1]-c2[1] and c3[1]-c2[1]==c3[2]-c2[2] and c1[0]-c3[0]==c1[1]-c3[1] and c1[1]-c3[1]==c1[2]-c3[2]):
    print("Yes")
else:
    print("No")

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

int main()
{
	long a=0 , b=0 , c=0 , n=0 , A=0 ;
	a=1000000 ;
	b=-1000000 ;
	cin >> n ;
	for(int i=0 ; i<n ; i++ )
	{
		cin >> A ;

		if (a>A) a=A ;
		if (b<A) b=A ;

		c+=A ;
	}
	cout << a << " " << b << " " << c << endl ;
	return 0 ;
}



Measured memory_bytes: 3076
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cmath>
#include <map>
#define ull unsigned long long
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    map<string,int> mp;
    int n,m;
    string s,t;
    vector<string> h;
    cin >> n;
    int ans=0;
    for(int i=0;i<n;i++){
        cin >> s;
        h.push_back(s);
        mp[s]++;
    }
    cin >> m;
    for(int i=0;i<m;i++){
        cin >> t;
        mp[t]--;
    }
    for(int i=0;i<n;i++){
        ans=max(mp[h[i]],ans);
    }
    cout << ans << endl;
    
    return 0;
}

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

long long int ncr[55]={0};

void set_ncr(long long int n){
    ncr[0] = 1;
    for(long long int r=1;r<=n;++r){
        ncr[r] = ncr[r-1] * (n - r + 1) / r;
    }
}

int main(){
    long long int n, a, b;
    cin >> n >> a >> b;
    vector<long long int> v;
    map<long long int, int> bucket;
    for(int i=0;i<n;++i){
        long long int tmp;
        cin >> tmp;
        v.push_back(tmp);
        bucket[tmp]++;
    }
    sort(v.rbegin(), v.rend());
    double avg = v[0];
    set<long long int> st;
    st.insert(v[0]);
    long long int c = 1;
    for(int i=1;i<a;++i){
        avg = (avg * i) / (double)(i + 1) + v[i] / (double)(i + 1);
        st.insert(v[i]);
        if(v[i-1] == v[i])c++;
        else c = 1;
    }
    long long int num = 1;
    if(bucket[v[a-1]] > 1){
        if(st.size() == 1){
            set_ncr(bucket[v[a-1]]);
            num = 0;
            for(int i=a;i<=b;++i)num += ncr[i];
        }else{
            set_ncr(bucket[v[a-1]]);
            num = ncr[c];
        }
    }

    printf("%.10f\n", avg);
    cout << num << endl;

    return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn.{readInt, readLine};

object Main {
    def main(args: Array[String]): Unit = {
        val n = readInt;
        val tree = new TreeWalk(n);
        for (i <- (0 until n)) {
            val line = readLine.split(" ").map(_.toInt);
            tree.add(line(0), line(1), line(2));
        }
        println("Preorder");
        println(" " + tree.preorder.mkString(" "));
        println("Inorder");
        println(" " + tree.inorder.mkString(" "));
        println("Postorder");
        println(" " + tree.postorder.mkString(" "));
    }
}
class TreeWalk(size: Int) {
    case class Node(id: Int, var parent: Node, var left: Node, var right: Node);
    val tree = new Array[Node](size);
    lazy val root: Option[Node] = tree.find(a => a != null && a.parent == null);
    def add(id: Int, left: Int, right: Int): Unit = {
        if (tree(id) == null) tree(id) = Node(id, null, null, null);
        if (left != -1) {
            if (tree(left) == null) tree(left) = Node(left, null, null, null);
            tree(left).parent = tree(id);
            tree(id).left = tree(left);
        }
        if (right != -1) {
            if (tree(right) == null) tree(right) = Node(right, null, null, null);
            tree(right).parent = tree(id);
            tree(id).right = tree(right);
        }
    }
    def preorder: List[Int] = {
        def go(curr: Node, ret: List[Int]): List[Int] = {
            if (curr == null) {
                ret;
            } else {
                val ret1 = curr.id :: ret;
                val ret2 = go(curr.left, ret1);
                val ret3 = go(curr.right, ret2);
                ret3;
            }
        }
        root match {
            case None => Nil;
            case Some(r) => go(r, Nil).reverse;
        }
    }
    def inorder: List[Int] = {
        def go(curr: Node, ret: List[Int]): List[Int] = {
            if (curr == null) {
                ret;
            } else {
                val ret1 = go(curr.left, ret);
                val ret2 = curr.id :: ret1;
                val ret3 = go(curr.right, ret2);
                ret3;
            }
        }
        root match {
            case None => Nil;
            case Some(r) => go(r, Nil).reverse;
        }
    }
    def postorder: List[Int] = {
        def go(curr: Node, ret: List[Int]): List[Int] = {
            if (curr == null) {
                ret;
            } else {
                val ret1 = go(curr.left, ret);
                val ret2 = go(curr.right, ret1);
                val ret3 = curr.id :: ret2;
                ret3;
            }
        }
        root match {
            case None => Nil;
            case Some(r) => go(r, Nil).reverse;
        }
    }
}


Measured memory_bytes: 44080
///   ***   ---   |||		 In the name of ALLAH		|||   ---   ***   ///



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


typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {			cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

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


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

const int mx = 2e5+123;
int a[mx], n , k;


bool check ( int num )
{
	int c = 0;
	for ( int i = n; i >= 1; i-- ) {

		if ( a[i] > num ) {
			if ( c >= k ) return 0;
			c += ( a[i] / num );
			c += ( a[i] % num != 0 );
			c--;
			if ( c > k ) return 0;
		}
		else break;
	}

	return 1;
}

int main()
{
	optimize();

	cin >> n >> k;


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

	sort ( a+1, a+n+1 );


	ll l = 1, r = 2e9;

	//dbg ( check(4) );

	ll ans = inf;
	while ( l <= r ) {
		ll mid = ( l + r ) >> 1;

		if ( check ( mid ) ) {
			ans = min ( ans, mid );
			r = mid-1;
		}
		else l = mid+1;
	}

	cout << ans << endl;

	return 0;
}


















Measured memory_bytes: 4416
#include <cstdio>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
typedef long long ll;

using namespace std;
int main(){
    ll n;
    cin >> n;
    cout<<(n*(n-1))/2<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b, c, k = list(map(int, readline().split()))
    if a + b >= k:
        print(min(a, k))
    else:
        print(a - (k - a - b))


if __name__ == '__main__':
    main()


Measured memory_bytes: 61692
import java.util.Scanner;

class Main{
    public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	
    	int a, b, c, d;
    	int week;
    	while (scan.hasNextInt()){
    		int num = scan.nextInt();
    		int count = 0;
    		for(int i = 0; i < 10; i++){
    			for(int j = 0; j < 10; j++){
    				for(int x = 0; x < 10; x++){
        				for(int y = 0; y < 10; y++){
        					if(i+j+x+y == num){
        						count++;
        					}
        				}
        			}
    			}    			
    		}
    		System.out.println(count);
    	}
    }
}

Measured memory_bytes: 18856
#include<bits/stdc++.h>
using namespace std;
#define A first
#define B second
int main(){
  pair<int,int> x[6];
  for(int i=0;i<6;++i){
    cin>>x[i].A>>x[i].B;
    if(x[i].A>x[i].B) swap(x[i].A,x[i].B);
  }
  sort(x,x+6);
  pair<int,int> y[3];
  for(int i=0;i<6;i+=2){
    if(x[i]==x[i+1]) y[i/2]=x[i];
    else{ cout<<"no\n"; return 0; }
  }
  if(y[0].A==y[1].A && y[1].B==y[2].B && y[2].A==y[0].B) cout<<"yes\n";
  else cout<<"no\n";
  return 0;
}

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

int main() {
  int n, s, f;
  cin >> n;
  vector<int> v(n);
  priority_queue<int> pq;
  rep(i, n){
    cin >> v[i];
    pq.push(v[i]);
  }
  f = pq.top();
  pq.pop();
  s = pq.top();
  rep(i, n){
    if(v[i] == f) cout << s << endl;
    else cout << f << endl;
  }
  return 0;
}

Measured memory_bytes: 3316
/*input
23
00110111001011011001110
*/

// Nihesh Anderson - knandy

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
ll MOD=1000000007;

#define endl '\n'
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back
ll INF = 2000000000000000001;
long double EPS = 1e-9;
ll power(ll a, ll n, ll md){if(n==0){return 1;}else{ll res=power(a,n/2,md);res=(res*res)%md;if(n%2!=0){res=(res*a)%md;}return res;}}
random_device rndm;
mt19937 grndm(rndm());
void mix(ll* a, ll* b){shuffle(a,b,grndm);}

int main(){
	fast_cin();
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
	ll n; cin >> n;
	string s; cin >> s;
	ll popcount = 0;
	for(auto c: s) {
		popcount += (c == '1');
	}
	map<ll, ll> md, pwr; 
	vector<ll> residues = {popcount - 1, popcount + 1};
	for(auto r: residues) {
		pwr[r] = 1;
	}
	for(ll i = n - 1; i >= 0; i--) {
		if(s[i] == '1') {
			for(auto r: residues) {
				if(r <= 0) continue;
				md[r] = (md[r] + pwr[r]) % r;
			}
		}
		for(auto r: residues) {
			if(r <= 0) continue;
			pwr[r] = (2 * pwr[r]) % r;
		}
	}
	vector<ll> ans;
	for(auto r: residues) {
		pwr[r] = 1;
	}
	for(ll i = n - 1; i >= 0; i--) { 
		if(s[i] == '1') {
			ll r = popcount - 1;
			if(r == 0) {
				ans.push_back(0);
			}
			else {
				ll rem = (md[r] - pwr[r] + r) % r;
				ll cnt = 1;
				while(rem) {
					cnt++;
					rem %= __builtin_popcount(rem);
				} 
				ans.push_back(cnt);
			}
		}	
		else {
			ll r = popcount + 1;
			ll rem = (md[r] + pwr[r]) % r;
			ll cnt = 1;
			while(rem) {
				cnt++;
				rem %= __builtin_popcount(rem);
			}
			ans.push_back(cnt);
		}
		for(auto r: residues) {
			if(r <= 0) continue;
			pwr[r] = (2 * pwr[r]) % r;
		}
	}
	reverse(ans.begin(), ans.end());
	for(ll i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}




















Measured memory_bytes: 5528
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n = int(input())

print((n-1) * n // 2)

Measured memory_bytes: 38460
n=int(input())
f=[0 for i in range(n)]
for i in range(n):
    fi=int("".join(list(input().split())),2)
    f[i] = fi
p=[[] for i in range(n)]
for i in range(n):
    pi=list(map(int,input().split()))
    p[i] = pi
ans=-9999999999999
for i in range(1,1024):
    bene=0
    for j in range(n):
        c = str(bin(i & f[j])).count("1")
        bene+=p[j][c]
    if(ans < bene):
        ans = bene
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={1,0,-1,0,1,-1,-1,1};
int dy[]={0,1,0,-1,1,1,-1,-1};
const int MOD = 1e9+7;
const long long INF = 1e18+10;

/*--------------------------------------------------------------------*/

signed main(){	
	int n,c,k;
	cin>>n>>c>>k;
	vi t(n);
	rep(i,n)cin>>t[i];
	sort(all(t));

	int ans=1;
	int cnt=0;
	int tmp=t[0];

	rep(i,n){
		cnt++;
		if(cnt>c){
			ans++;
			tmp=t[i];
			cnt=1;
		}else if(t[i]-tmp>k){
			ans++;
			tmp=t[i];
			cnt=1;
		}
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 3944
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define FOR(i,n,m) for(int i=n;i<=(int)(m);i++)
#define RFOR(i,n,m) for(int i=(int)(n);i>=m;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
vector<int> dy={1,0,-1,0};
vector<int> dx={0,1,0,-1};
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
int main(){
    int n,m;
    cin>>n>>m;
    
    vector<vector<int>> children(n);
    deque<int> ans;
    vector<bool> check(n,false);
    
    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;b--;
        if(i==0){
            ans.push_back(a);
            ans.push_back(b);
            check[a]=true;
            check[b]=true;
        }
        children[a].push_back(b);
        children[b].push_back(a);
    }
    
    while(true){
        int x=ans.front();
        int y=ans.back();
        
        bool ok=true;
        
        for(int child:children[x]){
            if(!check[child]) ok=false;
        }
        for(int child:children[y]){
            if(!check[child]) ok=false;
        }
        
        if(ok){
            cout<<sz(ans)<<endl;
            for(int k:ans) cout<<k+1<<endl;
            return 0;
        }
        
        bool go=false;
        for(int child:children[x]){
            if(!check[child]) {
                check[child]=true;
                ans.push_front(child);
                go=true;
                break;
            }
        }
        
        if(go) continue;
        
        for(int child:children[y]){
            if(!check[child]) {
                check[child]=true;
                ans.push_back(child);
                break;
            }
        }
        
    }
    
}




Measured memory_bytes: 6656
#include <iostream>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
using namespace std; typedef long long ll; const int MINF=-1e9; typedef pair<int,int> P;

int main() {
  int r,g,b,n; cin>>r>>g>>b>>n;
  int an=0;
  for(int i=0;i<=n;i+=r) {
    for(int j=0;i+j<=n;j+=g){
      if ((n-i-j)%b==0) an++;
    }
  }
  cout<<an<<endl;
}

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

#define INF (1e9)
#define MOD (1e9 + 7)
#define LINF (1e18)
ll n,x,y,m,k,ans,cnt,mini=N,flag;
ll w[N],v[N],b[N];
//vector< pair< ll,ll > > v;
string s;
map<char,ll>mp;
int main()
{
    ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n>>m;
    for(ll i=0;i<n;i++)
        cin>>w[i]>>v[i];

    ll max_v = 100000;
    vector<ll> dp(max_v + 1, LINF);

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = max_v; j >= 0; j--) {
            if (j - v[i - 1] >= 0)
                dp[j] = min(dp[j], dp[j - v[i - 1]] + w[i - 1]);
        }
    }

    ll ans = 0;
    for (int i = 0; i <= max_v; i++) {
        if (dp[i] <= m)
            ans = max(ans, (ll)i);
    }

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mp(x,y) make_pair(x,y)
const int nax=1e6+5;

void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    if(s.size() <= n) cout<<s<<'\n';
    else cout<<s.substr(0,n)+"...\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int tc;
    tc=1;
    while(tc--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3608
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#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)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int mul(int x, int y){
  if(x == 0 || y == 0) return 0;
  if(x == 2 && y == 2) return 2;
  return 1;
}

int add(int x, int y){
  if(x == 0 && y == 0) return 0;
  if(x == 2 || y == 2) return 2;
  return 1;
}

int neg(int x){
  return 2 - x;
}

int parse(string& str, int a, int b){
  int left = -1, right = -1;
  int s, cnt = 0, op = 0, n = 1;
  for(int i=a;i<b;++i){
	switch(str[i]){
	case '(':
	  if(cnt++ == 0) s = i+1;
	  break;
	case ')':
	  --cnt;
	  if(cnt == 0){
		if(left == -1)
		  left = (n < 0? neg(parse(str, s, i)): parse(str, s, i));
		else
		  right = (n < 0? neg(parse(str, s,i)): parse(str, s,i));
	  }
	  break;
	case '0': case '1': case '2':
	  if(cnt == 0){
		int d = str[i] - '0';
		if(left == -1)
		  left = (n < 0? neg(d): d);
		else
		  right = (n < 0? neg(d): d);
	  }
	  break;
	case '-':
	  if(cnt == 0) n *= -1;
	  break;
	case '+':
	  if(cnt == 0) n = 1, op = 1;
	  break;
	case '*':
	  if(cnt == 0) n = 1, op = 2;
	  break;
	}
  }
  if(right == -1)
	return left;
  else{
	if(op == 1)
	  return add(left, right);
	return mul(left, right);
  }
}

string rep(string& s, int p, int q, int r){
  string ret = s;
  for(int i=0;i<SZ(ret);++i){
	if(ret[i] == 'P') ret[i] = p+'0';
	if(ret[i] == 'Q') ret[i] = q+'0';
	if(ret[i] == 'R') ret[i] = r+'0';
  }
  return ret;
}

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

  string line;
  while(getline(cin,line)){
	if(line == ".") break;
	int ans = 0;
	for(int P=0;P<=2;++P)
	  for(int Q=0;Q<=2;++Q)
		for(int R=0;R<=2;++R){
		  string s = rep(line, P, Q, R);
		  if(parse(s, 0, SZ(s)) == 2)
			++ans;
		}
	cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll ceils(ll x,ll y)
{
    if(x%y==0)
        return x/y;
    return x/y+1;
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    ll a,b;
    cin>>n>>a>>b;
    for(int i=1;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        ll t=max(ceils(a,x),ceils(b,y));
        a=x*t,b=y*t;
    }
    cout<<a+b<<endl;
    return 0;
}

Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


X = I()

ans = 0
ans += (X // 500) * 1000
X -= (X // 500) * 500
ans += (X // 5) * 5
print(ans)

Measured memory_bytes: 38384
import scala.io.Source.stdin

object Main extends App{
  stdin.getLines.foreach { s=>
    var d = s.toDouble
    println {
      d + (for(i<-2 to 10) yield {
        if(i%2==0) d=d*2
        else d=d/3
        d
      }).sum
    }
  }
}

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

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> L(N);
    for (int i = 0; i < N; i++) cin >> L[i];

    vector<int> D(N + 1);
    D[0] = 0;
    for (int i = 1; i <= N; i++) D[i] = D[i - 1] + L[i - 1];
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        if (D[i] <= X) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC133A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;

            var word = Console.ReadLine().Split(' ');

            a = int.Parse(word[0]);
            b = int.Parse(word[1]);
            c = int.Parse(word[2]);

            if (a * b < c)
                Console.WriteLine(a * b);
            else
                Console.WriteLine(c);

            Console.ReadKey();
        }
    }
}


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

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PDD;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define dbl(k, x) fixed << setprecision(k) << (x)

template <typename _T>
inline void _DBG(const char *s, _T x) {
  cerr << s << " = " << x << "\n";
}
template <typename _T, typename... args>
void _DBG(const char *s, _T x, args... a) {
  while (*s != ',') cerr << *s++;
  cerr << " = " << x << ',';
  _DBG(s + 1, a...);
}

#define _upgrade                \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)

// ********************** CODE ********************** //

int main() {
  _upgrade;
  LL n;
  cin >> n;
  vector<LL> A(n + 1);
  for (auto &a : A) {
    cin >> a;
  }

  if (n == 0) {
    if (A[0] == 1) {
      cout << 1 << "\n";
    } else {
      cout << -1 << "\n";
    }
    return 0;
  }

  LL leaves_left = accumulate(all(A), 0LL);
  LL cur = 1 - A[0];
  LL res = leaves_left + cur;

  for (int level = 1; level < n + 1; level++) {
    leaves_left -= A[level];
    cur = min(2 * cur - A[level], leaves_left);
    if (cur < 0) {
      cout << -1 << "\n";
      return 0;
    }
    res += cur;
  }

  cout << res << "\n";
  return 0;
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

int main() {
  string s;
  cin >> s;
  int n = s.size();
  int ans = inf;
  int cnt = 0;
  rep (i, n) {
    if (i % 2 == 0) {
      if (s[i] == '0') cnt++;
    }
    if (i % 2) {
      if (s[i] == '1') cnt++;
    }
  }
  chmin(ans, cnt);
  cnt = 0;
  rep (i, n) {
    if (i % 2 == 0) {
      if (s[i] == '1') cnt++;
    }
    if (i % 2) {
      if (s[i] == '0') cnt++;
    }
  }
  chmin(ans, cnt);
  cout << ans << endl;
  
}


Measured memory_bytes: 512
n=int(input().rstrip())
A=list(map(int, input().rstrip().split())) #input parameters
A.sort()
work=int()
bestr=int(A[0])
#def comb(x,y):
#    return(math.factorial(x)/(math.factorial(x-y)*math.factorial(y)))
#for i in range(n-2):
#    if comb(A[n-1],A[i-1])>work:
#        work=comb(A[n-1],A[i-1])
#        bestr=A[i-1]
for i in range(n-2):
    if abs(A[i]-A[n-1]/2)<abs(bestr-A[n-1]/2):
        bestr=A[i]
print("{0} {1}".format(A[n-1],bestr))

Measured memory_bytes: 14428
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>

#define fo(i, x, y) for (int i = x; i <= y; ++i)
#define fd(i, x, y) for (int i = x; i >= y; --i)

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

int n, m;
char s[maxn], t[maxn];

int getint() {
	char ch;
	int res = 0, p;
	while (!isdigit(ch = getchar()) && ch != '-');
	p = ch == '-'? ch = getchar(), -1 : 1;
	while (isdigit(ch))
		res = res * 10 + ch - '0' , ch = getchar();
	return res * p;
}

int gcd(int a, int b) {
	return b? gcd(b, a % b) : a;
}

int main() {
	n = getint(); m = getint();
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	ll l = (ll)n / gcd(n, m) * m;
	fo (i, 0, n - 1) {
		int j = (ll)i * m / n;
		if ((ll)i * m == (ll)j * n && s[i + 1] != t[j + 1]) {
			printf("-1\n");
			return 0;
		}
	}
	cout << (ll)n / gcd(n, m) * m << endl;
	return 0;
}

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(int i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
  int n;
  cin >> n;
  int a[n];
  REP(i, n) cin >> a[i];
  int even = 0;
  REP(i, n){
    if(a[i]%2==0) even++;
  }
  if(even==n) cout << "second" << endl;
  else cout << "first" << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define inf 1145141919364364
#define double long double
using namespace std;
typedef pair<ll, ll>P;
ll gcd(ll x, ll y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
ll lcm(ll x, ll y) {
	return x * y / gcd(x, y);
}
signed main() {
	ll n;
	cin >> n;
	cout << 3 * n * n << endl;
	ggr
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
int main(){
        long long N,result=0;
        std::string A,B,C;
        std::cin>>N>>A>>B>>C;
        for(int i=0; i<N; i++) {
                if(A[i]==B[i]&&B[i]==C[i]) continue;
                else if(A[i]==B[i]||A[i]==C[i]||B[i]==C[i]) result++;
                else result=result+2;
        }
        std::cout<<result;
        return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int rating = sc.nextInt();

		System.out.println(convertKyu(rating));
	}
	
	private static int convertKyu(int rating) {
		if (rating >= 400 && rating <= 599) {
			return 8;
		}
		if (rating >= 600 && rating <= 799) {
			return 7;
		}
		if (rating >= 800 && rating <= 999) {
			return 6;
		}
		if (rating >= 1000 && rating <= 1199) {
			return 5;
		}
		if (rating >= 1200 && rating <= 1399) {
			return 4;
		}
		if (rating >= 1400 && rating <= 1599) {
			return 3;
		}
		if (rating >= 1600 && rating <= 1799) {
			return 2;
		}
		if (rating >= 1800 && rating <= 1999) {
			return 1;
		}
		
		throw new IllegalArgumentException("レーティングが400未満、または2000以上のため、級位に変換できません。");
	}
}




Measured memory_bytes: 27060
H,W = map(int,input().split())
inf=10**10
n=10

e = [[inf]*n for _ in range(n)]

for i in range(10):
    S=list(map(int,input().split()))
    for j in range(10):
        e[i][j]=S[j]





cost=[inf]*10


def dijkstra(s):
    color=["WHITE"]*n
    d=[inf]*n
    p=[-1]*n
    d[s]=0
    p[s]=-1
    while True:
        mincost =inf
        for i in range(n):
            if color[i] !="BLACK" and d[i] < mincost:
                mincost =d[i]
                u=i
        if mincost ==inf:
            break
        color[u]="BLACK"
        
        for v in range(n):
            if color[v] !="BLACK" and e[u][v] !=inf:
                if d[u] +e[u][v] <d[v]:
                    d[v]=d[u] +e[u][v]
                    p[v]=u
                    color[v] ="GRAY"
    return d[1]
ans=10**10

T=[0]*10
for i in range(H):
    S=list(map(int,input().split()))
    for j in range(W):
        if S[j]!=-1:
            T[S[j]]+=1



goukei=0
for i in range(10):
    if i!=1:
        ret=dijkstra(i)

        goukei+=ret*T[i]
print(goukei)

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

#define rep(i, a) for (int i = 0; i < a; i++)
#define reps(i, a, b) for (int i = a; i < b; i++)

int W, H;
bool m[52][52];

void reset()
{
	rep(i, 52) rep(j, 52) m[i][j] = false;	
}

void saiki(int r, int c)
{
	if (!m[r][c]) return;
	m[r][c] = false;
	int dr[] = {-1, -1, -1,  0,  0,  1,  1,  1};
	int dc[] = {-1,  0,  1, -1,  1, -1,  0,  1};
	rep(i, 8) saiki(r+dr[i], c+dc[i]);
}


int main(void){
	cin >> W >> H;
	while (H != 0) {
		reset();
		rep(i, H) rep(j, W) {
			int t;
			cin >> t;
			m[i+1][j+1] = t == 1;
		}
		int res = 0;
		rep(i, H) rep(j, W) {
			if (m[i+1][j+1]) {
				res++;
				saiki(i+1, j+1);
			}
		}
		cout << res << endl;
		cin >> W >> H;
	}
}


Measured memory_bytes: 3312
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(void) {
    int n;
    cin >> n;
    vector<int> A(n);
    for (auto &a: A) {
        cin >> a;
    }
    int ans = 0;
    sort(A.begin(), A.end(), greater<int>());
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) ans += A[i];
        else ans -= A[i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256