akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

#define OK 1
#define NG -1

typedef struct
{
	int iTop;
	int iNorth;
	int iEast;
	int iSouth;
	int iWest;
	int iBottom;
}DICE;

void vdDiceRoll(DICE* stDice, char chOrder);
void vdDiceRollRight(DICE* stDice);
int iCheck2Dice(DICE stDice1, DICE stDice2);
int iCheck2DiceRound(DICE stDice1, DICE stDice2);

// 2つのダイスの目が与えられ、それらが同じさいころかどうか判定
int main()
{
	DICE* stDice;
	int iInputDiceNum;
	int iCnt1, iCnt2;

	scanf("%d", &iInputDiceNum);

	stDice = (DICE*)malloc(sizeof(DICE) * iInputDiceNum);

	// さいころの目を入力
	for (iCnt1 = 0; iCnt1 < iInputDiceNum; iCnt1++)
	{
		scanf("%d", &stDice[iCnt1].iTop);
		scanf("%d", &stDice[iCnt1].iSouth);
		scanf("%d", &stDice[iCnt1].iEast);
		scanf("%d", &stDice[iCnt1].iWest);
		scanf("%d", &stDice[iCnt1].iNorth);
		scanf("%d", &stDice[iCnt1].iBottom);
	}

	for (iCnt1 = 0; iCnt1 < iInputDiceNum - 1; iCnt1++)
	{
		for (iCnt2 = iCnt1 + 1; iCnt2 < iInputDiceNum; iCnt2++)
		{
			// どれか一つでも同じさいころなら
			if (iCheck2Dice(stDice[iCnt1], stDice[iCnt2]) == OK)
			{
				printf("No\n");
				return 0;
			}
		}
	}

	printf("Yes\n");

	free(stDice);

	return 0;
}

// chOrderの方角にダイスを転がす
void vdDiceRoll(DICE* stDice, char chOrder)
{
	int iTopTmp = stDice->iTop;	// Top退避用
	switch (chOrder)
	{
	case 'N':
		stDice->iTop = stDice->iSouth;
		stDice->iSouth = stDice->iBottom;
		stDice->iBottom = stDice->iNorth;
		stDice->iNorth = iTopTmp;
		break;
	case 'E':
		stDice->iTop = stDice->iWest;
		stDice->iWest = stDice->iBottom;
		stDice->iBottom = stDice->iEast;
		stDice->iEast = iTopTmp;
		break;
	case 'S':
		stDice->iTop = stDice->iNorth;
		stDice->iNorth = stDice->iBottom;
		stDice->iBottom = stDice->iSouth;
		stDice->iSouth = iTopTmp;
		break;
	case 'W':
		stDice->iTop = stDice->iEast;
		stDice->iEast = stDice->iBottom;
		stDice->iBottom = stDice->iWest;
		stDice->iWest = iTopTmp;
		break;
	default:
		// 上記以外は何もしない
		break;
	}

	return;
}

// 上面から見て時計回りにダイスを回転
void vdDiceRollRight(DICE* stDice)
{
	int iSouthTmp = stDice->iSouth;

	stDice->iSouth = stDice->iEast;
	stDice->iEast = stDice->iNorth;
	stDice->iNorth = stDice->iWest;
	stDice->iWest = iSouthTmp;
	return;
}

// stDice1とstDice2が同じダイスかどうか判定
// 出力：同じダイスならOK、異なるダイスならNG
int iCheck2Dice(DICE stDice1, DICE stDice2)
{
	int iCnt;

	// 6面すべてを上にしてチェック
	//横回転
	for (iCnt = 0; iCnt < 4; iCnt++)
	{
		if (iCheck2DiceRound(stDice1, stDice2) == OK)
		{
			return OK;
		}
		vdDiceRoll(&stDice2, 'E');
	}
	// 縦回転
	for (iCnt = 0; iCnt < 3; iCnt++)
	{
		vdDiceRoll(&stDice2, 'N');
		// 上の横回転時にチェック済みの状態なのでそれ以外が上なら
		if (iCnt != 1) {
			if (iCheck2DiceRound(stDice1, stDice2) == OK)
			{
				return OK;
			}
		}
	}

	return NG;
}

// stDice2の上面を固定して1回転させたときにstDice1と同じさいころになるかチェック
// 出力：持っているならOK、もっていないならNGを返す
int iCheck2DiceRound(DICE stDice1, DICE stDice2)
{
	int iCnt;

	// 上面固定一回転してチェック
	for (iCnt = 0; iCnt < 4; iCnt++)
	{
		if (stDice1.iTop == stDice2.iTop &&
			stDice1.iEast == stDice2.iEast &&
			stDice1.iWest == stDice2.iWest &&
			stDice1.iNorth == stDice2.iNorth &&
			stDice1.iSouth == stDice2.iSouth &&
			stDice1.iBottom == stDice2.iBottom
			)
		{
			return OK;
		}
		// 上面固定で時計回り90度回転
		vdDiceRollRight(&stDice2);
	}

	return NG;
}



Measured memory_bytes: 2104
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.lang.*;
 
public class Main {
	
	static ArrayList<ArrayList<Integer> > graph = new ArrayList<ArrayList<Integer> >(100001);
	static boolean [] vis = new boolean[100001];
	static int [] longestPath = new int [100001];
	
	public static void main(String[] args) throws InterruptedException {
		FastScanner fs=new FastScanner();
		for(int i=0 ; i<100001 ; ++i) {
			graph.add(new ArrayList<>());
		}
		
		int n=fs.nextInt(), m=fs.nextInt();
		int u, v;
		for(int i=0 ; i<m ; ++i) {
			u = fs.nextInt();
			v = fs.nextInt();
			graph.get(u).add(v);
		}
		
		for(int i=1 ; i<=n ; ++i) {
			if(!vis[i]) {
				dfs(i);
			}
		}
		
		System.out.println(maxElement(longestPath) - 1);
	}
	
	static int dfs(int node) {
		vis[node] = true;
		int c=0;
		for(int to : graph.get(node)) {
			if(!vis[to]) {
				c = Math.max(c, dfs(to));
			}
			else {
				c = Math.max(c, longestPath[to]);
			}
		}
		++c;
		longestPath[node] = c;
		return c;
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> list=new ArrayList<>();
		for (int i:a) list.add(i);
		Collections.sort(list);
		for (int i=0; i<a.length; i++) a[i]=list.get(i);
	}
	
	static String reverse(String str) {
	    StringBuilder sb=new StringBuilder(str);
	    sb.reverse();
	    return sb.toString();
	}
	
	static long maxElement(int [] arr) {
		return Arrays.stream(arr).max().getAsInt();
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		public String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
	}
 
}

Measured memory_bytes: 76172
d = {}
a, b, c = raw_input(), raw_input(), raw_input()
d['a'] = (a, len(a))
d['b'] = (b, len(b))
d['c'] = (c, len(c))
p = {}
p['a'] = 0
p['b'] = 0
p['c'] = 0
t = 'a'

while True:
    p[t] += 1
    if p[t] > d[t][1]:
        print t.upper()
        break
    t = d[t][0][p[t]-1]


Measured memory_bytes: 2568
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>

#define pb push_back

using namespace std;

int main() {
	int len, cnt = 0;
	char teks[200010];
	bool valid = true;
	vector<int> s[30], t[30];
	map<char, int> peta;
	scanf("%s\n", teks);
	len = strlen(teks);
	for (int i = 0; i < len; i++) {
		if (peta.count(teks[i]) < 1)
			peta[teks[i]] = cnt++;
		s[peta[teks[i]]].pb(i);
	}
	peta.clear();
	cnt = 0;
	scanf("%s", teks);
	for (int i = 0; i < len; i++) {
		if (peta.count(teks[i]) < 1)
			peta[teks[i]] = cnt++;
		t[peta[teks[i]]].pb(i);
	}
	for (int i = 0; i < 26; i++) {
		if (s[i].size() != t[i].size())
			valid = false;
		if (!valid)
			break;
		for (int j = 0; j < (int) s[i].size(); j++)
			if (s[i][j] != t[i][j]) {
				valid = false;
				break;
			}
	}
	if (valid)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 2688
#include <stdio.h>
#include <stdlib.h>


int main(){
    int n,m,c;
    int in[20] = {0};

    int in2[20] = {0};

    int count = 0;
    char inc[20];
 
    scanf("%d%d%d",&n,&m,&c);

    
    for (int k = 0; k < m; k++) {
       scanf("%d",&in[k]);
    }



    for (int i = 0; i < n; i++) {
        for (int k = 0; k < m; k++) {
            scanf("%d",&in2[k]);
        }


        int ans = c;
        for (int j = 0; j < m; j++) {
            ans = ans + in[j]*in2[j];
        }

        if (ans > 0) {
            count++;
        }
    }
  
 
    printf("%d\n",count);
	return 0;
}


Measured memory_bytes: 128
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
n,k=map(int,input().split())
ab=[[]for _ in range(n)]
visited=[False]*n
for i in range(n-1):
	a,b=map(int,input().split())
	ab[a-1].append(b-1)
	ab[b-1].append(a-1)
ans=k
def dfs(i):
	global ans
	child=0
	visited[i]=True
	for x in ab[i]:
		if visited[x]==False:
			dfs(x)
			child+=1
	if i==0:
		ans*=p(k-1,child)
	else:
		ans*=p(k-2,child)
	ans%=mod
def p(a,b):
	e=1
	for i in range(a,a-b,-1):
		e*=i
		e%=mod
	return e	
mod=10**9+7
dfs(0)
print(ans)

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

int main(void)
{
    int a, b, c, k;

    scanf("%d %d %d %d" ,&a, &b, &c, &k);

    while(a>=b && k!=0)
    {
        k--;
        b*=2;
    }
    while(b>=c && k!=0)
    {
        k--;
        c*=2;
    }

    if(a<b && b<c)
        printf("Yes");
    else printf("No");
    return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef string str;
static const long long INF = 1LL<<59;
static const long long MOD = (ll)1e9+7;

#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
#define REP(i, n) for(ll i=0;i<n;i++)
#define SZ(v) (ll)((v).size())
#define WHOLE(v) (v).begin(), (v).end()
#define ASC(v) sort((v).begin(), (v).end())
#define DESC(v) sort((v).rbegin(), (v).rend())
#define INV(v) reverse((v).begin(), (v).end())
#define FOLDL(src, dst, lambda) partial_sum((src).begin(), (src).end(), (dst).begin(), lambda)
#define FOLDR(src, dst, lambda) INV(src);partial_sum((src).begin(), (src).end(), (dst).begin(), lambda);INV(dst)
#define CUMSUML(src, dst) FOLDL(src, dst, [](auto a, auto b) {return a+b;})
#define CUMSUMR(src, dst) FOLDR(src, dst, [](auto a, auto b) {return a+b;})
#define ACCUM(v, d0, lambda) accumulate((v).begin(), (v).end(), d0, lambda)
#define SUM(v, d0) ACCUM(v, d0, [](auto a, auto b) {return a+b;})
#define ERASE(v, i) v.erase(v.begin() + i)
#define UNIQ(v) ASC(v);v.erase(unique(v.begin(), v.end()), v.end())

template <typename T>void debug(T t) {cerr << t << endl;}
template <typename T, typename ...Args>void debug(T t, Args ...args) {cerr << t << " ";debug(args...);}
template <typename T>void out(T t) {cout << t << endl;}
template <typename T, typename ...Args>void out(T t, Args ...args) {cout << t << " ";out(args...);}

void solve() {
    ll N, C, K;
    cin >> N >> C >> K;
    vll T(N);
    for(auto &t:T) cin >> t;
    ASC(T);
    ll ans = 0, c = 0, lim = 0;
    if(C == 1) {
        out(N);
        return;
    }
    REP(i, N) {
        if(c == 0) {
            c++;
            lim = T[i] + K;
        }
        else {
            if(T[i] > lim) {
                c = 1;
                ans++;
                lim = T[i] + K;
                continue;
            }
            c++;
            if(c == C) {
                c = 0;
                ans++;
                lim = 0;
                continue;
            }
        }
    }
    if(c) ans++;
    out(ans);
}

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

Measured memory_bytes: 1024
#include <cstdio>
#include <vector>
#include <iostream>
typedef std::pair<int,int> pii;

int n,m,Ans,f[305][305][305];
std::vector<pii> e[305];
const int p=1000000007;

inline void Inc(int &x,int y){if((x+=y)>=p)x-=p;}

int main()
{
    scanf("%d%d",&n,&m),f[1][0][0]=3;
    for(int l,r,x;m--;)scanf("%d%d%d",&l,&r,&x),e[r].push_back(pii(l,x));
    for(int i=1;i<=n;++i)
        for(int j=0;j<i;++j)
            for(int k=j;k<i;++k)
            {
                for(pii x:e[i])
                    if(x.second==1)k>=x.first?f[i][j][k]=0:0;
                    else if(x.second==2)(k<x.first||j>=x.first)?f[i][j][k]=0:0;
                    else if(j<x.first)f[i][j][k]=0;
                if(i==n)Inc(Ans,f[i][j][k]);
                Inc(f[i+1][j][k],f[i][j][k]);
                Inc(f[i+1][j][i],f[i][j][k]);
                Inc(f[i+1][k][i],f[i][j][k]);
            }
    return printf("%d\n",Ans),0;
}

Measured memory_bytes: 108800
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdlib>
using namespace std;
int main(){
	int a,b,c,d,e;
	cin>>a>>b>>c>>d>>e;
	if(a>=0){
		cout<<(b-a)*e<<endl;
	}else{
		cout<<(-a*c)+d+b*e<<endl;
	}
	return 0;
}

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

int main(){
  int abcd;
  cin >> abcd;
  int A,B,C,D;
  A = abcd / 1000;
  B = abcd % 1000 / 100;
  C = abcd % 100 / 10;
  D = abcd % 10;
  string res = to_string(A);
  vector<long long>BCD = {B,C,D};
  for (int i=0;i<1<<3;i++){
    int s = A;
    bitset<3>bit(i);
    for (int j=0;j<3;j++){
      if (bit.test(j)){
        s += BCD.at(j);
      }else{
        s -= BCD.at(j);
      }
    }
    if (s == 7){
      for (int j=0;j<3;j++){
        if (bit.test(j)){
          res += "+" + to_string(BCD.at(j));
        }else{
          res += "-" + to_string(BCD.at(j));
        }
      }
      cout << res << "=7" << endl;
      return 0;
    }
  }
  cout << "koko" << endl;
}


Measured memory_bytes: 256
import sys

R, G, B, N = input().split()
R = int(R)
G = int(G)
B = int(B)
N = int(N)

cnt = 0

for r in range(int(N/R)+1):
    N1 = N - R*r
    for g in range(int(N1/G)+1):
        N2 = N1 - G*g
        if N2 % B == 0:
            cnt += 1

print(cnt)

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

using namespace std;

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

    int n , q;
    cin >> n >> q;

    vector<pair<int , int> > starts , ends;

    int s , e , x;
    for (int i = 0 ;i < n ;i++) {
        cin >> s >> e >> x;
        if (x < s) {
            starts.push_back({s - x, x});
            ends.push_back({e - x , x});
        } else if (x <= e) {
            starts.push_back({0 , x});
            ends.push_back({e - x , x});
        }
    }

    sort(starts.begin() , starts.end());
    sort(ends.begin() , ends.end());

    vector<pair<int , int> > v(q);
    for (int i = 0 ;i < q ;i++) {
        cin >> v[i].first;
        v[i].second = i;
    }

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

    vector<int> ans(q);

    int k = 0 , j = 0;
    multiset<int> ms;
    for (int i = 0 ;i < v.size() ;i++) {
        while (k < starts.size() && starts[k].first <= v[i].first)
            ms.insert(starts[k].second) , k++;

        while (j < ends.size() && ends[j].first <= v[i].first)
            ms.erase(ms.find(ends[j].second)) , j++;

        if (ms.size())
            ans[v[i].second] = *ms.begin();
        else
            ans[v[i].second] = -1;
    }


    for (auto x : ans)
        cout << x << '\n';
}


Measured memory_bytes: 18052
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef vector<int> vi;
typedef long long LL;
template<typename T>
inline void read(T &x){
	int ch = getchar(); x = 0;
	bool f = false;
	while((ch < '0' || ch > '9') && ch != '-') ch = getchar();
	if(ch == '-'){f = true; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}
	if(f) x = -x;	
}
int n, k;
vi a[6], A;
inline vi inv(const vi &p){
	vi q(n);
	for(Rint i = 0;i < n;++ i) q[p[i]] = i;
	return q;
}
inline vi mul(const vi &p, const vi &q){
	vi r(n);
	for(Rint i = 0;i < n;++ i) r[i] = p[q[i]];
	return r;
}
inline vi ksm(vi a, int b){
	vi res(n);
	for(Rint i = 0;i < n;++ i) res[i] = i;
	while(b){
		if(b & 1) res = mul(res, a);
		a = mul(a, a); b >>= 1;
	}
	return res;
}
int main(){
	read(n); read(k); -- k;
	a[0].resize(n); for(Rint i = 0;i < n;++ i) read(a[0][i]), -- a[0][i];
	a[1].resize(n); for(Rint i = 0;i < n;++ i) read(a[1][i]), -- a[1][i];
	for(Rint i = 2;i < 6;++ i) a[i] = mul(a[i - 1], inv(a[i - 2]));
	if(k < 6){for(Rint i = 0;i < n;++ i) printf("%d ", a[k][i] + 1); return 0;}
	A = ksm(mul(mul(a[1], inv(a[0])), mul(inv(a[1]), a[0])), k / 6);
	A = mul(mul(A, a[k % 6]), inv(A));
	for(Rint i = 0;i < n;++ i) printf("%d ", A[i] + 1); 
}


Measured memory_bytes: 5872
n = int(input())
t,a = [],[]
for i in range(n):
    tmp = [int(i) for i in input().split()]
    t.append(tmp[0])
    a.append(tmp[1])

p,q = 1,1
for i in range(n):
    tmp = max(-(-p//t[i]),-(-q//a[i]))
    p = t[i]*tmp 
    q = a[i]*tmp
print(p+q)  

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

int main( void )
{
    int a, b, c;
    cin >> a >> b >> c;
    if ( ( a == ( b + c ) ) || ( b == ( a + c ) ) || ( c == ( b + a ) ) )
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main (void){

  // 入力変数を3つ用意
  int a[3];
  scanf("%d%d%d",&a[0],&a[1],&a[2]);

  // バブルソートを実装する。
  int tmp;
  for(int i=0; i<3; i++){
      for(int j=3-1; j>i; j--){
        if(a[j] < a[j-1]){
          tmp = a[j];
          a[j] = a[j-1];
          a[j-1] = tmp;
        }
      }
    }
    printf("%d %d %d\n",a[0],a[1],a[2]);
    return(0);
}



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

ll solve() {
    ll N, C;
    cin >> N >> C;
    vector<ll> X(N+2), V(N+2);
    X[0] = 0;
    X[N+1] = C;
    V[0] = 0;
    V[N+1] = 0;
    for ( int i = 1; i <= N; i++ ) {
        cin >> X[i] >> V[i];
    }
    vector<ll> R1(N+2), R2(N+2), L1(N+2), L2(N+2), R2M(N+2), L2M(N+2);
    for ( int i = 1; i <= N; i++ ) {
        R1[i] = R1[i-1] + V[i] - (X[i]-X[i-1]);
        R2[i] = R2[i-1] + V[i] - (X[i]-X[i-1]) * 2;
        R2M[i] = max(R2M[i-1], R2[i]);
    }
    for ( int i = N; i >= 1; i-- ) {
        L1[i] = L1[i+1] + V[i] - (X[i+1]-X[i]);
        L2[i] = L2[i+1] + V[i] - (X[i+1]-X[i]) * 2;
        L2M[i] = max(L2M[i+1], L2[i]);
    }
    ll ans = 0;
    for ( int i = 0; i <= N; i++ ) {
        if ( ans < R1[i] ) ans = R1[i];
        ll u = R1[i] + L2M[i+1];
        if ( ans < u ) ans = u;
    }
    for ( int i = N; i >= 1; i-- ) {
        if ( ans < L1[i] ) ans = L1[i];
        ll u = L1[i] + R2M[i-1];
        if ( ans < u ) ans = u;
    }
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#define fi first
#define se second
#define rng(a) a.begin(),a.end()
#define pb push_back
#define sz(x) (int)(x).size()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
  int n, k; cin >> n >> k;
  vi v[n];
  for (int i=0; i<n; i++){
    int t; ll d; cin >> t >> d; t--;
    v[t].pb(d);
  }
  vp p;
  for (int i=0; i<n; i++){
    if (sz(v[i])>0){
      sort(rng(v[i]));
      for (int j=sz(v[i])-1; j>=0; j--){
        if (j==sz(v[i])-1){
          p.pb(P(v[i][j], 1));
        }
        else p.pb(P(v[i][j], 0));
      }
    }
  }
  sort(rng(p));
  
  ll ans, point;
  ll x=0;
  ll y=0;
  int count=0;
  stack<ll> st;
  for (int i=n-1; i>=0; i--){
    count++;
    if(count<=k){
      x += p[i].fi;
      if (p[i].se ==1){
        y ++;
      }
      else {
        st.push(p[i].fi);
      }
      
      if(count == k){
        point = x + y*y;
        ans = point;
      }
    }
    else {
      if (st.empty()){
        break;
      }
      else{
      if (p[i].se == 1){
        x = x + p[i].fi - st.top(); st.pop();
        y++;
        point = x + y*y;
        ans = max(ans, point);
      }
      }
    }
  }
  
  cout << ans << endl;
  return 0;
   
}

Measured memory_bytes: 6904
/* おまじない　*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    return gcd(a%b,b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

template<class T>
void print(vector<T>v){
	ll size=v.size();
	for(int i=0;i<size;i++){
		cout<<v[i]<<" ";
	}
	cout<<endl;
}

ll F(ll n){
	//0 xor 1 xor ... xor n
	/*ll ret=0;
	for(int i=0;i<60;i++){
		ll num=(n+1)/(ll)pow(2,i+1)*(ll)pow(2,i)+max(0LL,(n+1)%(ll)pow(2,i+1)-(ll)pow(2,i));
		if(num%2==1)ret+=(ll)pow(2,i);
	}
	return ret;*/
	ll ret=0;
	if((n+1)%2==0){
		ll num1=(n+1)/2;
		return num1%2;
	}
	ll num1=(n+1)/2;
	return ((num1%2)^n);
}

int main(){
    init();
	ll a,b;cin>>a>>b;
	ll ans=F(a-1)^F(b);
	cout<<ans<<endl;;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int V, m;
int cost[200][200];
int mincost[200];
bool used[200];

int prim(){
  for(int i=0; i < V; ++i){
    mincost[i] = INT_MAX/2;
    used[i] = false;
  }
  mincost[0] = 0;
  int res = 0;

  while(true){
    int v = -1;
    for(int u=0; u < V; u++){
      if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
    }

    if(v == -1) break;
    used[v] = true;
    res += mincost[v];

    for(int u=0; u < V; u++){
      mincost[u] = min(mincost[u], cost[v][u]);
    }
  }
  return res;
}

int main(void){
  while(cin >> V >> m, V | m){
    for(int i=0; i < V; i++)
      for(int j=0; j < m; j++)
        cost[i][j] = INT_MAX/2;
    for(int i=0; i < m; i++){
      int a, b, c; cin >> a >> b >> c;
      cost[a][b] = c;
      cost[b][a] = c;
    }
    cout << prim() << endl;
  }
  return 0;
}

Measured memory_bytes: 1244
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll mod =1e9+7;
const int N = 2e5+7;

int main()
{
    int k;
    scf(k);
    
    string s;
    cin>>s;
    
    if(s.size()<=k)
    cout<<s<<endl;
    
    else
    {
        rep(i,0,k)
        cout<<s[i];
        
        cout<<"...";
        
    
    }
    
    
}

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

using namespace std;
typedef long long ll;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp make_pair
#define pb push_back
#define lp(i,s,f) for(ll i = s; i < ll(f); i++)
#define inF freopen("input.in", "r", stdin);
#define outF freopen("output.in", "w", stdout);
#define endl '\n'
#define MOD 1000000007
#define mm(arr) memset(arr, 0, sizeof(arr))
#define F first
#define S second

int main(){
    FAST
    int n; cin >> n;
    vector<string> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
        sort(v[i].begin(), v[i].end());
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for(int i = 0; i < n; i++){
        string s = v[i];
        ll cnt = 0;
        while(s == v[i]){
            i++;
            cnt++;
            if(i == n)break;
        }
        i--;
        ans += cnt*(cnt - 1)/2;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 6320
#include<iostream>
#include<stack>

int main(){
	int n;
	std::stack<int>sta;
	while(std::cin>>n){
		if(n!=0)sta.push(n);
		else{
			std::cout<<sta.top()<<std::endl;
			sta.pop();
		}
	}
	return 0;
}

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

const double EPS = 1e-10;
double add(double a, double b) {
    if(abs(a+b) < EPS*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct Vector {
    double x, y;
    Vector() {}
    Vector(double x, double y):x(x), y(y) {}
    Vector operator+(Vector v) {return Vector(add(x, v.x), add(y, v.y));}
    Vector operator-(Vector v) {return Vector(add(x, -v.x), add(y, -v.y));}
    Vector operator*(double d) {return Vector(x*d, y*d);}
    Vector operator/(double d) {return Vector(x/d, y/d);}
    double dot(Vector v) {return add(x*v.x, y*v.y);}
    double cross(Vector v) {return add(x*v.y, -y*v.x);}
};
istream &operator>>(istream &is, Vector &v) {return is >> v.x >> v.y;}
ostream &operator<<(ostream &os, const Vector &v) {return os << v.x << ' ' << v.y;}
double sqdist(Vector v, Vector u) {return (v-u).dot(v-u);}
bool on_seg(Vector v1, Vector v2, Vector p) {
    return (v1-p).cross(v2-p) == 0 && (v1-p).dot(v2-p) <= 0;
}
//v1-v2とu1-u2の交点
Vector intersection(Vector v1, Vector v2, Vector u1, Vector u2) {
    assert((v1-v2).cross(u1-u2)); //2直線が平行だとだめ
    return v1 + (v2-v1)*((u2-u1).cross(u1-v1)/(u2-u1).cross(u2-v1));
}
Vector projection(Vector p1, Vector p2, Vector Q) {
    return p1+(p2-p1)*(Q-p1).dot(p2-p1)/sqdist(p1, p2);
}
bool cmp_x(const Vector &v, const Vector &u) {
    if(v.x != u.x) return v.x < u.x;
    return v.y < u.y;
}
//頂点数nの頂点集合vv
vector<Vector> convex_hull(vector<Vector> &vv, int n) {
    sort(vv.begin(), vv.end(), cmp_x);
    int k = 0;
    vector<Vector> res(n*2);
    for(int i = 0; i < n; i++) {
        while(k > 1 && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    for(int i = n-2, t = k; i >= 0; i--) {
        while(k > t && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    res.resize(k-1);
    return res;
}
signed main() {
    cout << fixed << setprecision(15);
    Vector p1, p2;
    cin >> p1 >> p2;
    int q;
    cin >> q;
    while(q--) {
        Vector Q;
        cin >> Q;
        Vector X = projection(p1, p2, Q);
        cout << X*2-Q << '\n';
    }
}


Measured memory_bytes: 3296
import math
import itertools
import statistics
#import collections
x = int(input())
#A = (map(int, input().split()))

total = 0
total += (x//500) *1000
x = x%500

total += (x//100)* 20 *5
x = x%100
total += (x//50) *10*5
x = x%50
total += (x//10) * 2*5
x = x%10
total += (x//5) *5

print(total)



Measured memory_bytes: 5788
import java.util.*;

public class Main {
	public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int L = sc.nextInt();
      String[] str = new String[N];
      for (int i=0;i<N;i++) {
        str[i] = sc.next();
      }
      Arrays.sort(str);
      for(String out : str){
        System.out.print(out);
      }
    }
}

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

int main() {
    int N;
    while (cin >> N, N) {
        vector<int> v(N);
        for (auto& i : v) cin >> i;

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

    return 0;
}

Measured memory_bytes: 3036
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(cnt,e) for(ll cnt=0;cnt<e;cnt++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT64_MAX;
typedef tuple<ll,ll,ll> T;

ll i,j,k;


int main(){
   ll X;
   cin>>X;
   ll kane=100;
   ll cnt=0;
   while(kane<X){
       cnt++;
       ll kari=kane*1.01;
       kane=kari;
   }
   cout<<cnt<<endl;
}


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


int main() {
    ll S;
    cin >> S;
    string N;
    cin >> N;
    vector<ll> w(0),r(0);
    for(ll i=0;i<N.size();i++){
        if(N.at(i)=='W')w.push_back(i);
        else r.push_back(i);
        
    }
    
    
    ll count=0;//,rb=0;
    for(ll i=0;i<N.size();i++){
        if(!r.size()||i>=r.back())break;
        if(N.at(i)=='W'){
            N.at(i)='R';
            //cout << r.back() << endl;
            N.at(r.back())='W';
            r.pop_back();
            count++;
        }
        
        
        
    }
    
  
    cout << count << endl;
}

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

using namespace std;

#define FOR(i,l,r) for (int i=(l); i<(r); ++i)
#define sz(x) (int)(x).size()
#define print(x) cout << (x) << endl
#define dbg(x) cout << (#x) << ' ' << (x) << endl
#define all(x) (x).begin(), (x).end()

typedef string str;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LLINF = 1LL << 60;

/* ------ END OF TEMPLATE ------ */

const int maxn = 5e2 + 5;

int n;
ll arr[maxn], psa[maxn], dp[maxn][maxn];

ll rec(int l, int r) {
    ll &ret = dp[l][r];
    if (ret != -1)
        return ret;
    if (l == r)
        return ret = 0;
    if (l+1 == r)
        return ret = arr[l] + arr[r];
    ret = LLINF; ll mx;
    for (int i = l; i < r; i++) {
        if (l > r) mx = LLINF;
        else mx = psa[r] - psa[l-1];
        ll val = rec(l,i) + rec(i+1,r) + (mx);
        ret = min(ret, val);
    }
    return ret;
}

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

    cin >> n;
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    for (int i = 1; i <= n; i++)
        psa[i] = arr[i] + psa[i-1];
    cout << rec(1, n) << "\n";
}


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

using namespace std;

int a, b;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> a >> b;
    int k = (a + b) / 2;
    if (abs(a - k) == abs(b - k)) {
        cout << k << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set> 
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x;
    cin>>x;
    int y=600;
    for(int j=8;j>=1;j--){
        if(x<y){
            cout<<j<<endl;
            break;
        }
        y+=200;
    }
    return 0;
}

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

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().ToCharArray().Select(x => x.ToString()).ToList();


            int firstIndex = s.FindIndex(x => (x == "A" || x == "C" || x == "G" || x == "T"));
            if (firstIndex < 0)
            {
                Console.WriteLine(0);
            }
            else
            {
                int i = firstIndex;
                int count = 1;
                while (i < s.Count() - 1)
                {
                    if (!(s[i] == "A" || s[i] == "C" || s[i] == "G" || s[i] == "T"))
                    {
                        i++;
                    }
                    else
                    {
                        int j = i + 1;
                        while (j < s.Count()&&(s[j] == "A" || s[j] == "C" || s[j] == "G" || s[j] == "T") )
                        {
                            j++;
                        }
                        count = Math.Max(count, j - i);
                        i = j+1;
                    }
                }

                Console.WriteLine(count);


            }

        }
    }
}


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

int main() {

	
    int x,y;

	cin >> x >> y ;
	
	int area,peri;
	
	area = x*y;
	peri = x+x+y+y;
	
	
	cout << area << " " << peri << endl;
	
	return 0;
}



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

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 100 * 1000 + 17;

int n, par[MAXN], h[MAXN], a[MAXN];
vector<int> adj[MAXN];
bool mark[MAXN];

void dfs(int v = 1, int pr = 0) {
	par[v] = pr;
	h[v] = h[pr] + 1;
	for (auto i : adj[v])
		if (i != pr)
			dfs(i, v);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int v, u;
		cin >> v >> u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	dfs();
	iota(a + 1, a + n + 1, 1);
	sort(a + 1 ,a + n + 1, [](int i, int j) { return h[i] < h[j]; });
	for (int i = n; i; i--) {
		int v = a[i];
		if (mark[v])
			continue;
		if (!par[v])
			return cout << "First" << endl, 0;
		if (mark[par[v]])
			return cout << "First" << endl, 0;
		else
			mark[v] = mark[par[v]] = true;
	}
	cout << "Second" << endl;
	return 0;
}


Measured memory_bytes: 7040
N,M=map(int,input().split())
AC=[0]*N
WA=[0]*N
for i in range(M):
    p,s=map(str,input().split())
    p=int(p)
    if s=="AC":
        AC[p-1]=1
    else:
        if AC[p-1]==0:
            WA[p-1]+=1

for i in range(N):
    if AC[i]==0:
        WA[i]=0

print(sum(AC),sum(WA))

Measured memory_bytes: 45656
#include<bits/stdc++.h>
using namespace std;
int n,m,s[100010],i,j,k;
bool r[100010];
int main(){
	for(cin>>n>>m,i=1;i<=n;i++)
	  s[i]=1;r[1]=1;
	while(m--){
	  cin>>i>>j;
	  s[i]--;s[j]++;
	  r[j]|=r[i];
	  if(s[i]==0)r[i]=0;
	}for(i=1;i<=n;i++)
	  if(r[i])s[0]++;
	cout<<s[0];
	return 0;
}


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

int main(){
  int A,B,C,x;
  cin >> A >> B >> C >> x;
  int res = 0;
  for(int a = 0; a <= A; ++a){
	  for(int b = 0; b <= B; ++b){
		  for(int c = 0; c <= C; ++c){
			  int total = 500*a+ 100*b + 50*c;
			  if(x == total) ++res;
		  }
	  }
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;

int main(){
    int x;
    cin>>x;
    int sum=0;
    int m=0;
    while(sum<x){
        m++;
        sum+=m;
    }
    cout<<m<<endl;
}


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

#define ll long long

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n,m,k;
    cin>>n>>m>>k;
    ll a[n],b[m];
    for(ll i=0;i<n;i++){
    	cin>>a[i];
	}
	for(ll i=0;i<m;i++){
		cin>>b[i];
	}
	ll sum=0;
    for(int i=0;i<m;i++) 
		sum+=b[i];
	int j=m;
    int ans = 0;
    for(int i=0;i<n+1;i++){
        while(j>0&&sum>k){
            --j;
            sum-=b[j];
        }
        if(sum>k) 
			break;
        ans = max(ans,i+j);
        if(i==n) 
			break;
        sum+=a[i];
    }
    cout<<ans;
}

Measured memory_bytes: 6780
'''
問題文
	猫のすぬけは文字を書く練習をしています。 すぬけは今日、数字の 1 と 9 を書く練習をしていたのですが、 間違えて 1 と 9 をあべこべに書いてしまいました。
	すぬけが書いた 3 桁の整数 n が与えられます。 
	n に含まれる 1 という桁をそれぞれ 9 に、 9 という桁をそれぞれ 1 に置き換えて得られる整数を出力してください。

制約
	111 ≤ n ≤ 999
	n は各桁が 1 か 9 である整数

入力
	入力は以下の形式で標準入力から与えられる。
	n

出力
	n の各桁の 1 と 9 を入れ替えた整数を出力してください。

入力例 1 
	119
出力例 1 
	991
	一の位の 9 を 1 に、十の位の 1 を 9 に、百の位の 1 を 9 に書き換えた 991 が答えとなります．

入力例 2 
	999
出力例 2 
	111
'''

def main():
	'''
	メイン関数
	'''
	# 入力を取得
	input_num = input()
	
	# 1と9を入れ替えて出力
	input_num = input_num.replace('1','-')
	input_num = input_num.replace('9','1')
	input_num = input_num.replace('-','9')
	print(input_num)



if __name__ == '__main__':
	main()


Measured memory_bytes: 3064
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main(void){
int a[200];
  int n,x,ans;
  scanf("%d",&n);
 x=0;
  for(int i=0;i<n;i++){
scanf("%d",&a[i]);
    x+=a[i];
  }
  ans=x;
    for(int i=0;i<n;i++){
      x-=(2*a[i]);
    ans=min(ans,abs(x));
  }
 
  printf("%d\n",ans);
  return 0;  
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
using namespace std;
typedef long long unsigned int ll;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007

#define REP(i,n) for(int i=0;i<n;i++)
#define REPS(i,f,n) for(int i=(f);i<(n);i++)
#define EACH(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)

#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy4[]={0, 0, 1, -1};
int dx4[]={1, -1, 0, 0};
int dx8[]={0, 0, 1, -1, 1, 1, -1, -1};
int dy8[]={1, -1, 0, 0, 1, -1, -1, 1};

// https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

int main() {
    int N, M; cin >> N >> M;
    vector<P> v;
    int a, b;
    REP(i, M) {
        cin >> a >> b;
        v.push_back({b, a});
    }

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

    int now = 0;
    int ans = 0;
    REP(i, M) {
        P p = v[i];
        if (p.second >= now) {
            ans++;
            now = p.first;
        }
    }

    cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 1400
if __name__ == '__main__':
    nm = input()
    nm = nm.split()
    n = int(nm[0])
    m = int(nm[1])

    if n%2==1:
        for i in range(1,m+1):
            print(i,n+1-i)


    if n%2==0:
        t = n
        f = 0

        for i in range(1,m+1):
            p = i-1+t-n
            if p>=n-i-1 and f==0:
                f = 1
                n -= 1
            print(i,n)
            n -= 1


Measured memory_bytes: 9276
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    // Sieve of Eratosthenes
    const int MAX = 100000;
    std::vector<int> is_prime(MAX, 1);
    is_prime[0] = 0;
    is_prime[1] = 0;
    for (int i = 2; i < MAX; ++i) {
        if (!is_prime[i]) { continue; }

        for (int j = 2 * i; j < MAX; j += i) {
            is_prime[j] = 0;
        }
    }

    std::vector<int> is_2017_like(MAX);
    for (int i = 0; i < MAX; ++i) {
        if (i % 2 == 0) { continue; }

        if (is_prime[i] && is_prime[(i + 1) / 2]) {
            is_2017_like[i] = 1;
        }
    }

    std::vector<int> cumsum(MAX + 1);
    std::partial_sum(
        is_2017_like.cbegin(), is_2017_like.cend(),
        cumsum.begin() + 1
    );

    int Q;
    std::cin >> Q;

    for (int i = 0; i < Q; ++i) {
        int l, r;
        std::cin >> l >> r;

        std::cout << cumsum[r + 1] - cumsum[l] << std::endl;
    }
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define FOR(i, s, e) for (ll(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (ll(i) = (s); (i) > (e); (i)--)
#define debug(x) cout << #x << ": " << x << endl
#define mp make_pair
#define pb push_back
const ll MOD = 1000000007;
const int INF = 1e9;
const ll LINF = 1e16;
const double PI = acos(-1.0);
int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/07/29  Problem: ARC 079 C / Link: http://arc079.contest.atcoder.jp/tasks/arc079_c  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

ll N;
ll a[51];
ll ans = 0LL;

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

	cin >> N;
	FOR(i, 0, N)cin >> a[i];
	
	FOR( x, 0,1000000) {
		FOR(i, 0, N) {
			if (a[i] >= N) {
				ll d = a[i] / N;
				ans += d;
				a[i] -= d*N;
				FOR(j, 0, N) {
					if (i != j)a[j] += d;
				}
			}
		}
	}
	
	
	
	
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
l_s = [a for a in input()]
l_str = ''
for a in l_s:
    if a == '0':
        l_str += ('0')
    elif a == '1':
        l_str += ('1')
    elif a == 'B':
        if l_str == '':
            pass
        else:
            l_str = l_str[:-1]

print(l_str)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define INF 1000000001
#define ll long long
using namespace std;
using pll = pair<ll, ll>;


int main()
{
  ll s;
  cin >> s;
  vector<bool> already(1000000, false);
  already.at(s) = true;
  ll ans = 1;
  while (true)
  {
    ans += 1;
    if (s % 2 == 0)
    {
      s = s / 2;
    }
    else
    {
      s = s * 3 + 1;
    }
    if (already.at(s))
    {
      cout << ans << endl;
      return 0;
    }
    already.at(s) = true;
  }
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
ll n;ll dat[2000005];
void init(ll n_){
n=1;
  while(n<=n_)n*=2;
}
void update(ll k,ll a){
k+=n-1;
  dat[k]=a;
  while(0<k){
  k=(k-1)/2;
    dat[k]=(dat[2*k+1]+dat[2*k+2]);
  }
}
ll query(ll a,ll b,ll k,ll l,ll r){
if(a<=l && r<=b)
  return dat[k];
  else if(r<=a || b<=l)
    return 0;
  else{
  ll val=query(a,b,2*k+1,l,(l+r)/2);
    ll var=query(a,b,2*k+2,(l+r)/2,r);
    return (val+var);
  }
}
ll N,Q;
int main(){
  cin>>N>>Q;init(N+2);
  vector<ll>c(N);
  for(int i=0;i<N;i++)
    cin>>c.at(i);
  vector<pair<P,ll>>A(Q);
  for(int i=0;i<Q;i++){
  ll l,r;cin>>l>>r;
    P p(r,l);
    pair<P,ll>p1(p,i);
    A[i]=p1;
  }sort(A.begin(),A.end());
  vector<ll>ans(Q);
  map<ll,ll>M;ll I=0;
  for(int i=0;i<N;i++){
  if(!M.count(c[i])){
    M[c[i]]=i;update(i,1);
  }else{
  update(M.at(c[i]),0);M.at(c[i])=i;update(i,1);
  }
     while(A[I].first.first==i+1){
     ll l=A[I].first.second;
       ll r=A[I].first.first;
       ll j=A[I].second;
       ll a=query(l-1,r,0,0,n);
       ans[j]=a;I++;
     
     }
  }for(int i=0;i<Q;i++)
     cout<<ans[i]<<endl;
   return 0;
}


Measured memory_bytes: 62400
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
long long n, a[100002], sum, cnt;
int main() {
	cin >> n; for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i <= n; i++) {
		if (a[i] == 0) { sum += cnt / 2; cnt = 0; }
		else { cnt += a[i]; }
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define ff first
#define ss second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
 
const int MOD = 1e9+7;
ll dp[405][405];
ll v[405];
ll psum[405];
bool mark[405][405];
 
ll f(int l, int r) {
	if(l == r) return 0;
	if(mark[l][r]) return dp[l][r];
	mark[l][r] = true;
 
	ll ret = 1e18;
	for(int i = l; i < r; i++)
		ret = min(ret, f(l, i) + f(i+1, r) + psum[i] - psum[l-1] + psum[r] - psum[i]);
 
	return dp[l][r] = ret;
}
 
int main() {
	int n;
	scanf("%d", &n);
 
	for(int i = 1; i <= n; i++)
		scanf("%lld", &v[i]);
 
	for(int i = 1; i <= n; i++)
		psum[i] = psum[i-1] + v[i];
 
	printf("%lld\n", f(1,n));
	
    return 0;
}

Measured memory_bytes: 1664
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::Read;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok().unwrap();
    ret
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.unwrap_or(0) == 0 || u8b[0] <= b' ' {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() }

fn solve() {
    let n = get();
    const INF: i32 = 1 << 30;
    let mut occur = [INF; 26];
    for _ in 0 .. n {
        let s = get_word();
        let mut cur = [0; 26];
        for c in s.bytes() {
            cur[(c - b'a') as usize] += 1;
        }
        for i in 0 .. 26 {
            occur[i] = min(occur[i], cur[i]);
        }
    }
    let mut output = String::new();
    for i in 0 .. 26 {
        for _ in 0 .. occur[i] {
            output.push((b'a' + i as u8) as char);
        }
    }
    println!("{}", output);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
def f_silver_fox_vs_monster():
    # 参考: https://atcoder.jp/contests/abc153/submissions/9773604
    from bisect import bisect_right
    import sys
    input = sys.stdin.readline
    N, D, A = [int(i) for i in input().split()]
    Monsters = sorted([[int(i) for i in input().split()] for j in range(N)])

    class BIT(object):
        """Binary Indexed Tree (1-indexed)"""

        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, index):
            """array[1] から array[index] までの和を計算"""
            ret = 0
            while index > 0:
                ret += self.tree[index]
                index -= index & (-index)
            return ret

        def add(self, index, value):
            """array[index] に value を加算"""
            while index <= self.size:
                self.tree[index] += value
                index += index & (-index)

    position = [row[0] for row in Monsters]
    hit_point = [row[1] for row in Monsters]
    # [k]: 左から k 番目の敵を爆発の左端で攻撃したときに届く右端の敵のインデックス
    pos_right = [bisect_right(position, pos + 2 * D) for pos in position]

    ans = 0
    bomb_damage = BIT(N + 1)  # bomb_damage.sum(k): 左から k 番目の敵に与えた累計ダメージ
    for i in range(N):
        hp, damage, right = hit_point[i], bomb_damage.sum(i + 1), pos_right[i]
        if hp - damage > 0:
            num_defeat = (hp - damage + A - 1) // A  # 注目中の敵を倒すのに必要な爆発回数
            ans += num_defeat
            bomb_damage.add(i + 1, num_defeat * A)
            # ここから右の敵はダメージが通っていないことを反映
            bomb_damage.add(right + 1, -num_defeat * A)
    return ans

print(f_silver_fox_vs_monster())

Measured memory_bytes: 96040
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
#include <set>
#include <iomanip>
using namespace std;


int main(){
    int M1, D1;
    cin >> M1 >> D1;
    if (M1  == 1 or M1 == 3 or M1 == 5 or M1 == 7 or M1 == 8 or M1 == 10 or M1 == 12){
        if (D1 == 31){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }else if (M1 == 2){
        if (D1 == 28){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }else{
        if (D1 == 30){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
use std::str::FromStr;
use std::collections::{HashMap,HashSet,VecDeque,BinaryHeap};
use std::cmp::{max,min,Ordering};
use std::io::Read;

fn main() {

    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut buf_it = buf.split_whitespace();

    let N = buf_it.next().unwrap().parse::<usize>().unwrap();
    let mut A = (0..N).map(|_| buf_it.next().unwrap().parse::<isize>().unwrap()).collect::<Vec<_>>();

    let mut ans = 0;
    
    for i in 0..N{
        let mut minj = i;
        for j in i..N{
            if A[j] < A[minj]{
                minj = j;
            }
        }
        if i != minj {
            let tmp = A[i];
            A[i] = A[minj];
            A[minj] = tmp;
            ans += 1;
        }
    }

    println!("{}",A.iter().map(|&a| format!("{}",a)).collect::<Vec<_>>().join(" "));
    println!("{}",ans);

}


Measured memory_bytes: 5040
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
    string s,t;
    int n,m;
    cin >> s >> t;
    n=s.size(); m=t.size();
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    if(s<t)
        cout << "Yes";
    else cout << "No";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
#define mREP(a,b) for (int i = a; i == (b); --i) 
typedef long long ll;
using namespace std;
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
/*
	　　　  　 ,ﾍ／L──- 、
	　　　   　Lﾆ)r_」=＝= ｲ
	　　 　,ﾍ、i ﾉノλﾉﾊﾉﾍ
	　　   ,'　｀(ﾊﾘ ﾟ ヮﾟﾉi)　',
	　　 .i　　 >〈(つ,i!と)　　i
	　　  vﾍγk´_/___i,ゝﾍノ
	　　　　　 ｀ﾞr_,ｨ_ｧﾞ´
*/
int n, m;
cin >> n >> m;
vector<ll>a(n);
rep0(i, n - 1)cin >> a[i];
sort(a.begin(), a.end());
ll ans = 5208425843524;
rep0(j, n - m) {
	ans = min(ans, a[j + m - 1] - a[j]);
}
cout << ans << endl;
return 0;
}


Measured memory_bytes: 1024