akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	class Program
	{
		static void Main(string[] args)
		{
			var firstLine = Console.ReadLine().Split(' ').Select(value => int.Parse(value)).ToList();
			var n = firstLine[0];
			var m = firstLine[1];

			var students = new List<List<long>>();
			for(var i = 0; i < n; i++)
			{
				students.Add(Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList());
			}

			var checkPoints = new List<List<long>>();
			for (var i = 0; i < m; i++)
			{
				checkPoints.Add(Console.ReadLine().Split(' ').Select(value => long.Parse(value)).ToList());
			}

			var answers = new List<int>();

			for(var i = 0; i < n; i++)
			{
				long minDistance = long.MaxValue;
				var index = -1;

				for(var j = 0; j < m; j++)
				{
					var distance = Math.Abs(checkPoints[j][0] - students[i][0]) + Math.Abs(checkPoints[j][1] - students[i][1]);
					if (minDistance > distance)
					{
						minDistance = distance;
						index = j;
					}
				}

				answers.Add(index);
			}

			foreach(var value in answers)
			{
				Console.WriteLine(value + 1);
			}
        }
	}
}


Measured memory_bytes: 13268
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

long[10^^5] HS, TABLE;

void main()
{
    auto nk = readln.split.to!(int[]);
    auto N = nk[0];
    auto K = nk[1];

    foreach (i, h; readln.split.to!(long[])) HS[i] = h;

    foreach_reverse (i; 0..N) {
        if (i == N-1) continue;
        auto c = long.max;
        foreach (j; i+1..i+1+K) {
            if (j == N) break;
            c = min(c, TABLE[j] + abs(HS[i] - HS[j]));
        }
        TABLE[i] = c;
    }

    writeln(TABLE[0]);
}

Measured memory_bytes: 6048
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>
#include<deque>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000000 + 7;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int N, K;
	cin >> N >> K;

	/*vector<vector<Int>> ab(N, vector<Int>(2, 0));
	for (Int i = 0; i < N; i++) {
		cin >> ab[i][0] >> ab[i][1];
	}
*/

	vector<pair<Int, Int>> ab(N);
	for (Int i = 0; i < N; i++) {
		cin >> ab[i].first >> ab[i].second;
	}

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

	Int count = 0;
	Int num = 0;

	while (count < K) {
		count += ab[num].second;
		num++;
	}

	cout << ab[num - 1].first << "\n";
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int h,w,n;
  cin>>h>>w>>n;
  vector<pair<int,int>> v;
  REP(i,n) {
    int x,y;
    cin>>x>>y;
    v.emplace_back(x,y);
  }
  sort(ALL(v));
  int mx = 1;
  int mn = h;
  int oldx = 1;
  REP(i,n) {
    int x, y;
    tie(x, y) = v[i];
    int newmx = mx + (x - oldx);
    if (y > newmx) continue;
    if (y == newmx) {
      mx = newmx - 1;
      oldx = x;
      continue;
    }
    mn = x-1;
    break;
  }
  cout << mn << endl;
  return 0;
}


Measured memory_bytes: 2420
#include<iostream>
using namespace std;
int main(){
    int A[4][3][10]={{{}}},n,b,f,r,v;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>b>>f>>r>>v;
        A[b-1][f-1][r-1]+=v;
    }
    for(int f=0;f<4;f++){
        if(f>0) cout<<"####################"<<endl;
        for(int b=0;b<3;b++){
            for(int r=0;r<10;r++){
                cout<<" "<<A[f][b][r];  
            }cout<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <bitset>
#include <time.h>
#include <set>
#include <algorithm>
#define ll long long
#define MAXN 1000
#define MODD 1000000007
#define Inf 10000000000000000ll
#define ll long long
using namespace std;

int A[111111];

int main() {
    int N;
    cin>>N;
    
    map<int,int> counts;
    for(int i=1;i<=N;i++) {
        cin>>A[i];
        counts[A[i]]++;
    }
    
    int num_twos = 0;
    int num_ones = 0;
    
    for(map<int,int>::iterator it = counts.begin();
        it != counts.end();
        ++it) {
        // 5->3->1
        int c = it->second;
        // c-2*k >= 1
        // 2*k <= c-1
        int k=(c-1)/2;
        (it->second) -= 2*k;
        
        
        if ((it->second) == 2)
            num_twos++;
        else
            num_ones++;
        
    }
    
    
    if (num_twos % 2 == 0) {
        cout << counts.size() << endl;
    } else if (num_twos % 2 == 1) {
        cout << num_twos + num_ones - 1 << endl;
    }
    
    
    
    
    
    // 1,1,2
    
    
    
}

Measured memory_bytes: 5376
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		for (long i=1;i<1000;i++) {
			for (long j=-1000;j<i;j++) {
				long tmp = i*i*i*i*i-j*j*j*j*j;
				if (tmp == X) {
					System.out.println(i+" "+j);
					return;
				}
			}
		}
	}
}

Measured memory_bytes: 38900
from collections import Counter

iN = int(input())
aV = [int(_) for _ in input().split()]

oV0 = Counter(aV[0::2]).most_common()
oV1 = Counter(aV[1::2]).most_common()
oV0 += [(0,0)]
oV1 += [(0,0)]

if oV0[0][0] != oV1[0][0] :
    print(iN - oV0[0][1] - oV1[0][1])
else:
    print(iN - max(oV0[0][1],oV1[0][1]) - max(oV0[1][1],oV1[1][1]))


Measured memory_bytes: 20700
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define EPS (1e-7)
#define INF (1e9)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const double PI = acos(-1);
const ll MOD = 1000000007;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////////////////////

ll dfs(string S) {
  int N = S.size();
  if (S[1] != '[') {
    ll k = stoll(S.substr(1,N-2));
    return k / 2 + 1;
  }
  int count = 0;
  vector<ll> A;
  string t = "";
  for (int i = 1; i < N-1; i++) {
    if (S[i] == '[') count++;
    if (S[i] == ']') count--;
    t.push_back(S[i]);
    if (count == 0) {
      A.emplace_back(dfs(t));
      t = "";
    }
  }
  sort(all(A));
  ll y = 0;
  rep(i,A.size() / 2 + 1) y += A[i];
  return y;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); //入出力高速化
  vector<int> sum = {1};
  int k = 0;
  while (sum[k] <= 1000000) {
    sum.emplace_back(sum[k] + (k+2));
    k++;
  }

  vector<int> four{1};
  k = 0;
  while (four[k] <= 1000000) {
    four.emplace_back(four[k] + sum[k+1]);
    k++;
  }

  int N = four.size();
  vector<int> dp(1000001,INF);
  dp[0] = 0;
  for (int i = 1; i <= 1000000; i++) {
    rep (j,N) {
      if (i < four[j]) continue;
      chmin(dp[i],dp[i-four[j]] + 1); 
    }
  }

  vector<int> odd(1000001,INF);
  odd[0] = 0;
  for (int i = 1; i <= 1000000; i++) {
    rep(j,N) {
      if (four[j] % 2 == 0) continue;
      if (i < four[j]) continue;
      chmin(odd[i],odd[i - four[j]] + 1);
    }
  }

  while (true) {
    int n; cin >> n;
    if (n == 0) break;
    cout << dp[n] << " " << odd[n] << endl;
  }
}


Measured memory_bytes: 10572
#include<stdio.h>
#include<math.h>
int main(){
  unsigned long long int in1,in2,in3,in4,r,a,b,lcm,sum = 0;
  scanf("%lld %lld %lld %lld",&in1 ,&in2 ,&in3 ,&in4);
  //sum = in2 - in1 + 1;
  
  if(in3 < in4){
    a = in4; b = in3;
  }else{
    b = in4; a = in3;
  }
  
  sum += (in2 - in1 + 1) - ((in2/in3) - (in1 - 1)/in3) - ((in2/in4) - (in1 - 1)/in4);
  
  r = a % b;
  while(r != 0){
    a = b;
    b = r;
    r = a % b;
  }
  
  lcm = in3 * in4 / b;
  sum += (in2/lcm) - (in1 - 1)/lcm;
  
  printf("%llu\n",sum);

  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

#define SIZE 300
#define INDEX_END 17

int c[SIZE + 1][INDEX_END + 1];

int run(int n, int index) {
    if (c[n][index] > 0) {
        return c[n][index];
    }
    if (n == 0) {
        return 1;
    }
    if (INDEX_END < index || n < index * index) {
        return 0;
    }
    int result = 0;
    result += run(n, index + 1);
    result += run(n - index * index, index);
    return c[n][index] = result;
}

int main() {
    memset(c, 0, sizeof(c));
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        cout << run(n, 1) << endl;
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	int n;
	ll T;
	cin >> n >> T;
	vector<ll>t(n);
	REP(i, n) {
		cin >> t[i];
	}
	ll ans = 0;
	for(int i=0;i<n-1;i++) {
		if (t[i + 1] - t[i] < T) {
			ans += t[i + 1] - t[i];
		}
		else {
			ans += T;
		}
	}
	ans += T;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    r,c,rr,cc=map(int,input().split())
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(rr+cc+10,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for i in range(c,cc+1):
        ans+=COM(rr+i+1,i+1)-COM(r+i,i+1)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 86256
#include <iostream>
using namespace std;
int x, y;
int g(int p) {return p>0 ? p:-p;}
int f(int p, int q) {return min(g(q-p), g(g(q)-g(p))+1);}
int main() {
	cin>>x>>y;
	cout<<(x<=y ? f(x,y) : f(-x,y)+1);
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std ;
int main()
{
	char moji[ 1001 ] ;
	cin >> moji ;
	for( short i = 0 ; moji[ i ] != '\0' ; i++ )
	{
		if( moji[ i ] == 'A' )
		{
			cout << 'X' ;
		}
		else if( moji[ i ] == 'B' )
		{
			cout << 'Y' ;
		}
		else if( moji[ i ] == 'C' )
		{
			cout << 'Z' ;
		}
		else
		{
			moji[ i ] -= 3 ;
			cout << moji[ i ] ;
		}
	}
	cout << endl ;
	return 0 ;
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;
const long long MOD = (long long)1e9 + 7;

int main(){
    string s;
    cin >> s;
    bool f = true;
    int n = s.size();
    int t = 0, q = n - 1;
    while(t < q){
        if(s[t] != s[q]){
            f = false;
            break;
        }
        t++;
        q--;
    }
    t = 0, q = (n - 1) / 2 - 1;
    while(f && t < q){
        if(s[t] != s[q]){
            f = false;
            break;
        }
        t++;
        q--;
    }
    t = (n + 3) / 2 - 1, q = n - 1;
    while(f && t < q){
        if(s[t] != s[q]){
            f = false;
            break;
        }
        t++;
        q--;
    }
    cout << (f? "Yes":"No") << endl;
    return 0;
}


Measured memory_bytes: 256
S = input()

ans = "AC"
tmp = S[2:-1]

if S[0] != "A":
  ans = "WA"
else:
  S = S.replace("A", "")
  
count = 0
for item in tmp:
  if item == "C":
    count += 1
    
if count != 1:
  ans = "WA"
elif count == 1:
  S = S.replace("C", "")

if not S.islower():
  ans = "WA"

print(ans)

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

const int N=505;

int n,m;
int a[N][N],num[N];
bool vis[N];

void work()
{
    int ans=n;
	for(int _=1;_<=m;_++){
		memset(num,0,sizeof(num)); 
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=m;j++)
				if(vis[a[i][j]]){num[a[i][j]]++;break;}
		int mx=0,id=0;
        for(int i=1;i<=m;i++) if(num[i]>=mx) mx=num[i],id=i;
        ans=min(ans,mx);
        vis[id]=0;
	}
	cout<<ans<<endl;
}

void init()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];
	for(int i=1;i<=m;i++) vis[i]=1;
}

int main()
{
	init();
	work();
	return 0;
}


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

// # DEFINES # //
#define ll long long
#define M (ll)(1e9+7)
#define EPS 1e-9

using namespace std;

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

    ll n;

    cin >> n;

    if(n == 7 || n == 5 || n == 3)
        cout << "YES" << endl;
    else 
        cout << "NO" << endl;


    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#define endl '\n'
using namespace std;

int Binary_search(int num[], int n, int x)
{
    int left, right, mid;
    left=0;
    right=n-1;
    while (left<=right) {
        mid=(left+right)/2;
        if (num[mid]==x) return mid;
        if (num[mid]<x) left=mid+1;
    else right=mid-1;
    }
    return -1;
}

int main()
{
    int x, n, flag1, flag2, tmp1, tmp2, tmp;
    cin >> x >> n;
    int str[n], i;
    for (i=0; i<n; i++) cin >> str[i];
    sort(str, str+n);
    tmp=Binary_search(str, n, x);
    if (tmp==-1) cout << x << endl;
    else {
        flag1=x+1;
        flag2=x-1;
        for (1 ; 1; 1) {
            tmp1=Binary_search(str, n, flag1);
            tmp2=Binary_search(str, n, flag2);

            if (tmp1==-1 || tmp2==-1) break;
            flag1++;
            flag2--;
        }
        if (tmp2==-1) cout << flag2 << endl;
        else if (tmp1==-1) cout << flag1 << endl;
    }
    return 0;
}


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

public class Main {

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

		double x0, x1, x2, xq, xr;
		double y0, y1, y2, yq, yr;
		double t;

		while ((line = br.readLine()) != null) {

			StringTokenizer st = new StringTokenizer(line, ",");
			x0 = x1 = Double.parseDouble(st.nextToken());
			y0 = y1 = Double.parseDouble(st.nextToken());
			x2 = Double.parseDouble(st.nextToken());
			y2 = Double.parseDouble(st.nextToken());
			xq = Double.parseDouble(st.nextToken());
			yq = Double.parseDouble(st.nextToken());

			if (x1 == 0 && x2 == 0) {
				// 線分が y軸の場合
				xr = -1 * xq;
				yr = yq;
			} else if (y1 == 0 && y2 == 0) {
				// 線分が x軸の場合
				xr = xq;
				yr = -1 * yq;
			} else {

				// P1 を原点に移動
				x1 -= x0;
				y1 -= y0;
				x2 -= x0;
				y2 -= y0;
				xq -= x0;
				yq -= y0;

				// 回転してx軸と平行に
				t = Math.atan2(y2, x2);

				// Q を -t回転
				double xq0 = xq, yq0 = yq;
				t *= -1;
				xq = xq0 * Math.cos(t) - yq0 * Math.sin(t);
				yq = xq0 * Math.sin(t) + yq0 * Math.cos(t);

				// R の座標を取得
				xr = xq;
				yr = -1 * yq;

				// R を t回転
				double xr0 = xr, yr0 = yr;
				t *= -1;
				xr = xr0 * Math.cos(t) - yr0 * Math.sin(t);
				yr = xr0 * Math.sin(t) + yr0 * Math.cos(t);

				// 原点から元の位置に戻す
				xr += x0;
				yr += y0;
			}
			System.out.println(String.format("%.6f %.6f", xr, yr));
		}
	}
}

Measured memory_bytes: 16960
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 2005;
const int INF = (1 << 30) - 1;

struct Edge
{
	int to;
	int nxt;
}edge[MAXN << 1];

int n,id,ans,totdep;
int first[MAXN];
int MIN[MAXN];
int MAX[MAXN];
int cnt[MAXN];

string s;

void addE(int u,int v)
{
	edge[++id] = (Edge){v,first[u]};
	first[u] = id;
}

void dfs(int u,int fa,int depth)
{
	totdep += (s[u - 1] - '0') * depth;
	cnt[u] = s[u - 1] - '0';
	MIN[u] = MAX[u] = 0;
	int MX = 0,MX2 = 0,sumMIN = 0,sumMAX = 0;
	for (int i = first[u];i;i = edge[i].nxt)
		if (edge[i].to != fa)
		{
			dfs(edge[i].to,u,depth + 1);
			cnt[u] += cnt[edge[i].to];
			sumMIN += MIN[edge[i].to];
			sumMAX += MAX[edge[i].to];
			if (MIN[edge[i].to] > MX)
			{
				MX = MIN[edge[i].to];
				MX2 = MAX[edge[i].to];
			}
			MAX[u] += MAX[edge[i].to];
		}
	if (MX > sumMIN / 2)
		MIN[u] = max(0,MX - sumMAX + MX2);
	if (fa)
	{
		MIN[u] += cnt[u];
		MAX[u] += cnt[u];
	}
}

int main()
{
	cin >> n >> s;
	for (int u,v,i = 1;i < n;i++)
	{
		cin >> u >> v;
		addE(u,v);
		addE(v,u);
	}
	ans = INF;
	for (int i = 1;i <= n;i++)
	{
		totdep = 0;
		dfs(i,0,0);
		if (MIN[i] || (MAX[i] & 1))
			continue;
		ans = min(ans,totdep >> 1);
	}
	cout << (ans == INF ? -1 : ans) << endl;
	return 0;
}

Measured memory_bytes: 512
# B
N = str(input())

sum = 0
for n in N:
    sum += int(n)

print('Yes' if sum % 9 == 0 else 'No')


# #A
# N, X, T = map(int, input().split())

# print(T * (N//X if N % X == 0 else N//X+1))


Measured memory_bytes: 9268
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
vi a,b;

int main(){
	cin>>n;
	a=b=vi(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		a[i]--;
		b[a[i]]++;
	}
	ll t=0;
	for(int i=0;i<n;i++) t+=(ll)b[i]*(b[i]-1)/2;
	for(auto i:a){
		cout<<t-(ll)b[i]*(b[i]-1)/2+(ll)(b[i]-1)*(b[i]-2)/2<<endl;
	}
}

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

int main() {
  int a, b, c, d;
  string op;
  cin >> a >> b >> c >> d;

  if ((a+b) == (c+d) ) {
    cout << "Balanced" << endl;
  }
  else if ((a+b) > (c+d) ) {
    cout << "Left" << endl;
  }
  else if ((a+b) < (c+d) ) {
    cout << "Right" << endl;
  }
  else {
 cout << "Error" << endl;
}
}
  

Measured memory_bytes: 256
import sys
N,M = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int,sys.stdin.readline().rstrip().split()))

from collections import defaultdict

d = defaultdict(int)  # d[i] = (Aの中でi本用いて表せる最大の数)
for i in range(M):
    if A[i] == 1:
        d[2] = 1
    elif A[i] == 7:
        d[3] = 7
    elif A[i] == 4:
        d[4] = 4
    elif A[i] in [2,3,5]:
        d[5] = max(d[5],A[i])
    elif A[i] in [6,9]:
        d[6] = max(d[6],A[i])
    else:
        d[7] = 8

B = list(d.keys())
B.sort()

a = B[0]
B[0] = 0

if N % a == 0:
    print(''.join([str(d[a])]*(N//a)))
    exit()

from itertools import combinations_with_replacement

C = []

for i in range(N//a,max(-1,N//a-7),-1):  # aをi回用いる
    x = N-a*i
    for u in list(combinations_with_replacement(B,5)):
        if sum(u) == x:
            s = []
            for j in range(5):
                if u[j] != 0:
                    s.append(u[j])
            C.append((i,s))

D = []
for i,j in C:
    if i + len(j) == C[0][0] + len(C[0][1]):
        D.append((i,j))

m = min(D[i][0] for i in range(len(D)))

q,r,s = 0,0,0
for i,j in D:
    X = [d[a]]*(i-m) + [d[k] for k in j]
    X.sort(reverse=True)
    M = ''
    for k in X:
        M += str(k)
    M = int(M)
    if q < M:
        q,r,s = M,i,j

E = [d[a]]*r + [d[i] for i in s]
E.sort(reverse=True)

ans = ''
for i in E:
    ans += str(i)
print(ans)

Measured memory_bytes: 74044
using namespace std;
#include <bits/stdc++.h>
#define rep(i, s) for (int i = 0; i < s; ++i)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define all(v) (v.begin(), v.end())
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))
const ll mod = 1000000007;
bool f(string s){
  bool ans=true;
  rep(i,s.size()/2){
    if(s[i]!=s[s.size()/2+i]){
      ans=false;
      break;
    }
  }
  return ans;
}



int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin>>N;
  vector<l_l>pair(N); 
  rep(i,N){
        ll a;
        ll b;
        cin >> a >> b;
        pair[i] = make_pair(b, a);
     
    }
  sort(pair.begin(),pair.end());
  ll time=0;
  rep(i,N){
    if(time+pair[i].second<=pair[i].first){
      time+=pair[i].second;
    }
    else{
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}
    
  
  


Measured memory_bytes: 3456
#include <stdio.h>
#include <math.h>

typedef struct {
  double x;
  double y;
  double r;
} Circle;

int FuncCmpCircle(Circle a, Circle b);

int main(void)
{
  int n;
  Circle buf[2];
  int i, j;

  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) {
    for ( j = 0; j < 2; j++ ) {
      scanf("%lf %lf %lf", &buf[j].x, &buf[j].y, &buf[j].r);
    }

    printf("%d\n", FuncCmpCircle(buf[0], buf[1]) );
  }

  return 0;
}

int FuncCmpCircle(Circle a, Circle b)
{
  double length = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
  double buf;

  if ( length + b.r < a.r ) {
    return 2;
  } else if ( length + a.r < b.r ) {
    return -2;
  } else if ( length <= (a.r + b.r) ) {
    return 1;
  } else {
    return 0;
  }
}

Measured memory_bytes: 640
import sys

A,B = map(int, raw_input().split())

#print A,B

if A > B:
    for i in range(A):
        sys.stdout.write(str(B))
    sys.stdout.write("\n")
else:
    for i in range(B):
        sys.stdout.write(str(A))
    sys.stdout.write("\n")


Measured memory_bytes: 2568
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#define INF 100000000
#define MOD 1000000007
using namespace std;


int main(){
    long long sum=0;
    
    string s;
    cin>>s;
    
    int l=s.length();
    
    int a=1<<(l-1);
    
    
    for(int i=0; i<a; i++){
        int plus[l-1];
        for(int k=0; k<l-1; k++){
            plus[k]=(i>>k)%2;
        }
        
        long long tmp=s[0]-'0';
        for(int k=0; k<l-1; k++){
            if(plus[k]==1){
                sum+=tmp;
                tmp=s[k+1]-'0';
            }else{
                tmp=tmp*10+(long long)(s[k+1]-'0');
            }
        }
        sum+=tmp;
        
      //  cout<<tmp<<" "<<sum<<endl;
    }
    cout<<sum<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int x;
  cin>>x;
  puts(x<1200 ? "ABC" : (x<2800 ? "ARC" : "AGC"));
  return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (x).size()

ll mod = 1000000007;

ll gcd(ll a, ll b){
  if (a%b == 0)return(b);
  else return(gcd(b, a%b));
}

ll inv(ll x){
  ll res = 1;
  ll k = mod - 2;
  ll y = x;
  while(k){
    if(k&1)res = (res*y)%mod;
    y = (y*y) % mod;
    k /= 2;
  }
  return res;
}

struct Square {
  int h,w,cnt;
  Square(int _h,int _w,int _cnt){
    h = _h;
    w = _w;
    cnt = _cnt;
  }
};

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

  int d,t,s;
  cin >> d >> t >> s;
  if(t*s >= d) cout << "Yes" << endl;
  else cout << "No" << endl;
}

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


int main() {

    string s;
    cin >> s;
    int cnt = 0;
    for (int i = 0; i < s.length()/2; ++i) {
        if (s[i] != s[s.length()-1-i]) ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

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

long long n, m, a[100005], w, ww, g, l = 1ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] /= 2;
		ww = 1;
		while((a[i] & 1ll) ^ 1ll) {
			a[i] >>= 1ll;
			ww <<= 1ll;
		}
		if(i == 1) w = ww;
		else {
			if(w != ww) {
				cout << 0 << endl;
				return 0;
			}
		}
		l = l * a[i] / (__gcd(l, a[i]));
		if(l > m) {
			cout << 0 << endl;
			return 0;
		}
	}
	l *= w;
	if(l > m) {
		cout << 0 << endl;
		return 0;
	}
	cout << (m / l + 1ll) / 2ll << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const

template<typename... Types>
struct dynarr: std::vector<Types...> {
  using std::vector<Types...>::vector;
  using size_type = typename std::vector<Types...>::size_type;
  auto&& operator[](size_type i) { return this->at(i); }
  auto&& operator[](size_type i) const { return this->at(i); }
};

int main() {
  i64 N, M;
  cin >> N >> M;
  dynarr<i64> A(N), B(M);
  rep(i,0,N) cin >> A[i];
  rep(i,0,M) cin >> B[i];

  sort(all(A));
  sort(all(B));
  reverse(all(A));
  reverse(all(B));
  if(A.front() != N * M ||  B.front() != N * M) {
    cout << 0 << endl;
    return 0;
  }
  i64 mod = 1e9 + 7;
  i64 now = N * M - 1;
  i64 a = 1;
  i64 b = 1;
  i64 ans = 1;
  i64 remain = 0;
  while(a < N || b < M) {
    i64 aa = (a < N && A[a] == now);
    i64 bb = (b < M && B[b] == now);
    if(aa && bb) {
      a++;
      b++;
      remain += a + b - 2;
    }
    else if(aa) {
      a++;
      ans = (ans * b) % mod;
      remain += b - 1;
    }
    else if(bb) {
      b++;
      ans = (ans * a) % mod;
      remain += a - 1;
    }
    else if(remain > 0) {
      ans = (ans * remain) % mod;
      remain--;
    }
    else {
      cout << 0 << endl;
      return 0;
    }
    now--;
  }

  rep(i,1,now + 1) {
    ans = (ans * i) % mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#解説参照
#i桁目で10^i円多くはらうか否か

n_ =list(input())
n = [int(i) for i in n_]
ans = 0
if len(n_)==1:
    print(min(n[0],11-n[0]))
    exit()
dp1 = 0
dp2 = 1

for i in range(len(n)):
    dp_1 = min(dp1+n[i],dp2+10-n[i])
    dp_2 = min(dp1+n[i]+1,dp2+9-n[i])
    dp1 = dp_1
    dp2 = dp_2
print(dp1)


Measured memory_bytes: 141884
N = gets.to_i
a_list = gets.split.map(&:to_i)
b_list = gets.split.map(&:to_i)

count = 0
b_list.each.with_index do |b, i|
  n = [b, a_list[i]].min
  b2 = b - n
  a_list[i] -= n
  count += n
  m = [b2, a_list[i + 1]].min
  b3 = b2 - m
  a_list[i + 1] -= m
  count += m
end
puts count


Measured memory_bytes: 19356
#include<stdio.h>

int main(){
  int a=0;
  int b=0;
  scanf("%d %d", &a, &b);

  printf("a ");
  if(a>b){
      printf(">");
  }
  else if(a<b){
      printf("<");
  }
  else{
      printf("==");
  }
  printf(" b\n");

  return 0;
}



Measured memory_bytes: 2056
''' بِسْمِ اللَّهِ الرَّحْمَٰنِ الرَّحِيمِ '''
#codeforces
gi = lambda : list(map(int,input().split()))
n, = gi()
b = gi()
a = [1e9] * n
k = 0
while k < n - 1:
	a[k] = min(a[k], b[k])
	a[k + 1] = min(a[k + 1], b[k])
	k += 1
print(sum(a))

Measured memory_bytes: 3188
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

#define rep(i, n) for(int i=0; i<(n); ++i)
#define max  200001

//qsort(str, n, sizeof(int), up_comp);
int up_comp(const void *a, const void *b){return *(int*)a - *(int*)b;}
int down_comp(const void *a, const void *b){return *(int*)b - *(int*)a;}
int int_sort( const void * a , const void * b ) {return strcmp(( char * )a , ( char * )b );}
int count_digit(int a){int i=0;while(a!=0){a=a/10;i++;}return i;}
int euclid( int a, int b ){int temp;if(a<b){temp=a;a=b;b=temp;}if(b<1)return -1;if(a%b==0) return b;return euclid(b,a%b);}

int main(void){
    
    int num=0, flag=0, fflag=0;
    char s[200], ans[3]="AC";
    
    
    
    scanf("%s", s);
    
    num=strlen(s);
    
    if (s[0]!='A') {
        strcpy(ans, "WA");
    }
    
    for (int i=2; i<num-1; i++) {
        if (s[i]=='C') {
            flag++;
        }
    }
    if (flag!=1) {
        strcpy(ans, "WA");
    }
    
    for (int i=1; i<num; i++) {
        if (s[i]>='a'&&s[i]<='z') {
            fflag++;
        }
    }
    
    if (fflag!=num-2) {
        strcpy(ans, "WA");
    }
    
    printf("%s", ans);
    
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int x, a;
  cin >> x >> a;

  if (x < a) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        const long MOD = 1000000007;
        var sc = new Scanner();
        int k = sc.nextInt();
        int x = sc.nextInt();

        Console.SetOut(new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        for (int i = x - (k - 1); i <= x + (k - 1); i++)
        {
            if (i == x - (k - 1)) Console.Write(i);
            else Console.Write(" " + i);
        }
        Console.Write("\n");
        Console.Out.Flush();
    }
}

// chokudai's Scanner
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public int[] ArrayInt(int N, int add = 0)
    {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0)
    {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0)
    {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++)
        {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

Measured memory_bytes: 13140
inf = float('inf')

def solve():
    N, M = map(int, input().split())
    edges = [None] * M

    for i in range(M):
        a, b, c = map(int, input().split())
        a, b = a-1, b-1
        edges[i] = (a, b, -c)

    ans = BellmanFord(N, M, edges)
    if ans is None:
        print('inf')
    else:
        print(-ans)

def BellmanFord(N, M, edges):
    d = [inf] * N
    d[0] = 0

    for i in range(N-1):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = d[u] + c

    for i in range(N):
        for(u, v, c) in edges:
            if d[u] + c < d[v]:
                d[v] = -inf

    if d[N-1] == -inf:
        return None
    else:
        return d[N-1]
    
if __name__ == '__main__':
    solve()
                
                


Measured memory_bytes: 45928
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	Scanner sc;

	Main() {
		sc = new Scanner(System.in);
	}

	class com implements Comparable<com> {
		int t;
		int s;
		int d;

		public int compareTo(com tar) {
			return t - tar.t;
		}
		com(int t ,int s , int d){
			this.t = t;
			this.s = s;
			this.d = d;
		}
	}

	public void run() {
		for (;;) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n == 0 ){
				break;
			}
			TreeSet<Integer> hl = new TreeSet<Integer>();
			com[] arr = new com[m];
			for(int i = 0; i < m ; i ++){
				com a = new com(sc.nextInt(),sc.nextInt(),sc.nextInt());
				arr[i] = a;
			}
			
			Arrays.sort(arr);
			hl.add(1);
			
			for(com c : arr){
				int s = c.s;
				int d = c.d;
				if(hl.contains(s)){
					hl.add(d);
				}
			}
			System.out.println(hl.size());
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

}

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

using ll = int64_t;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define drrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	os << "{";
	rep(i, (int)v.size()) {
		if (i)
			os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
	for (auto val : array)
		std::cout << val << ", ";
	std::cout << "\n";
}

const int MOD = 1'000'000'000 + 7;
const int INF = 1'000'000'000 + 5;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(16);

	ll n; std::cin >> n;
	vector<ll> len(n);
	ll sum = 0;
	rep(i, n) {
		std::cin >> len[i];
		sum += len[i];
	}
	ll cur_sum = 0, best = 1e18;
	rep(i, n-1) {
		cur_sum += len[i];
		ll diff = abs((sum - cur_sum) - cur_sum);
		if (diff < best)
			best = diff;
	}
	std::cout << best << "\n";
}


Measured memory_bytes: 1792
def tasu(a):
  out = (a*(a-1))//2 + a
  return out%(10**9 + 7)
    
  
N, K = map(int, input().split())
A_list = list(map(int, input().split()))
count = 0
count1 = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif (i<j) & (A_list[i] > A_list[j]):
      count += 1
    elif (i>j) & (A_list[i] > A_list[j]):
      count1 += 1

ans = (tasu(K) * count) + (tasu(K-1) * count1) 
print(ans%(10**9 + 7))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;cin>>N;
  int ma=0,mi=1000000001;
  for(int i=0; i<N; i++){
    int a;cin>>a;
    mi=min(mi,a);
    ma=max(ma,a);
  }
  cout<<ma-mi<<endl;
}

Measured memory_bytes: 256
S = input()
X = [None]*200001 + list(S) + [None]*200001
ifront = 200000
iback = 200001 + len(S)
rev = False

Q = int(input())
for _ in range(Q):
    query = input().split()
    if len(query)==1: rev = not rev
    else:
        F = int(query[1])
        C = query[2]

        if (not rev and F==1) or (rev and F==2):
            X[ifront] = C
            ifront -= 1
        else:
            X[iback] = C
            iback += 1

ans = ''.join(X[ifront+1:iback])
print(ans if not rev else ans[::-1])

Measured memory_bytes: 10952
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const ll MAXN = 1e18;
int main() {
    int n; cin >> n;
    ll a[n] = {};
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (count(a, a + n, 0)) {
        cout << 0 << "\n";
        return 0;
    }
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] > MAXN / ans) {
            cout << -1 << "\n";
            return 0;
        }
        ans *= a[i];
    }
    cout << ans << "\n";
}

Measured memory_bytes: 4424
S = gets.chomp.split("")
s_rev = S.reverse
s_con = s_rev.inject(:+)

N = S.length + 1
subs = ["maerd", "remaerd", "esare", "resare"]

N.times {
subs.each do |sub|
if s_con.start_with?(sub)
  s_con.slice!(0..sub.length - 1)
end
end
}

if s_con == ""
  puts "YES"
else
  puts "NO"
end

Measured memory_bytes: 108956
import java.util.*;
class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int X = A + B;
		int Y = A - B;
		int Z = A * B;
		int Ans = Math.max(X, Y);
		Ans = Math.max(Ans, Z);
		System.out.println(Ans);
	}
}

Measured memory_bytes: 22996
#include <stdio.h>
int main (){
    int a, b;
    scanf ("%d %d", &a, &b);
    
    int sum = a + b;
    int diff = a - b;
    int mult = a * b;
    
    if (sum >= diff && sum >= mult){
        printf ("%d", sum);
    }
    else if (diff >= sum && diff >= mult){
        printf ("%d", diff);
    }
    else if (mult >= sum && mult >= diff){
        printf ("%d", mult);
    }
    return 0;
}

Measured memory_bytes: 128
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;


int main(void) {
	long long int n, k;
	long long int a[100001] = {};
	long long int pos;
	long long int count = 0;

	cin >> n >> k;
	FOR(i, 1, n) {
		cin >> a[i];
		if (a[i] == 1) {
			pos = i;
		}
	}


	if (k == 2) {
		if ((pos - 1) % (k - 1) == 0) {
			count += (pos - 1) / (k - 1);
		}
		else {
			count += (pos - 1) / (k - 1);
			if (pos - 1 != 0) {
				count++;
			}

		}


		if ((n - pos) % (k - 1) == 0) {
			count += (n - pos) / (k - 1);
		}
		else {
			count += (n - pos) / (k - 1);
			if (n - pos != 0) {
				count++;
			}

		}
	}
	else {
		if ((n - 1) % (k - 1) == 0) {
			count += (n - 1) / (k - 1);
		}
		else {
			count += (n - 1) / (k - 1);
			count++;
		}
	}
	


	cout << count << endl;


	return 0;
}

Measured memory_bytes: 1152
def is_palindrome(s)
  s == s.reverse
end

S = gets.chomp
N = S.length

n1 = (N - 1) / 2
s1 = ""
for i in 0..n1 - 1
  s1 += S[i]
end

n2 = (N + 3) / 2
s2 = ""
for i in n2 - 1..N - 1
  s2 += S[i]
end

if is_palindrome(S) && is_palindrome(s1) && is_palindrome(s2)
  puts "Yes"
elsif puts "No"
end


Measured memory_bytes: 1788
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <functional>
#include <climits>
#include <cstring>

using namespace std;

#define int long long

#define rep(i, n) for (int i=0;i<(int)n;++i)
#define rep1(i, n) for (int i=1;i<=(int)n;++i)
#define unless(a) if(!(a))
#define all(a) begin(a),end(a)
#define fst first
#define scd second
#define PB emplace_back
#define PPB pop_back

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

bool chmin(int&a,int b){return a>b?(a=b,true):false;}
bool chmax(int&a,int b){return a<b?(a=b,true):false;}
int read(){int a;scanf("%lld",&a);return a;}

const int INF = 1e9 + 10;

/* 
 * 
 *  0 1 0 0 0 1 0 1 0 0 
 *  0 0 0 1 0 0 1 0 1 0
 *  0 1 0 0 0 0 0 0 0 0 
 *  0 0 0 1 0 1 0 1 0 0 
 */

int H, W;
int a[505][505];

using Data = pair<pii, pii>;

signed main()
{
	cin >> H >> W;

	rep(i, H) rep(j, W) {
		cin >> a[i][j];
		a[i][j] %= 2;
	}

	vector<Data> ans;

	rep(i, H) {
		rep(j, W - 1) {
			if (a[i][j] % 2 == 1) {
				ans.PB(pii(i, j), pii(i, j + 1));
				a[i][j + 1] += 1;
			}
		}
	}

	rep(i, H - 1) {
		if (a[i][W - 1] % 2 == 1) {
			ans.PB(pii(i, W - 1), pii(i + 1, W - 1));
			a[i + 1][W - 1] += 1;
		}
	}

	cout << ans.size() << endl;
	for (Data &d : ans) {
		printf("%lld %lld %lld %lld\n", d.fst.fst + 1, d.fst.scd + 1, d.scd.fst + 1, d.scd.scd + 1);
	}
}



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


int main () {
    int n ;
    cin >> n;
    int ans = 0;
    for(int i = 1; i <= n; i++){
        string s = to_string(i) ;
        if(s.size()%2==1){
            ans++ ;
        }
    }
    cout << ans << endl ;
} 


Measured memory_bytes: 3736
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x;
    int fenshu;
    string name;
};
bool operator <(node a,node b)
{
    if(a.name==b.name)return a.fenshu<b.fenshu;
    return a.name>b.name;
}
int main()
{
    priority_queue<node>qq;
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        node r;
         cin>>r.name>>r.fenshu;
        r.x=i;
        qq.push(r);
    }
    for(int i=1; i<=n; i++)
    {
        node g=qq.top();
        qq.pop();
        printf("%d\n",g.x);
    }
}


Measured memory_bytes: 256
n,m = map(int,input().split())

if n == 1 and m == 1:
    print(1)

elif n == 2 or m == 2:
    print(0)

elif n == 1:
    print(m-2)

elif m == 1:
    print(n-2)

else:
    print((n-2)*(m-2))



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

int main() {
	string a,b;
	cin>>a>>b;
	string ans="";
	int n=a.size(),m=b.size();
	int dp[n][m];
	if(a[0]==b[0])
	dp[0][0]=1;
	else
	dp[0][0]=0;
	for( int i=0; i<n; i++)
	{
	    for(int j=0; j<m; j++)
	    {
	       
	        if(i==0 && j!=0)
	        {if(a[i]==b[j])
	        dp[i][j]=1;
	        else
	        dp[i][j]=dp[i][j-1];}
	        else if(j==0 && i!=0)
	        {
	            if(a[i]==b[j])
	        dp[i][j]=1;
	        else
	        dp[i][j]=dp[i-1][j];
	        }
	        else if(i!=0 &&j!=0)
	        {
	            if(a[i]==b[j])
	            dp[i][j] = dp[i-1][j-1] +1;
	            else
	            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
	        }
	            
	    }
	}
	
	int i=n-1, j=m-1;
	while(i>0 && j>0)
	{
	    if(a[i]==b[j])
	    {ans = a[i] +ans;
	    i--;
	    j--;
	    }
	    
	    else
	    {
	        if(dp[i][j]==dp[i-1][j])
	        i--;
	        else
	        j--;
	    }
	}
	
	if(i==0 && j==0)
	{if(a[0]==b[0])
	ans= a[0]+ans;}
	else if(j==0)
	{
	    while(i>=0)
	    {if(a[i]==b[0])
	    {ans = b[0] + ans;
	    break;}
	    i--;}
	}
	else
	{
	    while(j>=0)
	    {if(a[0]==b[j])
	    {ans = a[0] + ans;
	    break;}
	    j--;}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 35456
//
//  main.cpp
//  D- Knapsack 1
//
//  Created by dz2701 on 8/26/20.
//  Copyright © 2020 dz2701. All rights reserved.
//

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 1e5+1;

int N, W;
ll dp[101][MAX];
//dp[i][j] = i consider j weight
ll w[MAX], v[MAX];

int main(){
    cin >> N >> W;
    for(int i=1;i<=N;i++){
        cin >> w[i] >> v[i];
    }
    
    dp[1][w[1]] = v[1];
    dp[1][0] = 0;
    for(int i=1;i<=W;i++){
        for(int j=1;j<=N;j++){
            if(i-w[j]>=0)dp[j][i] = max(dp[j-1][i-w[j]]+v[j], dp[j-1][i]);
            else dp[j][i] = dp[j-1][i];
        }
    }
    
    ll ans = -1e9;
    for(int i=1;i<=W;i++){
        for(int j=1;j<=N;j++){
            ans = max(ans, dp[j][i]);
        }
    }
    //dp[i][j] = MAX [ (if choose) dp[i-1][j-w] + v[i] , (if not choose) dp[i-1][j] ].
    
    cout << ans;
    return 0;
    
}


Measured memory_bytes: 81752
#include <iostream>
#include <string>
#include<algorithm>
#include <cstdlib>

using namespace std;
int main()
{
	int n,a[200000],b[200000];
	cin >> n;
	for (int i=0; i < n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	sort(a,a+n);
	int x = a[n / 2-1];
	int y = a[n / 2];
	for (int i = 0; i < n; i++){
		if (b[i] >x) cout << x<<endl;
		else cout << y<<endl;
	}
    return 0;
}



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

int cnt;
long long sum;
int mi = 1e9 + 7;

signed main() {

    int n;
    scanf("%d", &n);
    for ( int i = 0; i < n; i++ ) {
        int a;
        scanf("%d", &a);
        if ( a < 0 ) cnt++;
        a = abs(a);
        if ( a < mi ) {
            mi = a;
        }
        sum += a;
    }
    if ( 1 & cnt ) {
        sum -= mi*2;
    }
    printf("%lld\n", sum);

    return 0;
}

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

using namespace std;

int main(void) {
  int N, M; cin >> N >> M;
  vector<int> L[N+1];

  for (int i = 0; i < M; i++) {
    int x, y, z; cin >> x >> y >> z;
    L[x].push_back(y);
    L[y].push_back(x);
  }

  int grp[N+1];
  int ans = 0;
  memset(grp, 0, sizeof(grp));
  vector<int> p, n;

  for (int i = 1; i <= N; i++) {
    if (grp[i] != 0) continue;
    
    ans++;
    n.push_back(i);
    grp[i] = ans;
    while (!n.empty()) {
      p = n;

      n.clear();
      for (auto it = p.begin(); it != p.end(); ++it) {
        
        for (auto jt = L[*it].begin(); jt != L[*it].end(); ++jt) {
          if (grp[*jt] != 0) continue;

          n.push_back(*jt);
          grp[*jt] = ans;

        }
      }
    }

  }

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

Measured memory_bytes: 7416
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
int M = 100001;
int main(){
  int N;
  cin >> N;
  int num[M];
  for(int i=0;i<M;i++) num[i] = 0;

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

  int ans = 0;
  for(int i=0;i<M-2;i++){
    ans = max(ans, num[i]+num[i+1]+num[i+2]);
  }
  cout << ans <<endl;

  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

int find_gcd(int a, int b, int c)
{
    //cout << "(a, b, c) = " << a << "," << b << "," << c << endl;

    int m = min(min(a, b), c);
    for(int i = m; i >= 1; i --)
        if (a % i == 0 && b % i == 0 && c % i == 0)
            return i;
    return 1;
}

int main(void)
{
    int k;
    cin >> k;

    int arr[k + 1][k + 1][k + 1] = {0};

    

    vector<int> v;
    int sum = 0;
    for(int a = 1; a <= k; a ++)
    for(int b = 1; b <= k; b ++)
    for(int c = 1; c <= k; c ++)
    {
        v = {a, b, c};
        sort(v.begin(), v.end());
        if (arr[v[0]][v[1]][v[2]] == 0)
            arr[v[0]][v[1]][v[2]] = find_gcd(a, b, c);

        sum += arr[v[0]][v[1]][v[2]];

        v.clear();
    }

    cout << sum << endl;

    return 0;
}

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

using namespace std;
int main(){
    int a,b,k;
    cin >> a >> b >> k;
  	vector<int> ans(101,0);
   for(int i = 1;i < 101;i++){
     if(a % i == 0 && b % i == 0){
      ans.at(i) = i;
     }
   }
   sort(ans.begin(),ans.end());
   reverse(ans.begin(),ans.end());
   cout << ans.at(k-1) << endl;

     return 0;
}

Measured memory_bytes: 256