akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main(){
  int x, y;
  while(1){
    cin >> x >> y;
    if (x==0 && y==0) break;
    if (x >= y) cout << y << " " << x;
    else cout << x << " " << y;
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 3016
n = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))

def fact(n):
  if n==1:
    return 1
  else:
    return n*fact(n-1)

def hoge(n,lis):
    for i in range(len(lis)):
        if n==lis[i]:
            return i
        
def cnt(lis):
    #input: list
    l = list(range(1,len(lis)+1)) #[1,2,...,n]
    ret = 1
    for i in range(len(lis)-1):
        ret += (hoge(int(lis[i]),l)) * fact(len(l)-1)
#         print((int(lis[i])-1) * fact(len(l)-1))
        l.remove(lis[i])
#         print(l)
    return ret

print(abs(cnt(P) - cnt(Q)))

Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    var A = readLine()!!.split(" ").map { it.toInt() }.sorted()
    var min: Int = A.first()
    while (A.size > 1) {
        min = A.first()
        A = A.mapIndexed { index, i -> if (index != 0) i % min else i }.filter { it != 0 }.sorted()

    }
    println(if (A.isNotEmpty()) A[0] else min)
}

Measured memory_bytes: 60488
# coding: utf-8

if __name__ == "__main__":
    n, k, q = map(int, input().split(" "))
    scores = [0 for _ in range(n)]
    for _ in range(q): scores[int(input())-1] += 1
    for i in range(n):
        d = k-q+scores[i]>0
        print("Yes" if d else "No")

Measured memory_bytes: 4672
/*
 * FileName:     D_fix_2
 * CreatedDate:  2020-05-17 16:56:52 +0900
 * LastModified: 2020-05-17 17:24:42 +0900
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long int dp[101][100000]={};
long int dp_search(int *w,long int *v,int n,int W,int u){
    if(n==u){
        return 0;
    }
    if(dp[u][W]!=0){
        return dp[u][W];
    }
    if(W<w[u]){
        dp[u][W]=dp_search(w,v,n,W,u+1);
        return dp[u][W];
    }
    long int s1 = dp_search(w,v,n,W-w[u],u+1)+v[u];
    long int s2 = dp_search(w,v,n,W,u+1);
    if(s1>s2){
        dp[u][W]=s1;
        return s1;
    }
    else{
        dp[u][W]=s2;
        return s2;
    }
}
int main(void){
    int n,W;
    scanf("%d %d",&n,&W);
    int *w = malloc(n*sizeof(int));
    long int *v = malloc(n*sizeof(long int));
    for(int i=0;i<n;i++){
        scanf("%d %ld",w+i,v+i);
    }
    long int ans = dp_search(w,v,n,W,0);
    printf("%ld\n",ans);
    free(w);
    free(v);
    return 0;
}


Measured memory_bytes: 76288
#include <bits/stdc++.h>
#define INF 1000000000
#define LINF 1000000000000000000
#define MOD 1000000007
#define mod 1000007
#define INF63 1061109567
#define INF127 9187201950435737471
#define F first
#define S second
#define ll long long
#define N 100010
#define M 110
using namespace std;
ll n,b,w[M],v[M],dp[N][M],t=0,ans=0;
int main(){
	ll i,j;
	cin>>n>>b;
	w[0]=0;
	v[0]=0;
	for(i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];
		t+=w[i];
	}
	memset(dp,127,sizeof(dp));
	dp[0][0]=0;
	for(i=0;i<=t;i++)
	{
		for(j=1;j<=n;j++)
		{
			dp[i][j]=min(dp[i][j],dp[i][j-1]);
			if(i>=w[j])
			{
				dp[i][j]=min(dp[i][j],dp[i-w[j]][j-1]+v[j]);
			}
		}
	}
	for(i=t;i>=0;i--)
	{
		if(dp[i][n]<=b)
		{
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 86144
<?php
while (!feof(STDIN)) {
    $ary = explode(" ", trim(fgets(STDIN)));
    $x = $ary[0];
    $y = $ary[1];
    if ($x==0&&$y==0) break;
    if ($x > $y) {
        $tmp = $x;
        $x = $y;
        $y = $tmp;
    }
    echo $x." ".$y.PHP_EOL;
}

Measured memory_bytes: 15140
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    int k = b -a;
    if(k & 1) cout << "Borys" << endl;
    else cout << "Alice" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys

class UnionFind():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return

def inpl(): return list(map(int, input().split()))
input = sys.stdin.readline

N, M = inpl()
Edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

UF = UnionFind(N)
ic = N*(N-1)//2
Ans = []
for i, (a, b) in enumerate(Edge[::-1]):
    Ans.append(ic)
    ra = UF.find(a)
    rb = UF.find(b)
    if ra != rb:
        ic -= UF.size[ra]*UF.size[rb]
        UF.union(a, b)
for a in Ans[::-1]:
    print(a)


Measured memory_bytes: 121180
#include <iostream>
#include <math.h> 


using namespace std;

static inline bool is_closer(long long x, long long y, long long D)
{
	long long int xx, yy;
	long long int dd = D * D;
	xx = x * x;
	yy = y * y;
	if (xx + yy <= dd)
		return true;
	return false;
}

int main()
{
	int N, D;
	cin >> N >> D;
	int x, y;
	int count = 0;
	for(int i = 0; i < N; i++) {
		cin >> x >> y;
		if(is_closer(x, y, D))
			count++;
	}
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1100000000

int main(){
	
	int N;
	cin>>N;
	
	vector<int> a(N),b(N);
	for(int i=0;i<N;i++){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<N;i++){
		scanf("%d",&b[i]);
	}
	
	int ans = 0;
	
	for(int i=28;i>=0;i--){
		sort(b.begin(),b.end());
		
		int l[2] = {1<<i,(1<<(i+1))+(1<<i)};
		int r[2] = {1<<(i+1),1<<(i+2)};
		int t = 0;
		for(int j=0;j<N;j++){
			for(int k=0;k<2;k++){
				int d = distance(lower_bound(b.begin(),b.end(),l[k]-a[j]),lower_bound(b.begin(),b.end(),r[k]-a[j]));
				t ^= (d&1);
			}
		}

		ans ^= t<<i;
		
		for(int j=0;j<N;j++){
			if((a[j]>>i)&1)a[j]^=(1<<i);
			if((b[j]>>i)&1)b[j]^=(1<<i);
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 1792
read = input
n, m = map(int, read().split())
f = [-1 for i in range(n + 1)] # 1 ~ n
def find(x):
    if f[x]<0:
        return x
    else :
        f[x] = find(f[x])
        return f[x]
for i in range(m):
    x,y,z = map(int, read().split())
    if abs(x) < abs(y): #合并到x上，保证x是大集合
        x,y = y,x
    fx = find(x)
    fy = find(y)
    if fx == fy:continue
    f[fx] = f[fx] - 1
    f[fy] = fx
#     print(x,y,fx,fy,f)

ans = 0
for i in range(1, n+1): # 1~n
    if f[i] < 0:
        ans += 1
print(ans)

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

a = [int(input()) for i in range(m)]

broken = [[] for i in range(n+1)]

for i in a:
    broken[i] = 1

dp = [0 for i in range(n+2)]

mod = 1000000007

dp[n] = 1

for i in range(n-1, -1, -1):
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])


    

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

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

 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

//---------------------------------------------
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y]; //rootに素集合のサイズにマイナス符号をつけて保持
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
 
    UnionFind UF(N);
 
    rep(i,Q) {
        int P,A,B;
        cin >> A >> B;
        UF.merge(A,B);
    }
    int ans = 0;
    rep(i,N) {
        ans = max(ans,UF.size(i));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3992
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

bool is[10010];

int main(){
  int n;

  rep(i,10010){
    is[i] = true;
  }
  is[1] = is[0] = false;
  for(int i = 2; i < 10010; i++){
    for(int j = 2; i*j < 10010; j++){
      if(is[i] == true){
	is[i*j] = false;
      }
    }
  }

  while(1){
    cin >> n;
    if(n == 0) break;
    for(int i = n; i >= 0; i--){
      if(is[i] && is[i-2]){
	cout << i-2 << " "<< i << endl;
	break;
      }
    }
  }



  return 0;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;


int main(void)
{
    int H, W;
    cin >> H >> W;

    vector<string> s(H);
    int black = 0;
    for (int i = 0; i < H; i++)
    {
        cin >> s[i];
        for (int j = 0; j < W; j++)
        {
            if(s[i][j] == '#'){
                black++;
            }
        }
    }

    vector<vector<int>> dist(H, vector<int>(W, INF));
    vector<pii> dirs = {{0,1}, {1,0}, {-1,0}, {0,-1}};
    queue<pii> que;
    pii start = {0,0};
    que.push(start);
    dist[start.first][start.second] = 1;

    while (!que.empty())
    {
        pii current = que.front();
        que.pop();

        for (int d = 0; d < 4; d++)
        {
            int nextH = current.first + dirs[d].first;
            int nextW = current.second + dirs[d].second;

            if(nextH < 0 || nextH >= H) continue;
            if(nextW < 0 || nextW >= W) continue;

            if(s[nextH][nextW] != '.') continue;

            if(dist[nextH][nextW] > dist[current.first][current.second] + 1){
                
                dist[nextH][nextW] = dist[current.first][current.second] + 1;
                
                que.push({nextH, nextW});
            }
        }
    }
    
    int used = dist[H-1][W-1];

    if(used >= INF){
        cout << -1 << endl;
        return 0;
    }

    int unused = H * W - used;
    int ans = unused - black;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>          // printf(), scanf()
#include <stdbool.h>

#define MAX_N 10000

int par[MAX_N + 1];
int rank[MAX_N + 1];

void
init_union_find(int n)
{
	int i;

	for (i = 0; i <= n; ++i)
	{
		par[i] = i;
		rank[i] = 0;
	}
}

int
find(int x)
{
	if (x == par[x])
		return x;
	else
		return par[x] = find(par[x]);
}

void
unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y)
		return;

	if (rank[x] < rank[y])
		par[x] = y;
	else
	{
		par[y] = x;
		if (rank[x] == rank[y])
			rank[x]++;
	}
}

bool
same(int x, int y)
{
	return find(x) == find(y);
}

int
main(int argc, char** argv)
{
	int n, q;
	int c, x, y;

	scanf("%d %d", &n, &q);
	init_union_find(n);
	while (q--)
	{
		scanf("%d %d %d", &c, &x, &y);
		if (c == 0)
			unite(x, y);
		else
			printf("%d\n", same(x, y) ? 1 : 0);
	}

	return 0;
}

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

int main() {
  string S;
  int k=0;;

  cin >> S;

  for ( int i = 0; i < 4; i++ ) {
    if(S[i] == '+') {
      k++;
    } else {
      k--;
    }
  }

  cout << k << endl;

  return 0;
}


Measured memory_bytes: 256
import bisect
s = input()
t = input()
data = {}
max_s = len(s) + 1
for i in range(26):
    data[chr(i + ord('a'))] = []
for i in range(len(s)):
    data[s[i]].append(i+1)
for i in range(26):
    data[chr(i + ord('a'))].append(max_s)
pre = 0
ans = 0
for i in range(len(t)):
    char = t[i]
    if len(data[char]) == 1:
        print(-1)
        exit()
    else:
        index = bisect.bisect_left(data[char], pre+1)
        if data[char][index] == max_s:
            ans += len(s) - pre
            pre = data[char][0]
            ans += pre
        else:
            ans += data[char][index] - pre
            pre = data[char][index]
print(ans)


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

using namespace std;

#define INF 1e9

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

    int n,k;
    cin>>n>>k;

    int pos;

    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        if(a==1)pos=i;
    }

    int ans=(n-1+k-2)/(k-1);

    cout<<ans<<endl;

}

Measured memory_bytes: 256
main = do
  [a, b, c] <- map read . words <$> getLine :: IO [Int]
  k <- readLn :: IO Int
  putStrLn $ ans k $ f a b c 0

f :: Int -> Int -> Int -> Int -> Int
f a b c i
  | a >= b = f a (b * 2) c i + 1
  | b >= c = f a b (c * 2) i + 1
  | otherwise = i

ans k i
  | k >= i = "Yes"
  | otherwise = "No"


Measured memory_bytes: 3884
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	int a=scan.nextInt();
	int b=scan.nextInt();
	int c=scan.nextInt();
	int d=scan.nextInt();
	int h=d-b;
	int w=c-a;
	System.out.println((c-h)+" "+(d+w)+" "+(a-h)+" "+(b+w));
	scan.close();
}
}

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

int main ()
{
int a=0,b=0;
for(int i=0;i<4;i++)
{
int q;
cin>>q;
a+=q;
}
for(int i=0;i<4;i++)
{
int q;
cin>>q;
b+=q;
}
if(a>b)cout<<a<<endl;
else cout<<b<<endl;


return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incID(i, l, r) for(LL i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(LL i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(LL i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(LL i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC static_cast
#define SI(v) SC<int>(v.size())
#define SL(v) SC<LL >(v.size())
#define RF(e, v) for(auto & e: v)
#define ef else if
#define UR assert(false)

// ---- ----

int n, x, l[100];

int main() {
	cin >> n >> x;
	inc(i, n) { cin >> l[i]; }
	
	int ans = 1, d = 0;
	inc(i, n) {
		d += l[i];
		if(d <= x) { ans++; }
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
program main
	implicit none
    integer::n,t,i
    integer(8)::ans1,ans2
    integer,allocatable::a(:)
    real::ave
    read(*,*)n
    allocate(a(n))
    read(*,*)a
    ans1=0
    ans2=0
    ave=sum(a)/real(n,8)
    t=int(ave)
    do i=1,n
    	ans1=ans1+(a(i)-t)**2
    end do
    do i=1,n
    	ans2=ans2+(a(i)-(t+1))**2
    end do
    write(*,*) min(ans1,ans2)
    
    
    
    deallocate(a)
    stop
end program main


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
  int n;

  cin >> n;

  char str[n];
  int counter[n];
  int ans = 0;

  for (int i=0; i<n; i++) {
    cin >> str[i];
    counter[i]=0;
  }

  for (int j=0; j<n; j++) {
    map<char, int> mp{};
    for (int i=0; i<n; i++) {
      char temp = str[i];
      mp[temp] = 0;
    }
    // firmer part
    for (int i=0; i<j; i++) {
      char temp = str[i];
      if (mp[temp] == 0) {
        mp[temp] = 1;
      }
    }
    // later part
    for (int i=j; i<n; i++) {
      char temp = str[i];
      if (mp[temp] == 1) {
        mp[temp] = 2;
      }
    }

    for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
      if ( itr->second == 2)
        counter[j]++;
    }
  }


  for (int i=0; i<n; i++) {
    if (ans < counter[i])
      ans = counter[i];
  }

  cout << ans << endl;
}


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

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#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 ALL(v) (v).begin(), (v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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

    int k, a, b;
    cin >> k >> a >> b;

    for (int n=a; n<=b; n++) {
        if (n%k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long X;
    cin >> X;
    long yen = 100;
    for (int i = 0;;i++) {
        if (yen >= X) {
            cout << i << endl;
            return 0;
        }
        yen = (long)(yen * 1.01);
    }
    return 0;
}


Measured memory_bytes: 3636
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

score = {'r': P, 's': R, 'p': S}

ans = 0
for r in range(K):
    i = r
    p = '' #一個前の文字
    while i<N:
        if T[i] == p:
            p = ''
        else:
            ans += score[T[i]]
            p = T[i]
        i += K

print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>//STL vetor
#include <list>//STL list
#include <map>// STL map
#include <queue>// STL queue
#include <stack>//sTL stack
#include <bitset>
#include <algorithm>
using namespace std;

const int maxV = 1e5 + 9;
vector<int> v;
int n;
int cnt[maxV];

pair<int, int> getMax(int start) {
    memset(cnt, 0, sizeof cnt);

    int max1 = 0, max2 = 0;
    for (int i = start; i < n; i += 2) {
        ++cnt[v[i]];
        if (cnt[v[i]] > cnt[max1]) {
            max2 = max1;
            max1 = v[i];
        }
        else if (v[i] != max1 && cnt[v[i]] > cnt[max2]) max2 = v[i]; 
    }
    return make_pair(max1, max2);
}

int main() {
    cin>>n;
    v = vector<int>(n + 9, 0);
    for (int i = 0; i < n; ++i) cin>>v[i];
    
    pair<int, int> evenMax = getMax(0);
    int evenMax1 = cnt[evenMax.first];
    int evenMax2 = cnt[evenMax.second];

    pair<int, int> oddMax = getMax(1);
    int oddMax1 = cnt[oddMax.first];
    int oddMax2 = cnt[oddMax.second];
    
    int res;
    if (evenMax.first != oddMax.first) res = evenMax1 + oddMax1;
    else 
    if (evenMax2 > oddMax2) res = evenMax2 + oddMax1;
    else res = evenMax1 + oddMax2;
    
    cout<<n - res;
    return 0;
}



Measured memory_bytes: 1024
n=int(input())
a=list(map(int,input().split()))
ctm=0
for i in range(n):
  if a[i]<0:
    ctm+=1
    a[i]=abs(a[i])
if ctm%2==0:
  print(sum(a))
else:
  print(sum(a)-min(a)*2)

Measured memory_bytes: 14284
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vdouble = vector<double>;
using vstr = vector<string>;
typedef pair<int,int> P;
int dx[4] = {1, 0, -1, 0},dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
template<class T> inline bool chmax(T& a, T b){if(a<b) {a=b; return 1;} return 0; }
template<class T> inline bool chmin(T& a, T b){if(a>b) {a=b; return 1;} return 0; }
const ll INF = 1LL << 60;
const ll mod = 1000000007;

ll dp[3100][3100];// dp[i][j]=元の数列から連続する区間a[i],a[i+1],...,a[j-1]を抜き出した状態から最善を尽くした時のX-Yの値
int main(){
	ll N; cin>>N;
	vll a(N); rep(i,N) cin>>a[i];
	
	rep(i,N) dp[i][i]=0;
	
	for(ll i=1; i<=N; i++){//区間幅の長さ
		for(ll j=0; j+i<=N; j++){//先頭の番号
			ll k=i+j;//末尾の番号
			
			if((N-i)%2==0){
				dp[j][k]=max(dp[j+1][k]+a[j],dp[j][k-1]+a[k-1]);
			}
			else{
				dp[j][k]=min(dp[j+1][k]-a[j],dp[j][k-1]-a[k-1]);
			}
			
			
		}
	}
	
	cout<<dp[0][N]<<endl;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    rep(i, N) cin >> h[i];

    int res = 0;
    int bar = 0;
    rep(i, N) {
        if (bar < h[i]) {
            res += (h[i] - bar);
            bar = h[i];
        } else {
            bar = h[i];
        }
    }
    cout << res << endl;
}

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

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

typedef pair<int, int> P;

//ダイクストラ法を用いて単一始点最短路問題を解く
const int MAX_V = 110000;
const int INF = 1e12;

struct edge {
    int to, cost;
};

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d + V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first)
            continue;
        for (int i = 0; i < G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int K;
signed main() {
    cin >> K;
    V = K;
    for (int i = 0; i < K; i++) {
        if (i % 10 != 9)G[i].push_back({(i + 1) % K, 1});
        G[i].push_back({i * 10 % K, 0});
    }
    dijkstra(1);
    cout << d[0] + 1 << endl;
}


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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e8
#define INF_LL 1LL<<60
#define ll long long
#define MAX_V 100005

vector<int> alpha(26);

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    ll ans = 0;
    ans += (n / (a+b)) * a;
    ll tmp = n % (a+b);
    if(tmp >= a) cout << ans + a <<  endl;
    else cout << ans + tmp << endl;
    

    return 0;
}
 

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int j[2],m[2],e[2],c[2],i,t,s;
	for(i=0;i<2;i++){
		scanf("%d%d%d%d",&j[i],&m[i],&e[i],&c[i]);
		s=j[0]+m[0]+e[0]+c[0];
		t=j[1]+m[1]+e[1]+c[1];
	}
	if(s>t)printf("%d\n",s);
	else printf("%d\n",t);
	return 0;
}


Measured memory_bytes: 2112
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	lint N, M;
	lint ans;
	cin >> N >> M;

	if (N == M)
	{
		ans = 2;
		for (int i = 2; i < N + 1; i++)
		{
			ans *= i;
			ans %= INV;
			ans *= i;
			ans %= INV;
		}
	}
	else if (abs(N - M) == 1)
	{
		ans = 1;
		for (int i = 2; i < min(N, M) + 1; i++)
		{
			ans *= i;
			ans %= INV;
			ans *= i;
			ans %= INV;
		}
		ans *= max(N, M);
		ans %= INV;
	}
	else
	{
		ans = 0;
	}

	cout << ans << endl;

	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

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

char count(int m,int f,int r){

  int sum=m+f;
  char lank;
  if(m==-1||f==-1){lank='F';}
  else if(sum>=80){lank='A';}
  else if(sum>=65&&80>sum){lank='B';}
  else if(sum>=50&&65>sum){lank='C';}
  else if(sum>=30&&50>sum){if(r>=50){lank='C';}
                           else{lank='D';}}
  else if(30>sum){lank='F';}

  return lank;
}

int main(void){
  while(1){
    int m,f,r;
    cin>>m>>f>>r;
    if(m==-1&&f==-1&&r==-1)break;
    cout<<count(m,f,r)<<endl;
  }
}


Measured memory_bytes: 3092
#include <iostream>
#include <queue>
#include <map>
using namespace std;

#define Int int_fast64_t
#define pll pair<Int,Int>
template<class T> using pql = priority_queue<T,vector<T>>;
template<class T> using pq = priority_queue<T,vector<T>,greater<T>>;
#define LL(n) Int n; cin >> n;
#define RP(n) for (Int i = 0; i < n; i++)
#define REP(n,i) for (Int i = 0; i < n; i++)

struct node{
    int to;
    int length;
};

vector<vector<node>> to;
vector<int> flag;
vector<int> c;


void dfs(int from) {
    for (auto z : to.at(from)) {
        int next = z.to;
        int length = z.length;
        if (flag.at(next) == 0) {
            flag.at(next) = 1;
            if (length % 2 == 0) {
                c.at(next) = c.at(from);
            } else {
                c.at(next) = 1 - c.at(from);
            }
            dfs(next);
        }
    }
}

int main(void){
    LL(n);
    map<string,int> mp;
    RP(n) {
        string a;
        cin >> a;
        mp[a]++;
    }
    if (mp.size() == n) {
        cout <<"YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}

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

int main()
{
	int R, L, d;
	cin >> L >> R >> d;

	int count = 0;

	for (int i = L; i <= R; i++) {
		if (i%d == 0) {
			count++;
		}
	}

	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3228
#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;
typedef long long ll;
const int N = 1010;

int main()
{
	char a;
	scanf("%c", &a);
	if(a >= 'a' && a <= 'z')	puts("a");
	else if(a >= 'A' && a <= 'Z')	puts("A");
	return 0;
}



Measured memory_bytes: 3680
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
	string W,T;
	int cnt=0,i=0;
	cin>>W;
	while(1){
		i++;
		cin>>T;
		if(T=="END_OF_TEXT") break;
		transform(T.begin(),T.end(),T.begin(),::tolower);
		if(W==T) cnt++;
	}

	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 3216
N, W = map(int, input().split())

items = [[] for _ in range(4)]
w0, v0 = map(int, input().split())
items[0].append(v0)

for _ in range(N - 1):
    w, v = map(int, input().split())
    items[w - w0].append(v)

for i in range(4):
    items[i].sort(reverse=True)

sumItems = [[0 for _ in range(len(items[i]) + 1)] for i in range(4)]

for i in range(4):
    for j, v in enumerate(items[i]):
        sumItems[i][j + 1] = sumItems[i][j] + v

ans = 0
for firstCount in range(len(items[0]) + 1):
    for secondCount in range(len(items[1]) + 1):
        for thirdCount in range(len(items[2]) + 1):
            for forthCount in range(len(items[3]) + 1):
                sumWeight = w0 * firstCount + (w0 + 1) * secondCount + (w0 + 2) * thirdCount + (w0 + 3) * forthCount
                if sumWeight > W:
                    break
                sumV = 0
                for i, count in enumerate([firstCount, secondCount, thirdCount, forthCount]):
                    sumV += sumItems[i][count]
                ans = max(ans, sumV)

print(ans)

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    ll N, K; cin >> N >> K;
    vector<ll> a(N);
    rep(i, N) cin >> a[i];
    if(K == 1){
        cout << 0 << endl;
        return;
    }
    sort(all(a));
    auto b = a;
    reverse(all(b));
    modint res1 = 0, res2 = 0;
    Rep(i, K-1, N){
        res1 = res1 + comb(i, K-1)*modint(a[i]);
        res2 = res2 + comb(i, K-1)*modint(b[i]);
    }

    modint res = res1 - res2;

    cout << res.n << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end(), greater<>());
    int alice = 0, bob = 0;
    for (auto i = 0; i < a.size(); i++) {
        if(i % 2) bob += a[i];
        else alice += a[i];
    }

    cout << (alice - bob) << endl;
    return 0;
}

Measured memory_bytes: 256
def main():
    from heapq import heappush,heappop,heapify
    N, M = (int(i) for i in input().split())
    A = [-int(i) for i in input().split()]
    heapify(A)
    for divcnt in range(M):
        tmp = -heappop(A)
        tmp //= 2
        heappush(A,-tmp)
    print(-sum(A))
if __name__ == "__main__":
    main()


Measured memory_bytes: 72088
#!/usr/bin/perl
my ($n) = map { $_ - 0 } split(/\s+/,<STDIN>);
my @aa = map { $_ - 0 } split(/\s+/,<STDIN>);

my %t = ();

for(my $i=0;$i<$n;$i++){
  $t{"" . $aa[$i]} += 1;
}
my @k_t = keys %t;
my $n_k = 1 + $#k_t;

if( $n_k > 3 ){
  print "No\n";
  exit(0);
}

if( $n_k == 1 and ( $k_t[0] - 0 ) == 0 ){
  print "Yes\n";
  exit(0);
}

my $res = 'No';
if( ( $n % 3 ) == 0 ){
  if( $n_k == 3 ){
    if( ( ( ( $k_t[0] - 0 ) ^ ( $k_t[1] - 0 ) ) == ( $k_t[2] - 0 ) ) 
        and ( $t{$k_t[0]} == $t{$k_t[1]} ) and ( $t{$k_t[1]} == $t{$k_t[2]} ) ){
      $res = 'Yes';
    }
  } elsif( $n_k == 2 ){
    if( ( ($k_t[0] - 0) == 0 and $t{$k_t[1]} == $t{$k_t[0]} * 2 )
        or ( ($k_t[1] - 0) == 0 and $t{$k_t[0]} == $t{$k_t[1]} * 2 ) ){
      $res = 'Yes';
    }
  }
}

print "$res\n";

exit(0);



Measured memory_bytes: 26924
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

    n, q = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)
    ans = [0]*n
    for _ in range(q):
        p, x = map(int, input().split())
        p -=1
        ans[p] += x
    
    from collections import deque
    que = deque([0])
    parent = [-1]*n
    while que:
        node = que.pop()
        for v in adj[node]:
            if v == parent[node]:
                continue
            parent[v] = node
            que.append(v)
            ans[v] += ans[node]
    for a in ans:
        print(a)

        

    
if __name__ == '__main__':
    main()

Measured memory_bytes: 55108
s=[x for x in input()]
t=[x for x in input()]
ls=len(s)
lt=len(t)
ret=False
for i in range(ls-lt,-1,-1):
  flag=True
  for j in range(lt):
    if s[i+j]!='?' and s[i+j]!=t[j]:
      flag=False
  if flag==True:
    for j in range(lt):
      s[i+j]=t[j]
    ret=True
    break
for i in range(ls):
  if s[i]=='?':
    s[i]='a'
if ret==True:
  print(''.join(map(str,s)))
else:
  print('UNRESTORABLE')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
#define s(all)   s.begin(),s.end()
#define rep(i,n) for(long long i=0;i<n;i++)
#define ll       long long

int main() {
  int n;
  ll t;
  cin>>n>>t;
  vector<ll> v(n+1);
  rep(i,n)cin>>v[i];
  v[n]=LONG_LONG_MAX;
  ll ans=0;
  ll lag=0;
  rep(j,n){
    lag=v[j+1]-v[j];
    if(lag<t)ans+=lag;
    else ans+=t;
    cerr<<"at "<<j+1<<":ans="<<ans<<",lag="<<lag<<endl;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>
void view(const std::vector<T> &v)
{
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

#pragma region mod
const int p = 1e9 + 7; //10^9 + 7
struct mint
{
    ll x;
    mint(ll xx = 0) : x(xx % p) {}
    mint &operator+=(const mint a)
    {
        if ((x += a.x) >= p)
            x -= p;
        return *this;
    }
    mint &operator-=(const mint a)
    {
        if ((x += p - a.x) >= p)
            x -= p;
        return *this;
    }
    mint &operator*=(const mint a)
    {
        (x *= a.x) %= p;
        return *this;
    }

    mint operator+(const mint a) const
    {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const
    {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const
    {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const
    {
        mint r = 1;
        mint a = *this;
        while (true)
        {
            if (t & 1)
            {
                r *= a;
            }
            t >>= 1;
            if (t == 0)
                break;
            a *= a;
        }

        return r;
    }

    mint inv() const
    {
        return pow(p - 2);
    }

    mint &operator/=(const mint a)
    {
        return (*this) *= a.inv();
    }
};
istream &operator>>(istream &is, mint &a) { return is >> a.x; }
ostream &operator<<(ostream &os, const mint &a) { return os << a.x; }

struct comb
{
    vector<mint> fact, invs;
    comb(int n) : fact(n + 1), invs(n + 1)
    {
        assert(n < p);

        fact[0] = 1;
        for (int i = 1; i <= n; ++i)
            fact[i] = fact[i - 1] * i;

        invs[n] = fact[n].inv();
        for (int i = n; i >= 1; --i)
            invs[i - 1] = invs[i] * i;
    }
    mint operator()(int n, int k)
    {
        if (k < 0 || k > n)
            return 0;
        return fact[n] * invs[n - k] * invs[k];
    }
};
#pragma endregion

using vmint = vector<mint>;
int main()
{
    int n;
    cin >> n;
    vmint a(n);
    rep(i, n) cin >> a[i];
    vmint b(n + 1);
    rep(i, n) b[i + 1] = b[i] + a[i];
    mint ans = 0;
    rep(i, n)
    {
        ans += a[i] * (b[n] - b[i + 1]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6424
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N; long long K;
	cin >> N >> K; 
	long long A[200010], S[200010] = {}; // Sにはヘイホーを入れる
	for(int i = 0; i < N; i++){
		cin >> A[i]; 
		S[i] = A[i] * A[i]; 
	}
	sort(A, A+N); 
	sort(S, S+N); 
	long long ng = -1e18-7; 
	long long ok = 1e18+7; 
	K *= 2; K--; // 重複を考慮すると2K-1番目。ヘイホーはにぶたんの中で処理
	while(ok - ng > 1){
		long long mid = (ok + ng) / 2; 
		long long cnt = 0; 
		long long M = K; 
		M += upper_bound(S, S+N, mid) - S; // mid以下のものがM個以上か
		for(int i = 0; i < N; i++){
			if(A[i] == 0 && mid >= 0) cnt += N; 
			else if(A[i] < 0){
				cnt += N - (lower_bound(A, A+N, (long double) mid / A[i]) - A); // あやしい
			}
			else{
				cnt += upper_bound(A, A+N, (long double) mid / A[i]) - A; // あやしい
			}
		}
		if(cnt < M) ng = mid; 
		else ok = mid;  
	}
	cout << ok << endl; 
}

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


using ll = long long;
const int MaxD = 20;
int K;
int a[MaxD];
int f[MaxD][10];


int dfs(int pos, int pre, bool leading, bool limit)
{
    if (pos == -1) return 1;
    if (!leading && !limit && f[pos][pre] != -1) return f[pos][pre];
    int lo = (pos == 0 && leading) ? 1 : 0;
    int hi = (limit) ? a[pos] : 9;
    int ret = 0;
    for (int x = lo; x <= hi; x++) {
        if (leading)
            ret += dfs(pos - 1, x, leading && (x == 0), limit && (x == hi));
        else if (abs(pre - x) <= 1)
            ret += dfs(pos - 1, x, false, limit && (x == hi));
    }
    if (!leading && !limit) f[pos][pre] = ret;
    return ret;
}


int cnt(ll x)
{
    int idx = 0;
    while (x > 0) {
        a[idx++] = x % 10;
        x /= 10;
    }
    return dfs(idx - 1, 0, true, true);
}


void solve()
{
    memset(f, -1, sizeof(f));
    ll lo = 1LL, hi = 10000000000LL, mid;
    while (lo < hi) {
        mid = (lo + hi) / 2;
        int c = cnt(mid);
        if (c < K)
            lo = mid + 1;
        else
            hi = mid;
    }
    cout << lo << endl;
}


int main()
{
    cin >> K;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000000000000009
//#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl

bool comp(pair<int,int> F,pair<int,int> G){
    if(F.first!=G.first){
        return F.first<G.first;
    }else{
        return F.second<G.second;
    }
}

signed main(){
    int N,M,Ans=0;
    vector<pair<int,int>> P;
    int a[114514],b[114514];
    cin >> N >> M;
    REP(i,M){
        cin >> a[i] >> b[i];
        P.push_back(make_pair(a[i],b[i]));
    }
    sort(P.begin(),P.end(),comp);
    //REP(i,M){cout << P[i].first << " " << P[i].second << endl;}
    while(!P.empty()){
        Ans++;
        int otosuhashi=P[P.size()-1].first;
        //cout << otosuhashi << endl;
        REP(i,P.size()){
            if(P[i].first<=otosuhashi&&otosuhashi<=P[i].second-1){
                //cout << P[i].first << " " << P[i].second << endl;
                P.erase(P.begin()+i);
                i--;
            }
            
        }
        
        
       /* cout << "//生き残り" << endl;;
        REP(i,P.size()){
            cout << P[i].first << " " << P[i].second << endl;
        }
        cout << "終わり//"　<<endl;
        
        cout << endl << endl;*/
    }
    cout << Ans << endl;
    return 0;
}      


Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define f first
#define s second
#define si(x)   scanf("%d",&x)
#define sl(x)   scanf("%I64d",&x)
#define CLR(x)  memset(x,0,sizeof(x))
#define RESET(x,a) memset(x,a,sizeof(x))
#define pi pair<int,int>
#define pb push_back
#define mp make_pair
#define debug(x) cerr<<">value ("<<#x<<") : "<<x<<endl;
 
const int N=100005;
int a[N];
 
int main()
{
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    int t,n,m,i,j;
    ll ans=0;
    si(n);
    for(i=0;i<n;i++)
    {
        si(a[i]);
    }
    for(i=0;i<n-1;i++)
    {
        ans = ans +(ll)(a[i]/2);
        a[i]=a[i]%2;
        if(a[i]==1&&a[i+1]>=1)
        {
            ans++;
            a[i+1]--;;
        }
    }
    ans = ans + (ll)(a[i]/2);
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner stdIn = new Scanner(System.in);
		int N = stdIn.nextInt();
		int[] S = new int[4];
		for(int i = 0; i < S.length; i ++) {
			S[i] = 0;
		}
		for(int i = 0; i < N; i ++) {
			switch(stdIn.next()) {
			case "AC":
				S[0] ++;
				break;
			case "WA":
				S[1] ++;
				break;
			case "TLE":
				S[2] ++;
				break;
			case "RE":
				S[3] ++;
				break;
			}
		}
		System.out.println("AC x " + S[0]);
		System.out.println("WA x " + S[1]);
		System.out.println("TLE x " + S[2]);
		System.out.println("RE x " + S[3]);
	}
}

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[8] = {-1, 0, 1, 1, -1, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<ll> A(N);
  for (auto &it : A)
    cin >> it;
  ll ans = 0;
  for (int d = 0; d < 60; d++)
  {
    ll n0 = 0, n1 = 0;
    for (int i = 0; i < N; i++)
    {
      if ((A[i] >> d) & 1)
        n1++; // d桁目が1
      else
        n0++;
    }
    ll tmp = (1LL << d) % MOD;
    ll n = n0 * n1 % MOD;
    tmp = tmp * n % MOD;
    ans = (ans + tmp) % MOD;
  }
  cout << ans << endl;
  return 0;
}

// xor 各桁ごとに独立に考える．xorは桁上がりのない加算　


Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int k = sc.nextInt();
        String in = sc.next().trim();
        
        if (in.length() <= k) {
            System.out.println(in);
        } else {
            System.out.println(in.substring(0, k) + "...");
        }
    }
}

Measured memory_bytes: 27080
fun main(args: Array<String>) {
    val s = readLine()!!
    val n = s.length

    val t = Array(2) { LongArray(n) { Long.MAX_VALUE } }

    t[0][0] = (s.last() - '0').toLong()
    t[1][0] = 10L - (s.last() - '0')

    for (i in 1 until n) {
        val x1 = s[s.lastIndex - i] - '0'
        val x2 = x1 + 1

        t[0][i] = Math.min(t[0][i - 1] + x1, t[1][i - 1] + x2)
        t[1][i] = Math.min(t[0][i - 1] + (10 - x1), t[1][i - 1] + (10 - x2))
    }

    println(Math.min(t[0][s.lastIndex], t[1][s.lastIndex] + 1))
}


Measured memory_bytes: 70364
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug
from functools import lru_cache

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def mutual_division_method(a, b):
    while not (a == 0 or b == 0):
        if a < b:
            b = b % a
        else:
            a = a % b
    if a == 0:
        return b
    else:
        return a



def gcd(a, b, c):
    #print('a, b, c', a, b, c) # debug
    d = mutual_division_method(a, b)
    e = mutual_division_method(d, c)
    #print('e', e) # debug
    return e

if __name__ == '__main__':
    k = int(input())
    s = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                ans = gcd(a, b, c)
                s += ans
    #print('s') # debug
    print(s)

    #print('\33[32m' + 'end' + '\033[0m') # debug


Measured memory_bytes: 70972
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int N;cin>>N;
    long long int count=0;
    long long int maximum=0;
    vector<long long int> H(N);
    for(long long int i=0;i<N;i++){
        cin>>H[i];
    }
    for(long long int i=0;i<N-1;i++){
        if(H[i]>=H[i+1]){
            count++;
            maximum=max(maximum,count);
        }
        else {
            count = 0;
        }
    }
    cout<<maximum;
    return 0;
}



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

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

    int ans = max(a, b) * 2;
    if (a != b) ans--;

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define all(x) (x).begin(), (x).end()
#define PI 3.14159265358979323846264338327950L
using namespace std;
typedef long long ll;
typedef long double ld;
int main() {
    int a,b;
    cin>>a>>b;
    cout<<max(max(a+b,a-b),a*b);
}

Measured memory_bytes: 3616
#include <iostream> 
using namespace std;
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
int main()
{
	
	int n;
	cin>>n;
	queue<double>r;
	vector<double>nex;
	double m = 0;
	for(int i = 0;i<n;i++)
	{
		cin>>m;
		nex.push_back(m);
	}
	sort(nex.begin(),nex.end());
	for(auto &x :nex)
	{
		r.push(x);
	}
	double sum = r.front();
	r.pop();
	while(r.size())
	{
		double sec= r.front();
		r.pop();
		sum = (sum+sec)/2;
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256