akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const long long INF = 50000000000;

int n, m;
int K[152], x[152][10], d[152][10];
long long dp[152][10];

void init()
{
	dp[0][0] = 0;
	for (int i = 1; i <= 151; i++){
		for (int j = 0; j < 10; j++){
			dp[i][j] = INF;
		}
	}
	memset(K, 0, sizeof(K));
	K[0] = 1;
	K[n + 1] = 1;
	memset(x, 0, sizeof(x));
	memset(d, 0, sizeof(d));
}

int main()
{
	while (scanf("%d %d", &n, &m), n + m){
		init();
		
		for (int i = 1; i <= n; i++){
			scanf("%d", &K[i]);
			
			for (int j = 0; j < K[i]; j++){
				scanf("%d %d", &x[i][j], &d[i][j]);
			}
		}
		
		for (int i = 0; i <= n; i++){
			for (int j = 0; j < K[i]; j++){
				for (int k = 0; k < K[i + 1]; k++){
					if (i == 0 || i == n) dp[i + 1][k] = min(dp[i + 1][k], dp[i][j]);
					else dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + (d[i][j] + d[i + 1][k]) * abs(x[i][j] - x[i + 1][k]));
				}
			}
		}
		
		while (m--){
			for (int i = n - 1; i >= 0; i--){
				for (int j = 0; j < K[i]; j++){
					for (int k = 0; k < K[i + 2]; k++){
						if (i == 0 || i == n - 1) dp[i + 2][k] = min(dp[i + 2][k], dp[i][j]);
						else dp[i + 2][k] = min(dp[i + 2][k], dp[i][j] + (d[i][j] + d[i + 2][k]) * abs(x[i][j] - x[i + 2][k]));
					}
				}
			}
			
			for (int i = 0; i <= n; i++){
				for (int j = 0; j < K[i]; j++){
					for (int k = 0; k < K[i + 1]; k++){
						if (i == 0 || i == n) dp[i + 1][k] = min(dp[i + 1][k], dp[i][j]);
						else dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + (d[i][j] + d[i + 1][k]) * abs(x[i][j] - x[i + 1][k]));
					}
				}
			}
		}
		
		printf("%lld\n", dp[n + 1][0]);
	}
	
	return 0;
}

Measured memory_bytes: 1212
gets
  array = gets.split.map(&:to_i)

  elm_cnt = Array.new(array.max + 1){0}
  ans_arr = []

  array.each do | arr_elm |
    elm_cnt[ arr_elm ] += 1
  end

  elm_cnt.size.times do | idx |
    elm_cnt[idx] += elm_cnt[idx - 1] if idx > 0
  end

  array.reverse_each do | arr_elm |
    ans_arr[ elm_cnt[ arr_elm ] - 1 ] = arr_elm
    elm_cnt[ arr_elm ] -= 1
  end

  puts ans_arr.join(" ")



Measured memory_bytes: 150880
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools

def comb(n, k, mod):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % mod
        ret = ret * pow(i, mod - 2, mod) % mod
    return ret

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

A, B = map(int,input().split())
ans = A * B
if(A>9 or B>9):
    print(-1)
else:
    print(ans)


Measured memory_bytes: 39916
T = int(input())

def gcd (a: int,b: int) -> int:
    if a < b: a,b = b,a
    return a if b == 0 else gcd(b,a%b)
def lcm (a: int,b: int) -> int:
    return a // gcd(a,b) * b


for i in range(T):
    A,B,C,D = map(int,input().split(" "))
    g = gcd(B,D)
    if A < B or D < B:
        print("No")
        continue
    if C >= ((B - g) + (A % g)):
        print("Yes")
    else:
        print("No")




Measured memory_bytes: 46320
///FUCKOUT
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
#include <ext/rope> //header with rope
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
//#define endl '\n'

using namespace __gnu_cxx; //namespace with rope and some additional stuff

using ll = long long;
using db = long double;
using row = vector<int>;
using ii = pair<ll, ll>;

const int N = 3e5+5, M = 1e6 + 5, LG = 17, MOD = 1e9 + 7;
const int BLOCK = 55;
const int BLOCKN = N / BLOCK + 1;
const long double EPS = 1e-7;
using ull = unsigned long long;

int32_t main(){
#ifdef ONLINE_JUDGE
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#endif // ONLINE_JUDGE

  string s;
  char c;
  cin >> c; s.pb(c);
  cin >> c; s.pb(c);
  cin >> c; s.pb(c);
  cin >> c; s.pb(c);
  sort(s.begin(),s.end());
  if(s == "1479")
    cout << "YES\n";
  else
    cout << "NO\n";


  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 111;

int n, i, j, ans;
int a[maxN];

int main()
{
    //freopen("test.in","r",stdin);

    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (i = 1; i <= n; i = j) {
        for (j = i; j <= n; j++)
            if (a[i] != a[j])
                break;

        ans += (j - i) / 2;
    }

    cout << ans;


    return 0;
}


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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;


li nums[111];
li bonus[111];
bool use[111];
li d, g;

// x/y
inline li divup(li x, li y) {
    li res = x / y;
    return res + (x % y == 0 ? 0 : 1);
}

inline li calc(li state) {
    rep(i, d) {
        use[i] = ((bit(i)&state) > 0);
    }

    li res = 0;
    li score = 0;
    rep(i, d) {
        if (use[i]) {
            res += nums[i];
            score += (i + 1) * 100 * nums[i] + bonus[i];
        }
    }
    if (score >= g) {
        return res;
    }
    for (li i = d - 1; i >= 0; i--) {
        if (!use[i]) {
            li num = min(nums[i] - 1, divup(g - score, (i + 1) * 100));
            res += num;
            score += num * (i + 1) * 100;
        }
        if (score >= g) {
            break;
        }
    }
    if (score < g) {
        return INF;
    }
    return res;
}

int main() {
    cin >> d >> g;
    rep(i, d) {
        cin >> nums[i] >> bonus[i];
    }

    li res = INF;
    rep(i, bit(d)) {
        res = min(res, calc(i));
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
/*
 * ARC080_D.cpp
 *
 *  Created on: Jun 5, 2018
 *      Author: 13743
 */
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
typedef long long lng;
typedef unsigned long long ulng;

#define pb push_back
#define SZ(a) int((a).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

lng power(lng b, lng e) {lng sol=1; while(e>0) {if(e&1) {sol=sol*b;} e>>=1; b*= b;} return sol;}

vector<int> pa;

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

	int H, W, N;
	cin >> H >> W >> N;
	int c[10000];
	REP(i, N) {
		cin >> c[i];
	}

	REP(i, N) {
		REP(j, c[i]) {
			pa.pb(i+1);
		}
	}
	REP(i, H) {
		int l = i*W;
		int r = i*W+W-1;
		if(i%2 == 0) {
			cout << pa[l];
			FOR(j, l+1, r) {
				cout << " " << pa[j];
			}
		}
		else {
			cout << pa[r];
			FORD(j, r-1, l) {
				cout << " " << pa[j];
			}
		}
		cout << "\n";
	}

	cout << flush;
}






Measured memory_bytes: 512
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
using namespace std;

int main(){
    int N,M,k[20],p[20],s[20][20],x[20],sum=0;
    cin>>N>>M;
    for(int i=0;i<M;++i){
        cin>>k[i];
        for(int j=0;j<k[i];++j)
           cin>>s[i][j];
    }
    for(int i=0;i<M;++i)
        cin>>p[i];
    
    for(int bit=0;bit<(1<<N);++bit){
        for(int i=0;i<N;++i){
            if(bit & (1<<i))
               x[i]=1;
            else x[i]=0;
        }
    
        for(int i=0;i<M;++i){
            int sumi=0;
            for(int j=0;j<k[i];++j)
                sumi+=x[s[i][j]-1];
            if(sumi%2!=p[i])goto lol;
        }
        ++sum;
        lol:
        bool w;
    }
    
    cout<<sum<<endl;
    return 0;

}

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

int main(){
     ios::sync_with_stdio(0);
     cin.tie(0);
     int x = 0;
     int b[5];
     for(int i = 0; i<5; i++){
		 cin >> b[i];
	     if(b[i] == 0){
			 x = i+1;}
	 }
	  cout << x;


}


Measured memory_bytes: 3636
#include<iostream>
#include<sstream>
#include<iomanip>
#include<stdlib.h>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<utility>
#include<algorithm>
using namespace std;
#define loop(i,l,r) for(int (i)=(int)(l);(i)<(int)(r);(i)++)
#define rloop(i,l,r) for(int (i)=(int)(l);(i)>(int)(r);(i)--)
#define rep(i,n) loop(i,0,n)
#define rrep(i,n) rloop(i,n-1,-1)
#define INF 0x3f3f3f3f
#define mod 1000000007
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

int main(){
	int dp[31],d;
	fill(dp,dp+31,0);
	dp[0]=1;
	rep(i,30)rep(j,3)if(i-j>=0)dp[i+1]=dp[i+1]+dp[i-j];
	while(1){
		cin>>d;
		if(d==0)break;
		cout<<dp[d]/3650+1<<endl;
	}
}
	

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#include <numeric>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int x,a,b;
    cin >> x;
    if(x==1) cout << "Hello World";
    else{
        cin >> a >> b;
        cout << a+b << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
using namespace std;
const int N=300005;
int n,m,ans=0,cnt,ok;
int x[N],t[N],l[N],r[N];
int main(){
	scanf("%d%d",&n,&m); m*=2;
	For(i,1,n) scanf("%d",&x[i]);
	For(i,1,n) scanf("%d",&t[i]);
	For(i,1,n){
		int v=t[i]%m;
		ans+=t[i]/m+(t[i]%m!=0);
		l[i]=(0<v&&v<=2*x[i]);
		r[i]=(0<v&&v<=m-2*x[i]);
	}
	For(i,1,n-1)
		if (cnt&&r[i]){
			if (l[i]) ++ok;
			--ans; --cnt;
		}
		else if (l[i]) cnt++;
		else if (r[i]&&ok) ok--,cnt++;
	if (!r[n]) ans++;
	printf("%lld",1ll*ans*m);
}

Measured memory_bytes: 4992
#include <stdio.h>

int main() {
	int n;
	short a[5];
	scanf("%d", &n);
	for (int i = 0; i < 4; i++) {
		a[i] = n % 10;
		n /= 10;
	}

	if ((a[0]==a[1] && a[1]==a[2]) || (a[1]==a[2] && a[2]==a[3])) printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin>>n;
  
  long long int dp[n+1][4];
  for(int i=1;i<=n;i++)
    for(int j=1;j<=3;j++)
      		dp[i][j]=0;
  
  long long int a,b,c;
  cin>>a>>b>>c;
  dp[1][1]=a;dp[1][2]=b;dp[1][3]=c;
  
  for(int i=2;i<=n;i++)
  {
    cin>>a>>b>>c;
    
    dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a;
    dp[i][2]=max(dp[i-1][1],dp[i-1][3])+b;
    dp[i][3]=max(dp[i-1][2],dp[i-1][1])+c;
  
  }  
  cout<<max(dp[n][1],max(dp[n][2],dp[n][3]));
  return 0;
}
  


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

N = int(input())
nums = list(map(int, input().split()))

# ある番号で2分割して、それぞれのグループの総和の差を出す

min_diff = 1000000
for n in range(N):
    former = sum(nums[:n])
    later = sum(nums[n:])
    diff_num = abs(former - later)
    # 0ならそこで終了
    if diff_num == 0:
        min_diff = 0
        break
    # 今回の方が小さいなら更新
    if min_diff > diff_num:
        min_diff = diff_num

print(min_diff)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#ifdef PRAGMA
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif
#define fst first
#define snd second
#define fore(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define bs binary_search
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(n) ((int) (n).size())
#define MAXI ((ll)1e16)
#define MINI ((ll)-1e16)
using namespace std;
typedef long long ll;  
     
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b,a%b); } 
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }          
ll n,k;
ll a[101];
ll dp[100001][2];

ll solve(ll sum, ll p){
	if(sum==0&&p==1)return -1;
	if(sum==0&&p==0)return 1;
	if(dp[sum][p]!=0)return dp[sum][p];
	if(p){
		dp[sum][p]=-1;
		fore(i,0,n){
			if(sum-a[i]>=0)dp[sum][p]=max(dp[sum][p],solve(sum-a[i],(p+1)%2));
		}
	}
	if(!p){
		dp[sum][p]=1;
		fore(i,0,n){
			if(sum-a[i]>=0)dp[sum][p]=min(dp[sum][p],solve(sum-a[i],(p+1)%2));
		}
	}
	return dp[sum][p];
}
int main(){FIN;
	cin >> n >> k;
	fore(i,0,n){
		cin >> a[i];
	}
	if(n==1){
		if((k%a[0]==0 && (k/a[0])%2==0) || (k%a[0]!=0 && ((int)floor((k/a[0])))%2!=0))cout<<"Second";
		else cout << "First";
		return 0;
	}
	memset(dp,0,sizeof(dp));
	if(solve(k,0)<1)cout<<"First";
	else cout << "Second";
}

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

int main(){
	int N;
	int V[20];
	int C[20];
	int i;
	
	scanf(" %d",&N);
	for(i=0;i<N;i++){
		scanf(" %d", &(V[i]));
	}
	for(i=0;i<N;i++){
		scanf(" %d", &(C[i]));
	}
	
	int sum=0;
	for(i=0;i<N;i++){
		if(V[i]>C[i]){
			sum+=V[i]-C[i];
		}
	}
	
	printf("%d\n",sum);
	
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main()
{
	int n, i, j, pre = 0;
	long long num = 1;
	char a[55] = { 0 };
	cin >> n;
	for (i = 0; i<n; i++)
		cin >> a[i];
	if (a[0] == a[1]) { num = 6; i = 2; pre = 0; }
	else { num = 3; i = 1; pre = 1; }
	for (i; i<n; i++)
	{
		if (i<n-1&&a[i] == a[i + 1])
		{
			if (pre == 0)
			{
				num *= 3;
				num %= 1000000007;
				pre = 0;
			}
			else
			{
				num *= 2;
				num %= 1000000007;
				pre = 0;
			}
			i++;
		}
		else
		{
			if (pre == 0)pre = 1;
			else
			{
				num *= 2;
				num %= 1000000007;
				pre = 1;
			}
		}
	}
	cout << num << endl;
	return 0;
}

Measured memory_bytes: 256
#import numpy as np
def main():
    N = int(input()) #count of numbers
    A = list(map(int,input().split())) # array of imput numbers

    # countor, flag = 0, 0
    # while flag == 0:
    #     #print("iteration start")
    #     A = list(map(lambda x: x/2, A))
    #     countor += 1
    #     if (1 in list(map(lambda x: x%2, A))) == True: flag = 1 
    #     #print(flag)
    # print(countor)

    countor = 0
    while True:
        #print("iteration start")
        if (1 in list(map(lambda x: x%2, A))) == True: break
        A = list(map(lambda x: x/2, A))
        countor += 1
        #print(flag)
    print(countor)

if __name__ == "__main__":
    main()

Measured memory_bytes: 39024
h, w, k = map(int, input().split())

c = [0] * h
for i in range(h):
    c[i] = input()

cnt = 0
    
for rows in range(1 << h):
    for cols in range(1 << w):
        black = 0
        for i in range(h):
            if (rows >> i) % 2 == 1:
                continue
            for j in range(w):
                if (cols >> j) % 2 == 1:
                    continue
                black += c[i][j] == '#'
        if black == k:
            cnt += 1

print(cnt)

Measured memory_bytes: 9204
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define rep0(i,n) for (int i=0; i<=(int)(n); ++i)
#define rep1(i,n) for (int i=1; i<=(int)(n); ++i)
#define rrep(i,n) for (int i=(int)(n)-1; i>=0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
template<typename T> using Graph = vector<vector<T>>;
template<typename T> using Spacial = vector<vector<vector<T>>>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MOD = 1e9+7;
const int MOD2 = 998244353;
const double EPS = 1e-9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

template<typename T> struct is_pair : false_type{};
template<typename T1, typename T2> struct is_pair<pair<T1, T2>> : true_type{};
template<typename T> struct is_vector : false_type{};
template<typename T> struct is_vector<vector<T>> : true_type{};

template<typename T1, typename T2>
istream &operator >> (istream &istr, pair<T1, T2> &p) {
  istr >> p.first >> p.second;
  return istr;
} 
template<typename T1, typename T2>
ostream &operator << (ostream &ostr, const pair<T1, T2> &p) {
  ostr << p.first << " " << p.second;
  return ostr;
}
template<typename T>
ostream &operator << (ostream &ostr, const vector<T> &vec) {
  if (vec.empty()) return ostr;
  bool vp = is_vector<T>() || is_pair<T>();
  ostr << vec.front();
  for (auto itr = ++vec.begin(); itr != vec.end(); ++itr) {
    ostr << (vp ? "\n" : " ") << *itr;
  }
  return ostr;
}

template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int modpow(int a, long long n, int mod = MOD) {
  int ret = 1;
  do {
    if (n & 1) ret = 1LL * ret * a % mod;
    a = 1LL * a * a % mod;
  } while (n >>= 1);
  return ret;
}

template<typename T>
T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<typename T>
T LCM(T a, T b) { return a / GCD(a, b) * b; }

template<typename T1, typename T2>
bool CompareBySecond(pair<T1, T2> a, pair<T1, T2> b) {
  return a.second != b.second ? a.second < b.second : a.first < b.first;
}
template<typename T>
bool CompareBySlope(pair<T, T> a, pair<T, T> b) {
// counterclockwise from 12 o'clock direction
  if (a.first * b.first < 0) return a.first < b.first;
  if (a.first == 0) return a.second >= 0 || b.first > 0;
  if (b.first == 0) return b.second < 0 && a.first < 0;
  return a.second * b.first < a.first * b.second;
}


/* -------- <templates end> -------- */


void solve() {
  int n, k; cin >> n >> k;
  int ans = 1;
  while (n >= k) {
    n /= k;
    ++ans;
  }
  cout << ans << endl;
}


/* -------- <programs end> -------- */


signed main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
import sys
A,B = map(int,input().split())

cunt = 0
if not 10000 <= A <= B <= 99999:
    print(0)
    sys.exit(0)
for i in range(A,B+1):
    sita = list(str(i))
    ue = sita[::-1]

    if sita == ue:
        cunt += 1

print(cunt)


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

typedef long long int ll;
#define T int t,q; scanf("%d",&t); for(q=1;q<=t;q++)

int main(){
	ll n=5,i;
	//cin >> n;
	ll ar[n+5];
	
	for(i=0;i<n;i++){
		cin >> ar[i];
		if(ar[i]==0)cout << i+1 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3584
fun main(args: Array<String>) {
    val (A, B, M) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    val b = readLine()!!.split(" ").map { it.toInt() }
    println(Math.min(a.min()!! + b.min()!!, (1..M).map {
        val (x, y, c) = readLine()!!.split(" ").map { it.toInt() }
        a[x - 1] + b[y - 1] - c
    }.min()!!))
}

Measured memory_bytes: 103896
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
count=0
if N==1 and N==2:
    print(0)
else:
    for i in range(N-2):
        for j in range(i+1,N-1):
            if L[i]!=L[j]:
                for k in range(j+1,N):
                    if L[j]<L[k] and L[k]<L[i]+L[j]:
                        count+=1
    print(count)

Measured memory_bytes: 9096
n, m, r = map(int,input().split())
R = list(map(int,input().split()))
A = [list(map(int,input().split())) for i in range(m)]

M = [[float("inf")] * (n+1) for i in range(n+1)]

for i in range(1, n+1):
    M[i][i] = 0
for i in range(m):
    M[A[i][0]][A[i][1]] = A[i][2]
    M[A[i][1]][A[i][0]] = A[i][2]

# for k in range(1, n+1):
#     for i in range(1, n+1):
#         for j in range(1, n+1):
#             M[i][j] = min(M[i][j], M[i][k] + M[k][j])

from scipy.sparse.csgraph import floyd_warshall
M = floyd_warshall(M)

import itertools
R1 = list(itertools.permutations(R))

ans = float("inf")
for i in range(len(R1)):
    ans1 = 0
    for j in range(r-1):
        ans1 += M[R1[i][j]][R1[i][j+1]]
    ans = min(ans, ans1)

print(int(ans))


Measured memory_bytes: 25772
#include<iostream>
#include <string>
#include<algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long lint;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep0(i,n) rep(i,0,n)

int main(void){
	ios::sync_with_stdio(false);
	int a, b;
	cin >> a >> b;
	if (a < b) {
		cout << "0";
	}
	else {
		cout << "10";
	}
	return 0;
}

//sort Ｎ個の配列a
//sort(a, a + N); //昇順
//sort(a, a + N, greater<int>()); //降順

////最大公約数（ユークリッドの互除法利用）
//int gcd(int a, int b) {
//	if (a == 0) return b;
//	if (b == 0) return a;
//	int m = max(a, b);
//	int n = min(a, b);
//	if (m%n == 0) return n;
//	else return gcd(n, m%n);
//
//}
//
////最小公倍数
//int lca(int a, int b) {
//	if (a == 0) return 0;
//	if (b == 0) return 0;
//	return a * b / gcm(a, b);
//}
//
////n^k(整数)
//int pow_int(int n, int k) {
//	int re = 1;
//	for (int i = 0; i < k; i++) re *= n;
//	return re;
//}


Measured memory_bytes: 256
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln(ch):
    _res = list(map(int,str(input()).split(ch)))
    return _res

def pend(x,f,n):
    b = [0 for i in range(0,n+1)]
    for i in range(1,n+1):
        tmp =  f[i] - f[i-1]
        if tmp % n != 0:
            return 'NO'
        b[i] = -(tmp // n)
    b[0] = 0
    k = 0
    l = 0
    for i in range(0,n):
        b[i] = b[i-1] + b[i]
        k = k + n - i
        l = l + (n - i) * b[i]
    x = x - l
    if x < 0 : return 'NO'
    if x % k > 0: return 'NO'
    a[0] = x // k
    for i in range(1,n):
        a[i] = a[0] + b[i]
    for i in range(0,n):
        if(a[i] < 0):
            return 'NO'
    return 'YES'

n = int(input())
a = readln(' ')
f = [0 for i in range(0,n)]
f[0] = a[0]-a[n-1]
for i in range(1,n):
    f[i] = a[i] - a[i-1]

f.append(f[0])
print(pend(a[n-1],f,n))
# an-1 = nx1+n-1x2


Measured memory_bytes: 14428
#include<stdio.h>

#define N 100

int main(){

  int i,j,n,minj,tmp,count=0;
  int arr[N];

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

  for(i=0;i<=n-1;i++){
    minj = i;
    for(j=i;j<=n-1;j++){
      if(arr[j]<arr[minj]){
	minj = j;
      }}
    if(arr[i]!=arr[minj]){	  
      tmp = arr[i];
      arr[i] = arr[minj];
      arr[minj] = tmp;
      count++;
    }}
  
  for(i=0;i<n-1;i++){
    printf("%d ",arr[i]);
  }

  printf("%d\n",arr[n-1]);

  printf("%d\n",count);

  return 0;
}

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

int MSB(bitset<40> b){
  int res = -1;
  rep(i, 40) if(b[i] == 1) res = i;
  return res;
}

Int toI(bitset<40> b){
  Int k = 1, res = 0;
  rep(j, 40){
    if(b[j] == 1) res += k; k *= 2;
  }
  return res;
}

int main(){
  Int N, K;
  vector<bitset<40>> A(100010);
  vector<int> cnt(40, 0);

  cin >> N >> K;

  rep(i, N){
    Int a; cin >> a;
    A[i] = bitset<40>(a);

    rep(j, 40){ if(A[i][j] == 1) cnt[j]++;}
  }

  bitset<40> X; int msb = MSB(K);
  for(int i=39; i>=0; i--){
    if(cnt[i] <= N/2 && i <= msb) X[i] = 1;
    else X[i] = 0;

    if(toI(X) > K) X[i] = 0;
  }

  Int ans = 0;
  rep(i, N){
    bitset<40> tmp = X ^ A[i];
    ans += toI(tmp);
  }

  cout << ans << endl;
}




Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define fi first
#define se second
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};

signed main(){
  int n;
  cin>>n;
  if(!n){
    cout<<0<<endl;
    return 0;
  }
  vector<P>v1,v2;
  set<int>a1;
  map<int,int>a2;
  int x=-2;
  for(int i=0;i<32;i++){
    int y=1;
    r(j,i)y*=x;
    if(y<0)v1.push_back(P(y,1<<i));
    else v2.push_back(P(y,1<<i));
  }
  r(i,(1<<v1.size())){
    int k=0,l=0;
    r(j,v1.size())if(i&(1<<j))k+=v1[j].fi,l+=v1[j].se;
    a1.insert(k);
    a2[k]=l;
  }
  r(i,(1<<v2.size())){
    int k=0,l=0;
    r(j,v2.size())if(i&(1<<j))k+=v2[j].fi,l+=v2[j].se;
    x=n-k;
    if(a1.count(x)){
      int p=l+a2[x];
      string s;
      r(j,32)
        if(p&(1<<j))s+='1';
        else s+='0';
      reverse(s.begin(),s.end());
      while(s[0]=='0')s.erase(s.begin());
      cout<<s<<endl;
      return 0;
    }
  }
}

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

int main(){
    int X, A, B;
    cin >> X >> A >> B;
    if(A>=B){
        cout << "delicious" << endl;
    }else if(B <= A+X){
        cout << "safe" << endl;
    }else{
        cout << "dangerous" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5500+5,M=1500,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define il inline
int sx,sy,ex,ey;
int main(){
	cin>>sx>>sy>>ex>>ey;
	for(int i=0;i<ey-sy;i++)	putchar('U');
	for(int i=0;i<ex-sx;i++) putchar('R');
	for(int i=0;i<ey-sy;i++)	putchar('D');
	for(int i=0;i<ex-sx;i++) putchar('L');
	putchar('L');
	for(int i=0;i<=ey-sy;i++)	putchar('U');
	for(int i=0;i<=ex-sx;i++) putchar('R');
	putchar('D');
	putchar('R');
	for(int i=0;i<=ey-sy;i++)	putchar('D');
	for(int i=0;i<=ex-sx;i++) putchar('L');
	putchar('U');
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
double x[100][100], dp[101][100]; int n, m;
int main() {
	while (true) {
		cin >> n >> m; if (n == 0 && m == 0) { break; }m--;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++)cin >> x[i][j];
		}
		for (int i = 0; i < 101; i++) {
			for (int j = 0; j < 100; j++)dp[i][j] = 0.0;
		}
		for (int i = 0; i < 100; i++)dp[0][i] = 1.0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] * x[j][k]);
				}
			}
		}
		double maxn = 0;
		for (int i = 0; i < 100; i++)maxn = max(maxn, dp[m][i]);
		printf("%.2lf\n", maxn);
	}
	return 0;
}

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

int main(){

	double r, f, g;

	cin >> r;

	f = 3.141592653589*r*r;
	g = 3.141592653589 * 2 * r;

	cout <<fixed<< setprecision(6)<<f << " " << g << endl;

	return 0;
}


Measured memory_bytes: 3240
#include<stdio.h>

int main(void){
    int a,b;
    while(scanf("%d%d",&a,&b) != EOF){
    int cnt=1;
    int sum=a+b;
    while(sum>=10){
        sum /= 10;
        cnt++;
    }
    printf("%d\n",cnt);
    }
    return 0;
}


Measured memory_bytes: 2032
#define _GLIBCXX_DEBUG
// header {{{
#include <bits/stdc++.h>
using namespace std;
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
#define ASSERT(expr...) assert((expr))
using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = __float80;
// }}}
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
// util {{{
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}
// }}}

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;
// }}}

//--------------------------------------------------------------------

signed main() {
    int n;
    cin>>n;

    if(n%2==0){
        cout<<0.5<<endl;

    } else {
        cout<<(n+1.0)/(2*n)<<endl;
    }

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

Measured memory_bytes: 256
// Create your own template by modifying this file!
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cassert>
#include <deque>
#include <stack>
#include <functional>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x;  }
void _R(int &x) { scanf("%d", &x);  }
void _R(int64_t &x) { scanf("%lld", &x);  }
void _R(double &x) { scanf("%lf", &x);  }
void _R(char &x) { scanf(" %c", &x);  }
void _R(char *x) { scanf("%s", x);  }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...);  }
template<class T> void _W(const T &x) { cout << x;  }
void _W(const int &x) { printf("%d", x);  }
void _W(const int64_t &x) { printf("%lld", x);  }
void _W(const double &x) { printf("%.16f", x);  }
void _W(const char &x) { putchar(x);  }
void _W(const char *x) { printf("%s", x);  }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' ');  }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...);  }
#ifdef DEBUG
 #define debug(...) {printf("[DEBUG] ");W(__VA_ARGS__);}
#else
 #define debug(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1<<20;
template<class T> void MIN(T& a, const T& b) { a = min(a, b); }
template<class T> void MAX(T& a, const T& b) { a = max(a, b); }

#include <atcoder/all>
#define MULTITEST 0

using namespace atcoder;

void solve() {
    static char buf[500'001];
    R(buf);
    string s = buf;
    auto sa = suffix_array(s);
    auto lcp = lcp_array(s, sa);

    int N = SZ(s);
    LL ans = N - sa[0];
    REPP(i, 1, N) {
        ans += N - sa[i] - lcp[i-1];
    }
    W(ans);
}

int main() {
#if MULTITEST    
    CASET{
        solve();
    }
#else
    solve();
#endif
    return 0;
}


Measured memory_bytes: 15720
N = int(input())
A = list(map(int,input().split()))


counter = dict()
for i in A:
    if i not in counter.keys():
        counter[i] = 1
    else:
        counter[i]+=1

for i in range(1,N+1):
    if i not in counter.keys():
        print(0)
    else:
        print(counter[i])



Measured memory_bytes: 33584
N = int(input())
y = 0

for i in range(1,N+1):
  x = 0
  if i%2 == 0 or i == 1:
    remainder = 0
  else:
    remainder = 1
  while i%2 == 0:
    x += 1
    i /= 2
  if x >= y:
    y = x
    z = 2**x+remainder
    
print(z)
  

Measured memory_bytes: 2940
(defun ans (s)
  (do ((n 0 (1+ n)) (result "Good"))
      ((<= (1- (length s)) n) result)
        (if (equal (aref s n) (aref s (1+ n)))
          (setq result "Bad")
            )
    )
  )

(format t "~a~%" (ans (read-line)))

Measured memory_bytes: 3432
#include <iostream>
#include <vector>

bool is_exist[2019] = {0};

int main()
{
    int piece_count = 0;
    std::cin >> piece_count;
    
    std::vector<int> pieces;
    pieces.reserve(piece_count);
    
    for(int i = 0 ; i < piece_count; ++i)
    {
        int value = 0;
        std::cin >> value;
        pieces.emplace_back(value - 1);
    }
    
    for(int piece : pieces)
    {
        is_exist[piece] = true;
    }
    
    int command_count = 0;
    std::cin >> command_count;
    
    std::vector<int> commands;
    commands.reserve(command_count);
    
    for(int i = 0; i < command_count; ++i)
    {
        int value = 0;
        std::cin >> value;
        commands.emplace_back(value - 1);
    }
    
    for(int command : commands)
    {
        if(pieces[command] + 1 < 2019 && is_exist[pieces[command] + 1] == false)
        {
            is_exist[pieces[command]] = false;
            is_exist[pieces[command] + 1] = true;
            ++(pieces[command]);
        }
    }
    
    for(int piece : pieces)
    {
        std::cout << piece + 1 << std::endl;
    }
    
    return 0;
}


Measured memory_bytes: 3096
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let x: usize = read_as_vec()[0];

    let mut dp = vec![false;x+1];
    dp[0] = true;

    let choices = vec![100, 101, 102, 103, 104, 105];
    for i in 100..x+1{
        for &choice in &choices{
            if dp[i - choice]{
                dp[i] = true;
                break;
            }
        }
    }

    if dp[x]{
        println!("1");
    }else{
        println!("0");
    }

}


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

int a[100001][3],dp[100001][3];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i][0];
cin>>a[i][1];
cin>>a[i][2];
}
for(int i=1;i<=n;i++){
dp[i][0]=a[i][0]+max(dp[i-1][1],dp[i-1][2]);
dp[i][1]=a[i][1]+max(dp[i-1][2],dp[i-1][0]);
dp[i][2]=a[i][2]+max(dp[i-1][0],dp[i-1][1]);
}
cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}


Measured memory_bytes: 2560
main = do
  li <- getLine
  let n = read li
  li <- getLine
  let ps = map read $ words li
  li <- getLine
  let qs = map read $ words li
  let ans = compute n ps qs
  print ans

{-
1..nの順列で、最小のものは 1 2 .. n 最大のものは n n-1 ... 2 1
下から数えて、iケタめが増えるということは、i-1桁ぶんの順列を使い果たすということなので、(i-1)!増えるということ。
i-1種類の記号のうちの何番目なのかは、上で使ってしまった記号を除いた残りで数える必要がある。
-}
compute :: Int -> [Int] -> [Int] -> Int
compute n ps qs = abs (p-q)
  where
    p = nth ps [1..n]
    q = nth qs [1..n]

nth [] [] = 0
nth (p:ps) ns = n * product [1..length ns-1] + nth ps ns1
  where
    (n,ns1) = find p ns

find p (n:ns)
  | p == n = (0,ns)
  | True   = let (k,ns1) = find p ns in (succ k,n:ns1)


Measured memory_bytes: 508
//Mahir Ratanpara (DA-IICT)
#include<bits/stdc++.h>
using namespace std;
#define Ff(i,a,n) for(i=a;i<n;i++)
#define Fr(i,a,n) for(i=a;i>n;i--)
#define ll long long
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
typedef pair<ll, ll>	pa;
typedef vector<ll>		vc;
typedef vector<pa>		vp;
typedef vector<vc>		vvc;
int mpow(int base, int exp); 
void ipgraph(ll n,ll m);
void dfs(int u, int par);
const int mod = 1000000007;
const int N = 3e5, M = N;
//=======================

vc g[N];

int main() {
    FAST;
    ll t, i, j, k, p, q, r, x, y, u, v, n, m;
	cin>>n;
	vc a(n);
	Ff(i,0,n)
	cin>>a[i];

	ll maxi=0;
	ll ans=0;
	Ff(i,0,n)
	{
		maxi=max(a[i],maxi);
		ans+=abs(maxi-a[i]);
	}
	cout<<ans;
    return 0;
}

int mpow(int base, int exp) {
  base %= mod;
  int result = 1;
  while (exp > 0) {
    if (exp & 1) result = ((ll)result * base) % mod;
    base = ((ll)base * base) % mod;
    exp >>= 1;
  }
  return result;
}

void ipgraph(ll n, ll m){
	int i, u, v;
	while(m--){
		cin>>u>>v;
		g[u-1].pb(v-1);
		g[v-1].pb(u-1);
	}
}

void dfs(int u, int par){
	for(int v:g[u]){
		if (v == par) continue;
		dfs(v, u);
	}
}

Measured memory_bytes: 11760
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int a,b,c;
    int cnt = 0;
    cin >> a >> b >> c;

    if (a == b) cnt++;
    if (b == c) cnt++;
    if (a == c) cnt++;

    if (cnt == 1) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
'''
Implement and make use of priority queue using heapq module.
Using priority queue(heapq) is fast because all of insertion, deletion, and popping is done by order O(log n).

heapq documentation: https://docs.python.org/ja/3/library/heapq.html
'''

import heapq
# heapq a.k.a priority queue

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)


# Initialize heap.
# Values are given as negative integers, because python heapq is a min-heap and pops minimum value in it.
# The form of values are tuple of (-value, indices of A,B,C).
# Indices are used to push new candidates to the heap after pop.
candidates = [] # name of the heap
heapq.heappush(candidates, (-(A[0]+B[0]+C[0]), 0,0,0))

# Initialize a set to store indices of A, B, and C so that there won't be any duplicates.
used = {(0,0,0)}

for _ in range(K):

    s, i, j, k = heapq.heappop(candidates)
    print(-s)

    if i < X-1 and (i+1,j,k) not in used:
        heapq.heappush(candidates, (-(A[i+1]+B[j]+C[k]), i+1,j,k))
        used.add((i+1,j,k))

    if j < Y-1 and (i,j+1,k) not in used:
            heapq.heappush(candidates, (-(A[i]+B[j+1]+C[k]), i,j+1,k))
            used.add((i,j+1,k))

    if k < Z-1 and (i,j,k+1) not in used:
            heapq.heappush(candidates, (-(A[i]+B[j]+C[k+1]), i,j,k+1))
            used.add((i,j,k+1))


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long  
#define pb push_back

		   //       |----|       /\      |    |   -----   |
		   //       |   /       /  \     |    |     |     |
		   //       |--/       /----\    |----|     |     |
		   //       |   \     /      \   |    |     |     |
		   //       |    \   /        \  |    |   -----   -------

int32_t main()
{
	IOS;
	int n,k;
	cin>>n>>k;
	cout<<n-k+1;
}

Measured memory_bytes: 256
from fractions import gcd
a, b = [int(i) for i in input().split()]
c = gcd(a, b)

def p(x):
    a=[]
    i=2
    while True:
        if x % i == 0:
            j=0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x,1))
    return a

print(len(p(c))+1)

Measured memory_bytes: 64108
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}



vector<ll>v[200];
int main()
{

    fastread();

    ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

    bool flag=false;

    string str,ptr;


    cin>>str>>ptr;

    n=str.size();

    m=ptr.size();

    for(i=0; i<n; i++)
    {
        v[str[i]].eb(i);
    }

    for(i=0; i<m; i++)
    {
        if(v[ptr[i]].size()==0)break;
    }

    if(i==m)
    {
        ans=0;

        ll last=-1;

        for(auto x : ptr)
        {
            auto xp=upper_bound(vll(v[x]),last);

            if(xp==v[x].end())
            {
                last=-1;

               ans++;

                auto xp=upper_bound(vll(v[x]),last);

                 last=xp-v[x].begin();

                last=v[x][last];


            }
            else
            {
                last=xp-v[x].begin();

                last=v[x][last];
            }



        }

        ans*=n;

        ans+=last+1;

        cout<<ans<<endl;


    }
    else
        cout<<-1<<endl;













}



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

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

typedef long long ll;
typedef array<int, 3> tri;
typedef long double ld;

template <class T> istream& operator>>(istream& I, vector<T>& v) {for (T &e: v) I >> e; return I;}
template <class T> ostream& operator<<(ostream &O, const vector<T>& v) {for (const T &e: v) O << e << ' '; return O;}



void _main() {
        int n, k; cin >> n >> k;
        string s; cin >> s;
        s[k - 1] = tolower(s[k - 1]);
        cout << s;
}



signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//        freopen("input.txt", "r", stdin);
        int _t = 1;
//        cin >> _t;
        while (_t--) _main();
        return 0;
}


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

#define MAX 1000100

int n;
int f[MAX];
int g[MAX];

int main( int argc, char *argv[] )
{
    int a;

    scanf( "%d", &n );
    for( int i=0; i<n; i++ ) {
        scanf( "%d", &a );
        if( f[a] ) g[a] = 1;
        f[a] = 1;
    }

    for( int i=1; i<MAX; i++ ) {
        if( f[i] == 0 ) continue;
        int k = i * 2;
        while( k < MAX ) {
            f[k] = 0;
            k += i;
        }
    }

    int count = 0;
    for( int i=1; i<MAX; i++ )
        if( f[i] && !g[i] ) count ++;

    printf( "%d\n", count );
}


Measured memory_bytes: 9536
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<ll, P> E;
#define MOD (1000000007ll)
#define l_ength size
#define EPS (1e-10)

int ds(int x){
	int ret = 0;
	while(x){
		ret += x%10;
		x /= 10;
	}
	return ret;
}

int main(void){
	int n,i,ans=INF;
	cin >> n;
	for(i=1; i<n; ++i){
		ans = min(ans,ds(i)+ds(n-i));
	}
	cout << ans << endl;
	return 0;
}


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

int main() {
   string S, T;
   cin >> S >> T;
    int sum = 0;
   for(int i = 0; i < S.size(); i++) {
       if(S[i] != T[i]) sum++;
   }

   cout << sum;
   return 0;
}

Measured memory_bytes: 3912
#import <stdio.h>
typedef long long INT;
int main(){
    INT N,M;
    scanf("%lld %lld",&N,&M);
    INT result = 0;
    if (M<=2*N) {
        result = M/2;
    } else {
        result = N;
        M -= 2*N;
        result += M/4;
    }
    printf("%lld", result);
}


Measured memory_bytes: 2164
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cstring>
#include <queue>


#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define eREP(i, n) for(int (i) = 0; (i) <= (n); ++(i))
#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; ++(i))
#define ALL(TheArray) TheArray.begin(), TheArray.end()

template <class T> inline T& chmax(T& a, T b){return (a < b) ? a = b : a;}
template <class T> inline T& chmin(T& a, T b){return (a > b) ? a = b : a;}

using lli = long long int;
using pli = std::pair<lli, int>;


int main(void){
    int a, b, c; std::cin >> a >> b >> c;
    int x = 0;
    while((x+1) * a <= b) x++;
    if(x > c) x = c;
    std::cout << x << '\n';
    return 0;
}

Measured memory_bytes: 256
open System

[<AutoOpen>]
module Cin =
    let read f = stdin.ReadLine() |> f
    let reada f = stdin.ReadLine().Split() |> Array.map f

[<EntryPoint>]
let main _ =
    let a = read int
    let b = read int
    let c = read int
    let x = read int
    seq {
        for i in 0..a do
            for j in 0..b do
                for k in 0..c do
                    yield i * 500 + j * 100 + k * 50
    }
    |> Seq.sumBy (fun y -> if y = x then 1 else 0)
    |> printfn "%d"
    0


Measured memory_bytes: 14044
n = gets.to_i
hs = gets.split.map(&:to_i)

ans = 'Yes'
last = hs[0]

hs.each do |h|
  if last <= h
    last = h
  elsif last == h + 1
    last = h + 1
  else
    ans = 'No'
    break
  end
end

puts ans


Measured memory_bytes: 10116