akhauriyash/Code-Regression huggingface dataset:
def search_down_index(index, depthes, L):
    "index?????????????§??????????????????¨?????????????????????"
    for i in range(index, L - 1):
        if depthes[i] > depthes[i + 1]:
            return i
    return None

def search_down_index_reverse(index, depthes, L):
    "index?????????????§??????????????????¨?????????????????????"
    for i in range(index, -1, -1):
        if depthes[i] > depthes[i - 1]:
            return i
    return None

def search_up_index(index, depthes, L):
    "index?????????????§??????????????????¨?????????????????????"
    for i in range(index, L - 1):
        if depthes[i] < depthes[i + 1]:
            return i
    return None

def search_up_index(index, depthes, L):
    "index?????????????§??????????????????¨?????????????????????"
    for i in range(index, -1, -1):
        if depthes[i] < depthes[i + 1]:
            return i
    return None

def search_index_by_depth(index, depth, depthes, L):
    for i in range(index, L):
        if depthes[i] == depth:
            return i
    return None

def search_index_by_depth_reverse(index, depth, depthes, L):
    for i in range(index, -1, -1):
        if depthes[i] == depth:
            return i
    return None

def calc_area(begin_index, end_index, depthes):
    init_depth = depthes[begin_index]
    area = 0
    for i in range(begin_index, end_index):
        d1 = depthes[i]
        d2 = depthes[i + 1]
        if d1 > d2:
            area += (init_depth - d2 - 0.5)
        elif d1 == d2:
            area += init_depth - d1
        else:
            area += (init_depth - d1 - 0.5)
    return area

depthes = []
depth = 0
depthes.append(0)
for c in input():
    if c == "/":
        depth += 1
    elif c == "?\" or c == "\\":
        depth += -1
    depthes.append(depth)

L = len(depthes)
pond_ranges = []
stack = []
left_begin_index = search_down_index(0, depthes, L)
right_begin_index = search_down_index_reverse(L - 1, depthes, L)
while left_begin_index != None and right_begin_index != None and left_begin_index < right_begin_index:
    dl = depthes[left_begin_index]
    dr = depthes[right_begin_index]
    if dl < dr:
        left_end_index = search_index_by_depth(left_begin_index + 1, dl, depthes, L)
        pond_ranges.append((left_begin_index, left_end_index))
        left_begin_index = search_down_index(left_end_index, depthes, L)
    else:
        right_end_index = search_index_by_depth_reverse(right_begin_index - 1, dr, depthes, L)
        pond_ranges.append((right_end_index, right_begin_index))
        right_begin_index = search_down_index_reverse(right_end_index, depthes, L)

pond_ranges.sort()

k = len(pond_ranges)
areas = []
for r in pond_ranges:
    areas.append(int(calc_area(r[0], r[1], depthes)))
print(sum(areas))
if len(pond_ranges) == 0:
    print(0)
else:
    print(str(k), " ".join(map(str, areas)))

Measured memory_bytes: 8580
import numpy as np
N = int(input())
A = list(map(int,input().split()))
tmp = A[0]
state = 0
M = 1
for i in range(N):
    if state == 0:
        if A[i] > tmp :
            state = 1
        elif A[i] < tmp:
            state = 2
    elif state == 1:
        if A[i] < tmp :
            state = 0
            M += 1
    else:
        if A[i] > tmp :
            state = 0
            M += 1
    tmp = A[i]
print (M)


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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    ll ans = 0;
    priority_queue<int> que;
    rep(i, n){
        cin >> a[i];
        ans += a[i];
        que.push(a[i]);
    }
    rep(i, m){
        int x = que.top();
        que.pop();
        ans -= x - x / 2;
        que.push(x / 2);
    }
    cout << max(ans, 0ll) << endl;
}

Measured memory_bytes: 4216
#include<iostream>
#include<cstring>
using namespace std;
using ll = long long;

int main (){
    int x[6];
    for (int i = 1; i < 6; i++){
        cin >> x[i];
    }
    int cnt = 0;
    for (int i = 1; i < 6; i++){
        cnt++;
        if (x[i] == 0){
            cout << cnt << endl;
            return 0;
        }
    }
    return 0;
}
    
    

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

typedef long long ll;
typedef vector<ll> vll;

int main() {
    ll n, k;
    cin >> n >> k;
    vll nums(n);
    vll v(50);
    ll mask = 0;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        for (int j = 49; j >= 0; --j) {
            mask = 1ll << j;
            if (mask & nums[i]) {
                ++v[j];
            }
        }
    }
    ll cur = 0;
    ll X = k;
    ll ans = 0;
    for (auto &num : nums) {
        cur += (X ^ num);
    }
    ans = max(cur, ans);
    for (int i = 49; i >= 0; --i) {
        X = k;
        cur = 0;
        mask = 1ll << i;
        X = X & ~(mask);
        if (X < k) {
            for (int j = 49; j >= 0; --j) {
                mask = 1ll << j;
                if (j >= i) continue;
                if (v[j] > n - v[j]) {
                    X = X & ~(mask);
                } else {
                    X = X | mask;
                }
            }
            for (auto &num : nums) {
                cur += (X ^ num);
            }
            ans = max(cur, ans);
        }
    }
//    cout << X << endl;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
from collections import deque
s=input()
de=deque(list(s))
rev=0
append,appendleft=de.append,de.appendleft
for _ in range(int(input())):
	t=input()
	if t[0]=="1":
		rev^=1
	else:
		_,f,c=t.split()
		if f=="1":
			if rev:
				append(c)
			else:
				appendleft(c)
		else:
			if rev:
				appendleft(c)
			else:
				append(c)
li=list(de)
if rev:
	li=li[::-1]
print("".join(li))


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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 100010;
const double eps = 1e-6;

int a[4], b[4];
int g[4][4];

int main()
{
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            cin >> g[i][j];

    for(int i = 0; i <= 100; i++)
        for(int j = 0;j <= 100; j++)
            for(int k = 0; k <= 100; k++)
            {
                a[1] = i, a[2] = j, a[3] = k;
                b[1] = g[1][1] - a[1], b[2] = g[1][2] - a[1], b[3] = g[1][3] - a[1];

                bool flag = true;
                for(int r = 2; r <= 3; r++)
                    for(int c = 1; c <= 3; c++)
                        if(g[r][c] != a[r] + b[c])
                        {
                            flag = false;
                            break;
                        }
                if(flag)
                {
                    puts("Yes");
                    return 0;
                }
            }

    puts("No");
    return 0;
}


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

int main() {

    int n;

    scanf("%d",&n);

    int p[n];

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

    long long int ans = 5000000000;

    int t1[n],t2[n];

    /*for(int i=0;i<n;i++){
        t1[i] = t2[i] = p[i];
    }

    long long int test = 0;

    for(int i=0;i<n-1;i++){
        if(t1[i]>=t1[i+1]){
            test += t1[i]*2;
            t1[i] = t1[i+1] = 0;
        }
        else {
            test += t1[i]*2;
            t1[i + 1] -= t1[i];
            t1[i] = 0;
        }
    }

    if(t1[n-1]!=0){
        test += t1[n-1];
    }

    ans = test;

    test = t2[0];

    t2[0] = 0;

    for(int i=1;i<n-1;i++){
        if(t2[i]>=t2[i+1]){
            test += t2[i]*2;
            t2[i] = t2[i+1] = 0;
        }
        else {
            test += t2[i]*2;
            t2[i + 1] -= t2[i];
            t2[i] = 0;
        }
    }

    if(t2[n-1]!=0){
        test += t2[n-1];
    }*/

    for(int i=0;i<=p[0];i++) {

        long long int test = 0;

        for(int j=0;j<n;j++){
            t1[j] = p[j];
        }

        test = i;

        t1[0] -= i;

        for(int j=0;j<n-1;j++){
            if(t1[j]>=t1[j+1]){
                test += t1[j]*2;
                t1[j] = t1[j+1] = 0;
            }
            else {
                test += t1[j]*2;
                t1[j + 1] -= t1[j];
                t1[j] = 0;
            }
        }

        if(t1[n-1]!=0){
            test += t1[n-1];
        }

        ans = min(ans, test);

    }

    cout << ans << endl;


    return 0;
}

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

int main()
{
        int N;
        cin >> N;
        int T[N];
        int A[N];
        for (int i = 0; i < N; ++i) {
                cin >> T[i] >> A[i];
        }
        long long tc = 0;
        long long ac = 0;
        int tLast = 0;
        int aLast = 0;
        for (int i = 0; i < N; ++i) {
                if (tLast == T[i] && aLast == A[i]) continue;
                if (tc < T[i] && ac < A[i]) {
                        tc = T[i];
                        ac = A[i];
                }
                else {
                        long long tmp1 = tc / T[i];
                        if (tc % T[i]) tmp1++;
                        long long tmp2 = ac / A[i];
                        if (ac % A[i]) tmp2++;
                        long long tmp = (tmp1 > tmp2) ? tmp1 : tmp2;
                        tc = (long long)T[i] * tmp;
                        ac = (long long)A[i] * tmp;
                }
                tLast = T[i];
                aLast = A[i];
        }
        cout << tc + ac << endl;
}


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

int main() {
	ll n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	int count = 0;
	for (int i = 0; i < n; i++) {
		x -= a[i];
		if (x >= 0) count++;
	}

	if (x > 0) count--;
	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
MAX_INDEX = 51
MAX_SUM = 2505

dp = [[[-1 for _ in range(MAX_INDEX)] for _ in range(MAX_SUM)] for _ in range(MAX_INDEX)]

def waysutil(index, sum, count, arr, K) : 

	if (index < 0) : 
		return 0; 

	if (index == 0) : 

		if (count == 0) : 
			return 0; 
			
		remainder = sum % count; 

		if (remainder != 0) : 
			return 0; 
			
		average = sum // count; 

		if (average == K) : 
			return 1; 

	if (dp[index][sum][count] != -1) : 
		return dp[index][sum][count]; 

	dontpick = waysutil(index - 1, sum, count, arr, K); 


	pick = waysutil(index - 1, sum + arr[index], count + 1, arr, K); 
						
	total = pick + dontpick; 

	dp[index][sum][count] = total; 
	
	return total; 


def ways(N, K, arr) : 

	Arr = []; 

	Arr.append(-1); 
	for i in range(N) : 
		Arr.append(arr[i]); 

	answer = waysutil(N, 0, 0, Arr, K); 
	return answer; 


n, k = map(int, input().split())
arr = list(map(int, input().split()))
N = len(arr)

print("%d" % (ways(N, k, arr)))


Measured memory_bytes: 74816
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}
int main(){
  int n;
  cin>>n;
  int a[n];
  int r[n],l[n];
  cin>>a[0];
  r[0]=a[0];
  for(int i=1;i<n;i++){
    cin>>a[i];
    r[i]=gcd(a[i],r[i-1]);
  }
  l[n-1]=a[n-1];
  for(int i=n-2;i>=0;i--){
    l[i]=gcd(a[i],l[i+1]);
  }
  int ans=l[1];
  for(int i=1;i<n-1;i++){
    int es;
    es=gcd(r[i-1],l[i+1]);
    if(ans<es){
      ans=es;
    }
  }
  if(ans<r[n-2]){
    ans=r[n-2];
  }
  cout<<ans<<endl;
  return(0);
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
using namespace std;
 
#define MAX 200000
#define SENTINEL 2000000000
typedef long long llong;
 
int L[MAX / 2 + 2], R[MAX / 2 + 2];
 
llong merge(int A[], int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  for ( int i = 0; i < n1; i++ ) L[i] = A[left + i];
  for ( int i = 0; i < n2; i++ ) R[i] = A[mid + i];
 
  L[n1] = R[n2] = SENTINEL;
  int i = 0;
  int j = 0;
  llong cnt = 0;
 
  for ( int k = left; k < right; k++ ) {
    if (L[i] <= R[j]) {
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
      cnt += n1 - i;
    }
  }
 
  return cnt;
}
 
llong mergeSort(int A[], int left, int right) {
  llong v1, v2, v3;
  if ( left + 1 < right ) {
    int mid = (left + right) / 2;
    v1 = mergeSort(A, left, mid);
    v2 = mergeSort(A, mid, right);
    v3 = merge(A, left, mid, right);
    return v1 + v2 + v3;
  } else return 0;
}
 
int main() {
  int n;
  int A[MAX];
 
  cin >> n;
  for ( int i = 0; i < n; i++ ) {
    scanf("%d", &A[i]);
  }
 
  llong ans = mergeSort(A, 0, n);
  cout << ans << endl;
 
  return 0;
}

Measured memory_bytes: 4780
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
#include<set>
using namespace std;

#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
llfor;///////////////////////////////////////////////////////////
int main(){
 ll h,w,n;
 sc(h);sc(w);sc(n);
 ll a=max(h,w);
 a=cei(n,a);
 pr(a);
return 0;}

Measured memory_bytes: 3596
import java.util.*;
import java.io.*;

class Main {
    public static int[] wt;
    public static int[] val;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        String t = br.readLine();

        int s_len=s.length();
        int t_len=t.length();
        int[][] dp = new int[s_len+1][t_len+1];

        for (int i = 1; i<=s_len; i++){
            for (int j = 1; j <= t_len; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(s.charAt(i-1)==t.charAt(j-1))
                    dp[i][j]=Math.max(dp[i][j], dp[i-1][j-1]+1);
            }
        }

        int i=s_len,j=t_len;
        StringBuilder ans=new StringBuilder();
        while(i>0 && j>0){
            if(dp[i-1][j]==dp[i][j]){
                i--;
                continue;
            }
            else if (dp[i][j-1]==dp[i][j]){
                j--;
                continue;
            }
            else{
                ans.append(s.charAt(i-1));
                i--;
                j--;
            }
        }
        System.out.println(ans.reverse().toString());
    }
}


Measured memory_bytes: 84560
#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int l, r;
	cin >> l >> r;
	if (r - l > 2019)r = l + 2019;
	int ans = 2020;
	for (int i = l; i <= r; i++) {
		for (int j = i + 1; j <= r; j++) {
			ans = min(ans, ((i % 2019) * (j % 2019)) % 2019);
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3640
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

# Written by NoKnowledgeGG @YlePhan

#import math
#mod = 10**9+7



def main():
  s = input()
  na = ""
  i = 0
  while i < len(s):
    na += s[i:i+1]
    i += 2
  print(na)
if __name__ == '__main__':
  main()

Measured memory_bytes: 3188
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int sum = 0;
		
		for(int i = 0; i < 10; i++){
			sum += sc.nextInt();
		}
		
		System.out.println(sum);
		
		sc.close();
	}
}

Measured memory_bytes: 17168
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
vector<pi>adj[M];
int dis[M];
bool vis[M];
void bfs(int src)
{
    queue<int>q;
    q.push(src);
    dis[src]=0;
    vis[src]=1;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto x:adj[u])
        {
            int v=x.fi;
            int w=x.si;
            if(vis[v]==0)
            {

                dis[v]=dis[u]+w;
                vis[v]=1;
                q.push(v);
            }
        }
    }

}
 main()

{

    int n;
    scanf("%lld",&n);
    f(i,1,n-1)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        adj[u].pb(mp(v,w));
        adj[v].pb(mp(u,w));
    }
    //done("chk")
    bfs(1);
   // done("chk")
    f(i,1,n)
    {
        //done(dis[i])
        if(dis[i]%2==0)
         {
             printf("0\n");
         }
         else printf("1\n");
    }
    return 0;

}





































Measured memory_bytes: 11936
#include <stdio.h>

int main(){
	int a=0;
	int ans=0;
	int i = 0;
	for (i = 0; i < 5; i++){ 

		scanf("%d", &a);
		if (a <= 40)a = 40;
		ans += a;

	}
	printf("%d\n", ans / 5);

	return 0;
}

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

using namespace std;

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

int main(){
	ll a, b, c;
	cin >> a >> b >> c;


	int ans = 0;
	while(a % 2 + b % 2 + c % 2 == 0){
		ans++;
		if (ans > 1e6){ ans = -1; break; }
		ll ta = a, tb = b, tc = c;
		a = tb / 2 + tc / 2;
		b = tc / 2 + ta / 2;
		c = ta / 2 + tb / 2;
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

#define BUF (51)
int N,M;
char A[BUF][BUF],B[BUF][BUF];

void input(void){
	scanf("%d %d",&N,&M);
	int i=0;
	for(i=0;i<N;i++){
		scanf("%s",A[i]);
	}
	for(i=0;i<M;i++){
		scanf("%s",B[i]);
	}

}

int main(void){
	input();

	int ret = 0;

	int i,j,k;
	for(i=0;i<N-M+1;i++){
		for(j=0;j<N-M+1;j++){
			for(k=0;k<M*M;k++){
				if(B[k/M][k%M]!=A[k/M+i][k%M+j]){
					break;
				}

				if(k==M*M-1)ret = 1;		
			}

		}
	}

	if(ret) printf("Yes");
	else printf("No");
	return 0;
}



Measured memory_bytes: 128
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


N, M = map(int, input().split())
AB = []
for _ in range(M):
    A, B = map(int, input().split())
    AB.append((A-1, B-1))

uf = UnionFind(N)
ans = [N*(N-1)//2]
for A, B in AB[:0:-1]:
    if uf.isSameGroup(A, B):
        ans.append(ans[-1])
    else:
        ans.append(max(0, ans[-1]-uf.Count(A)*uf.Count(B)))
    uf.Unite(A, B)
print(*ans[::-1], sep='\n')


Measured memory_bytes: 113368
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
const long long MOD = 1e9+7;
template<typename T> inline void add(T& a, T b) { a += b; if (a >= MOD) a -= MOD; }

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

  int n; cin >> n;
  vector<int> ans(n);
  rep(i, n - 1) {
    int tmp; cin >> tmp;
    ans[tmp - 1]++;
  }

  rep(i, n) {
    cout << ans[i] << endl;
  }
}


Measured memory_bytes: 3992
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define f(i,a,b) for(ll i=a;i<b;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define MAX 1e9
 
ll modpow(ll base, ll exp, ll modulus) {base %= modulus;ll result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}
const ld pi=acos(-1);


int main(){
    IOS;
    ll n;cin>>n;
    ll a,b;cin>>a>>b;
    bool ok=0;
    f(i,a,b+1){
        if(i%n==0){ok=1;break;}
    }
    cout<<((ok)?"OK":"NG");
    return 0;  
} 





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

#define INF 0x3f3f3f3f
#define ii pair<int,int >
#define MAXN 100005

int memo[MAXN], a[MAXN];
int n;

int f(int idx){

	if(idx == n) return 0;
	if(memo[idx] != -1) return memo[idx];
	int ans1 = INF, ans2 = INF;
	if(idx+1<=n) ans1 = f(idx+1) + abs(a[idx+1] - a[idx]);
	if(idx+2<=n) ans2 = f(idx+2) + abs(a[idx+2] - a[idx]);
	//cout << ans1 << " " << ans2 << endl;
	return memo[idx] = min(ans1, ans2);
}

int main(){

	while(cin >> n){
		//cout << n << endl;
		memset(memo, -1, sizeof(memo));
		for(int i=1; i<=n; i++) cin >> a[i];
		cout << f(1) << endl;
	}	

	return 0;
}

Measured memory_bytes: 5760
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
#include <set>

int main() {
  uint32_t N = 0;
  std::cin >> N;
  std::vector<uint32_t> A(N);
  bool one = false;
  for(auto &&a: A){
    std::cin >> a;
    if(a == 1) one = true;
  }

  std::sort(A.begin(), A.end());
  std::set<uint32_t> S, D;
  for (size_t i = 0; i < N; i++)
  {
    if(S.size() == 0){
      S.insert(A[i]);
      continue;
    }

    if(S.find(A[i]) != S.end()){
      D.insert(A[i]);
      continue;
    }

    bool div = one;
    for (size_t j = 2; !div && j <= std::sqrt(A[i]); j++)
    {
      if(A[i]%j == 0){
        if(S.find(j) != S.end() || S.find(A[i]/j) != S.end()) div = true;
      }
    }
    if(!div){
      S.insert(A[i]);
    }
  }
  

  std::cout << S.size() - D.size() << std::endl;

  return 0;
}

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

int main() {
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  for (int i = sx; i < tx; i++) {
    cout << "R";
  }
  for (int i = sy; i < ty; i++) {
    cout << "U";
  }
  for (int i = sx; i < tx; i++) {
    cout << "L";
  }
  for (int i = sy; i <= ty; i++) {
    cout << "D";
  }
  for (int i = sx; i <= tx; i++) {
    cout << "R";
  }
  for (int i = sy; i <= ty; i++) {
    cout << "U";
  }
  cout << "L";
  cout << "U";
  for (int i = sx; i <= tx; i++) {
    cout << "L";
  }
  for (int i = sy; i <= ty; i++) {
    cout << "D";
  }
  cout << "R" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
int main() {
    long long n;
    cin>>n;
    ll a[n],s=0,y=1000,x;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++){
        if(i==n-1 || (a[i]>a[i+1] && s)){
            x=s*a[i];
            s=0;
            y+=x;
        }
        else if(a[i]<a[i+1] && y>=a[i]){
                x=y/a[i];
                s=x;
                y=y-(x*a[i]);
            }
           // cout<<s<<" "<<y<<"\n";
    }
    cout<<y;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// debug
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
  os << "(" << p.first << "," << p.second << ")";return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  for (auto it = v.begin();it != v.end();++it){
    if(it != v.begin())os << " ";os << *it;
      }return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &mp){
  for(auto x: mp)os << "(" << x.first << "," << x.second << ")" << endl;
  return os;
}
template<typename T, int SIZE>
int array_length(const T (&)[SIZE]){return SIZE;}
template<typename T, int N>
void PRINTF(const T (&a)[N], int s = N, int t = -1, bool f = true){
	if(t == -1){rep(i,s){if(i)cout << " ";cout << a[i];}}
	else repi(i,s,t){if(i!=s)cout << " ";cout << a[i];}
	if(f)cout << "\n";
}
template<typename T, int N1, int N2>
void PRINTF(const T (&a)[N1][N2], int h = N1, int w = N2){
	rep(i,h){rep(j,w){cout << a[i][j] << " \n"[j==w-1];}}
}
string substr(const string &str, int S1, int S2 = -1){
  if(S2 == -1)return str.substr(S1);
  return str.substr(S1, S2-S1);
}
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;


int a[400000];
//公約数
int gcd(int a, int b){
  if(a == 0 || b == 0)return max(a, b);
  if(a == b)return a;
  if(a > b)a = a%b;
	else b = b%a;
  return gcd(a, b);
}

signed main(){
  int n;
  scanf("%lld", &n);
  rep(i,n)scanf("%lld", &a[i]);
  int ans = a[0];
  repi(i,1,n)ans = gcd(ans, a[i]);
  printf("%lld\n", ans);
  return 0;
}








Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

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

	int n, i, j, k, x;
	cin >> n;
	set<int> s;
	for (i = 0; i < n; i++) {
		cin >> x;
		s.insert(x);
	}
	if (s.size() == n) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}


Measured memory_bytes: 9600
def sol_act(n,k):
    from itertools import combinations
    if k>(n-1)*(n-2)//2:
        return -1
    res=set((i,n) for i in range(1,n))
    for _,c in zip(range((n-1)*(n-2)//2-k),combinations(range(1,n),2)):
        res.add(c)
    return res
def sol(inp=input):
    n,k=map(int,inp().split())
    res=sol_act(n,k)
    if res==-1:
        return('-1')
    return '\n'.join([str(len(res))]+['{} {}'.format(*l) for l in res])
  
print(sol())

Measured memory_bytes: 40176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i = (int)a; i <= (int)b; i++)
#define DEC(i, a, b) for(int i = (int)a; i >= (int)b; i--)
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define disc(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
#define INF (int) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss

int n;
ld ans;
vi v;

int main() {
	fastio; cin >> n;
	FOR(i, 1, n) {
		int a; cin >> a;
		v.pb(a);
	}
	sort(all(v));
	ans = (ld) (v[0] + v[1])/2;
	FOR(i, 2, n-1) {
		ans = (ld) (ans + v[i])/2;
	}
	cout << fixed << setprecision(9) << ans;
}


Measured memory_bytes: 3804
#include<bits/stdc++.h>
using namespace std;
int n;
struct res
{
	int id,p;
	string s;
};
vector<res> v;
bool comp(res a,res b)
{
	if(a.s!=b.s) return a.s<b.s;
	return a.p>b.p;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		res x;
		x.id=i;
		cin>>x.s>>x.p;
		v.push_back(x);
	}
	sort(v.begin(),v.end(),comp);
	for(int i=0;i<v.size();i++)
		cout<<v[i].id<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int main (){
    int N; cin >> N;
    int sum = 0;
    for (int i=1;i<=N;i++){
      sum += i;
    }
    cout << sum;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#define ll long long
//for (auto &x : a) { cin >> x; }
using namespace std;

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

    //naive solution
    int n,x,t;
    cin >> n >> x >> t;
    int amt = x;
    int ans = 1;
    while(n > amt){
        amt+=x;
        ans++;
    }
    cout << ans*t;
}

Measured memory_bytes: 3616
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <map>
#define for1(x,y) for(long long x = 1; x<ll(y); x++)
#define forn(x,y,z) for(long long x = y; x< ll(z); x++)
#define for0(x,y,z) for(long long x = y; x< ll(z); x++)
# define PII pair<int,int>
# define FF first
# define SS second
# define PB push_back

#define forn(x,y,z) for(long long x = y; x< ll(z); x++)
#define for0(x,y,z) for(long long x = y; x< ll(z); x++)
using namespace std;
typedef long long ll;
typedef long double ld;	

#define maxn 1000015
const double EPS = (1e-7), EPSm= (1e7);
const ll linf = (ll)1e17 + 5;
long double PI = 3.14159265359;
int dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{1,1},{-1,1},{1,-1}};
	
const int MAXN = 1e5 + 10;
const int NINF = -1e5;
const int INF = 2000000000;

void solve()
{
	string s[4]={"AC","WA","TLE","RE"};
	int n;
	cin>>n;
	map<ll,ll> m;
	while(n--){
		string x;
		cin>>x;
		for(int i=0;i<4;i++){
			if(s[i]==x) m[i]++;
		}
	}
	for(int i=0;i<4;i++){
		cout<<s[i]<<" x "<<m[i]<<endl;
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	setprecision(20);
	int test;
	//cin >> test;
	//while(test--)
		solve();
	return 0;
}


Measured memory_bytes: 3624
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
ans=[[0]*w for _ in range(h)]
now=0
nokori=a[0]
for i in range(h):
    if i%2==0:
        for j in range(w):
            ans[i][j]=now+1
            nokori-=1
            if nokori==0:
                now+=1
                if now<n:
                    nokori=a[now]
    else:
        for j in range(w-1,-1,-1):
            ans[i][j]=now+1
            nokori-=1
            if nokori==0:
                now+=1
                if now<n:
                    nokori=a[now]

for i in range(h):
    print(*ans[i])


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

namespace _0009
{
    class Program
    {
        static void Main(string[] args)
        {
            string str;
            int[] count = new int[1000000];
            count[1] = 0;
            count[2] = 1;
            for (int i = 3; i < 1000000; ++i)
            {
                if (i % 2 == 0)
                {
                    count[i] = count[i - 1];
                }
                else if (IsPrimary(i) == true)
                {
                    count[i] = count[i - 1] + 1;
                }
                else
                {
                    count[i] = count[i - 1];
                }
            }

            while ((str = Console.ReadLine()) != null)
            {

                Console.WriteLine(count[int.Parse(str)]);

            }

        }
        static bool IsPrimary(long number)
        {
            double j = Math.Sqrt(number);

            for (double i = 3; i <= j; i+=2)
            {
                if (number % i == 0)
                {
                    return false;
                }
            }

            return true;
        }
    }
}







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

int main(){
        int n, m;
        scanf("%d %d", &n, &m);
        std::vector<int> h(n);
        for(int i=0; i<n; i++) scanf("%d", &h[i]);

        int max[n] = {};
        for(int i=0; i<m; i++){
                int a, b;
                scanf("%d %d", &a, &b);
                max[a-1] = std::max(max[a-1], h[b-1]);
                max[b-1] = std::max(max[b-1], h[a-1]);
        }

        int ans = 0;
        for(int i=0; i<n; i++){
                if(max[i]<h[i]) ans++;
        }
        printf("%d\n", ans);
        return 0;
}

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

#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define input freopen("input.txt","r",stdin);
#define output freopen("output.txt","w",stdout);
#define fast_io ios::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL);
#define fix cout << fixed << setprecision(15);
//#define left left228
//#define right right228
//#define next next228
#define rank rank228
//#define prev prev228
#define y1 y1228
#define dout if(debug) cout
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int> ;
using pll = pair<ll, ll>;
using pci = pair<char, int>;
using vi = vector<int> ;
using vll = vector<ll> ;
using vpii = vector<pii> ;
const ll infll = 1e18 + 3;
const int maxn = 1e6 + 77;
const int nmax = 1e6 + 577;
const ll basell = 1e18 + 3;
const int mod = 1e9 + 7;
const ld eps = 1e-7;
const int inf = 1009000999;
const int nv = 100505;
const int baseint = 1000200013;
const ld PI = acos(-1.0);
inline bool EQ(ld a, ld b) { return fabs(a-b) < 1e-9; }
inline bool IF(int a, int b, int c) { return (a >= b && a <= c); }
inline bool IFS(int a, int b, int c) { return (a > b && a < c); }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
//typedef pair<int, int> pt;
//#define x first
//#define y second
//ifstream cin("input.txt");
//ofstream cout("output.txt");
/*
sort(a, a + n, [&](pair<pt, int> a, pair<pt, int> b){if (a.x.x != b.x.x)
        return a.x.x < b.x.x; return a.x.y > b.x.y;});
for(int c : s)
for(int &i : a) cin >> i;
for(int c = 'a'; c <= 'z'; ++c)
vector<vector<ll>> dp(n, vector<ll>(n+2));
__int128;
char 0 = int 48;
char c = cin;
int h = (int)c - 48;
*/

/*char memory[(int)1e8];

char memorypos;

inline void * operator new(size_t n){
    char * ret = memory + memorypos;
    memorypos += n;
    return (void *)ret;
}

inline void operator delete(void *){}
*/

int dp[3050][3050];

int g[3050][3050];

int h, w;

int inline solve() {
    //input;//,output;
    //fix;
    fast_io;
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            char t;
            cin >> t;
            g[i][j] = (t == '#');
        }
    }
    dp[0][0] = 1;
    for (int x = 0; x < h; ++x) {
        for (int y = 0; y < w; ++y) {
            dp[x][y] %= mod;
            if(g[x][y]) continue;
            if(x + 1 < h) {
                dp[x + 1][y] += dp[x][y];
            }
            if(y + 1 < w) {
                dp[x][y + 1] += dp[x][y];
            }
        }
    }
    cout << dp[h - 1][w - 1];
    return 0;
}

int32_t main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    solve();
    return 0;
}
/*
6
2 1 6 3 4 5
2 1 3 4 5 6
6 0
1 7 8 2 4 6
 * */

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

#define FLASH ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define int long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vpp vector<pair< int, int > >  
#define pll pair<int , int >
#define ppll pair < pll , pll >
#define debug(n1) cout << n1 << endl
#define len(a) ((int) (a).size())
#define endl "\n"

int32_t main()
{
   int x;
   cin>>x;
   while(1)
   {
   int f=0;
   for(int i=2;i<x;i++)
   {
   	if(x%i==0)
   	{
   		f=1;
   		break;
   	}
   }
   if(f==1){
   x++;
   }
   else{
   	break;
   }
   }
   cout<<x<<endl;
}
//do somethimg instead of nothing! never give up!

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

using namespace std;
typedef long long ll;

int main(void)
{
  ll K,X;cin>>K>>X;
  string res;
  if(K*500>=X){
    res = "Yes";
  }
  else{
    res= "No";
  }

  cout<<res<<endl;

  return 0;
}

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


int main()
{
	int N;
	scanf("%d", &N);
 
	int i = N / 111;
	if (N % 111 != 0) ++i;
 
	printf("%d\n", i * 111);
	return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

long long gcd(long long aaa,long long bbb) {
    if(bbb==0) {
        return aaa;
    }
    return gcd(bbb,aaa%bbb);
}

int main (){

    ll N;
    cin >> N;
    ll X[N],tmp[N],tmpp=0,tmppp[2]={},cmp=0;
    map<ll,ll>m;
    for(ll i = 0; i < N; i++) {
        cin >> X[i];
        tmp[i] = X[i];
    }
    sort(X,X+N);
    for(ll i = 0; i < N; i++) {
        tmpp++;
        if(tmpp - N/2 == 0) {
            tmppp[0] = X[i];
            tmppp[1] = X[i+1];
            break;
        }
    }
        for (ll i = 0; i < N; i++) {
            if(tmp[i] < tmppp[0]) {
                cout << tmppp[1] << endl;
            }else if(tmp[i] == tmppp[0]) {
                cout << tmppp[1] << endl;
            }else if(tmp[i] == tmppp[1]) {
                cout << tmppp[0] << endl;
            }else {
                cout << tmppp[0] << endl;
            }
        }
    return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long 

int odd[10101010],even[10101010];
int main() {
	vector<int>a,b;
	int cnt=0;
	for(int i=1;i<=10101010;i++){
		int x=i*(i+1)*(i+2)/6;
		if(x>10101010)break;
		a.push_back(x);
		if(x%2==1) b.push_back(x);
	}
	//cout<<"kazua"<<a.size()<<" kazub"<<b.size()<<endl;
	rep(i,a.size()){
		int cnt=1;
		while(a[i]*cnt<10101010){
    		if(a[i]*cnt<10101010){
				even[a[i]*cnt]=cnt;
			}else break;
			cnt++;
		}
	}
	rep(i,b.size()){
		int cnt=1;
		while(b[i]*cnt<10101010){
			if(b[i]*cnt<10101010){
				odd[b[i]*cnt]=cnt;
			}else break;
			cnt++;
		}
	}
	
		//rep(i,1010101){odd[i]=1010101;}
		//rep(i,1010101){even[i]=1010101;}
		rep(j,a.size()){
			for(int i=0;i<10101010;i++){
				if(even[i]!=0&&i+a[j]<10101010)chmin(even[i+a[j]],even[i]+1);
			}
		}
		rep(j,b.size()){
    		for(int i=0;i<10101010;i++){
				if(odd[i]!=0&&i+b[j]<10101010)chmin(odd[i+b[j]],odd[i]+1);
			}
		}
	int n=1;
	while(cin>>n){
		if(n==0)break;
		cout<<even[n]<<" "<<odd[n]<<endl;
	}
	return 0;
}


Measured memory_bytes: 82052
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

#define SIZE(x) (int((x).size()))
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define repd(i,r,l) for (int i=(r); i>=(l); i--)
#define rept(i,c) for (typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

#ifndef ONLINE_JUDGE
#define debug(x) { cerr<<#x<<" = "<<(x)<<endl; }
#else
#define debug(x) {}
#endif

int a[10000];

void lemon()
{
	int n,m; scanf("%d%d",&n,&m);
	rep(i,1,m) scanf("%d",&a[i]);
	sort(a+1,a+m+1);
	rep(i,1,m-1) a[m]-=a[i];
	printf("%d\n",max(a[m]-1,0));
}

int main()
{
	ios::sync_with_stdio(true);
	#ifndef ONLINE_JUDGE
		//freopen("B.in","r",stdin);
	#endif
	lemon();
	return 0;
}



Measured memory_bytes: 256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
string silent_ans = "RRRBBB";
string sim(vector<int> inputs) {
	int cnt[2] = {};
	REP(i, inputs.size()) {
		if (silent_ans[inputs[i] - 1] == 'R') {
			cnt[0]++;
		}
		else {
			cnt[1]++;
		}
	}
	if (cnt[0] > cnt[1]) {
		return "Red";
	}
	else {
		return "Blue";
	}
}
int cnt = 0;
int output(vector<int> inputs) {
	cnt++;
	if (cnt >= 210) {
		cout << "Limit Exceed." << endl;
		exit(0);
	}
	cout << "?";
	REP(i, inputs.size()) {
		cout << " " << inputs[i];
	}
	cout << endl;
	string s;
	cin >> s;
	if (s == "-1") {
		exit(0);
	}
	if (s == "Red") {
		return 0;
	}
	else if(s == "Blue"){
		return 1;
	}
}
int n;
int starting(int i) {
	vector<int> kousei;
	REP(q, n) {
		kousei.push_back((i + q) % (2 * n) + 1);
	}
	return output(kousei);
}
int ans[200000] = {};
int main(){
	cin >> n;
	int bot = 0;
	int top = n;
	int hoge = starting(0);
	while (top - bot > 1) {
		int mid = (top + bot) / 2;
		int a = starting(mid);
		if (hoge == a) {
			bot = mid;
		}
		else {
			top = mid;
		}
	}
	//we now the itr now
	int now_itr = top;
	vector<int> checkit;
	for (int q = 0; q < n-1; ++q) {
		checkit.push_back((q + now_itr + 1));
	}
	for (int q = 0; q < 2 * n; ++q) {
		if (now_itr > q || now_itr + (n - 1) <= q) {
			checkit.push_back(q+1);
			int hoge = output(checkit);
			if (hoge == 0) {
				ans[q] = 1;
			}
			else {
				ans[q] = 2;
			}
			checkit.pop_back();
		}
	}
	int cnt[2] = {};
	checkit.clear();
	for (int q = 0; q < 2 * n; ++q) {
		if (ans[q] != 0) {
			if (ans[q] == 1) {
				cnt[0]++;
				if (cnt[0] <= n / 2) {
					checkit.push_back(q+1);
				}
			}
			else {
				cnt[1]++;
				if (cnt[1] <= n/2) {
					checkit.push_back(q+1);
				}
			}
		}
	}
	for (int q = 0; q < 2 * n; ++q) {
		if (ans[q] == 0) {
			checkit.push_back(q+1);
			int hoge = output(checkit);
			if (hoge == 0) {
				ans[q] = 1;
			}
			else {
				ans[q] = 2;
			}
			checkit.pop_back();
		}
	}
	cout << "! ";
	REP(i, 2 * n) {
		if (ans[i] == 1) {
			cout << "R";
		}
		else {
			cout << "B";
		}
	}
	cout << endl;
}


Measured memory_bytes: 1220
#include<iostream>
#include<algorithm>
#include<map>
#include<math.h>
#include<set>
#include<string>
#include<vector>
using namespace std;

#define int long long

void fastio()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

int32_t main()
{
	fastio();
	int k;
	cin >> k;
	string s, ss;
	cin >> s;
	if (s.length() > k)
	{
		ss = s.substr(0, k);
		cout << ss << "...";
	}
	else
		cout << s;
	return 0;

}


Measured memory_bytes: 3124