akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int H, W, K;
string S[10];
//---------------------------------------------------------------------------------------------------
int cnt[11];
int solve(vector<int> grp) {
	int res = 0;
	int x = 0;

	while (x < W) {
		rep(c, 0, 11) cnt[c] = 0;

		int nxt = x;
		rep(xx, x, W) {
			bool ng = false;
			rep(y, 0, H) if (S[y][xx] == '1') {
				cnt[grp[y]]++;
				if (K < cnt[grp[y]]) ng = true;
			}
			if (ng) break;
			chmax(nxt, xx + 1);
		}

		if (nxt == x) return inf;
		x = nxt;

		res++;
	}

	return res - 1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> H >> W >> K;
	rep(y, 0, H) cin >> S[y];

	int ans = inf;
	rep(div, 0, 1 << (H - 1)) {
		vector<int> grp;
		int g = 1, cnt = 0;
		rep(i, 0, H - 1) {
			grp.push_back(g);
			if (div & (1 << i)) g++, cnt++;
		}
		grp.push_back(g);

		chmin(ans, solve(grp) + cnt);
	}
	cout << ans << endl;
}







Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };

struct MyStruct
{
	int list[13];
};


signed main() {
	int i, j, n, sum = 0, cnt = 0;
	string s, s1, s2;
	bool flag = false;
	vector<int>list(26,0);



	cin >> s;

	for (i = 0; i < s.length(); i++) {
		if (s[i] >= 'A' && s[i] <= 'Z') s[i] += ('a' - 'A');
	}


	//cin.clear();
	//cin.ignore(999999999, '\n');


	//while ( getline(cin,s1) )
	while ( cin >> s1 )
	{

		if (s1 == "END_OF_TEXT") break;
		//cin.clear();
		//cin.ignore(99999999999, '\n');
		//cin.ignore(INT_MAX, '\n');

		//cout << "aaa" << endl;
		
		for (i = 0; i < s1.length(); i++) {
			if (s1[i] >= 'A' && s1[i] <= 'Z') s1[i] += ('a' - 'A');
		}

		int num = 0;

		//while (s1.find(s,num) != string::npos)
		if( s1 == s )
		{
			//cout << "bbb" << endl;

			//num = s1.find(s, num) + s.length();
			//num--;
			cnt++;
		}

		//cout << "ccc" << endl;


	}

	cout << cnt << endl;







	getchar();
	getchar();
	return 0;
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define se second
#define fi first
#define ll long long
#define INF INT_MAX
#define mod 1000000007
#define chutiyaap ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
ll pw(ll a, ll b) {
    if (b == 0) return 1;
    ll t = pw(a, b / 2);
    if (b % 2 == 0) return (t * t)%mod;
    else return ((t * t)%mod * a)%mod;
}
int main()
{
	ll n;cin>>n;
	ll res=0;
	for(ll i=1;i<=n;i++)
	{
		ll x=i,terms=n/i,common=i;
		res+=terms*(2*i+(terms-1)*i)/2;
	}
	cout<<res;
}


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

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)

#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())

#define ll long long
#define ALL(a)  (a).begin(),(a).end()

#define pb(a) push_back(a)

int now,n,k;


int main(){
  int ans=0;
  string s;cin>>s;
  int aa=0;
  int bb=0;
  aa=(s[1]-48)+(s[0]-48)*10;
  bb=(s[3]-48)+(s[2]-48)*10;
  //まず01～12の範囲内か確認
  int flga=0;
  int flgb=0;
  if ((aa>=1)&(aa<=12))flga=1;
  if ((bb>=1)&(bb<=12))flgb=1;
  if ((flga==1)&(flgb==1)){//どちらもありうる
    cout<<"AMBIGUOUS"<<endl;
    return 0;
  }
  
  if ((flga==0)&(flgb==1)){//bがMM
    cout<<"YYMM"<<endl;
    return 0;
  }
  
  if ((flga==1)&(flgb==0)){//aがMM
    cout<<"MMYY"<<endl;
    return 0;
  }
  
  if ((flga==0)&(flgb==0)){//aがMM
    cout<<"NA"<<endl;
    return 0;
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < n; ++i)
typedef long long ll;
using namespace std;
const int INF = 1e9;
const int MOD = INF + 7;

struct mint {
    ll x;
    mint(ll x = 0) : x((x % MOD + MOD) % MOD) {}
    mint operator-() const { return mint(-x); }
    mint &operator+=(const mint a) {
        if ((x += a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    mint &operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD)
            x -= MOD;
        return *this;
    }
    mint &operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }

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

int main() {
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    mint ans = 0;
    rep(i, n) {
        rep(j, n) {
            if (i == j)
                continue;
            if (a[i] > a[j]) {
                ans += k * (k - 1) / 2;
                if (i < j)
                    ans += k;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a.at(i);
    ll money = 1000;
    rep(i,n-1){
        ll b = a.at(i);
        ll s = a.at(i+1);
        if(b < s){
            ll t = money / a.at(i);
            money %= a.at(i);
            money += s * t;
        }
    }
    cout << money << endl;
    
}

Measured memory_bytes: 3628
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll n, m, q, a[50] = {}, b[50] = {}, c[50] = {}, d[50] = {}, ans = 0;

void dfs(ll cur, vector<ll> A, ll num) {
	if (cur < n) {
		A.pub(num);
		for (int i = A[cur]; i <= m; i++)dfs(cur + 1, A, i);
	}
	else {
		ll box = 0;
		rep(i, q) {
			if (A[b[i]] - A[a[i]] == c[i])box += d[i];
		}
		ans = max(ans, box);
	}
}

int main() {
	cin >> n >> m >> q;
	rep(i, q) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		a[i]--;
		b[i]--;
	}
	vector<ll> A;
	rep(i, m)dfs(0, A, i + 1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3600
k, n = (int(each) for each in input().split(' '))

a = [int(each) for each in input().split(' ')]
distance = []
for i in range(len(a)-1):
    distance.append(a[i+1]-a[i])

distance.append(a[0] + (k-a[-1]))

print(k - max(distance))

Measured memory_bytes: 26444
s = input()
t = input()
a = {}
b=set()
for i, j in zip(s, t):
    if i in a:
        if a[i] != j:
            print("No")
            exit()
    else:
        if j in b:
            print("No")
            exit()
        b.add(j)
        a[i]=j
print("Yes")


Measured memory_bytes: 3632
from collections import Counter
N, M = map(int, input().split())
node = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    node.append(a)
    node.append(b)
C = Counter(node)
ret = 'YES'
for c in C.values():
    if c % 2 == 1:
        ret = 'NO'
        break
print(ret)

Measured memory_bytes: 15992
using System;
class Program
{
	static void Main(string[] args)
	{
      	string[] input = Console.ReadLine().Split(' ');
        double n = double.Parse(input[0]);
      	double d = double.Parse(input[1]);
      	double ans = Math.Ceiling(n / (2 * d + 1));
		Console.WriteLine(ans);	
	}
}

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

int r;
int D;
int x2000;

int main()
{
    cin >> r >> D >> x2000;

    int current = x2000;
    for (int i = 0; i < 10; ++i) {
        current = r * current - D;
        cout << current << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
#include <boost/range/irange.hpp>
using namespace std;
using boost::irange;

// 定義
typedef long long           ll;
typedef pair<ll, ll>        P;
#define ALL(x)              (x).begin(),(x).end()
#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)
const ll                    INF = 2e9;
const ll                    INF_LL = 1LL<<60;
const ll                    MOD = 1e9 + 7;
namespace {
	ll Ceil(ll val, ll div)   { return (val + div - 1) / div; }
	ll CeilN(ll val, ll div)  { return Ceil(val, div) * div; }
	ll FloorN(ll x, ll n)     { return (x - x % n); }
	bool IsOdd(ll x)          { return ((x & 1) == 1); }
	bool IsEven(ll x)         { return ((x & 1) == 0); }
	template<class T> bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
	template<class T> bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
};

/* 約数の列挙 */
vector<ll> divisorExec(ll n)
{
	vector<ll> res;
	for (ll i = 1; i <= sqrt(n); i++){
		if ((n % i) == 0) {
			res.push_back(i);
			if ((i * i) != n) {
				res.push_back(n / i);
			}
		}
	}
	sort(res.begin(), res.end());
	return res;
}

// 処理
void Solve()
{
	ll N;
	cin >> N;

	vector<P> bc;
	REPN(b, 1, 3501) {
		REPN(c, 1, 3501) {
			ll tmp1 = N * b * c;
			ll tmp2 = 4 * b * c - N * (b + c);
			if (0 < tmp2) {
				if (tmp1 % tmp2 == 0) {
					cout << tmp1 / tmp2 << " " << b << " " << c << endl;
					return;
				}
			}
		}
	}
}

// メイン
int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Solve();
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using ll = long long int;

constexpr int MAX_N = (int)1e5 * 2, INF = (int)1e9;

int n;
ll sumx[MAX_N], sumy[MAX_N];

int main() {

	std::cin >> n;

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

	for (int i = 1; i < n; ++i)
		sumx[i] += sumx[i - 1];

	for (int i = n - 2; i >= 0; --i)
		sumy[i] += sumy[i + 1];

	ll ans = INF * 2;

	for (int i = 0; i < n - 1; ++i)
		ans = std::min(ans, llabs(sumx[i] - sumy[i + 1]));

	std::cout << ans << std::endl;

	system("pause");
	return 0;
}

Measured memory_bytes: 3576
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

ll cal(string &s){
    ll cnt = 0;
    for(ll i = 1; i < s.size(); i++){
        if(s[i - 1] == s[i]){
            s[i] = '*';
            cnt++;
        }
    }
    return cnt;
}

int main(){

    string s;
    cin >> s;
    ll K;
    cin >> K;
    if(s.size() == 1){
        cout << K / 2 << endl;
        return 0;
    }

    string t1 = s, t2 = s, t3 = s;
    ll a1 = 0, a2 = 0, a3 = 0;
    a1 += cal(t1);
    if(t1[t1.size() - 1] == t2[0]){
        t2[0] = '*';
        a2++;
    }
    a2 += cal(t2);
    if(t2[t2.size() - 1] == t3[0]){
        t3[0] = '*';
        a3++;
    }
    a3 += cal(t3);
    // cout << t1 << " : " << a1 << endl;
    // cout << t2 << " : " << a2 << endl;
    // cout << t3 << " : " << a3 << endl;
    
    if(K == 2){
        cout << a1 + a2 << endl;
        return 0;
    }
    if(K == 3){
        cout << a1 + a2 + a3 << endl;
        return 0;
    }
    if(t1 == t2 && t2 == t3){
        cout << a1 * K << endl;
        return 0;
    }
    if(t1 != t2 && t2 == t3){
        cout << a1 + a2 * (K - 1)<< endl;
        return 0;
    }
    if(t1 != t2 && t2 != t3){
        ll A = (K + 1) / 2;
        ll B = K / 2;
        cout << a1 * A + a2 * B << endl;
        return 0;
    }


    return 1;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char *argv[])
{
  for(;;) {
    int N, M;
    cin >> N >> M;
    if(N == 0) break;
    int r;
    cin >> r;
    vector<vector<int>> log;
    for(int i = 0; i < r; i++) {
      int t, n, m, s;
      cin >> t >> n >> m >> s;
      log.push_back({t, n, m, s});
    }
    int q;
    cin >> q;
    
    for(int i = 0; i < q; i++) {
      int ts, te, m;
      cin >> ts >> te >> m;
      int ans = 0, t = 0, in = 0;
      for(vector<int> v : log) {
        if(v[2] == m) {
          if(v[3] == 1) {
            in++;
            if(in == 1) t = v[0];
          } else {
            in--;
            if(in == 0) {
              int tt = v[0];
              if(t < ts) t = ts;
              if(tt > te) tt = te;
              ans += max(0, tt - t);
            }
          }
        }
      }
      cout << ans << endl;
    }
  }
  return 0;
}

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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if((abs(a-c)<=d) || (abs(a-b)<=d && abs(b-c)<=d)) cout << "Yes" << endl;
  else cout << "No" << endl;   
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<map>
using namespace std;
 
int main()
{
    string str;
    while(cin >> str)
    {
        int s = 0;
        for(int i = 0; i < str.size(); i++)
        {
            char c = str[i];
            char next = (i==str.size()-1 ? 0 : str[i+1]);
            switch(c)
            {
            case 'I': 
                if(next == 'V') s += 4, i++;
                else if(next == 'X') s += 9, i++;
                else s+=1;
                break;
            case 'V':
                s += 5;
                break;
            case 'X':
                if(next == 'L') s += 40, i++;
                else if(next== 'C') s += 90, i++;
                else s+=10;
                break;
            case 'L':
                s += 50;
                break;
            case 'C':
                if(next == 'D') s += 400, i++;
                else if(next =='M') s += 900, i++;
                else s += 100;
                break;
            case 'D':
                s += 500;
                break;
            case 'M':
                s += 1000;
                break;
            }
        }
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 1180
import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()


Measured memory_bytes: 84792
#include <stdio.h>

int main (){
	
	int i;
	int a, b;
	scanf("%d %d", &a, &b);
	char str [a + b +1];
	scanf("%s", &str);

	int ans = 0;
	for(i = 0; i<a+b+1; i++){
		if (i != a) 
		{if (str[i]>='0' && str[i]<='9'){
			ans++;
		}
	}else if (str[i] == '-'){
		ans++;
	}
	}
	if (ans == a + b + 1){
		printf("Yes");
	} else {
		printf("No");
	}
	
	return 0;
}

Measured memory_bytes: 1672
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int main(int argc, char *argv[]){
        char W[4];
        scanf("%s",W);
        int i;
        int R=0;
        for(i = 0; i < 3; i++){
                if(W[i] == 'R'){
                        R++;
                }
                if(W[1] == 'S'){
                        if(W[0] == 'R' || W[2] == 'R'){
                                R = 1;
                        }
                }
        }
        printf("%d\n", R);
        return 0;
}

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

int main()
{
    int r, c, i, I, x, y = 0;
    int rc[101][101] = {{0}, {0}};
    scanf("%d%d", &r, &c);
    for(i = 0 ; i < r ; i++)
    {
        x = 0;
        while(scanf("%d", &rc[i][x]))
        {
            char c = getchar();
            if(c == '\n')
            {
                break;
            }
            x++;
        }
    }
    for(i = 0 ; i < c ; i++)
    {
        for(I = 0 ; I < r ; I++)
        {
            rc[r][i] += rc[I][i];
        }
    }
    for(i = 0 ; i <= r ; i++)
    {
        for(I = 0 ; I < c ; I++)
        {
            rc[i][c] += rc[i][I];
        }
    }
    for(i = 0 ; i <= r ; i++)
    {
        for(I = 0 ; I <= c ; I++)
        {
            printf("%d", rc[i][I]);
            if(I < c) printf(" ");
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2092
#include<bits/stdc++.h>
using namespace std;
 int sum (int a){
   if(a == 0){
     return 0;
   }
   int s = sum(a-1);
   return s + a;
 }

int main(){
  int x,y;
  cin >>x >> y;
  int hig = sum(abs(x-y));
  cout << hig - y << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (n); ++i)
 
typedef long long ll;
typedef pair<int, int> P;
 
const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;
 
int dp[105][5][2];
const int ls = 0, eq = 1;
int main(){
    string IN;
    int K;
    cin >> IN >> K;
 
    vector<int> N;
    for (char &c : IN) N.push_back(c - '0');
 
    int n = N.size();
 
    dp[0][0][eq] = 1;
 
    rep(i, n) {
        int num = N[i];
        rep(j, K+1) {
            if (num > 0) {
                dp[i+1][j][ls] += dp[i][j][ls] + dp[i][j][eq];
                dp[i+1][j+1][ls] += dp[i][j][ls] * 9 + dp[i][j][eq] * (num-1);
                dp[i+1][j+1][eq] += dp[i][j][eq];
            } else {
                dp[i+1][j][ls] += dp[i][j][ls];
                dp[i+1][j][eq] += dp[i][j][eq];
                dp[i+1][j+1][ls] += dp[i][j][ls] * 9;
            }
        }
    }
 
    cout << dp[n][K][ls] + dp[n][K][eq] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c,d,e,count=0,flag=0;
    cin>>a>>b>>c>>d>>e;
    while (a<b) {
        if (a<0) {
            count+=c;
            a++;
        } else if (a==0&&flag==0) {
            count+=d;
            flag++;
        } else {
            count+=e;
            a++;
        }
    }
    cout<<count<<endl;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
 using namespace std;
 #define rep(i,N) for(int i=0;i<int(N);++i)
 using ll = long long;
 //int nax = max_element(p.begin(),p.end())-p.begin();
 //int nin = max_element(p.begin(),p.end())-p.begin();

 int main(){
     int n,k;
     cin >> n >> k;
     int now = 1;
     while(n>0){
         n--;
         if(now<k){
             now*=2;
         }
         else
            now+=k;
     }
    cout << now << endl;
     return 0;
 }

Measured memory_bytes: 256
from collections import *

def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 23696
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  unsigned long long n, a, b;
  cin >> n >> a >> b;
//  cout << "n=" << n << " a=" << a << " b=" << b << endl;

  unsigned long long  m = n % (a+b);
  unsigned long long  d = n / (a+b);

//  cout << "m=" << m << endl;
  if (m == 0) {
    cout << d * a << endl;
  }
  else if (m <= a) {
    cout << d * a + m << endl;
  }
  else {
    cout << d * a + a<< endl;
  }
}


Measured memory_bytes: 3532
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min; using std::max;
using std::swap; using std::sort;
typedef long long ll;

template<typename T>
void read(T &x) {
	int flag = 1; x = 0; char ch = getchar();
	while(ch < '0' || ch > '9') { if(ch == '-') flag = -flag; ch = getchar(); }
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= flag;
}

const int _ = 5e5 + 10, P = 1e9 + 7;
int n, p[_], s[_]; char c[_];

int chk0(int r) {
	int len = r, now = len % (len - p[r]);
	if(!now) return len / (len - p[r]) == 1;
	return 1;
}

int chk1(int l) {
	int len = n - l + 1, now = len % (len - s[l]);
	if(!now) return len / (len - s[l]) == 1;
	return 1;
}

int main () {
	scanf("%s", c + 1), n = strlen(c + 1);
	for(int i = 2; i <= n; ++i) {
		int j = p[i - 1];
		while(j && c[j + 1] != c[i]) j = p[j];
		j += c[j + 1] == c[i], p[i] = j;
	}
	std::reverse(c + 1, c + n + 1);
	for(int i = 2; i <= n; ++i) {
		int j = s[i - 1];
		while(j && c[j + 1] != c[i]) j = s[j];
		j += c[j + 1] == c[i], s[i] = j;
	}
	std::reverse(s + 1, s + n + 1);
	std::reverse(c + 1, c + n + 1);
	int now = n - p[n];
	if(now == 1) return printf("%d\n%d\n", n, 1), 0;
	if(n % now == 0 && n / now > 1) {
		printf("%d\n", 2);
		int ret = 0;
		for(int i = 1; i < n; ++i)
			if(chk0(i) && chk1(i + 1)) ++ret;
		printf("%d\n", ret);
	} else printf("%d\n%d\n", 1, 1);
	return 0;
} 
//

Measured memory_bytes: 4608
import sys
n, m = map(int, input().split())
sc = [list(map(int, input().split())) for _ in range(m)]
ans = [-1 for _ in range(n)]
ng = False
for s, c in sc:
	if ans[s-1] >= 0 and ans[s-1] != c:
		ng = True
	if n > 1 and s == 1 and c == 0:
		ng = True
	else:
		ans[s-1] = c
if ng:
	print(-1)
	sys.exit()
for i in range(n):
	if ans[i] == -1:
		if n > 1 and i == 0:
			ans[i] = 1
		else:
			ans[i] = 0
print(*ans, sep="")

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

using namespace std;

// Solve function here


// End Solve function

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a, b, c;
  	cin >> a >> b >> c;
  	printf("%d %d %d\n", c,a,b);
  	return 0;
	
}


Measured memory_bytes: 256
a,b,c = map(int,input().split())
if a > b:
    b,a = a,b
    if b > c:
        b,c = c,b
        if a > b:
            b,a = a,b
else:
    if b > c:
        b,c = c,b
        if a > b:
            b,a = a,b
            
print(f"{a} {b} {c}")


Measured memory_bytes: 5612
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin(), v.end()
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    rep(i, 3) {
        if(S[i] == '7')
            ans = 1;
    }

    if(ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3640
import java.util.*;
public class Main{
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] a = new int[n];
      int[] b = new int[n];
      for(int i = 0;i < n;i++){
        a[i] = sc.nextInt();
        b[i] = a[i];
      }
      Arrays.sort(a);
      for(int i = 0;i < n;i++){
      	if(b[i]==a[n-1])System.out.println(a[n-2]);
        else System.out.println(a[n-1]);
      }
    }
}

Measured memory_bytes: 86108
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using P = pair<int, int>;
#define debug(var) cerr << "[" << #var << "] " << var << endl
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};


int main(){
    string a, b;
    cin >> a >> b;
    string ans = "";
    int na = a.size();
    int nb = b.size();
    if (na>nb) {
        ans = "GREATER";
    }
    else if (na<nb) {
        ans = "LESS";
    }
    else {
        ans = "EQUAL";
        rep(i, na) {
            if (a[i]==b[i]) continue;
            else {
                if (a[i]>b[i]) ans = "GREATER";
                else ans = "LESS";
                break;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}


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

int main() {
    int h, w; cin >> h >> w;
    while (h != 0 && w != 0) {
        for (int height = 1; height <= h; ++height) {
            string line = "";
            for (int width = 1; width <= w; ++width) {
                bool h_is_even = true; if (height & 1) h_is_even = false;
                bool w_is_even = true; if (width & 1) w_is_even = false;
                // #
                if ((!h_is_even && !w_is_even) || (h_is_even && w_is_even)) line += "#";
                // .
                else line += ".";
            }
            cout << line << endl;
        }
        cout << endl;
        
        cin >> h >> w;
    }
    
    return 0;
}


Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
struct UnionFind {
    vector<int> A;
    UnionFind(int n) : A(n, -1) {}
    int find(int x) {
        if (A[x] < 0) return x;
        return A[x] = find(A[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (A[x] > A[y]) swap(x, y);
        A[x] += A[y];
        A[y] = x;
    }
    int size(int x) {
        return -A[find(x)];
    }
};
int main() {
    int N, M, K; cin >> N >> M >> K;
    vector<int> A(M), B(M);
    for (int i = 0; i < M; i++) cin >> A[i] >> B[i], A[i]--, B[i]--;
    vector<int> C(K), D(K);
    for (int i = 0; i < K; i++) cin >> C[i] >> D[i], C[i]--, D[i]--;
    vector<int> ans(N);
    UnionFind uf(N);
    for (int i = 0; i < M; i++) {
        uf.unite(A[i], B[i]);
    }
    for (int i = 0; i < N; i++) {
        ans[i] = uf.size(i);
    }
    for (int i = 0; i < K; i++) {
        if (uf.find(C[i]) == uf.find(D[i])) {
            ans[C[i]]--, ans[D[i]]--;
        }
    }
    for (int i = 0; i < M; i++) {
        ans[A[i]]--, ans[B[i]]--;
    }
    for (int i = 0; i < N; i++) {
        cout << ans[i] - 1 << " \n"[i == N - 1];
    }
    return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n, r;
    while(cin >> n >> r, n|r){
        vector<int> deck;
        for(int i=n; i>0; --i)deck.push_back(i);
        while(r--){
            int p, c;
            cin >> p >> c;
            --p;
            rotate(deck.begin(), deck.begin() + p, deck.begin() + p + c);
        }
        cout << deck[0] << '\n';
    }
    return 0;
}

Measured memory_bytes: 1220
#include <iostream>
using namespace std;
int main(void){
    int n,a[100] = {0};
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = n - 1; i >= 0; i--){
        if(i == n - 1){
            cout << a[i];
        }
        else{
            cout << " " << a[i];
        }
    }
    cout << endl;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int n,a,c[3005][3005],r[3005];
int main() {
	scanf("%d",&n);
	for(int i=0; i<=n; i++)
		for(int j=0; j<=i; j++)
			if(!i||!j)c[i][j]=1;
			else c[i][j]=(c[i-1][j]+c[i-1][j-1])%n;
	for(int i=0; i<n; i++) {
		scanf("%d",&a);
		if(!a)continue;
		int now=1;
		for(int j=n-1; j>=0; j--) {
			r[j]-=c[n-1][j]*now%n,r[j]%=n;
			now*=-i,now%=n;
		}
		r[0]++;
	}
	for(int i=0;i<n;i++)printf("%d ",(r[i]+n)%n);
	return 0;
}


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

int Exp(long long int exp_n,long long int exp_e, long long exp_mod);


int main(){
  long long int N,K,r,s;
  r=0;
  
  cin >> N >> K;
  long long int T[N+1], C[N+1];
  T[0] = 1;
  
  map<long long int, long long int> mp;
  
  int long long a;
  for(int i=0;i<N;i++){
    cin >> a;
    mp[i+1] = a;
    //cout << i+1 << ":" << mp[i+1] <<endl;
  }
  
  for(int i=0;i<N+1;i++){
    C[i] = 0;
  }
  
  for(int i=1;i<N+1;i++){
    T[i] = mp[T[i-1]];
    if(C[T[i]] !=0){
      r = i-C[T[i]];
      s = C[T[i]];
      break;
    }
    C[T[i]] = i;
    
    
    //cout << T[i] << " ";
  }
  
  //cout <<r<<endl;
  if(K>s){
    K = (K-s)%r;
    
    cout << T[K+s] <<endl;    
  }else{
    cout << T[K] <<endl;
  }

}


int Exp(long long int exp_n,long long int exp_e, long long int exp_mod){
  long long int exp_o = 1;
  long long int exp_x=exp_n;
  long long int exp_tmp;
  
  while(0<exp_e){
    exp_tmp = exp_e/2;
    if(exp_e - exp_tmp*2 == 1){
      exp_o = exp_o*exp_x;
      if(exp_o>exp_mod){
        exp_o=exp_o%exp_mod;
      }
    }
    
    exp_x = exp_x*exp_x;
    if(exp_x>exp_mod){
      exp_x=exp_x%exp_mod;
    }
    exp_e = exp_tmp;
  }
  return exp_o;
}


Measured memory_bytes: 19068
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>

using namespace std;
typedef long long ll;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define REP2(i,n,s) for(int i=(int)s;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int n;cin>>n;
    vector< vector<int> > a(2, vector<int>(n));
    REP(i,2) {
        REP(j,n) {
            int b;cin>>b;
            a[i][j] = b;
        }
    }

    vector<int> r(n, 0);
    REP(i, n) {
        REP(j, n) {
            if (j < i) r[i] += a[0][j];
            else if (j > i) r[i] += a[1][j];
            else r[i] += a[0][j] + a[1][j];
        }
    }

    sort(ALL(r));
    cout << r.back() << endl;
}


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

using namespace std;
typedef long long ll;

#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
const int maxn=1e5+5;
int a[maxn],b[maxn];

int main()
{
    int a;
    cin>>a;
    string s1,s2;
    cin>>s1>>s2;
    string s="";
    for(int i=0;i<s1.length();i++)
    {
        s+=s1[i];
        s+=s2[i];
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>

#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>

#include<algorithm>
#include<cmath>

using namespace std;
typedef long long ll;
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 long long INF = 1LL << 60;
typedef pair<int, int> P;
/*
//A
int main() {
    int N;
    cin >> N;
    printf("%10lf", (N-N/2)/(double)N);


}*/
/*
//B
int N;
int main() {
    cin >> N;
    vector<pair<int, int> > A(N);
    for (int i = 0; i < N; i++) {
      int a;
      cin >> a;
      A[i] = make_pair(a, i + 1);
    }
    sort(A.begin(), A.end());
    for (int i = 0; i < N; i++) {
      cout << A[i].second << " ";
    }    
    cout << "\n";
}*/

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

int main() {
  ll A, B;
  cin >> A >> B;
  ll C = gcd(A, B);
  ll res = 1;
  ll N = C;
  ll i = 2;
  while (i * i <= N) {
      if (C % i == 0) res++;
      while (C % i == 0) C = C / i;
      i++;
  }
  if (C > 1) res++;
  cout << res << "\n";



}


   

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

ll mod;

ll fac[MAX_N], inv[MAX_N], fiv[MAX_N]; //fiv:inv(fac(i))

ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return a * res % mod * res % mod;
}

ll invf(ll a) {
	return mod_pow(a, mod - 2);
}


void C_init(int n) {
	fac[0] = fac[1] = 1; inv[1] = 1;
	fiv[0] = fiv[1] = 1;
	rep(i, 2, n) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fiv[i] = fiv[i - 1] * inv[i] % mod;
	}
}

int A[MAX_N];

vector<int> div(int a) {
	vi vec(mod + 1, 0);
	vi res(mod , 0);
	vec[mod] = 1;
	vec[1] = mod - 1;
	rer(i, mod, 0) {
		int v = vec[i + 1];
		res[i] = v;
		vec[i + 1] = 0;
		ADD(vec[i], v * a);
	}
	return res;
}

void solve() {
	cin >> mod;
	rep(i, 0, mod) cin >> A[i];
	C_init(mod);
	vi ans(mod, 0);
	rep(i, 0, mod) {
		if(!A[i]) continue;
		vi vec = div(i);
		// debug(i, vec);
		int p = fac[i];
		int q = fac[mod - i - 1];
		if((mod - i - 1) % 2) q = (mod - q) % mod;
		rep(j, 0, mod) {
			MUL(vec[j], inv[p] * inv[q]);
			ADD(ans[j], vec[j]);
		}
	}
	rep(i, 0, mod) {
		cout << ans[i] << " ";
	}
	cout << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



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

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

	int cnt = 0;
	for(int i=0; i<n; i++){
		if(p[i]!=i+1) cnt++;
	}

	if(cnt<=2) puts("YES");
	else puts("NO");
	return 0;
}



Measured memory_bytes: 3768
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


S =  sys.stdin.readline().rstrip()
K =  int(sys.stdin.readline())

L = min(len(S), K)
S = S[:L]

for s in S:
    if s != "1":
        print(s)
        exit()
print("1")


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

int main()
{
	int N;
	cin >> N;
	vector<long long> A( N );
	for( int i = 0; i < N; i++ ) {
		cin >> A[i];
	}

	long long ans = 0;
	int cnt = 0;
	for( int i = 0; i < N; i++ ) {
		ans += abs( A[i] );
		if( A[i] < 0 ) cnt++;
	}
	if( cnt % 2 ) {
		long long mi = INT64_MAX / 2;
		for( int i = 0; i < N; i++ ) {
			if( abs( A[i] ) < mi ) mi = abs( A[i] );
		}
		ans -= mi * 2;
	}

	cout << ans << endl;
}


Measured memory_bytes: 4032
#include<iostream>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<math.h>
using namespace std;

int main()
{
    // get a integer
    int N;
    cin >> N;

    vector<int> a;
    vector<bool> b;

    for (auto&& i = 0; i < N; ++i ) {
        int input;
        cin >> input;
        a.push_back( input );
        b.push_back( false );
    }

    bool result = false;
    int i = 0;
    int count = 0;
    while( true )
    {
        /* cout << count << endl; */
        i = a[i] - 1;
        count++;

        if( i == 1 )
        {
            result = true;
            break;
        }
        else if( b[i] )
        {
            result = false;
            /* cout << i << "hoge" << endl; */
            break;
        }
        else if( count > N )
        {
            result = false;
            break;
        }

        b[i] = true;
    }
    if( !result )
        cout << -1 << endl;
    else
        cout << count << endl;
}



Measured memory_bytes: 892
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define M 1000000007
using namespace std;




int main()
{
	int t=1;
	//cin>>t;
	
	while(t--)
	{
		int n;
		cin>>n;
		
		double *p=new double[n];
		for(int i=0;i<n;i++)
		{
			cin>>p[i];
		}
		
		double **dp=new double*[n+1];
		for(int i=0;i<=n;i++)
		{
			dp[i]=new double[n+1];
		}
		
		dp[0][0]=1.000000000;
		
		for(int i=1;i<=n;i++)
		{
			dp[i][0]=(1.000000000-p[i-1])*dp[i-1][0];
			dp[0][i]=0;
		}
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dp[i][j]=dp[i-1][j-1]*p[i-1]+(1.000000000-p[i-1])*dp[i-1][j];
			}
		}
		
		
		double prob=0.00000000;
		
		for(int i=n/2+1;i<=n;i++)
		{
			prob+=dp[n][i];
		}
		cout<<setprecision(10)<<prob<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 74196
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int N;
int A[200005];

int main() {
  INCANT;
  cin >> N;
  int a;
  rep(i, N-1) { //2-N-1にすること
    cin >> a;
    A[a-1]++;
  }
  rep(i, N) cout << A[i] << "\n";
  return 0;
}

Measured memory_bytes: 4392
n=int(input())
a=[int(input())for _ in[0]*n]
for i in range(4):
 for j in range(n-1,i,-1):
  if a[i]>a[j]:a[i],a[j]=a[j],a[i]
p=[]
for i in range(3):
 for d in a[i+1:4]:
  c=a[i]
  p+=[int(f'{c}{d}'),int(f'{d}{c}')]
for i in range(3):
 for j in range(11,i,-1):
  if p[i]>p[j]:p[i],p[j]=p[j],p[i]
print(sorted(p)[2])


Measured memory_bytes: 5988
//abc153_c.cpp
//Sat Feb 22 18:11:50 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,k;
	cin >> n >> k;

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

	sort(h,h+n,greater<ll>());

	ll ans = 0;
	for (int i=k;i<n;i++){
		ans += h[i];
	}

	cout << ans << endl;
//	printf("%.4f\n",ans);
}

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

int main() {
long long n,h,w;
cin >> n>>h>>w;
vector<long long>a(n);
vector<long long>b(n);
for(int i=0;i<n;i++){
    cin >> a.at(i)>>b.at(i);
}
long long ans=0;
for(int i=0;i<n;i++){
    if(a.at(i)>=h&&b.at(i)>=w){
        ans++;
    }
}
cout << ans << endl;
}


Measured memory_bytes: 256
/*input
4
3 4 3 2
*/
#include <bits/stdc++.h>
using namespace std;
 
#define mx 500005
#define ll long long
#define MOD 2000000000000007ll
#define fs first
#define sc second
 
 
int main()
{
    int n;
    scanf("%d", &n);
    ll ara[n];
    for(int i = 0; i<n; i++)
        scanf("%lld", &ara[i]);
    ll l = 1, r = MOD;
    int found = 0;
    ll ansa = 0, ansb = 0 ;
    while(l <= r)
    {
        ll mid = (l + r) / 2ll;
        ll now = mid;
        for(int i = 0; i < n; i++)
        {
            mid = (mid/ara[i]) * ara[i];
        }
        if(mid == 2){
            found = 1;
            ansa = now;
            r = now - 1;
        } else if(mid > 2){
            r = now - 1;
        } else l = now + 1;
    }
    if(found == 0){
        printf("-1\n");
        return 0;
    }
    l = 1, r = MOD;
    while(l <= r)
    {
        ll mid = (l + r) / 2;
        ll now = mid;
        for(int i = 0; i < n; i++)
        {
            mid = (mid/ara[i]) * ara[i];
        }
        if(mid > 2){
            r = now - 1;
        } else if(mid==2){
            ansb = now;
            l = now + 1;
        }else{
            l = now + 1;
        }
    }
    if(ansa > ansb) cout << -1 << endl;
    else cout << ansa << " " << ansb << endl;
    return 0;
}

Measured memory_bytes: 1024
n,x,y = list(map(int,input().split()));

knum = [0]*(n-1);
d = [[0]*(n) for i in range(n)];

for i in range(n) :
    for j in range(i+1,n) :
        d[i][j] = j - i;
        d[j][i] = j - i;

d[x-1][y-1] = 1;
d[y-1][x-1] = 1;

for i in range(n) :
    for j in range(i+1,n) :
        mind = min(d[i][j],d[i][x-1]+1+d[y-1][j],d[i][y-1]+1+d[x-1][j]);
        d[i][j] = mind;
        d[j][i] = mind;

for i in range(n) :
    for j in range(i+1,n) :
        knum[d[i][j]-1] += 1;

for i in range(n-1) :
    print(knum[i]);

Measured memory_bytes: 77020
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
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; }
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    int K;
    cin >> K;
    int count = 0;
    while (A >= B) {
        B = B * 2;
        count += 1;
    }

    while (B >= C) {
        C = C * 2;
        count += 1;
    }

    if (K >= count) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>
int main ( ){
    int a,b,sum, mul,sub;
    scanf("%d%d", &a, &b);
    sum=a+b;
    sub=a-b;
    mul=a*b;
    if(sum>=sub && sum>=mul)
        printf("%d", sum);
    else if(sub>=sum && sub>=mul)
        printf("%d", sub);
    else
        printf("%d", mul);


    return 0;
}


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

int main() {
  
  int N,A,K=0,L;
  cin >> N >> A;
  
  while(A%2==0){
      K++;
      A=A/2;
  }
  
  for (int i = 1; i < N; i++) {
    
    cin >> A;
    L=0;
    
    while(A%2==0){
      L++;
      A=A/2;
    }
    
    if(L<K){
      K=L;
    }
    
  }
  
  cout << K << endl;
}

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  u64 n, k;
  cin >> n >> k;

  vector<u64> p(n);
  deque<double> e(k);

  rep(i, n) { cin >> p[i]; }

  double ans = 0.0;
  double ex = 0.0;

  rep(i, k) {
    e[i] = (1.0 + p[i]) * p[i] / 2.0 / p[i];
    ex += e[i];
  }

  ans = ex;

  rep(i, n - k) {
    ex -= e.front();
    e.pop_front();
    e.push_back((1.0 + p[i + k]) * p[i + k] / 2.0 / p[i + k]);
    ex += e.back();

    if (ex > ans) {
      ans = ex;
    }
  }

  printf("%.7lf\n", ans);

  return 0;
}


Measured memory_bytes: 6304