akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>U[10100];
int w[1010000], st[1010000];
vector<int> Make(vector<int>A, vector<int>B) {
	int i, cnt = 0;
	for (i = 0; i < A.size(); i++)w[cnt++] = A[i];
	for (i = B.size() - 1; i >= 0; i--)w[cnt++] = B[i] ^ 1;
	int top = 0;
	for (i = 0; i < cnt; i++) {
		if (top && (st[top] ^ 1) == w[i]) top--;
		else st[++top] = w[i];
	}
	vector<int>r;
	for (i = 1; i <= top; i++)r.push_back(st[i]);
	return r;
}
int p[101000], q[101000], pr[101000], qr[100100], n, K, T[101000], Res[101000];

int AA[101000], BB[101000];
int AU[101000][30], BU[101000][30];

int GoA(int a, int k) {
	int i = 0;
	while (k) {
		if (k & 1)a = AU[a][i];
		i++, k >>= 1;
	}
	return a;
}
int GoB(int a, int k) {
	int i = 0;
	while (k) {
		if (k & 1)a = BU[a][i];
		i++, k >>= 1;
	}
	return a;
}

void Solve() {
	int i, j;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d", &p[i]);
		pr[p[i]] = i;
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &q[i]);
		qr[q[i]] = i;
	}

	if (K == 1) {
		for (i = 1; i <= n; i++) {
			printf("%d ", p[i]);
		}
		return;
	}

	for (i = 1; i <= n; i++) {
		AA[i] = q[pr[qr[p[i]]]];
		BB[i] = pr[q[p[qr[i]]]];
		AU[i][0] = AA[i], BU[i][0] = BB[i];
	}
	for (i = 0; i < 29; i++) {
		for (j = 1; j <= n; j++) {
			AU[j][i + 1] = AU[AU[j][i]][i];
			BU[j][i + 1] = BU[BU[j][i]][i];
		}
	}

	if (K % 3 == 2) {
		int t = K / 3;
		for (i = 1; i <= n; i++) {
			T[i] = GoB(i,t/2);
		}
		for (i = 1; i <= n; i++) {
			if (t % 2 == 0) {
				Res[i] = GoA(q[T[i]], (t + 1) / 2);
			}
			else {
				Res[i] = GoA(qr[T[i]], (t + 1) / 2);
			}
		}
	}

	if (K % 3 == 0) {
		int t = K / 3 - 1;
		for (i = 1; i <= n; i++) {
			T[i] = GoB(i, t / 2);
		}
		for (i = 1; i <= n; i++) {
			if (t % 2 == 0) {
				Res[i] = GoA(q[pr[T[i]]], (t + 1) / 2);
			}
			else {
				Res[i] = GoA(p[qr[T[i]]], (t + 1) / 2);
			}
		}
	}

	if (K % 3 == 1) {
		int t = K / 3 - 1;
		for (i = 1; i <= n; i++) {
			T[i] = GoB(i, t / 2);
		}
		for (i = 1; i <= n; i++) {
			if (t % 2 == 0) {
				Res[i] = GoA(q[pr[qr[T[i]]]], (t + 1) / 2);
			}
			else {
				Res[i] = GoA(q[p[qr[T[i]]]], (t + 1) / 2);
			}
		}
	}
	for (i = 1; i <= n; i++)printf("%d ", Res[i]);
}
int main() {
	U[1].push_back(0);
	U[2].push_back(2);
	int i;
	for (i = 3; i <= 30; i++) {
		U[i] = Make(U[i - 1], U[i - 2]);
	}
/*	for (int j = 1; j <= 3; j++) {
		for (i = j; i <= 30; i += 3) {
			for (auto &t : U[i])printf("%d ", t);
			puts("");
		}
	}*/
	Solve();
	return 0;
}

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

int main(void){
    int n, a, b;
    cin >> n >> a >> b;
    
    int ans;
    
    if(n*a>b) ans = b;
    else ans = n*a;
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
#define PI 3.1415926535897932384626433832795028
#define INF (1<<29)
#define LINF (1LL<<60)
using namespace std;
using INT = long long;
using P = pair<int,int> ;

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



Measured memory_bytes: 3624
#include <iostream>
using namespace std;
int N, K, M;
int C[305][305];
int DP[305][305], Partial[305][305];
inline void Add(int& x, int y)
{
    x += y;
    if(x >= M)
        x -= M;
}
void precalcC()
{
    C[0][0] = 1;
    for(int i = 1; i <= 302; i++)
        C[i][0] = 1;
    for(int i = 1; i <= 302; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            C[i][j] = C[i - 1][j];
            Add(C[i][j], C[i - 1][j - 1]);
        }
    }
}
void Solve()
{
    for(int i = 0; i <= K; i++)
        DP[1][i] = 1, Partial[1][i] = i + 1;
    for(int i = 2; i <= N + 1; i++)
    {
        for(int x = 0; x <= K; x++)
        {
            for(int k = 1; k < i; k++)
            {
                int aux = (1LL * DP[i - k][x] * C[i - 2][k - 1]) % M;
                int aux2 = Partial[k][K] - Partial[k][x];
                if(aux2 < 0)
                    aux2 += M;
                Add(DP[i][x], (1LL * aux * aux2) % M);
            }
            Partial[i][x] = DP[i][x];
            if(x > 0)
                Add(Partial[i][x], Partial[i][x - 1]);
        }
    }
    cout << DP[N + 1][0] << "\n";
}
int main()
{
    cin >> N >> K >> M;
    precalcC();
    Solve();
    return 0;
}


Measured memory_bytes: 1280
#include <iostream>

using namespace std;

int main()
{
   int N,A,B;
   cin>>N>>A>>B;
 if(N>=1&&A>=1&&B>=1&&N<=20&&A<=50&&B<=50){
   if((N*A)<B){
       cout<<N*A;
   }
   if(B<=(N*A)){
       cout<<B;
   }
}
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
  int n, m;
  int l = 0;
  int r = 100000000;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int t = 0;
    cin >> t;
    if (t > l) l = t;
    cin >> t;
    if (t < r) r = t;
  }
  if (r >= l)
    cout << r-l+1 << endl;
  else
    cout << 0 << endl;

  return 0;
}


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

int main() {
	int q;
	cin >> q;
	list<int> v;
	list<int>::iterator it=v.begin();

	for (int i = 0; i < q; i++) {
		int c; cin >> c;
		if (c == 0) {
			int x;
			cin >> x;
			it = v.insert(it,x);
		}
		else if (c == 1) {
			int d;
			cin >> d;
			for (int i = 0; i < abs(d); i++) {
				if(d<0) it--;
				else it++;
			}
		}
		else {
			it = v.erase(it);
		}
	}
	for (auto itr=v.begin(); itr!=v.end(); itr++) {
		cout << *itr << endl;
	}
}
	



Measured memory_bytes: 18552
from bisect import bisect_right
N, M = map(int, input().split())
S = input()

A = [i for i, s in enumerate(S) if s == '0']
now = N
ans = []

while True:
    left = bisect_right(A, now - M - 1)
    new = A[left]
    ans.append(now - new)
    if new == 0:
        break
    if new == now:
        print(-1)
        exit()
    now = new

print(*ans[:: -1])

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

string S;
int A,B;

int main(){
	cin>>S;
	if(S.at(2)==S.at(3) && S.at(4)==S.at(5)){
		cout<<"Yes"<<endl;
	}
	else
		cout<<"No"<<endl;
}

Measured memory_bytes: 256
m[10][2],x[10][2],z[10][2],zz[10][2];
rotx[4][2]={{1,0},{0,-1},{-1,0},{0,1}};
roty[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
mov[4][2]={{0,0},{0,0},{0,0},{0,0}};
main(N,M,Z,t,i,j,k,mxm,mym,mxM,myM,zxm,zym,zxM,zyM){
  for(;scanf("%d",&N),N;puts("+++++")){
    /*input zero*/
    zxm=zym=9999,zxM=zyM=-9999;
    for(scanf("%d",&Z),i=0;i<Z;i++){
      scanf("%d%d",z[i],z[i]+1);
      if(zxm>z[i][0])zxm=z[i][0];
      if(zym>z[i][1])zym=z[i][1];
      if(zxM<z[i][0])zxM=z[i][0];
      if(zyM<z[i][1])zyM=z[i][1];
    }
    for(i=0;i<Z;i++)z[i][0]-=zxm,z[i][1]-=zym,zz[Z-1-i][0]=z[i][0],zz[Z-1-i][1]=z[i][1];
    zxM-=zxm,zyM-=zym;
    for(j=0;j<N;j++){
      /*input line*/
      mxm=mym=9999,mxM=myM=-9999;
      for(scanf("%d",&M),i=0;i<M;i++){
        scanf("%d%d",m[i],m[i]+1);
        if(mxm>m[i][0])mxm=m[i][0];
        if(mym>m[i][1])mym=m[i][1];
        if(mxM<m[i][0])mxM=m[i][0];
        if(myM<m[i][1])myM=m[i][1];
      }
      for(i=0;i<M;i++)m[i][0]-=mxm,m[i][1]-=mym;
      mxM-=mxm,myM-=mym;
      if(M!=Z)continue;
      mov[1][0]=myM,mov[2][0]=mxM,mov[2][1]=myM,mov[3][1]=mxM;
      /*compare*/
      for(k=0;k<4;k++){
        for(i=0;i<M;i++)x[i][0]=rotx[k][0]*m[i][0]+rotx[k][1]*m[i][1]+mov[k][0],x[i][1]=roty[k][0]*m[i][0]+roty[k][1]*m[i][1]+mov[k][1];
        if(!memcmp(x,z,4*2*M)||!memcmp(x,zz,4*2*M))printf("%d\n",j+1),k=4;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline char GET(void)
{
  static char buf[1<<15],*s1=buf,*s2=buf;
  return s1==s2&&(s2=(s1=buf)+fread(buf,1,1<<15,stdin),s1==s2)?EOF:*s1++;
}
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=GET();while(c<48||c>57){f^=c==45,c=GET();}
  while(c>47&&c<58){x=x*10+c-48,c=GET();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
static inline int Max(int x,int y){return x>y?x:y;}
static inline void AscRadix32(int *a,const int sz)
{
  int x,shift=0,elem[0400],temp[sz];
  while(shift<040)
  {
    int bucket[0400]={0};
    rep(i,sz){x=(a[i]>>shift)&0377;bucket[x]++;temp[i]=a[i];}
    elem[0]=0;rep(i,0377)elem[i+1]=elem[i]+bucket[i];
    rep(i,sz){x=(temp[i]>>shift)&0377;a[elem[x]]=temp[i];elem[x]++;}
    shift+=010;
  }
}
int work[10006][3],sz=0;
static inline void Add(int x,int y,int v){work[sz][0]=x;work[sz][1]=y;work[sz++][2]=v;}
int main(void)
{
  int N=IN(),A[3*N],dp[N][N],B[N],mx,extra=0;
  rep(i,3*N)A[i]=IN()-1;
  memset(B,-0x3f,sizeof(B));
  memset(dp,-0x3f,sizeof(dp));
  dp[A[0]][A[1]]=dp[A[1]][A[0]]=B[A[0]]=B[A[1]]=mx=0;
  rep(i,N-1)
  {
    int x[3]={A[3*i+2],A[3*i+3],A[3*i+4]};
    AscRadix32(x,3);
    if(x[2]==x[0]){extra++;continue;}
    if(x[0]==x[1])rep(j,N)Add(j,x[2],dp[j][x[0]]+1);
    if(x[1]==x[2])rep(j,N)Add(j,x[0],dp[j][x[1]]+1);
    rep(j,3)Add(x[j==0],x[j==2?1:2],dp[x[j]][x[j]]+1);
    rep(j,3)rep(k,j)Add(x[j],x[k],mx);
    rep(j,N)rep(k,3)Add(j,x[k],B[j]);
    rep(j,sz)if(dp[work[j][0]][work[j][1]]<work[j][2])
      dp[work[j][0]][work[j][1]]=dp[work[j][1]][work[j][0]]=work[j][2],
      B[work[j][0]]=Max(B[work[j][0]],work[j][2]),
      B[work[j][1]]=Max(B[work[j][1]],work[j][2]),mx=Max(mx,work[j][2]);
    sz=0;
  }
  return OUT(Max(mx,dp[A[3*N-1]][A[3*N-1]]+1)+extra),0;
}

Measured memory_bytes: 17244
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(a[k - 1])



Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
#define pb push_back
long long mod=1000000007;

int main()
{
    int n;
    string s;
    cin>>n;
    cin>>s;
    long long cnt[30];
    for(int i=0;i<30;i++)cnt[i]=0;
    for(int i=0;i<n;i++){
        cnt[ s[i] - 'a' ]++;
    }
    long long res=1;
    for(int i=0;i<26;i++){
        res*=( cnt[i]+1 )%mod;
        res%=mod;
    }
        res--;
        if(res<0) res+=mod;
        cout<<res<<endl;

	return 0;
}



















Measured memory_bytes: 1020
N,M = map(int,input().split())
X = list(map(int,input().split()))

if N >= M:
    print(0)
else:
    X.sort()
    dis = []
    for i in range(M-1):
        dis.append(X[i+1]-X[i])
    dis.sort()
    p = 0
    for j in range(M-N):
        p += dis[j]
    print(p)

Measured memory_bytes: 13968
#include <stdio.h>
int main(void){
    int i,j,k;
    int n,m,l;
    int a[101][101],b[101][101];
    long int s;
    
    scanf("%d %d %d",&n,&m,&l);
    
    for(i=0;i<n;i++){
        for(j=0;j<m;j++)
        scanf("%d",&a[i][j]);
    }
        
    for(i=0;i<m;i++){
        for(j=0;j<l;j++)
        scanf("%d",&b[i][j]);
    }    
        
        for(i=0;i<n;i++){
            for(j=0;j<l;j++){
               s=0;
               for(k=0;k<m;k++)
               s+=a[i][k]*b[k][j];
               printf("%ld",s);
                 if(j+1==l)
                     printf("\n");
                 else
                    printf(" ");
            }
        }    
    return(0);
}



Measured memory_bytes: 2104
# coding: utf-8
# Your code here!

n,a,b,c = [int(i) for i in input().split()]
l = [int(input()) for _ in range(n)]

ans = 10000000
for i in range(1,2**n):
    for j in range(1,2**n):
        for k in range(1,2**n):
            cost=0
            if j&k != 0 or i&k != 0 or i&j!=0:
                continue
            L = [l[ii] for ii in range(n) if (2**ii)&k !=0]
            ck = 10*(len(L)-1) + abs(c-sum(L))  
            cost += ck
            LL = [l[ii] for ii in range(n) if (2**ii)&j !=0]
            bk = 10*(len(LL)-1) + abs(b-sum(LL))
            cost += bk
            LLL = [l[ii] for ii in range(n) if (2**ii)&i !=0]
            ak = 10*(len(LLL)-1) + abs(a-sum(LLL))
            cost += ak
#            print(cost,ak,bk,ck,i,j,k,L)
            ans = (ans if ans<cost else cost)

print(ans)
            

Measured memory_bytes: 70488
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int h[MAXN], dp[MAXN];
int main ()
{
    ///for(int i = 1; i <= MAXN - 5; ++i) h[i] = MAXN;
    int n; cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    dp[2] = abs(h[1] - h[2]);
    for(int i = 1; i <= n - 1; ++i){
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
        dp[i + 2] = dp[i] + abs(h[i + 2]  - h[i]);
    }
    cout << dp[n] << " ";
    return 0;
}
///dp[i] += (dp[i - 1] < dp[i - 2]) ? dp[i - 1] + abs(h[i - 1] - h[i]) : dp[i - 2] + abs(h[i - 2] - h[i]);


Measured memory_bytes: 1024
//
//  main.cpp
//  Entrance Examination
//
//  Created by x15071xx on 2017/06/15.
//  Copyright ?? 2017??´ AIT. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

int main(int argc, const char * argv[]) {
    
    while(1){
        
        int m,nmin,nmax;
        vector<int> score;
        vector<int> gap;
        
        cin >> m >> nmin >> nmax;
        
        if (m == 0 && nmin == 0 && nmax == 0) {
            break;
        }
        int tmp;
        for (int i = 0; i < m; i++) {
            cin >> tmp;
            score.push_back(tmp);
        }
        
        
        for (int i = nmin-1; i < nmax; i++) {
            gap.push_back(abs(score[i]-score[i+1]));
        }
        
        nmax = -1;
        for (int i = 0; i < gap.size(); i++) {
            if (gap[nmax] <= gap[i]) {
                nmax = i;
            }
        }
        
        cout << nmin+nmax << endl;
        
    }
    return 0;
}

Measured memory_bytes: 3152
d = Hash[*%w(^ v < >).zip([[-1, 0], [1, 0], [0, -1], [0, 1]]).flatten(1)]

loop {
    m, n = gets.split.map &:to_i
    break if m == 0

    a = (1..m).map{ gets.scan /./ }

    y, x = 0, 0
    reached = {[0, 0] => 0}
    loop {
        if !d[a[y][x]]
            puts [x, y] * ' ' 
            break
        end
        dy, dx = d[a[y][x]]
        y += dy
        x += dx
        if reached[[y, x]] 
            puts 'LOOP'
            break
        end
        reached[[y, x]] = 0 
    }   
}

Measured memory_bytes: 8860
def main(N,Y):
    # type: (int, int) -> None
    """
    次の方程式
        x + y + z = N
        10x + 5y + z = Y
    の解を探索する．zを消去すると
        9x + 4y = Y - N
      where
        x >= 0
        y >= 0
        x + y <= N
    w = 2x+y と置くと
        x + 4w = Y - N
      where
        x >= 0
        w >= 0
        w - x <= N
    xを消去すると条件は
        w  >= 0
        4w <= Y - N
        5w <= Y
        9w >= 2(Y - N)
    であり
        x = Y - N - 4w
        y = w - 2x
        z = N - x - y
    wを適当にboundした後は x>=0 and y>=0 and z >= 0 でfilteringするのが安心だが
    練習のために w のみでfilteringしてみる
    """
    Y = Y // 1000
    lb = (2*(Y-N)-1) // 9 + 1
    ub = min ((Y-N) // 4, Y // 5)
    ans = [ (x,y,z) for w in range(lb,ub+1) for x in [Y-N-4*w] for y in [w - 2*x] for z in [N - x - y] ]
    if ans == []:
        print("-1 -1 -1")
    else:
        x,y,z = ans[0]
        print("{0} {1} {2}".format(x,y,z))
    return

if __name__ == '__main__':
    N, Y, *_ = map(int, input().split())
    main(N,Y)


Measured memory_bytes: 3064
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
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 (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int dp[1000010][2];
	string S;
	cin >> S;

	reverse(S.begin(), S.end());
	S += '0';
	int N = S.size();
	REP(i, N + 1)REP(j, 2)dp[i][j] = INF;
	dp[0][0] = 0;

	REP(i, N) {
		REP(j, 2) {
			int x = S[i] - '0';

			x += j;
			REP(a, 10) {
				int ni = i + 1, nj = 0;
				int b = a - x;
				if (b < 0) {
					nj = 1;
					b += 10;
				}
				chmin(dp[ni][nj], dp[i][j] + a + b);
				//dp[ni][nj] = min(dp[ni][nj], dp[i][j] + a + b);
			}
		}
	}
	
	cout << dp[N][0] << endl;
	return 0;
}



Measured memory_bytes: 17052
#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cout<<(#v)<<":";for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;
#define printVS(vs) cout<<(#vs)<<":"<<endl;for(auto(s):(vs)){cout<<(s)<< endl;}
#define printVV(vv) cout<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cout<<" "<<(x);}cout<<endl;}
#define printP(p) cout<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cout<<(#vp)<<":"<<endl;for(auto(p):(vp)){cout<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 2e9;
const int mod = 1e9 + 7;


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

    int n;
    while (cin >> n, n) {
        vi a(n);
        rep(i, n) cin >> a[i];

        int ans = inf;
        rep(i, n) {
            rep(j, i) {
                chmin(ans, abs(a[i] - a[j]));
            }
        }
        cout << ans << endl;        
    }
}

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

int main() {
    int N; cin >> N;
    string S; cin >> S;
    vector<char> A(N);
    A.at(0) = S.at(0);
    int j = 0;
    for (int i = 0; i < S.size(); i++) {
        if (S.at(i) != A.at(j)) {
            j++;
            A.at(j) = S.at(i);
        }
    }
    cout << j + 1 << endl;
}

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

int main()
{
	int N;
	cin >> N;
	vector<int> L(N), sum(N + 1);
	for (int i = 0; i < N; i++) {
		cin >> L[i];
		sum[i + 1] = sum[i] + L[i];
	}
	int res = sum[N];
	for (int i = 1; i <= sum[N] - 1; i++) {
		vector<int> dp(N + 1, -sum[N]);
		dp[0] = i;
		for (int j = 0; j < N; j++) {
			for (int k = 0; k <= j; k++) if (sum[j + 1] - sum[k] <= i) {
				dp[j + 1] = max(dp[j + 1], min(dp[k], sum[j + 1] - sum[k]));
			}
		}
		res = min(res, i - dp[N]);
	}
	cout << res << endl;
	return 0;
}



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

/*
f(L,R)=R-L+1-{i|L<=u[i],v[i]<=R}
つまり、長さの方は1がn,2がn-1,3がn-2,...だから合計でi*(n-i-1)のiが1~n
u[i],v[i]の方はu[i]<v[i]として、1-indexedでu[i]*(n-v[i]+1)
*/
#define int long long

signed main(){
  int n,ans=0;cin>>n;
  for(int i=0;i<n;i++)ans+=(i+1)*(n-i);
  for(int i=1;i<n;i++){
    int u,v;cin>>u>>v;if(u>v)swap(u,v);
    ans-=u*(n-v+1);
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define int long long
#define P(x) {if (debug) cout << x << endl;}
#define H(x) P(#x << ": " << (x))
#define FR(i,a,b) for (int i=(a); i<(b); i++)
#define F(i,n) FR(i,0,n)
#define DR(i,a,b) for (int i=(b); i-->(a);)
#define D(i,n) DR(i,0,n)
#define S(s) (int)(s).size()
#define ALL(v) v.begin(), v.end()
#define MI(a,v) a = min(a,v)
#define MA(a,v) a = max(a,v)
#define V vector
#define pb push_back
#define mt make_tuple
using namespace std;
template<class T> ostream &operator<<(ostream &os, V<T> v) {
    F(i,S(v)) os<<(i?" ":"")<<v[i];
    return os;
}
const bool debug = 1;

V<bool> vis;
V<V<int>> g;
void dfs(int u, V<int> &out) {
    if (vis[u]) return;
    vis[u] = true;
    out.pb(u);
    for (int v : g[u])
        dfs(v, out);
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin>>n;
    g.resize(n);
    vis.assign(n, false);
    F(i,n-1) {
        int a,b; cin>>a>>b;
        a--, b--;
        g[a].pb(b);
        g[b].pb(a);
    }
    V<int> cs(n);
    F(i,n) cin>>cs[i];
    sort(ALL(cs));
    int sum = 0;
    F(i,n-1) sum += cs[i];
    reverse(ALL(cs));
    V<int> out;
    dfs(0, out);
    V<int> ds(n);
    F(i,n) ds[out[i]] = cs[i];
    cout<<sum<<"\n";
    cout<<ds<<"\n";
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (!(i % 3 == 0 || i % 5 == 0))
            sum += i;
    }
    cout << sum << '\n';
    return 0;
}

Measured memory_bytes: 3628
A = [ord(a) - 97 for a in input()]
N = len(A)
D = {}
ans = N * (N - 1) // 2 + 1
for i, a in enumerate(A):
    if a in D:
        ans -= D[a]
        D[a] += 1
    else:
        D[a] = 1
print(ans)

Measured memory_bytes: 5096
#include <iostream>
#include <list>
#include <vector>
#include <cassert>
// #include <string>
// #include <algorithm>
// #include <numeric>
// #include <queue>
// #include <cmath>
// #include <set>
// #include <map>
// #include <iomanip>

#define MOD 1000000007
// #define INF 1000000001
#define S 100001

using namespace std;
typedef unsigned long long ull;
// typedef long long ll;

void p_() {
    cout << "\n";
}
template<class Head, class... Body>
void p_(Head head, Body... body) {
    cout << head << ",";
    p_(body...);
}


vector<ull> fac(S+1);
vector<ull> ifac(S+1);

ull pow_mod(ull x, ull n) {
    ull ans = 1;
    while (n != 0) {
        if (n & 1) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD;
        n = n >> 1;
    }
    return ans;
}

ull comb_mod(ull a, ull b) {
    assert(a > 0 && b >= 0 && a >= b);
    ull tmp = ifac[a-b] * ifac[b] % MOD;
    return tmp * fac[a] % MOD;
}

void init_fac() {
    fac[0] = 1;
    ifac[0] = 1;
    for (int i = 1; i <= S; i++) {
        fac[i] = fac[i-1] * i % MOD;
        ifac[i] = ifac[i-1] * pow_mod(i, MOD-2) % MOD;
    }
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    vector<vector<int>> idxs(n);
    int n_l, n_r;
    for (int i = 0; i < n+1; ++i) {
        int a;
        cin >> a;
        int key = a-1;
        idxs[key].push_back(i);
        if (idxs[key].size() == 2) {
            n_l = idxs[key][0];
            n_r = n - idxs[key][1];
        }
    }
    // cout << pos << " " << n - pos << endl;

    cout << n << endl;

    init_fac();
    for (int k = 2; k <= n+1; ++k) {
        ull num = comb_mod(n+1, k);
        if (n_l + n_r >= k-1) {
            // p_(n_l, n_r, k-1);
            num = (num + MOD - comb_mod(n_l + n_r, k-1)) % MOD;
        }
        cout << num << endl;
    }

    return 0;
}


Measured memory_bytes: 8192
A,B,C,D =map(int,input().split())
x = C
y = D
while y>0:
    x,y = y,x%y
E = (C//x)*D
bc = B//C
bd = B//D
be = B//E
b = B-(bc+bd-be)
ac = (A-1)//C
ad = (A-1)//D
ae = (A-1)//E
a = A-1-(ac+ad-ae)
print(b-a)

Measured memory_bytes: 61928
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    static String conversion(int a) {
        StringBuilder sb = new StringBuilder();

        int t = a / 3600;
        sb.append("0" + t + ":");
        a -= t * 3600;

        int h = a / 60;
        if (h < 10)
            sb.append("0");
        sb.append(h + ":");
        a -= h * 60;

        if (a < 10)
            sb.append("0");
        sb.append(a);

        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;

        while (!(line = br.readLine()).equals("-1 -1 -1")) {
            String[] ths = line.split(" ");
            int T = Integer.parseInt(ths[0]);
            int H = Integer.parseInt(ths[1]);
            int S = Integer.parseInt(ths[2]);
            int seconds = 7200 - 3600 * T - 60 * H - S;
            System.out.println(conversion(seconds));
            System.out.println(conversion(seconds * 3));
        }

    }
}


Measured memory_bytes: 24260
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>



using namespace std;


int main()
{
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    int m=a+b,n=c+d;
    if(m==n) cout<<"Balanced"<<endl;
    else if(m>n) cout<<"Left"<<endl;
    else cout<<"Right"<<endl;


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll l=c/__gcd(c,d)*d;
    ll cc=b/c-(a-1)/c,cd=b/d-(a-1)/d,ccd=b/l-(a-1)/l;
    cout<<b-a+1-cc-cd+ccd<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
  int n,m,x;
  cin >> n >> m >> x ;
  int L=0;
  int R=0;
  for(int i=1;i<=m;i++){
    int a;
    cin >> a;
    if (a<x){
      L++;
      }else{
        R++;
      }
      }
      cout << min(L,R) << endl;
      return 0 ;
      }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << ele << endl
#define print10(ele) cout << fixed << setprecision(10) << ele << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int x = 0;
  int ans = 0;
  REP(i, n) {
    if (s[i] == 'I')
      x++;
    else
      x--;
    ans = max(ans, x);
  }
  print(ans);
  return 0;
}

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

int gcd(int a, int b){
    if(a==0) return b;
    if(b==0) return a; 

    int x=a;
    int y=b;
    if(x>y){
        int t=y;
        y=x;
        x=t;
    }
    int r=y%x;
    while(r!=0){
        y=x;
        x=r;
        r=y%x;
    }
    return x;
}
 
int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    
    vector<int> l(n+1), r(n+1);
    l[0]=0;
    r[n]=0;

    for(int i=1; i<=n; i++){
        l[i]=gcd(a[i-1], l[i-1]);
    }
    for(int i=n-1; i>=0; i--){
        r[i]=gcd(a[i], r[i+1]);
    }
    
    int m=0;
    for(int i=0; i<=n; i++){
        int g=gcd(r[i+1], l[i]);
        m=max(m,g);
    }

    cout<<m<<endl;
}


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

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define FORR(i,m,n) for(int i=m;i>=n;i--)
#define pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 999999999999

using namespace std;

#define int long long

int32_t main(){
	int n;
	string a, b;
	cin >> n >> a >> b;
	
	int ans=2*n;
	for(int i=n-1; i>=0; i--){
		if(a[i]==b[0]){
			int cnt=1;
			int k=1;
			bool flag=true;
			for(int j=i+1; j<n; j++){
				if(a[j]!=b[k]){
					flag=false;
					cnt+=INF;
					break;
				}
				cnt++;
				k++;
			}
			
			if(flag) ans=min(2*n-cnt, ans);
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
import sys
l = sys.stdin.readline().strip()
N, M, K = map(int, l.split())
comb_quick = {}
mod = 998244353
C = [1]
for i in range(1, (N-1) // 2 + 2):
    next = C[-1] * (N-i) * pow(i, mod-2, mod)
    C.append(next % mod)

res = 0

for x in range(K+1):
    crt =  (pow(M-1, N-x-1, mod) * M) % mod 
    crt %= mod
    #print("start")
    idx = min(x, N-1-x)
    crt *= C[idx]
    #print("end")
    crt %= mod
    res += crt
    res %= mod

print(res)

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


#define int long long 

int ask(int x) {
	cout << "? " << x << endl;
	fflush(stdout);
	string str; cin >> str;
	return str == "Y";
}

/*int ask(int x) {
	int k = 100;
	return ((x <= k && to_string(x) <= to_string(k)) ||
			(x > k && to_string(x) > to_string(k)));
}*/

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int len;
	for(int i = 10; i >= 0; i--) {
		if(ask((int)pow(10, i))) {
			len = i;
			break;
		}
	}

	if(len > 9) {
		int sum = 0;
		for(int i = 1; i <= 10; i++) {
			sum = sum * 10 + 9;
			if(ask(sum)) {
				len = i - 1;
				break;
			}
		}
		cout << "! " << (int)pow(10, len) << endl;
		fflush(stdout);
		return 0;
	}

	int l = (int)pow(10, len), r = (int)pow(10, len + 1) - 1;

	while(l < r) {
		int mid = (l + r + 1) >> 1;
		if(!ask(mid * 10)) l = mid;
		else r = mid - 1;
	}

	cout << "! " << l + 1 << endl;
	fflush(stdout);
}

Measured memory_bytes: 4068
function Main(input) {
    const lines = input.split('\n')
    const s = lines[0];

    if (s == 'ABC') {
        console.log('ARC')
    } else if (s == 'ARC') {
        console.log('ABC')
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29480
n=int(input())
a=list(map(int,input().split()))
c=[a[i]-i-1 for i in range(n)]
cum_c=[0]*n
c.sort()
cum_c[0]=c[0]
for i in range(1,n):
  cum_c[i]=cum_c[i-1]+c[i]
ans=min(cum_c[n-1]-n*c[0],n*c[n-1]-cum_c[n-1])
for i in range(1,n):
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i-1])
  ans=min(ans,cum_c[n-1]-2*cum_c[i-1]+(2*i-n)*c[i])
print(ans)

Measured memory_bytes: 29124
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int dp[1000000];
string S;
int main() {
	cin >> S; dp[0] = 1;
	for (int i = 0; i < S.size(); i++) {
		if (dp[i] == 0)continue;
		if (i + 5 <= S.size() && S.substr(i, 5) == "dream")dp[i + 5] = 1;
		if (i + 7 <= S.size() && S.substr(i, 7) == "dreamer")dp[i + 7] = 1;
		if (i + 5 <= S.size() && S.substr(i, 5) == "erase")dp[i + 5] = 1;
		if (i + 6 <= S.size() && S.substr(i, 6) == "eraser")dp[i + 6] = 1;
	}
	if (dp[S.size()] == 1)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 896
#pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 2147483647
#define LLINF 9223372036854775807LL
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef int_fast64_t ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
inline void fastio(){cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}
ll gcd(ll a,ll b){ll c=max(a,b);ll d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n){ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k){ll b=1;k=min(n-k,k);DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

ll N;
ll A[50];
ll m, q, d, n;

inline ll divide(int i) {
    m = 1, q = 0, d = N, n = A[i];
    while (d <= n) {
        d <<= 1;
        m <<= 1;
    }
    while (1 < m) {
        d >>= 1;
        m >>= 1;
        if (n >= d) {
            n -= d;
            q |= m;
        }
    }
    return q;
}

int main() {
    fastio();
    cin >> N;
    REP(i, N) cin >> A[i];
    ll ans = 0, tmp, prev = 0, res, M = N + 1;
    while (1) {
        tmp = 0;
        REP(i, N) {
           A[i] += prev;
           if(A[i] < N) continue;
           res = divide(i);
           A[i] -= res * M;
           tmp += res;
        }
        if(tmp < 1) break;
        ans += tmp;
        prev = tmp;
    }
    printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 256
//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
signed main() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=0; i<n; ++i) {
        int l, r;
        cin >> l >> r;
        ans += (r-l)+1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef set<int> S;
typedef S::iterator Sit;

int getNum(string a){
  int res=0;
  for(int i=0;i<a.size();i++) res=res*10+a[i]-'0';
  return res;
}

map<string,P> val;
vector<string> el;
int n;

int calc(){
  stack <S> stk;
  for(int i=0;i<n;i++){
    string e=el[i];
    S t;
    if(isdigit(e[0]))t.insert(getNum(e));
    else if(isalpha(e[0])){
      int l=val[e].first,r=val[e].second;
      while(l<=r)t.insert(l++);
    }
    else {
      S B=stk.top();stk.pop();
      S A=stk.top();stk.pop();
      for(Sit i=A.begin();i!=A.end();i++)
	for(Sit j=B.begin();j!=B.end();j++){
	  int a=*i,b=*j,r;
	  if(e[0]=='+')r=(a+b)%256;
	  if(e[0]=='-')r=(a-b+256)%256;
	  if(e[0]=='*')r=(a*b)%256;
	  if(e[0]=='/'){
	    if(!b) return 0;
	    r=(a/b)%256;
	  }
	  t.insert(r);
	}
    }
    stk.push(t);
  }
  return 1;
}

int main(){
  int m;
  cin>>m;
  for(int i=0,a,b;i<m;i++){
    string t;
    cin>>t>>a>>b;
    val[t]=P(a,b);
  }
  cin>>n;
  el.resize(n);
  for(int i=0;i<n;i++) cin>>el[i];
  cout<<(calc()?"correct":"error")<<endl;
  return 0;
}

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

int main() {
  ll n, a, b;
  cin >> n >> a >> b;
  ll ans = 2e18;
  if ((b - a) % 2 == 0) ans = min(ans, (b - a) / 2);
  else {
    ans = min(ans, (n-b) + (b-a-1)/2 + 1);
    ans = min(ans, (a-1) + (b-a-1)/2 + 1);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
# -*- coding: utf-8 -*-
"""
B - すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit)
https://atcoder.jp/contests/abc047/tasks/abc047_b

"""
import sys


def solve(W, H, N, points):
    grid = [[1]*W for _ in range(H)]
    for x, y, a in points:
        if a == 1:
            for cy, row in enumerate(grid):
                for cx in range(x):
                    row[cx] = 0
        elif a == 2:
            for cy, row in enumerate(grid):
                for cx in range(x, W):
                    row[cx] = 0
        elif a == 3:
            for cy in range(y):
                grid[cy] = [0]*W
        elif a == 4:
            for cy in range(y, H):
                grid[cy] = [0]*W

    return sum([sum(row) for row in grid])


def main(args):
    W, H, N = map(int, input().split())
    points = [[int(i) for i in input().split()] for _ in range(N)]
    ans = solve(W, H, N, points)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ll long long
#define pii pair<int,int>


void test_case()
{
    ll k,n;
    cin>>k>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
        cin>>a[i];
    ll maxgap=0;
    for(int i=0;i<n-1;i++)
        maxgap=max(maxgap, a[i+1]-a[i]);
    maxgap=max(maxgap, a[0]+k-a[n-1]);
    cout<<k-maxgap;
}

int main()
{
    fastio
//    int t;
//    cin>>t;
//    while(t--)
    test_case();
}


Measured memory_bytes: 5188
#include<stdio.h>
int main(void){
int a,b;
scanf("%d %d",&a,&b);
if(a<b){
printf("a < b");
}
if(a>b){
printf("a > b");
}
if(a == b){
printf("a == b");
}
printf("\n");
return 0;
}


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

int main() {
    int k;
    cin >> k;
    queue<ll> q;
    for(ll a = 1; a < 10; a++){
        q.push(a);
    }
    while (--k) {
        ll x = q.front();
        q.pop();
        ll key = x % 10;
        if (key != 0) q.push(10 * x + key - 1);
        q.push(10 * x + key);
        if (key != 9) q.push(10 * x + key + 1);
    }
    cout << q.front() << endl;
}

Measured memory_bytes: 1792
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

C=input()

if C <= 'Z':
    print('A')
else:
    print('a')


Measured memory_bytes: 9240
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int r[n+1],g[n+1],b[n+1],rn=0,gn=0,bn=0;
	for(int i=0;i<n;i++){
		if(s[i]=='R'){
			rn++;
			r[rn]=i;
		}
		if(s[i]=='G'){
			gn++;
			g[gn]=i;
		}
		if(s[i]=='B'){
			bn++;
			b[bn]=i;
		}
	}
	long long ans=0;
	for(int i=1;i<=rn;i++){
		for(int j=1;j<=bn;j++){
			int xx=gn;
			if(min(r[i],b[j])-abs(r[i]-b[j])>=0){
				if(binary_search(g+1,g+gn+1,min(r[i],b[j])-abs(r[i]-b[j]))){
					xx--;
				}
			}
			if(max(r[i],b[j])+abs(r[i]-b[j])<n){
				if(binary_search(g+1,g+gn+1,max(r[i],b[j])+abs(r[i]-b[j]))){
					xx--;
				}
			}
			if(abs(r[i]-b[j])%2==0){
				if(binary_search(g+1,g+gn+1,abs(r[i]-b[j])/2+min(r[i],b[j]))){
					xx--;
				}
			}
			//cout<<r[i]<<" "<<b[j]<<" "<<xx<<" "<<max(r[i],b[j])+abs(r[i]-b[j])<<endl;
			ans+=xx;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3640
import java.util.*;

class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int[] size = new int[3];
                for(int i = 0 ; i < 3 ; i++){
                        size[i] = sc.nextInt();
                }   
                while(size[0] != 0){ 
                        int n = sc.nextInt();
                        int minr2 = minr2(size);
                        for(int i = 0 ; i < n ; i++){
                                int r = 2*sc.nextInt();
                                if(r*r > minr2){
                                        System.out.println("OK");
                                }else{
                                        System.out.println("NA");
                                }   
                        }   
                        for(int i = 0 ; i < 3 ; i++){
                                size[i] = sc.nextInt();
                        }   
                }   
                sc.close();
        }   
        static int minr2(int[] size){
                Arrays.sort(size);
                return size[0]*size[0]+size[1]*size[1];
        }   
}

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

int main(){
    int n; long long res=1, a[100005], lim=1;
    for (int i=0; i<18; ++i) lim*=10;
    scanf("%d", &n);
    for (int i=0; i<n; ++i){
        scanf("%lld", &a[i]);
        if (a[i]==0){
            printf("0");
            return 0;
        }
    }
    for (int i=0; i<n; ++i){
        if (res>(lim/a[i])){
            printf("-1");
            return 0;
        }
        res*=a[i];
    }
    printf("%lld", res);
    return 0;
}


Measured memory_bytes: 4504
#include <iostream>

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

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

	bool is2 = false;
	int cnt = 0;
	int i = 0;
	while( cnt < n ) {
		cnt += 1;
		if( a[ i ] == 2 ) {
			is2 = true;
			break;
		}
		i = a[ i ] - 1;
	}

	std::cout << ( is2 ? cnt : -1 ) << std::endl;
	return 0;
}


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

int main(){
  string str;
  cin>>str;
  int N=str.size();
  int f=true;
  for(int i=0;i<N;i++){
    f=f&&(str[i]==str[N-i-1]);
  }
  for(int i=0;i<(N-1)/2;i++)f=f&&(str[i]==str[(N-1)/2-i-1]);
  for(int i=0;i<=(N-3)/2;i++)f=f&&(str[(N+3)/2+i-1]==str[N-i-1]);
  if(f)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int K = scanner.nextInt();
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int input = scanner.nextInt();
			if (input >= K) {
				ans++;
			}
		}
		System.out.println(ans);
		scanner.close();
	}
}

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> v(n);
    for(int i = 0;i < n;i++){
        cin >> v[i];
    }
    long long ret = 0;
    for(int i = 0;i <= min(n,k);i++){
        for(int l = 0;l <= i;l++){
            vector<int> neg;
            long long val = 0;
            for(int j = 0;j < l;j++){
                if(v[j] < 0){
                    neg.push_back(v[j]);
                }
                val += v[j];
            }
            for(int j = 0;j < i-l;j++){
                if(v[n-1-j] < 0){
                    neg.push_back(v[n-1-j]);
                }
                val += v[n-1-j];
            }
            sort(neg.begin(),neg.end());
            for(int j = 0;j < min((int)neg.size(),k-i);j++){
                val -= neg[j];
            }
            ret = max(ret,val);
        }
    }
    cout << ret << endl;
}

Measured memory_bytes: 256
def usage():
    product = 1
    N, P = map(int, input().split())

    fct = factorize(P)

    for i in range(len(fct)):
        fct[i][1] = fct[i][1]//N

        if fct[i][1] >= 1:
            product = product*(fct[i][0]**fct[i][1])
    print(product)
    
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append([b, e])
        b, e = b + 1, 0
    if n > 1:
        fct.append([n, 1])
    return fct

if __name__ == '__main__':
    usage()

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>


 
using namespace std;

bool change_switch(vector<int> &switch_on,int N){

    bool flag1=false;

        for(int i=0; i<N ; i++){
             if(switch_on.at(i) ==0){
                 flag1=true;
             }
        }

        if(flag1==false){
            return false;
        }


        bool flag=false;


        switch_on.at(0)+=1;
        for(int i=0; i<N;i++){
            if(flag==true){
                switch_on.at(i)+=1;
                flag=false;
            }
            if(switch_on.at(i)==2){
                flag=true;
                switch_on.at(i)=0;
            }else{
                break;
            }            
        }



        return true;

}


int main(){
    int N;
    int M;
    int count=0;

    cin >> N >> M;

    vector<int> k(M,0);
    vector<int> p(M,0);
    vector<vector<int>> s;

    vector<int> switch_on(N,0);

 
    
    for(int i = 0; i<M;i++){
        
        cin >> k.at(i);

        for(int j=0; j<k.at(i); j++){
            vector<int> c;
            int b;
            cin >> b;

            s.push_back(c);
            s.at(i).push_back(b);


        }
    }

    for(int i = 0; i<M;i++){
        cin >> p.at(i);
    }

    do {
    
        bool all_light = true;
        for(int i=0; i< M; i++){
            int c=0;
            for(int j = 0; j<k.at(i); j++){
                c += switch_on.at(s.at(i).at(j)-1);
            }

            if(c%2 != p.at(i)){
                all_light =false;
                break;
            }
            
        }

        if(all_light == true){
            count +=1;
        }



         
    } while (change_switch(switch_on,N));

    cout << count << endl;
 





    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

    /*
    ||||||||||||||||||||||||||||||||||||||||||||||||
       |      |||         |      ||||    ||||  |   |
      | |     |   |      | |     |   |  |      |   |
     |   |    |    |    |   |    |   |  |      |   |
    |||||||   |    |   |||||||   |||     |||   |||||
    |     |   |   |    |     |   | |        |  |   |
    |     |   |||      |     |   |  ||  ||||   |   |
    ||||||||||||||||||||||||||||||||||||||||||||||||

    */
    using namespace std;
    //#include "testlib.h"
    #define ff first
    #define ss second
    #define mp make_pair
    #define all(v) v.begin(),v.end()
    #define int long long
    #define ll long long
    #define M 1000000007

    #define mii  map<ll ,ll >
    #define msi  map<string,ll >
    #define mis  map<ll int, string>
    #define rep(a,b)    for(ll i=a;i<b;i++)
    #define rep0(n)    for(ll i=0;i<n;i++)
    #define repi(i,a,b) for(ll i=a;i<b;i++)
    #define pb push_back
    #define vi vector<ll>
    #define mp make_pair
    #define vs vector<string>
    #define ppb pop_back
    #define endl '\n'
    #define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define r0 return 0;
    #define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
    #define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
    #define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
    #define input freopen("input.txt", "r", stdin);
    #define Set(a, s) 4(a, s, sizeof (a))
    #define FOR repi
    #define pii pair<int,int>
    //#define float long double
    ll max(ll a, ll b) { return (a > b)? a : b;}
    int min(int a, int b) { return (a < b)? a : b;}


     int solve()
     {
        int n;
        cin>>n;
        int m;
        cin>>m; vi ans(n+1,1);
        vi a(n+1,0); rep0(m) {int t;cin>>t;a[t]=1;ans[t]=0;}
       
        rep(1,n+1){
            if(a[i]) continue;
            ans[i]=ans[i-1];
            if(i>=2) ans[i]=(ans[i]+ans[i-2])%M;        
     
        }
        cout<<ans[n];
        }
    signed main()
    {   
        asdf
        int t=1;
        //cin>>t;
        while(t--)
        {
            solve();
        }     
        
}

Measured memory_bytes: 1792
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <algorithm>
using namespace std;

using ll = long long;
int const a[] { 2, 3, 5 };
int b[3], d;

ll f(ll n, unordered_map<ll, ll>& memo) {
    ll& ans = memo[n];
    if (n > 0 && ans == 0) {
        ans = 1e12;
        if (n < ans / d)
            ans = n * d;
        for (int i = 0; i < 3; i++) {
            int p = a[i], c = b[i];
            ll k = n / p, r = n % p;
            ans = min({ ans, f(k, memo) + r * d + c, r ? f(k + 1, memo) + (p - r) * d + c : ans });
        }
    }
    return ans;
}

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

    int t;
    for (cin >> t; t--;) {
        ll n;
        cin >> n;
        copy_n(istream_iterator<int>(cin), 3, b);
        cin >> d;
        unordered_map<ll, ll> memo{ {1, d} };
        cout << f(n, memo) << '\n';
    }
    return 0;
}


Measured memory_bytes: 4136