akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;
const int MOD = 1000000007;

signed main(){
    
    while(1){
        string a, b, c; cin >> a;
        if(a == "0") break;
        cin >> b >> c;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        reverse(c.begin(), c.end());
        int n = (int)a.size();
        vector<vector<int> > dp(n + 1, vector<int> (2, 0));
        dp[0][0] = 1LL;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 2; j++){
                if(dp[i][j] == 0) continue;

                for(char x = '0'; x <= '9'; x++) for(char y = '0'; y <= '9'; y++) for(char z = '0'; z <= '9'; z++){
                    if(a[i] != '?' && a[i] != x) continue;
                    if(b[i] != '?' && b[i] != y) continue;
                    if(c[i] != '?' && c[i] != z) continue;
                    if(i == n - 1){
                        if(x == '0' || y == '0' || z == '0') continue;
                    }

                    int numa = (int)(x - '0');
                    int numb = (int)(y - '0');
                    int numc = (int)(z - '0');
                    int left = numa + numb + j;
                    int right = numc;
                    int nxtj = (10 <= left);
                    left %= 10;
                    if(left != right) continue;
                    dp[i + 1][nxtj] += dp[i][j];
                    dp[i + 1][nxtj] %= MOD;
                }
            }
        }
        cout << dp[n][0] << endl;
    }

    return 0;
}




Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os << *i << (i==end(v)-1 ? "" : "\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is >> *i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
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;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

ll gcd(ll a,ll b) { return a?gcd(b%a,a):b; }
ll lcm(ll a,ll b) { return a/gcd(a,b)*b; }
signed main() {
    int n;
    cin>>n;
    vector<int> t(n);
    cin>>t;
    int l=t[0];
    REPF(i,1,n) {
        l=lcm(l,t[i]);
    }
    cout<<l<<endl;
    return 0;
}


Measured memory_bytes: 256
def solve():
  while True:
    h,w,n = map(int,input().split())
    if not h: break
    mp = [[int(s) for s in input().split()] for i in range(h)]
    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    dp[0][0] = n - 1
    for x in range(h):
      dpx = dp[x]
      dpxp = dp[x + 1]
      mpx = mp[x]
      for y in range(w):
        a = dpx[y]
        b = mpx[y]
        if b:
          if a % 2:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2 + 1
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        else:
          if a % 2:
            dpxp[y] += a // 2 + 1
            dpx[y + 1] += a // 2
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        mpx[y] = (a + b) % 2
  
    x = y = 0
    while x < h and y < w:
      if mp[x][y]:
        y += 1
      else:
        x += 1
    print(x + 1,y + 1)
solve()


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

bool cell[12][12];

void search(int i, int j){
	if(i<0 || i>11 || j<0 || j>11) return;
	if(cell[i][j]) cell[i][j] = false;
	else return;
	search(i+1, j);
	search(i-1, j);
	search(i, j+1);
	search(i, j-1);
}

int main(){
	while(1){
		int ans = 0;

		//ÇÝÝ
		bool flag = false;
		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				char buf;
				if(!(cin >> buf)){
					flag = true;
					break;
				}
				buf -= '0';
				if(buf) cell[i][j] = true;
				else cell[i][j] = false;
			}
			if(flag) break;
		}
		if(flag) break;

		//Tõ
		for(int i=0;i<12;i++){
			for(int j=0;j<12;j++){
				if(cell[i][j]){
					search(i, j);
					ans++;
				}
			}
		}

		cout << ans << endl;
	}
}

Measured memory_bytes: 0
# -*- coding: utf-8 -*-

import sys
import os
import math

N = int(input())

for i in range(N):
    ax, ay, ar, bx, by, br = map(float, input().split())

    between_center = math.sqrt( (ax-bx)**2 + (ay-by)**2 )

    # ????????£????????????
    if between_center > ar + br:
        print(0)

    # ????????????????????¨
    else:
        # B in A
        if ar > between_center + br:
            print(2)

        # A in B
        elif br > between_center + ar:
            print(-2)

        else:
            print(1)

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

int main() {
    int A,B,C,D,E,F;

    cin >> A >> B >> C >> D;

    E = 0;
    F = 0;

    while (C>0)
    {
        E += 1;
        C -= B;
    }

    while (A>0)
    {
        F += 1;
        A -= D;
    }
    
    if(F>=E) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}

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

int main(){
  int  X,Y;
  cin >> X >>Y;
  string t = "No";
 
  rep(i, X){
  if(Y - 4*i == 2*X -2*i){
  t = "Yes";
  }
  }
    rep(i, X){
  if(Y - 2*i == 4*X -4*i){
  t = "Yes";
  }
  }
  
  cout << t << endl;
  return 0;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    cin>>s>>t;
    ll ans=0;
    for(ll i=0; i<s.length(); i++) {
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3880
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    ll H;
    cin >> H;
    ll ans = 0;
    ll log_mons_num = 0;
    while (true) {
        H /= 2;
        ans += pow(2, log_mons_num);
        log_mons_num++;
        if (H==0) break;
    }
    cout << ans << endl;
}

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

int main() 
{
    int a, b, k; cin >> k >> a >> b;
    for (int i = a; i <= b; i++) {
        if (i % k == 0) {
            cout << "OK\n";
            return 0;
        }
    }
    cout << "NG\n";
}


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

int main(void){
	int N;
	cin >> N ;
	int V[N],C[N];
	int ans = 0;
	for(int i =0;i<N;i++)cin >> V[i];
	for(int i =0;i<N;i++)cin >> C[i];
	for(int i=0;i<N;i++){
		if( (V[i]-C[i]) >0){
			ans += (V[i]-C[i]);
		}
	}
	cout << ans ;
	return 0;
}

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

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

using namespace std;

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

	while(n != 0 && m != 0){
		vector<int> x, y;
		x.push_back(0);
		y.push_back(0);
		REP(i, n){
			int h;
			cin >> h;
			h += y[i];
			y.push_back(h);
		}
		REP(i, m){
			int w;
			cin >> w;
			w += x[i];
			x.push_back(w);
		}

		map<int, int> cnt;
		REP(i, n + 1){
			REP(j, m + 1){
				cnt[y[i] - x[j]]++;
			}
		}
				
		int ans = 0;
		map<int, int>::iterator it = cnt.begin();
		while(it != cnt.end()){
			ans += it -> second *( it -> second - 1)/ 2;
			it++;
		}
		cout << ans << endl;
		cin >> n >> m;
	}
	return 0;
}

Measured memory_bytes: 28000
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();
		int count = 0;
		for (int i = Math.min(A, B); i > 0; i--) {
			if (A%i == 0 && B%i == 0) {
				count++;
				if (count == K) {
					System.out.println(i);
					break;
				}
			}
		}
		
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 21332
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;

int main() {

    int a, b;
    cin >> a >> b;
    
    cout << (a+b) % 24 << endl;
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String str[] = sc.nextLine().split(" ");
        for(int i=n-1;i>=0;i--){
            if(i==0){
                System.out.print(str[i]);
            }else{
                System.out.print(str[i]+" ");
            }
        }
        System.out.println();
    }
}


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

int compara(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int main() {
	int N,d=1000000000,e=0;
	int a[100];
	scanf("%d", &N);
	for (int n = 0; n < N; n++) {
		scanf("%d", &a[n]);
		if (e < a[n]) {
			e = a[n];
		}
		if (d > a[n]) {
			d = a[n];
		}
	}
	int add = e - d;
	printf("%d", add);
}

Measured memory_bytes: 128
double D,px,py,vx,vy,a,p,l;
main(){
	for(;scanf("%lf",&D),D;){
		scanf("%lf%lf%lf%lf",&px,&py,&vx,&vy);
		p=px*vx+py*vy;
		a=hypot(px,py);
		l=D+1;
		if(fabs(px*vy-py*vx)<1e-9)
			l=p<0?a:2-a;
		if(D>=l)
			printf("%.8f\n",l);
		else
			puts("impossible");
	}
	exit(0);
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

string s[100];

signed main()
{   
    int H,W; cin>>H>>W;
    REP(i,H) cin>>s[i];

    REP(i,H) REP(j,W){
        if(s[i][j]=='#') continue;

        int cnt=0;
        for(int dy=-1;dy<=1;dy++) for(int dx=-1;dx<=1;dx++){
            int y=i+dy,x=j+dx;
            if(y<0 or H<=y or x<0 or W<=x) continue;
            if(s[y][x]=='#') cnt++;
        }
        s[i][j]=(char)(cnt+'0');
    }
    REP(i,H) cout<<s[i]<<endl;
    
}

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

int main() {
  int N, K, x, A=0;
  cin >> N >> K;
  
  while(N >> 0){
  cin >> x;
  if(x <= K / 2){
  A += 2 * x;
  }
  else{
  A += 2 * (K - x);
  }  
  N--;
  }  
  cout << A;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, c;
    cin >> a >> b >> c;
    ll num = c - a - b;
    if (num <= 0) {
        cout << "No" << endl;
    } else {
        ll p = 4 * a * b;
        ll q = num * num;
        if (p < q) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

ll f(ll num)
{
    if (num < 2) return 1;
    else if (num == 2) return 2;
    else if (num % 2 == 0) return 2; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return i;
        }
    }

    // 素数である
    return num;
}

vector<ll> factorList(ll x) {
  vector<ll> res;
  while (x != 1) {
    res.push_back(f(x));
    x /= f(x);
  }
  return res;
}



/*
1≤k≤n≤10^7
p は素数 (上の実装ではさらに p>n を仮定している)
*/

const int MAX = 110000;//階乗の配列数
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}




int main(){
  COMinit();
  ll n, m;
  cin >> n >> m;
  vector<ll> l=factorList(m);
  map<ll, int> MP;
  rep(i, l.size()){
    MP[l[i]]++;
  }
  ll ans=1;
  for(auto p: MP){
    int x=p.second;
    (ans*=COM(n-1+x,x))%=MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2816
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>
#include<utility>

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define P pair<int, int>
#define PLI pair<ll, int>

using namespace std;

typedef long long ll;


int W, H, C;

int gcb(int a, int b) {
	if (b == 0) return a;
	return gcb(b, a%b);
}

int main() {
	cin >> W >> H >> C;
	int g = gcb(W, H);
	W /= g; H /= g;

	cout << W * H * C << endl;

	return 0;
}


Measured memory_bytes: 3136
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
lst = [[] for _ in range(H * W)]

for i in range(H):
    for j in range(W):
        lst[A[i][j]-1] = [j, i]
tr = [[0] for _ in range(D)]
for i in range(D):
    for j in range(i+D, W*H, D):
        dlt = abs(lst[j][0] - lst[j-D][0]) + abs(lst[j][1] - lst[j-D][1])
        tr[i].append(tr[i][-1] + dlt)

Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    idx = (l - 1) % D
    if (l-1)//D == 0: st = 0
    else: st = (l - 1) // D
    ed = (r - 1) // D
    print(tr[idx][ed] - tr[idx][st])

Measured memory_bytes: 28544
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{
    int N;
    scanf("%d\n",&N);

    int res=0;
    for(int d=10; d/10<=N; d*=100)
    {
        if(N/d==0){ res+=N-(d/10-1); }
        else{ res+=(d-1)-(d/10-1); }
    }

    printf("%d\n",res);
    return 0;
}

Measured memory_bytes: 128
// {{{ include
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
// }}}

using namespace std;

typedef long long ll;
inline int in(){int x;scanf("%d",&x);return x;}

int main()
{
  int n;
  while (n = in()){
    bool ground = true;
    bool F[2] = {false, false};
    int cnt = 0;
    for (int i = 0; i < n; i++){
      string S;
      cin >> S;
      F[S[0] == 'r'] = S[1] == 'u';
      if (F[0] == ground && F[1] == ground) {
        cnt++;
        ground = !ground;
      }
    }
    cout << cnt << endl;
  }

  return 0;
}

Measured memory_bytes: 1228
#include<bits/stdc++.h>
using namespace std;
#define N 6000 + 5
#define M 2000 + 5
#define rep(i, l, r) for(int i = l; i <= r; ++i)
int n, ans, Mod, dp[N][M];
int read(){
    char c; int x = 0, f = 1;
    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int Inc(int a, int b){
    return (a += b) >= Mod ? a - Mod : a;
}
int Mul(int a, int b){
    return 1ll * a * b % Mod;
}
int main(){
    n = read(), Mod = read();
    dp[0][0] = 1;
    rep(i, 1, 3 * n) rep(j, 0, min(i / 2, n)){
        dp[i][j] = Inc(dp[i][j], dp[i - 1][j]);
        if(i >= 2 && j >= 1) dp[i][j] = Inc(dp[i][j], Mul(dp[i - 2][j - 1], i - 1));
        if(i >= 3 && j >= 1) dp[i][j] = Inc(dp[i][j], Mul(dp[i - 3][j - 1], Mul(i - 1, i - 2)));
    }
    rep(i, 0, n) ans = Inc(ans, dp[3 * n][i]);
    printf("%d", ans);
    return 0;
}


Measured memory_bytes: 46896
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
int mod = 998244353;
// int mod = 1000000007;
const double eps = 1e-8;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T> ostream& operator << (ostream& os, const set<T>& s) { for (auto si : s) os << si << " "; return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { (a += (b % mod + mod)) %= mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(12);
    int T;
    T = 1;
    while (T--) solve();
}

// https://atcoder.jp/contests/abc169/submissions/17012136
// xiどれかを+1すると, n=奇数なら中央値+0or+1, n=偶数なら中央値+0or+1/2
// また, 最小値と最大値はとる
// よって, すべてのxiを最小値から最大値に動かす間, 中央値は最小値から最大値までのすべての値をとる
// (刻みは, n=奇数なら1, n=偶数なら1/2)
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    sort(all(a));
    sort(all(b));
    
    auto calc = [&](vector<ll> x) {
        if (n % 2) return x[(n + 1) / 2 - 1];
        else return (x[n / 2 - 1] + x[n / 2]) / 2;
    };
    
    if (n % 2) {
        cout << calc(b) - calc(a) + 1 << endl;
    } else {
        rep(i, n) {
            a[i] *= 2;
            b[i] *= 2;
        }
        cout << calc(b) - calc(a) + 1 << endl;
    }
}



Measured memory_bytes: 9476
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<iostream>

using namespace std;
int main(void){
	int N,H,W,ans;
	cin >> N >> H >> W;
	ans = (N-H+1)*(N-W+1);
	cout << ans << endl;
	return 0;
}

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

int main()
{
	int x, y;
	scanf("%d%d", &x, &y);
	for(int i=0; i<=x; i++) // This is the chicken
	{
		int j = x - i;
		if((i * 2 + j * 4) == y ) 
				return printf("%s", "Yes"), 0;
	}
	printf("%s", "No"); 
}

Measured memory_bytes: 3824
#include <algorithm>
#include <array>
#include <climits> // INT_MAX, LONG_MAX, LLONG_MAX, UINT_MAX, ULONG_MAX, ULLONG_MAX
#include <cmath>
#include <cstdint>
#include <cstring> // memset
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
 
#define ALL(x) (x).begin(), (x).end()
#define INF 1e9
#define LOG(x) cout << #x << " = " << (x) << endl
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
 
using namespace std;

int s[2][1000][1000];


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

    REP(i, n) {
        int xi, yi;
        string ci;
        cin >> xi >> yi >> ci;

        if (ci[0] == 'B')
            xi += k; // Do not use -= for %
        if (xi % (2 * k) >= k) {
            xi += k; // Do not use -= for %
            yi += k; // Do not use -= for %
        }

        if (yi % (2 * k) >= k)
            s[1][xi % k][yi % k]++;
        else
            s[0][xi % k][yi % k]++;
    }

    REP(p, 2) REP(q, k) REP(r, k)
        s[p][q][r] += (q > 0 ? s[p][q - 1][r] : 0) + (r > 0 ? s[p][q][r - 1] : 0) - (q > 0 && r > 0 ? s[p][q - 1][r - 1] : 0);

    int best = 0;

    REP(p, k) REP(q, k) {
        best = max(best,
                   max(s[0][k - 1][k - 1] - s[0][p][k - 1] - s[0][k - 1][q] + 2 * s[0][p][q] + s[1][p][k - 1] + s[1][k - 1][q] - 2 * s[1][p][q],
                       s[1][k - 1][k - 1] - s[1][p][k - 1] - s[1][k - 1][q] + 2 * s[1][p][q] + s[0][p][k - 1] + s[0][k - 1][q] - 2 * s[0][p][q]));
    }
    
    cout << best << endl;
    
    return 0;
}


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

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    int b[n];
    for (int i = 0; i < n; i++) cin >> b[i];
    bool x[30] = {0};
    for (int i = 29; i >= 0; i--) {
        if (n % 2) {
            for (int j = 0; j < n; j++) {
                x[i] ^= (a[j] >> i) % 2;
                x[i] ^= (b[j] >> i) % 2;
            }
        }
        for (int j = 0; j < n; j++) {
            a[j] %= 1 << i;
            b[j] %= 1 << i;
        }
        sort(b, b + n);
        for (int j = 0; j < n; j++) {
            x[i] ^= (b + n - lower_bound(b, b + n, (1 << i) - a[j])) % 2;
        }
    }
    int res = 0;
    for (int i = 0; i < 30; i++) {
        res += x[i] << i;
    }
    cout << res << "\n";
    return 0;
}


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

const string YES = "YES";
const string NO = "NO";

void solve(std::string A, std::string B, std::string C) {
    string ans;
    (A[A.length()-1]==B[0] and B[B.length()-1]==C[0])?ans=YES:ans=NO;
    cout<<ans<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You
// use the default template now. You can remove this line by using your custom
// template)
int main() {
  std::string A;
  std::cin >> A;
  std::string B;
  std::cin >> B;
  std::string C;
  std::cin >> C;
  solve(A, B, C);
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int N=0;
  int X=0;
  int i=0;
  
  scanf("%d",&N);

  int A[N];
  
  for(i=0;i<N;i++)
  {
    scanf("%d",&A[i]);
  }
  
  for(i=0;i<N;i++)
  {
    if(A[i]%2==0)
    {
      if(A[i]%3!=0)
      {
        if(A[i]%5!=0)
        {
          X++;
        }
      }
    }
  }

if(X==0)
{
  printf("APPROVED\n");
}

else
{
  printf("DENIED\n");
}

return 0;  
}



Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int a[100005];
multiset<int> st;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        multiset<int>::iterator cur=st.lower_bound(a[i]);//查找最大的比该元素小的元素 lower-1
        if(cur==st.begin())
        {
            st.insert(a[i]);
        }
        else
        {
            cur--;
            st.erase(cur);
            st.insert(a[i]);
        }
    }
    printf("%d\n",st.size());
}


Measured memory_bytes: 5376
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<string, int> P;

bool pairCompare(const P &firstElof, const P &secondElof)
{
    return firstElof.second > secondElof.second;
}
bool pairCompare2(const P &firstElof,const P &secondElof){

    if(firstElof.first<secondElof.first) {
        return firstElof.first < secondElof.first;
    }
    else if(firstElof.first==secondElof.first){
        return firstElof.second > secondElof.second;
    }
    else
        return firstElof.first > secondElof.first;
}

int main(void)
{
    string s;
    cin >> s;
    long long ans = 0, cnt = 0;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if(s[i]=='A')
            cnt++;
        else if (s[i]=='B'){
            if(i+1<n && s[i+1]=='C'){
                ans += cnt;
                i++;
            }
            else
                cnt = 0;
        }
        else
            cnt = 0;
    }
    cout << ans << endl;

    return 0;
}

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

def main():
    M=int(input())
    print(48-M)

if __name__ == '__main__':
    main()


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

template<typename T, typename U>
using pv=vector<pair<T,U>>;
template<typename T>
using matrix=vector<vector<T>>;
template<typename T>
using pque=priority_queue<T>;
template<typename T>
using lpque=priority_queue<T,vector<T>,greater<T>>;

using ll=long long;
using intpair=pair<int,int>;
using llpair=pair<ll,ll>;
using ilpair=pair<int,ll>;
using lipair=pair<ll,int>;
using intvec=vector<int>;
using llvec=vector<ll>;
using intq=queue<int>;
using llq=queue<ll>;
using intmat=vector<intvec>;
using llmat=vector<llvec>;

#define PI 3.141592653589793
#define INTINF ((1<<30)-1)
#define LLINF ((1LL<<62)-1)
#define MPRIME 1000000007
#define MPRIME9 998244353
#define MMPRIME ((1ll<<61)-1)

#define len length()
#define pushb push_back
#define fi first
#define se second

#define all(name) name.begin(),name.end()
#define rall(name) name.rbegin(),name.rend()
#define gsort(vbeg,vend) sort(vbeg,vend,greater<>())

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;
}

template<class T>
inline void init(T& v) {
	for(auto &a: v) cin>>a;
}
template<class T, class U>
inline void init(vector<pair<T,U>>& v) {
	for(auto &a: v) cin>>a.first>>a.second;
}
template<class T, class N>
inline void init(T& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a;
}
template<class T, class U, class N>
inline void init(vector<pair<T,U>>& v, N n) {
	v.resize(n);
	for(auto &a: v) cin>>a.first>>a.second;
}

template<class T>
inline void out(T a) {
	cout<<a<<endl;
}
template<class T, class... U>
inline void out(T a, U... alist) {
	cout<<a<<" ";
	out(forward<U>(alist)...);
}

template<class N>
void resiz(N n) {
	//empty
}
template<class N, class T, class... U>
void resiz(N n, T&& hd, U&&... tl) {
	hd.resize(n);
	resiz(n,forward<U>(tl)...);
}

ll binpow(ll a, ll ex, ll p) {
	ll result=1;
	while(ex>0) {
		if(ex&1) result=result*a%p;
		ex>>=1;
		a=a*a%p;
	}
	return result;
}


ll A,B,C;

void input() {
	cin>>A>>B>>C;
}

void solve() {
	cout<<(A+B-1)/B*C<<endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
	int t=1;
	while(t) {
		input();
		solve();
		t--;
	}
}


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

int main(){
    int n, a, b, c;
    
    cin >> n;
    
    for(int i = 0;i < n;i++){
        cin >> a >> b >> c;
        
        if(a*a == b*b + c*c || b*b == a*a + c*c || c*c == a*a + b*b){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 3088
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    info0 = []
    info1 = []
    for _ in range(N):
        x, y, h = map(int, input().split())
        if h == 0: info0.append((x, y))
        if h != 0: info1.append((x, y, h))

    for cx in range(101):
        for cy in range(101):
            H = -1
            for x, y, h in info1:
                wrong = False
                if h > 0 and H == -1:
                    H = h + abs(cx - x) + abs(cy - y)
                elif h > 0:
                    if H != h + abs(cx - x) + abs(cy - y):
                        wrong = True
                        break
            if wrong: continue
            for x, y in info0:
                wrong = False
                if abs(cx - x) + abs(cy - y) < H:
                    wrong = True
                    break
            if wrong: continue
            print("{} {} {}".format(cx, cy, H))
            exit()

if __name__ == "__main__":
    main()



Measured memory_bytes: 40560
N = int(input())
A = [int(x) for x in input().split()]
cnt = 0 
maxx = 0
for i in range(N-1):
	if A[i]>=A[i+1]:
		cnt+=1
		maxx = max(cnt, maxx)
		#print(cnt)
	else:
		
		cnt = 0 
print(maxx)


Measured memory_bytes: 14252
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int N,i,j,k,q;char T[50],c[9];scanf("%d",&N);while (N--) {
        scanf("%s%s",&c,&T);j=strlen(c),k=strlen(T)-1;
        while (j--) {
            if (c[j]=='P') {
                for (i=k;i>=0;i--) {if (T[i]>='1' && T[i]<='9') T[i]--; else if (T[i]=='0') T[i]='9';}
            } else if (c[j]=='M') {
                for (i=k;i>=0;i--) {if (T[i]>='0' && T[i]<='8') T[i]++; else if (T[i]=='9') T[i]='0';}
            } else if (c[j]=='E') {
                for (i=k,q=(k-1)/2;q>=0;i--,q--) swap(T[i],T[q]);
            } else if (c[j]=='A') {
                for (i=0,q=k;i<q;i++,q--) swap(T[i],T[q]);
            } else if (c[j]=='J') {
                c[8]=T[k];for (i=k;i>0;i--) T[i]=T[i-1];T[0]=c[8];
            } else {
                c[8]=T[0];for (i=0;i<k;i++) T[i]=T[i+1];T[k]=c[8];
            }
        }
        puts(T);
    }
}

Measured memory_bytes: 1012
import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
table = [[] for i in range(N)]
Q = deque()
visited = [0]*N
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    table[A].append(B)
    table[B].append(A)

for x in range(N):
    if visited[x] == 0:
        ans += 1
        Q.append(x)
        while Q:
            x = Q.popleft()
            for y in table[x]:
                if visited[y]==0:
                    Q.append(y)
                    visited[y] = 1

print(ans-1)

Measured memory_bytes: 81440
#include <stdio.h>

int main(void){
    int line[10],v1,v2,i,sum=0;
    double sign,time;
    for(;;sum=0){
        for(i=0;i<10;i++){
            if(scanf("%d,",&line[i]) == EOF)
                return 0;
            sum+=line[i];
        }
        scanf("%d,%d",&v1,&v2);
        time=(double)sum/(v1+v2);
        sign=time*v1;
        for(sum=0,i=0;i<10;i++){
            sum+=line[i];
            if(sum >= sign)
                break;
        }
        printf("%d\n",i+1);
    }
    return 0;
}

Measured memory_bytes: 1684
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}



signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,m;cin>>n>>m;
  V<ll> v(n);
  ll sum=0,cnt=0;
  rep(i,0,n){
    cin>>v[i];
    sum+=v[i];
  }

  rep(i,0,n){
    if(v[i]*4*m>=sum){
      cnt++;
    }
  }

  if(cnt>=m)cout<<"Yes"<<ENDL;
  else cout<<"No"<<ENDL;

}
//! ( . _ . ) ! 
//CHECK overflow,vector_size,what to output?

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;

using ll = long long;

int main()
{
    ll n, m;
    cin >> n >> m;

    vector<int> yakusu;
    for (int i = 1; i <= sqrt(m); i++) {
        if (m % i == 0) {
            yakusu.push_back(i);   
            yakusu.push_back(m / i);
        }
    }

    sort(yakusu.begin(), yakusu.end(), greater<int>());

    ll result = 1;
    for (int i = 0; i < yakusu.size(); i++) {
        if (yakusu[i] * n > m) continue;

        if ((m - yakusu[i] * n) % yakusu[i] == 0) {
            result = yakusu[i];
            break;
        }
    }

    cout << result << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <string>
#include <vector>

int main(void){
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for(int i = 0; i < n; i++){
        std::cin >> a[i];
    }

    sort(a.begin(),a.end());
    std::cout << a[n-1] - a[0];
    return 0;
}


Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    a,b,c=map(int, input().split())
    if a%2==0 or b%2==0 or c%2==0:
        print(0)
    else:
        l=[a,b,c]
        l.sort()
        print(l[0]*l[1])
resolve()


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

vector<string> farm(101);
vector< vector<int> > farmBuf(101, vector<int>(101));
int H, W;

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

void rec(char c, int y, int x) {
	int i, xx, yy;
	farmBuf[y][x] = 1;
	for (i = 0; i < 4; i++) {
		xx = x+dx[i]; yy = y+dy[i];
		if (xx<0||W<=xx||yy<0||H<=yy) continue;
		if (farm[yy][xx]==c && !farmBuf[yy][xx]) rec(c, yy, xx);
	}
	return;
}

int main()
{
	int i, j, count;
	while (cin>>H>>W, H||W) {
		for (i = 0; i < H; i++)
			for (j = 0; j < W; j++)
				farmBuf[i][j] = 0;
		for (i = 0; i < H; i++) cin>>farm[i];
		count = 0;
		for (i = 0; i < H; i++) {
			for (j = 0; j < W; j++) {
				if (!farmBuf[i][j]) {
					rec(farm[i][j], i, j);
					count++;
				}
			}
		}
		cout<<count<<endl;
	}

	return 0;
}

Measured memory_bytes: 0
import math
n,m=map(int,input().split())
mod=10**9+7
if abs(n-m)>1:
    print(0)
elif abs(n-m)==1:
    print(math.factorial(n)*math.factorial(m)%mod)
else:
    print(2*math.factorial(n)*math.factorial(m)%mod)


Measured memory_bytes: 5184
#include<iostream>

int main(void) {
	int N;
	std::cin >> N;
	int sum = 0;
	int tmp = N;

	while (tmp > 0) {
		sum += tmp % 10;
		tmp /= 10;
	}
	std::cout << ((N % sum == 0) ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
#define SSTR(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'


int main() {
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n; ll k; cin >> n >> k;
	vector<ll> nums(n);
	for_(i, 0, n) cin >> nums[i];
	
	ll lo = 1, hi = 1e9+1;
	while (lo < hi) {
		ll mid = (lo + hi) / 2;
		ll ct = 0;
		for_(i, 0, n) if (nums[i] > mid) {
			auto res = div(nums[i], mid);
			ct += res.quot-1;
			if (res.rem) ct += 1;
		}
		//cout << mid << " " << ct << endl;
		if (ct <= k) hi = mid;
		else lo = mid+1;
	}
	
	cout << lo << endl;

	return 0;
}


Measured memory_bytes: 4772
import sys
readline = sys.stdin.buffer.readline


N, K = map(int, readline().split())
A = list(map(int, readline().split()))
passed = [0] * N
P = []
c = 0
for _ in range(N):
    c = A[c] - 1
    if passed[c] == 1:
        s = c
        break
    P.append(c)
    passed[c] = 1
    
if K <= len(P):
    print(P[K-1] + 1)
else:
    idx = P.index(s)
    m = (K - idx) % (len(P) - idx)

    print(P[idx:][m-1] + 1)


Measured memory_bytes: 27976
import numpy
import re
import math

def calc_pattern_num(a, b, c, sum_target):
	"""
	硬貨のパターンからsumになるパターンを算出
	:param a:
	:param b:
	:param c:
	:param sum:
	:return:
	"""
	count = 0
	for i in range(0, a+1):
		for j in range(0, b + 1):
			for k in range(0, c + 1):
				sum = 500 * i + 100 * j + 50 * k
				if sum == sum_target:
					count += 1
	return count

def main():
	"""
	テストコード実行
	:return:
	"""
	a = int(input())
	b = int(input())
	c = int(input())
	sum = int(input())
	print(calc_pattern_num(a, b, c, sum))

if __name__ == '__main__':
	main()


Measured memory_bytes: 22268
#include <bits/stdc++.h>
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define RREP(i, n) for(int (i)=((int)(n)-1); (i)>=0; i--)
#define RFOR(i, a, b) for(int (i) =((int)(b)-1); (i)>=(int)a; i--)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define FT first
#define SC second

using namespace std ;
typedef long long ll;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int, int> pint;
const int INF = 1e9;
const double EPS = 1e-9;



int main()
{
  int a, b ;
  cin >> a >> b ;
  int count = 0 ;
  
  FOR(i,a,b+1){
    int j = i/10000+(i%10000/1000)*10+(i%1000/100)*100+(i%100/10)*1000+(i%10)*10000 ;
    if(j==i){
      count++ ;
    }
  }
  
  cout << count <<endl ;
  

  return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
   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; }
    const int MAX =200002;
const int MOD =1000000007;
   int modpow(int a, int n, int mod) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
     signed main(){
 int n,m;
 cin>>n>>m;
 vector<int> t[n];
 int a,b;
 for(int i=0;i<m;i++){
     cin>>a>>b;a--;b--;
     t[a].push_back(b);
     t[b].push_back(a);
 }
 bool used[n]={};
 queue<int> que;
 int ans=0;
 for(int i=0;i<n;i++){
     if(used[i])continue;
     que.push(i);
     int k=1;
     used[i]=true;
     while(!que.empty()){
         for( auto&& j:t[que.front()]){
             if(!used[j]){
                 used[j]=true;
                 k++;
                 que.push(j);
             }
         }
         que.pop();
     }
     ans=max(ans,k);
 }
 cout<<ans<<endl;
   }
     


 


 






    





      

        


Measured memory_bytes: 17456
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>a>>b>>c>>d;
    Cout(min(a,b)+min(c,d));
    return 0;
}


Measured memory_bytes: 256
/* *Your Love Makes me STRONG,
   You'r Hate Makes Me UNSTOPABBLE.*
 
  *HOPE is a good thing,Maybe The BEST of Things.
   And No Good Things Ever Dies.*
  
  *Keep calm,Be patient And Chase Your DREAM*

*/


#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MN7 ios::sync_with_stdio(0);cin.tie(nullptr);
using namespace std;
ll t,n,i,j,k,a,b,c,d,p,q,r,x,y,z,m,cnt,flag,ans;
string s;
void nahid()
{
 cin>>n;
 m=n;
 while(n)
 {
 	ans+=n%10;
 	n/=10;
 }
 if(m%ans)cout<<"No"<<endl;
 else cout<<"Yes"<<endl;
}
int main()
{ MN7 //cin>>t;while(t--)
  nahid();
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

// Stores set of lines a*x+b, supports max-queries at given x-values.
// Lines must be inserted by increasing slope a.
// Maxima must be queried by increasing x.
struct envelope {
	struct line {
		ll a, b;
		ll operator()(ll x) { return a*x + b; }
	};
	deque<line> v;

	bool bad(line s, line t, line u) {
		return __int128(t.a-s.a)*(u.b-s.b) <= __int128(u.a-s.a)*(t.b-s.b);
	}

	void add_line(ll a, ll b) {
		v.push_front({a,b});
		while (sz(v) >= 3 && bad(v[0],v[1],v[2])) v.erase(begin(v)+1);
	}
	
	ll find_max(ll x) {
		if (v.empty()) return -oo;
		while (sz(v) >= 2 && v[sz(v)-2](x) >= v[sz(v)-1](x)) v.pop_back();
		return v[sz(v)-1](x);
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, C;
	cin >> n >> C;
	vl h(n), dp(n);
	FOR(i,0,n) cin >> h[i];
	
	// dp[i] = min(dp[j] + (h[j]-h[i])^2 + C)
	//       = C + h[i]^2 + min(dp[j] + h[j]^2 - 2*h[j] * h[i])
	//       = C + h[i]^2 - max(-dp[j] - h[j]^2 + 2*h[j] * h[i])
	
	envelope E;
	FOR(i,0,n) {
		if (i) dp[i] = C + h[i]*h[i] - E.find_max(h[i]);
		E.add_line(2*h[i], -dp[i] - h[i]*h[i]);
	}
	cout << dp.back() << endl;
}



Measured memory_bytes: 5632
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>

using namespace std;

/* b-aで南蛮メカ求める */


int main(){
    int a,b;
    int sub;
    int height=0;
    int ans;
    scanf("%d %d",&a,&b);
    sub = b-a;
    for(int i=0;i<sub;i++){
        height=height+i+1;
    }
    ans=height-b;
    printf("%d",ans);
}


Measured memory_bytes: 256