akhauriyash/Code-Regression huggingface dataset:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
T = LIST()
A = LIST()

h = [0]*N
ma = -1
for i, t in enumerate(T):
	if ma < t:
		h[i] = t
		ma = t


ma = -1
for i, a in enumerate(A[::-1]):
	if ma < a:
		if h[-i-1] and a != h[-i-1]:
			print(0)
			exit()
		h[-i-1] = a
		ma = a

acc_t = list(accumulate(h, max))
acc_a = list(accumulate(h[::-1], max))[::-1]

if acc_t != T or acc_a != A:
	print(0)
	exit()

mi = [min(t, a) for t, a in zip(T, A)]

ans = 1
for i in range(N):
	if h[i] == 0:
		ans *= mi[i]
		ans %= mod

print(ans)

Measured memory_bytes: 26396
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);let input_i=-1;const tn=():number=>{input_i++;return Number(input[input_i])};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{input_i++;return String(input[input_i])};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const ceil=(a)=>{return Math.ceil(a)};const asc=(ar:number[])=>{const t=[...ar];return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{const t=[...ar];return t.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1]}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const deduplicate=(a:any[]):any[]=>{return Array.from(new Set(a))};const gcd=(x,y)=>{while(y){[x,y]=[y,x%y]}return x};const sum=(arr)=>{return arr.reduce((a,b)=>a+b);};
const main=()=>{
  let [a,b]=tnn(2),tn=new Array(3)
  tn.fill(0)
  tn[a-1]=1,tn[b-1]=1
  for(let i=0;i<3;i++){
    if(tn[i]==0){to(i+1)}
  }
}
main()


Measured memory_bytes: 7500
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define revrep(i, n) for(ll i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll max3(ll a, ll b, ll c){return max(a, max(b, c));};
ll min3(ll a, ll b, ll c){return min(a, min(b, c));};
ll max4(ll a, ll b, ll c, ll d){return max(max(a, b), min(c, d));};
ll min4(ll a, ll b, ll c, ll d){return min(min(a, b), min(c, d));};
ll max5(ll a, ll b, ll c, ll d, ll e){return max(max(a, b), max3(c, d, e));};
ll min5(ll a, ll b, ll c, ll d, ll e){return min(min(a, b), min3(c, d, e));};

const ll INFL = 1LL << 60;//10^18 = 2^60
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD = 998244353;

vector<ll> dy = {0, 0, 1, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, -1, 0, 0, 1, -1, 1, -1, 0};


ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}
ll pow_mod(ll x, ll k){
  x %= MOD; x += MOD; x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

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

ll lcm(ll x, ll y){return x / gcd(x, y) * y;};

ll kai_mod(ll x){
  if(x == 0) return 1;
  return x * kai_mod(x-1) % MOD;
}

/*
//コンビネーション
const int MAXcomb = 200010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; 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;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}
*/

vector<ll> compress(vector<ll> X){
  vector<ll> xs;
  rep(i, X.size()) xs.pb(X[i]);
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  rep(i, X.size()) X[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
  return X;
}

ll N;
vector<ll> A;
int main(){
  cin >> N;
  A.resize(N);
  rep(i, N) cin >> A[i];
  A = compress(A);
  ll cnt = 0;
  rep(i, N){
    if(i % 2) continue;
    if(A[i] % 2) cnt++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    int num = 0;
    int HP = 0;
    int min_HP = 10000000;
    while (num <= 101){
        rep(i,N){
            HP += (vec[i] - num) * (vec[i] - num);
        }
        if (HP < min_HP){
            min_HP = HP;
        }
        num++;
        HP = 0;
    }
    cout << min_HP << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int D = sc.nextInt();
    int E = sc.nextInt();
    int F = sc.nextInt();
    double max = -1.0;
    int waterANS = -1;
    int sugarANS = -1;
    for (int i = 0; (100 * A * i) <= F; i++) {
      int waterA = 100 * A * i;
      for (int j = 0; (waterA + (100 * B * j)) <= F; j++) {
        int waterB = 100 * B * j;
        int water = waterA + waterB;
        if (water == 0) {
          continue;
        }
        for (int k = 0; (C * k) <= F; k++) {
          int sugarC = C * k;
          for (int l = 0; (sugarC + (D * l)) <= F; l++) {
            int sugarD = D * l;
            int sugar = sugarC + sugarD;
            int mul = water / 100;
            double late = (double)(100 * sugar) / (double)(water + sugar);
            if (water + sugar <= F && sugar <= E * mul && late > max) {
              max = late;
              waterANS = water;
              sugarANS = sugar;
            }
          }
        }
      }
    }
    System.out.println((waterANS + sugarANS) + " " + sugarANS);
  }
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
#define int long long int
#define inf 1000000000000
#define hell (int)(1e9+7)

using namespace std;

void solve(){
    int n;
    cin>>n;
    vector <int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ma=inf,ans=0;
    for(int x:a){
        ma=min(ma,x);
        if(x==ma)
            ans++;
    }
    cout<<ans;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}


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

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

    double n,k;
    cin >> n >> k;
    
    cout << ceil((n-k)/(k-1)) + 1;
}


Measured memory_bytes: 256
import bisect

n = int(input())
ll = [int(w) for w in input().split()]
ll.sort()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(ll, ll[i] + ll[j]) - (j + 1)

print(ans)


Measured memory_bytes: 8996
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		int  a=sc.nextInt();
		int  b=sc.nextInt();
		int  c=sc.nextInt();
		int  tmp;

		if(a>b) {
			tmp=a;
			a=b;
			b=tmp;
		}
		if(b>c) {
			tmp=b;
			b=c;
			c=tmp;
		}
		if(a>b) {
			tmp=a;
			a=b;
			b=tmp;
		}

		System.out.println(a+" "+b+" "+c);



	}
}



Measured memory_bytes: 26144
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

typedef long long ll;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int l = 0;
    int r = 0;
    FOR(i,0,n){
        if(s[i]=='(') l++;
        else if(l==0) r++;
        else l--;
    }
    int rr = r;
    l = 0;
    r = 0;
    for(int i = n - 1; i >= 0; --i){
        if(s[i]==')') r++;
        else if(r==0) l++;
        else r--;
    }
    FOR(i,0,rr) s = '(' + s;
    FOR(i,0,l) s += ')';
    cout << s << endl;
}


Measured memory_bytes: 256
//** aman**/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define dl          double
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define lb lower_bound
#define ub upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main(){
	ll r,d,x;cin>>r>>d>>x;
	for(int i=1;i<=10;i++){
		cout<<(x*r-d)<<endl;
		x=(x*r-d);
	}
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  //counter
  int i,j;

  //input
  int n;
  scanf("%2000000d",&n);
  
  int A[n];
  int k=0;  // TODO serching "k"
  for(i=0;i<n;i++){
    scanf("%10000d",&A[i]);
    if(A[i]>k){
      k = A[i];
  }
  }

  
  //Counting Sort

  int C[k+1];
  for(i=0;i<k+1;i++){
    C[i] = 0;
  }
  for(j=0;j<n;j++){
    C[A[j]]++;
  }
  for(i=1;i<k+1;i++){
    C[i] = C[i] + C[i-1];
  }
    int B[n];
    for(j=(n-1);j>=0;j--){
    B[C[A[j]]-1] = A[j];
    C[A[j]]--;
    }

  //output
  for(i=0;i<n-1;i++){
    printf("%d ",B[i]);
  }
  printf("%d\n",B[n-1]);
  


    return 0;
}



Measured memory_bytes: 17360
import static java.util.Arrays.binarySearch;
import java.util.Scanner;
import static java.util.Arrays.sort;

/**
 *
 * @author cs18097
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int tmp;
        int n[]= new int[num];
        int count=0;
        for(int i=0;i<num;i++){
            n[i] = sc.nextInt();
        }
        sort(n);
        for(int i=0;i<num-1;i++){
            for(int j=i+1;j<num-1;j++){
                for(int k = j+1;k<num;k++){
                    //if(n[i]+n[j])
                    if(n[i]+n[j]>n[k]){
                        count++;
                        }else break;
                }
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 28448
#include <bits/stdc++.h>
using namespace std;
 
int main() { 
  int N;
  cin >> N;
  char S;
   
  for (int i = 0; i < N; i++) {
    cin >> S;
    if(S=='Y') {
      cout << "Four" << endl;
      break;
    }
  }
  if(S!='Y')cout << "Three" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define PI 3.14159265359

void kock(int n, double px1, double py1, double px2, double py2) {
    
    double sx,sy,tx, ty, ux, uy;
    if (n == 0) return;
    
    sx = (2*px1 + 1*px2)/3;
    sy = (2*py1 + 1*py2)/3;
    tx = (1*px1 + 2*px2)/3;
    ty = (1*py1 + 2*py2)/3;
    ux = (tx - sx) * cos(PI/3) - (ty - sy) * sin(PI/3) + sx;
    uy = (tx - sx) * sin(PI/3) + (ty - sy) * cos(PI/3) + sy;

    
    kock(n-1, px1, py1, sx, sy);
    printf("%f %f\n",sx, sy);
    
    kock(n-1, sx, sy, ux, uy);
    printf("%f %f\n", ux, uy);
    
    kock(n-1, ux, uy, tx, ty);
    printf("%f %f\n", tx, ty);
    
    kock(n-1, tx, ty, px2, py2);
    
}

int main() {
    int n;
    scanf("%d", &n);
    
    printf("0 0\n");
    kock(n, 0, 0, 100, 0);
    printf("100 0\n");
    
    return 0;
}

Measured memory_bytes: 1796
def main():
  N = input()
  N = '0'+N
  dp= [[float('inf') for _ in range(2)] for _ in range(len(N)+1)]
  dp[0][0] = 0
  for i in range(len(N)):
    n = int(N[len(N)-1-i])
    for j in range(2):
      # jが1のときは繰り下がりあり。
      # 引かれる数から1を引く代わりに、引く数xに1を足す。
      x = n+j
      # xが10のとき、必ず繰り下がりが起こる。
      if x < 10:
        dp[i+1][0] = min(dp[i+1][0],dp[i][j]+x)
      # xが0のとき、繰り下がりは起こせない。
      if x > 0:
        dp[i+1][1] = min(dp[i+1][1],dp[i][j]+10-x)
  print(dp[len(N)][0])  
  # print(dp)
  
if __name__ == '__main__':
  main()


Measured memory_bytes: 211972
import sys

n = int(input())
li = list(map(int, input().split()))

for i in range(n):
  a = li[i]
  if a%2 ==0:
    if (a % 3 == 0 or a % 5 == 0)==False:
      print("DENIED")
      sys.exit()

print("APPROVED")


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
typedef long long ll;
typedef long double ld;
const long long INF = 1e18;
# define len(x) ((int)(x).size())
# define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(int i=((int)(n)-1); i>=0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>0; --i)
# define foreps(i, m, n) for(int i = m;i < n;i++)
# define ALL(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
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; }

int main() {
    int N, T; cin >> N >> T;

    int minv = 1e5, ans = 0;
    rep(i, N) {
        int c, t; cin >> c >> t;
        if (t <= T) minv = min(minv, c);
    }
    if (minv == 1e5) {
        cout << "TLE" << endl;
        return 0;
    }
    cout << minv << endl;
}

Measured memory_bytes: 3616
#include <stdio.h>

int main(void)
{
	int d;
	int x;
	long long int S;
	while(scanf("%d", &d)!=EOF) {
		S=0;
		for(x=d; 600-x>0; x+=d)
			S+=x*x*d;
		printf("%lld\n", S);
	}
	return 0;
}


Measured memory_bytes: 596
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc =new Scanner(System.in);
		
			int Chris = 25;
			int lol = sc.nextInt();
			if(lol ==25) {
				System.out.println("Christmas");
				System.exit(0);
			}
			System.out.print("Christmas ");
			for(int i =0; i<Chris-lol; i++) {
				System.out.print("Eve ");
			}
	}

}


Measured memory_bytes: 35640
table=[1 for i in range(10**5+10)]

table[0]=0
table[1]=0
for i in range(int(len(table)**0.5)+10):
    if table[i]==0:
        continue

    k=2
    while True:
        try:
            table[k*i]=0
            k+=1
        except IndexError:
            break

X=int(input())

while table[X]==0:
    X+=1
print(X)


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

#define ll long long
#define pb push_back



int main()
{
    int n;
    cin>>n;
    map<string,int>mp;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        mp[s]++;
    }
    cout<<"AC x "<<mp["AC"]<<endl;
    cout<<"WA x "<<mp["WA"]<<endl;
    cout<<"TLE x "<<mp["TLE"]<<endl;
    cout<<"RE x "<<mp["RE"]<<endl;


}



Measured memory_bytes: 3648
//
// Created by tattsun on 2017/02/11.
//

#include <iostream>
#include <vector>
using namespace std;

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

    int u, k, p;
    for(int i=0; i<n; i++) {
        cin >> u >> k;

        vector<int> dest;
        for(int j=0; j<k; j++) {
            cin >> p;
            dest.push_back(p);
        }

        vector<int>::iterator it = dest.begin();
        for(int j=0; j<n; j++) {
            if(j != 0) cout << " ";
            if(it != dest.end() && j == *it-1) {
                cout << "1";
                it++;
            } else {
                cout << "0";
            }
        }
        cout << endl;
    }
}

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

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

    scanf("%d",&K);
    int p[N];
    int min[N];
    int sum=0;
    int tmp;
    
    for (int i=0;i<N;i++){
        scanf("%d",&p[i]);
    }

    for (int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(p[i]>p[j]){
                tmp = p[i];
                p[i] = p[j];
                p[j] = tmp;

            }
        }
    }










    /*for(int j=K;j<N;j++){
        for (int k=0;k<K;k++){
            if((p[j]>=min[k])&&(p[j]<=min[k+1])){
                mins = min[k+1];
                min[k+1] = p[j];
                for (int x=k+2;x<K;x++){
                    min[x] = mins;
                    mins = min[x+1];
                }
            }

    
        }
    }
    */
    
    for (int i=0;i<K;i++){  
        //printf(" %d ",min[i]);
        sum += p[i];
    }

    printf("%d",sum);
    return 0;
}

Measured memory_bytes: 1704
// Template
#include <bits/stdc++.h>
//#include <atcoder/all>
#define rep_override(x, y, z, name, ...) name
#define rep2(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep3(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define rep(...) rep_override(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define per(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
//using namespace atcoder;
using ll = long long;
constexpr int inf = 1001001001;
constexpr ll INF = 3003003003003003003LL;
template <typename T> inline bool chmin(T &x, const T &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T> inline bool chmax(T &x, const T &y) {if (x < y) {x = y; return 1;} return 0;}
struct IOSET {IOSET() {cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10);}} ioset;

int main() {
    int n;
    cin >> n;
    int g = 0;
    auto rec = [&](auto f, int x, int y) -> int {
        if (x < y) return 0;
        int z = x / y;
        if (x % y == 0) return z;
        else return f(f, x - z - 1, y);
    };
    rep(i, n) {
        int a, k;
        cin >> a >> k;
        g ^= rec(rec, a, k);
    }
    cout << (g ? "Takahashi\n" : "Aoki\n");
}


Measured memory_bytes: 3688
adjacent = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)

GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# Bidirectional search using breadth-first search
def solve(start):
    if start == GOAL:
        return 0
    # 0: forward, 1: backward
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s

import sys

start = list(map(int, sys.stdin.read().split()))

print(solve(start))

Measured memory_bytes: 13080
def is_prime(n):
  if n == 1:
    return True
  for i in range(2,int(n**0.5) + 1):
    if n % i == 0:
      return False
  return True

x=int(input())
while True:
  if is_prime(x)==True:
    break
  x+=1
print(x)

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

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

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int n;

ll p[100010];
ll l[100010];

ll sum[100010];

ll merge_count(vector<ll> &a){
	int n=a.size();
	if(n<=1)
		return 0;
	ll cnt=0;
	vector<ll> b(a.begin(),a.begin()+n/2);
	vector<ll> c(a.begin()+n/2,a.end());

	cnt+=merge_count(b);
	cnt+=merge_count(c);

	int ai=0,bi=0,ci=0;
	while(ai<n){
		if(bi<b.size()&&(ci==c.size()||b[bi]<=c[ci])){
			a[ai++]=b[bi++];
		}else{
			cnt+=n/2-bi;
			a[ai++]=c[ci++];
		}
	}
	return cnt;
}


int main(void){
	cin >> n;
	rep(i,n) cin >> p[i];
	rep(i,n) cin >> l[i];

	vector<ll> res;

	rep(i,n){
		if(i-1>=0) sum[i]+=sum[i-1];
		sum[i]+=p[i];
		res.pb(sum[i]);
	}

	ll ans=merge_count(res);

	bool ok=true;
	rep(i,n){
		ll cur=res[i];
		if(i-1>=0) cur-=res[i-1];
		if(cur<l[i]) ok=false;
	}
	if(ok)
		cout << ans << endl;
	else
		cout << -1 << endl;
	return 0;
}

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

int main(){
	ll x,k,d;
	cin >> x >> k >> d;

	if(x < 0){
		ll ans1 = (abs(x)%d)*-1;
		ll ans2 =  ans1 + d;
		if(abs(x)/d < k){
			if( (abs(x)/d) %2 == k%2) cout << abs(ans1) << endl;
			else cout << abs(ans2) << endl;
		}
		else{
			cout << abs(x+k*d);
		}
	}
	else{
		ll ans1 = x%d;
		ll ans2 = ans1 -d;
		if(abs(x)/d < k){
			if((x/d)%2 == k%2)cout << abs(ans1) << endl;
			else cout << abs(ans2) << endl;
		}
		else{
			cout << abs(x - k*d) << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 3596
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	count := 0
	for i := 1; i < 10; i++ {
		for j := 1; j < 10; j++ {
			if i*j == n {
				count++
			}
		}
	}
	if count > 0 {
		fmt.Print("Yes")
	} else {
		fmt.Print("No")
	}
}


Measured memory_bytes: 1772
#include <stdio.h>
int main (){
int a,b,c,d;
while (1){
scanf ("%d %d %d\n",&a,&b,&c);
d=a+b;
if (a==-1&&b==-1&&c==-1) {break;}
else if (a<0||b<0){printf ("F\n");}
else {
if (d>=80) {printf ("A\n");}
else if (d>=65) {printf ("B\n");}
else if (d>=50) {printf ("C\n");}
else if (d>=30) {
if (c>=50){printf ("C\n");}
else {printf ("D\n");}
}
else if (d<30) {printf ("F\n");}
}
}
return 0;
}


Measured memory_bytes: 2144
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int w[100],v[100];
const ll INF =1e18;
template<typename T>
void min_self(T& x,T y)
{
	if(y<x)x=y;
}
template<typename T>
void max_self(T& x,T y)
{
	if(y>x)x=y;
}
int main()
{
	int n,W;
	cin>>n>>W;
	int sum_value=0;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
		sum_value+=v[i];
	}
	vector<ll> dp(sum_value+1,INF);
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int val=sum_value;val>=v[i];val--)
		{
			min_self(dp[val],dp[val-v[i]]+w[i]);
		//	cout<<dp[val]<<" ";
		}
	//	cout<<"\n";
	}
	ll ans=0;
	for(int i=0;i<=sum_value;i++)
	{
		if(dp[i]<=W)ans=ll(i);
	}
	cout<<ans;
}

Measured memory_bytes: 1152
lists=[]
while True:
    H,W=map(int,input().split())
    if H==0 and W==0:
        break
    lists.append(H)
    lists.append(W)

j=0
for h in range(len(lists)//2): 
    for i in range(lists[2*j]):
        if i==0:
            for k in range(lists[2*j+1]-1):
                print("#", end='')
            print("#")
        if i!=0 and i!=lists[2*j]-1:
            print("#", end='')
            for k in range(lists[2*j+1]-2):
                print(".", end='')
            print("#")
        if i==lists[2*j]-1:
            for k in range(lists[2*j+1]-1):
                print("#", end='')
            print("#")
    print("")
    j=j+1
    


Measured memory_bytes: 7008
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  cout << setprecision(15) << fixed;
  double l;
  cin >> l;
  double d = l / 3.0;

  cout << d * d * d << endl;

  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

// 111,222,...,999はすべて111の倍数であることを利用
int main() {
    int n; cin >> n;
    // *11以下なら最上位桁-1を，*11を超えるなら最上位桁を取り出したい
    int a = n / 111;
    // nがちょうどゾロ目回でないなら最上位桁は次へ
    if (n % 111 != 0)
    {
        a++;
    }
    // 最上位桁*111が次に参加する回
    cout << a*111 << endl;
    return 0;
}

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

  
int main() {
  int x,n;
  cin >> x >> n;
  vector<int> a(n);
  rep(i,n) cin >> a.at(i);
  bool ans;
  int t = x;
  while(true){
    rep(i,n){
      if(t == a.at(i)) ans = false;
    }
    if(ans) break;
    ans = true;
    t++;
  }
  int s = x;
  while(true){
    rep(i,n){
      if(s == a.at(i)) ans = false;
    }
    if(ans) break;
    ans = true;
    s--;
  }
   if(x-s == t-x) cout << s << endl;
   else if(x-s < t-x) cout << s << endl;
   else cout << t << endl;
  }


Measured memory_bytes: 3632
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

answer = np.inf
for p in range(100):
    a = 0
    for x in X:
        a += (x - p) ** 2
    if answer > a:
        answer = a
print(answer)



Measured memory_bytes: 12484
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
	int n; cin >> n;
	vector<int> av;
	for(int i = 0; i < n; i++){
		int a; cin >> a;
		av.push_back(a);
	}

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

	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

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

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  ll ans=LLONG_MAXs;
  //ll ans=0;
  ll N,K;
  cin>>N>>K;

  ll A[N];
  FOR(i,0,N-1){
    cin>>A[i];
  }
  FOR(i,0,N-K){
    ll syou,dai;
    syou = A[i];
    dai = A[i+K-1];
    ll tmp;
    if(syou*dai<=0){
      tmp=min(-syou+dai*2,-syou*2+dai);
    }else{
      tmp=max(-syou,dai);
    }
    ans=min(ans,tmp);
  }



cout<<ans<<endl;
return 0;

}
 


Measured memory_bytes: 1024
#include <iostream>
#include<string>

using namespace std;

int main() {
	string s;
	cin >> s;
	int counter = 0;
	if (s[0] == 'o')counter++;
	if (s[1] == 'o')counter++;
	if (s[2] == 'o')counter++;
	cout << 700 + counter * 100 << endl;
	return 0;
}

Measured memory_bytes: 256
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    int a,b,c,d;
    a=s[0]-'0';
    b=s[1]-'0';
    c=s[2]-'0';
    d=s[3]-'0';
    if(a+b+c+d==7) cout << a << '+' << b << '+' << c << '+' << d << "=7" << endl;
    else if(a-b+c+d==7) cout << a << '-' << b << '+' << c << '+' << d << "=7" << endl;
    else if(a+b-c+d==7) cout << a << '+' << b << '-' << c << '+' << d << "=7" << endl;
    else if(a+b+c-d==7) cout << a << '+' << b << '+' << c << '-' << d << "=7" << endl;
    else if(a-b-c+d==7) cout << a << '-' << b << '-' << c << '+' << d << "=7" << endl;
    else if(a+b-c-d==7) cout << a << '+' << b << '-' << c << '-' << d << "=7" << endl;
    else if(a-b+c-d==7) cout << a << '-' << b << '+' << c << '-' << d << "=7" << endl;
    else cout << a << '-' << b << '-' << c << '-' << d << "=7" << endl;
}

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

int H, W, K;
int ans=0;

int main() {
    cin >> H >> W >> K;
    vector <string> c(H);
    vector <string> cp(H);
    for (int i=0; i<H; i++) cin >> c.at(i);
    for (int bit=0; bit<pow(2, H+W); bit++) {
        // bit = 0000 = 0
        cp = c;
        for (int i=0; i<(H+W); i++) { // bit走査
            if(!(bit & (1<<i))) continue;// iビット目が0
            if (i<W) { // 列を消す
                for (int k=0; k<H; k++) cp.at(k).at(i) = '*';
            }
            else { // 行を消す
                for (int k=0; k<W; k++) cp.at(i-W).at(k) = '*';
            }
        }
        int cnt=0;
        for (int i=0; i<H; i++) { // カウント
            for (int j=0; j<W; j++) {
                if (cp.at(i).at(j)=='#') cnt++;
            }
        }
        if (cnt==K) ans++;
    }
    cout << ans;
}

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

using namespace std;

int main(){
  string str;cin>>str;
  int n;cin>>n;
  vector<string> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  int ans=0;
  for(int i=0;i<n;i++){
    int num=0,cnt=0;
    string vstr = v[i]+v[i];
    for(int j=0;j<vstr.size();j++){
      if(str[num]==vstr[j]){
        num++;
        cnt++;
      }else if(vstr[j]==vstr[j-1]){

      }else{
        num=0;
      }
      if(num==str.size()){
        ans++;
        break;
      }
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;

const ll MOD = 1e9 + 7;

vvi matmul(const vvi& a, const vvi& b) {
    int n = a.size();
    vvi ans(n, vi(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                ans[i][k] = (ans[i][k] + 1ll*a[i][j]*b[j][k]) % MOD;
            }
        }
    }
    return ans;
}

vvi matpow(vvi x, ll k) {
    int n = x.size();
    vvi ans(n, vi(n));
    for (int i=0; i<n; i++) {
        ans[i][i] = 1;
    }
    for (; k; k/=2) {
        if (k % 2) {
            ans = matmul(ans, x);
        }
        x = matmul(x, x);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vvi adj(n, vi(n));
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> adj[i][j];
        }
    }
    adj = matpow(adj, k);
    int ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            ans = (ans + adj[i][j]) % MOD;
        }
    }
    cout << ans << '\n';
}


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

int main() {
    int N, ans=0;
    string S;
    cin >> N;
    cin >> S;
    for(int i=0; i<10; i++){
	for(int j=0; j<10; j++){
	    for(int k=0; k<10; k++){
		int cnt=0;
		for(int l=0; l<N; l++){
		    int a[3]={i, j, k};
		    if(S[l]=='0'+a[cnt])
			cnt++;
		    if(cnt==3){
			ans++;
			break;
		    }
		}
	    }
	}
    }
    cout << ans << endl;
}



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

using namespace std;

int main()
{
	string str;
	string d;
	int cont = 0;
	int n;
	
	cin >> str >> n;
	
	vector<string> data(n);
	
	for(int i = 0; i < n; i++){
		cin >> data[i];
	}
	
	for(int i = 0; i < n; i++){
		data[i] += data[i];
		string::size_type isFind = data[i].find(str);
		if(isFind != string::npos){
			cont++;
		}
	}
	
	cout << cont << endl;
	
}

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



int main(){
	int N,K;cin >> N >> K;
  int A0[N];
	vector<int> V0, V1;
	int fc=0, bc=0;
	int tmp;
  //1で配列をSplitする。その時1は複製する
	for(int i=0;i<N;i++){
		cin >> A0[i];
		fc++;
		tmp = i;
		if(A0[i] ==1) break;
	}

	//１の分をIncrementしてから残りも数える。
	bc++;
	for(int i=tmp+1;i<N;i++){
		cin >> A0[i];
		bc++;
	}

	int ans =0;
	//前の計算
	// cout << fc << endl;
	// if(fc > 1){
	// 	ans++;
	// 	fc -=K;
	// 	while(fc>0){
	// 		fc-=K-1;
	// 		ans++;
	// 	}
	// }
	// cout << ans << endl;
	//後ろの計算
	// if(bc > 1){
	// 	ans++;
	// 	bc -=K;
	// 	while(bc>0){
	// 		bc-=K-1;
	// 		ans++;
	// 	}
	// }
	ans = (N-1)/(K-1);
	if((N-1)%(K-1) != 0)ans++;
	cout << ans << endl;
  return 0;
  // そしたら二つの配列の長さをa0.a1,としたら
  // a0/N + a1/N わりきれない場合はインクリメント

}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H=0,W=0;
  cin >> H >> W;
  char board[H][W];
  for (int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin >> board[i][j];
    }
  }
  int dH[]={1,0,-1,0};
  int dW[]={0,1,0,-1};
 
  bool judge = true;
  
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){

      if(board[i][j]=='#'){
        
          bool flg=false;

         for(int k=0;k<4;k++){
          int x=i+dH[k];
          int y=j+dW[k];
           
          if(x>=0 && x<H && y>=0 && y<W && board[x][y]=='#'){
           flg = true; 
          }
         
        }
         if(!flg){
            judge=false;
         }
           
        
      }
      
    }
  }
  
  if(judge){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    using namespace std;
    
    int main(){
      int ans = 0;
      string str;
      cin >> str;
      for(int i = 0 ; i < str.length() ; i++){
          if(str[i] == 'x') ans += 1;
      }
      if(ans >= 8){
          cout << "NO" << endl; 
      }else{
          cout << "YES" << endl; 
      }
      
      return 0;
    }

Measured memory_bytes: 256
while True :
    try :
        lst = list(input().split())
    except EOFError :
        break
    
    stack = []
    for i in lst :
        if i == '+' :
            b = stack.pop(-1)
            a = stack.pop(-1)
            stack.append(a+b)
        elif i == '-' :
            b = stack.pop(-1)
            a = stack.pop(-1)
            stack.append(a-b)
        elif i == '*' :
            b = stack.pop(-1)
            a = stack.pop(-1)
            stack.append(a*b)
        elif i == '/' :
            b = stack.pop(-1)
            a = stack.pop(-1)
            stack.append(a/b)
        else :
            stack.append(int(i))
    print('{:.8f}'.format(stack[0]))


Measured memory_bytes: 5612
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  int base=a%b;
  for(int i=1;i<=b;i++){
    if((base*i)%b==c){
      cout<<"YES";
      return 0;
    }
  }
  cout<<"NO";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp(a,b) (make_pair((a),(b)))
using namespace std;

int k;

const int N = 1e5+5;

int ne[2*N],we[2*N],to[2*N];//注意数组越界 
int fi[2*N];

int cnt;
void add(int u, int v, int w)
{
//	cout << u << ' ' << v <<' ' << w << endl;
	to[++cnt] = v;
	we[cnt] = w;
	ne[cnt] = fi[u];
	fi[u] = cnt;
//	printf("fi[%d]=%d\n", u,fi[u]);
//	system("pause");
}

int d[N];

deque<pair<int,int> > dq;

bool vis[N];

int main()
{
	cin >> k;
	for(int i = 0; i < k; i++)
	{
		if(i%10 != 9)
			add(i,(i+1)%k,1);
		add(i,(10*i)%k, 0);
//		if(fi[1] != 4)
//			cout << "!" << fi[1] << endl;
	}
	
	memset(d,0x3f,sizeof(d));

	dq.push_front(mp(1,1));
	
	
	while(!dq.empty()) //01bfs不能刷表实现 
	{
		auto cur = dq.front();
		int x = cur.first;
		dq.pop_front();
		if(vis[x]) continue;
		vis[x] = 1;
		d[x] = cur.second; 
		for(int i = fi[x]; i; i=ne[i])
		{
			int y = to[i];
 
			if(we[i] == 0)
			{
				dq.push_front(mp(y,d[x]+we[i]));
			}
			else
			{
				dq.push_back(mp(y,d[x]+we[i]));
			}
		}
		
	}
 	
	int ans = d[0];
	
	cout << ans << endl;
	return 0;
}

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

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

#define INF 1e9
constexpr int maxd = 500010;
int dp[maxd];

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> c(m);
  REP(i, m){
    cin >> c[i];
  }
  REP(i, n+1){
    dp[i] = INF;
  }
  dp[0] = 0;
  REP(i, m){
    REP(j, n+1){
      dp[j+c[i]] = min(dp[j+c[i]], dp[j]+1);
    }
  }
  cout << dp[n] << endl;
  return 0;
}



Measured memory_bytes: 3320
# ABC094B - Toll Gates
from bisect import bisect_left


def main():
    n, m, x = list(map(int, input().rstrip().split()))
    lst = sorted(list(map(int, input().rstrip().split())))
    cur = bisect_left(lst, x)
    print(min(cur, m - cur))


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
using namespace std;
int n,l[200],ans;
main(){
    cin>>n;
    for(int i=0;i<2*n;i++)cin>>l[i];
    sort(l,l+2*n);
    for(int i=0;i<n;i++)ans+=l[2*i];
    cout<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  map<int, int> mp;
  
  for(int i=0; i<n; i++){
    int p; cin >> p;
    mp[p]++;
  }
  
  int ans=0;
  for(auto itr=mp.begin(); itr != mp.end(); itr++){
    ans++;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n,m,k;
  cin >> n >> m >> k;
  ll a[n],b[m];
  rep(i,n) R a[i];
  rep(i,m) R b[i];
  ll ans=0;
  ll s1=0,s2=0,r=m-1;
  rep(i,m) s2+=b[i];
  rep(i,n+1) {
    while(r>=0&&s1+s2>k) {
      s2-=b[r];
      r--;
    }
    if(s1+s2<=k) ans=max(ans,i+r+1);
    if(i<n) s1+=a[i];
  }
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 6776
#include <iostream>
#include <list>

int main()
{
	int A, B, C;
	std::cin >> A >> B >> C;

	int weekCoin = 7 * A + B;

	int weekNum = C / weekCoin;

	C -= weekNum * weekCoin;

	int dayNum =0;
	if (C / A >= 7) dayNum = 7;
	else dayNum = C / A + ((C%A) ? 1 : 0);
	
	
	std::cout << weekNum * 7 + dayNum << std::endl;

    return 0;
}



Measured memory_bytes: 3096
n, x = map(int, input().split())
A = [int(i) for i in input().split()]

cnt = 0
if A[0] > x:
    cnt = A[0] - x
    A[0] = x
for i in range(n - 1):
    if A[i] + A[i + 1] > x:
        cnt += A[i] + A[i + 1] - x
        A[i + 1] -= A[i] + A[i + 1] - x
        
print(cnt)

Measured memory_bytes: 14472
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Q = list(map(int, input().split()))
A.sort()

lst = []
for i in range(2**n):
    num = 0
    for j in range(n):
        if((i >> j) & 1):
            num += A[j]
    lst.append(num)

lst = set(lst)
for i in range(q):
    if(Q[i] in lst):
        print("yes")
    else:
        print("no")


Measured memory_bytes: 43084
# B
A, B, M = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = 10**5*2
for i in range(M):
    x, y, c = list(map(int, input().split()))
    tmp = (a[x-1] + b[y-1] - c)
    if tmp < ans:
        ans = tmp

ans = min(ans, min(a)+min(b))
print(ans)

Measured memory_bytes: 18736
#include <iostream>
#include <iomanip>

int main()
{
    double a, b;

    std::cin >> a >> b;
    
    std::cout << std::fixed <<  static_cast<long long>(a)/static_cast<long long>(b) << ' ' << static_cast<long long>(a) % static_cast<long long>(b) << ' ' << std::setprecision(15) << a * (1.0 / b) <<  std::endl;

    return 0;
}



Measured memory_bytes: 3284
n = int(input())
a = list(map(int, input().split()))

result = 0
has_odd_number = False
while True:
    for i in range(n):
        if a[i] % 2 != 0:
            has_odd_number = True
            break
        a[i] //= 2

    if has_odd_number:
        break
    else:
        result += 1

print(result)


Measured memory_bytes: 2940
using System;
using System.Linq;

namespace AtCoder190804_E
{
    class Program
    {
        static void Main()
        {
            string[] input = Console.ReadLine().Split();
            int k = int.Parse(input[0]);
            int x = int.Parse(input[1]);

            string[] res = Enumerable.Range(x - (k - 1), 2 * k - 1).Select((n)=>n.ToString()).ToArray();
            Console.WriteLine($"{string.Join(" ", res)}");
        }
    }

}

Measured memory_bytes: 13396
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

k, x = MAP()
if 500 * k >= x:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 60652
s = list(input())
t = list(input())
cou = 0
ans = len(t)
for i in range(len(s)-len(t)+1):
    moji = s[i:i+len(t)]
    #print(moji)
    for j in range(len(t)):
        if t[j] != moji[j]:
            cou += 1
    if ans > cou:
        ans = cou
        if ans == 0:
            break
    cou = 0
print(ans)

Measured memory_bytes: 9132
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vpll vector<pll>
#define vpii vector<pii>
#define pb push_back
#define eb emplace_back
#define mt make_tuple
#define MP make_pair
#define fs first
#define sc second
#define F first
#define S second
#define nl "\n"
#define asche cerr<<"Ekhane asche\n";
#define pf printf
#define sf scanf
#define mem(a,x) memset(a,x,sizeof(a))
#define SZ(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define one(x) __builtin_popcount(x)
#define fout(x) fixed<<setprecision(x)
#define BeatMeScanf ios_base::sync_with_stdio(false)
//int dx[]={1,0,-1,0,1,-1,-1,1};
//int dy[]={0,1,0,-1,1,1,-1,-1};
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); deb(_it, args); }
void deb(istream_iterator<string> it) {}
template<typename T, typename... Args>
void deb(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    deb(++it, args...);
}
//template <typename T> using o_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
namespace IO
{
    #define in() ( { int a ; scanf("%d",&a); a; } )
    #define LL() ( { ll a ; scanf("%lld",&a); a; } )
    #define ULL() ( { ull a ; scanf("%llu",&a); a; } )
    #define DD() ({ double a; scanf("%lf", &a); a;})
    #define CC() ( { char a ; scanf("%c",&a); a; } )
    #define pf1(a) printf("%d\n",a)
    #define pf1ll(a) printf("%lld\n",a)
}
using namespace IO;

const int mod=1e9+7;
const int N=3e5+9;
const double eps=1e-9;
const double PI=acos(-1.0);
ll qpow(ll n,ll k) {ll ans=1;assert(k>=0);n%=mod;while(k>0){if(k&1) ans=(ans*n)%mod;n=(n*n)%mod;k>>=1;}return ans%mod;}

vi g[N];
int dfs(int u,int pre)
{
    int ans=0;
    for(auto v:g[u]) if(v!=pre) ans^=(1+dfs(v,u));
    return ans;
}
int32_t main()
{
    int n=in();
    for(int i=1;i<n;i++){
        int u=in(),v=in();
        g[u].eb(v);
        g[v].eb(u);
    }
    int ans=dfs(1,0);
    if(ans) puts("Alice");
    else puts("Bob");
    return 0;
}
///Before submit=>
///    *check for integer overflow,array bounds
///    *check for n=1


Measured memory_bytes: 15104