akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
    ll n;
    cin>>n;
    ll b[200001]={0},x;
    for (ll i=1;i<n;i++){
        cin>>x;
        b[x]++;
    }
    for (ll i=1;i<=n;i++){
        cout <<b[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 5192
#include <iostream>
using namespace std;
 
int N, M, Q, p[509][509];
int main() {
	cin >> N >> M >> Q;
	for (int i = 1; i <= M; i++) { int L, R; cin >> L >> R; p[L][R]++; }
	for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) p[i][j] += p[i][j - 1]; }
	for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) p[i][j] += p[i - 1][j]; }
 
	for (int i = 1; i <= Q; i++) {
		int L, R; cin >> L >> R;
		cout << p[R][R] + p[L - 1][L - 1] - p[L - 1][R] - p[R][L - 1] << endl;
	}
	return 0;
}

Measured memory_bytes: 1920
#include<stdio.h>
#include<string.h>

int main (void)
{
    int i, n;
    double a,s=0;
    char c[3];

    scanf("%d",&n);
    for(i=0;i<n;i++){
    scanf("%lf",&a);
    scanf("%s",c);
    if(strcmp(c,"BTC")==0)
    s=s+380000.0*a;
    else if(strcmp(c,"JPY")==0)
    s=s+a;
    }
    printf("%lf\n",s);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using i64 = long long;
using Matrix = std::vector<std::vector<i64>>;

const i64 mod = 1000000007;
int n;

void mul(Matrix &m, const Matrix p) {
    Matrix ret(n, std::vector<i64>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                ret[i][j] = (ret[i][j] + m[i][k] * p[k][j] % mod) % mod;
            }
        }
    }
    std::swap(m, ret);
}

int main() {
    i64 k;
    std::cin >> n >> k;
    Matrix mat(n, std::vector<i64>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        std::cin >> mat[i][j];
    }

    Matrix ret(n, std::vector<i64>(n));
    if (k % 2) ret = mat;
    else for (int i = 0; i < n; i++) ret[i][i] = 1;
    for (int i = 1; (1ll << (i64)i) <= k; i++) {
        mul(mat, mat);
        if (!(k & 1ll << (i64) i)) continue;
        mul(ret, mat);
    }

    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) std::cout << ret[i][j] << " ";
    //     std::cout << '\n';
    // }

    i64 out = 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) out = (out + ret[i][j]) % mod;
    std::cout << out << std::endl;

    return 0;
}

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

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

    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<int> ans(n+1);
    for (int i = n; i >= 1; i--) {
        int m = 0;
        for (int j = 2; i * j <= n; j++) m += ans[i * j];
        if (m % 2 != a[i]) ans[i] = 1;
    }

    cout << accumulate(begin(ans), end(ans), 0) << endl;
    for (int i = 1; i <= n; i++) if (ans[i]) cout << i << " ";
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
typedef pair<int, int> P;

int main(){
  unsigned long long N;
  cin >> N;

  stack<unsigned long long> Nums;

  while(N >= 26){
    N--;//各桁に対して1-26を0-25に変換
    Nums.push(N%26);
    N /= 26;
  }
  if(N != 0){
    N--;
    Nums.push(N);
  }

  char a;
  while(!Nums.empty()){
    a = 'a' + (char)Nums.top();
    Nums.pop();
    cout << a;
  }

  cout << endl;
}


Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int n, d[3003][3003];
string s;
int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) d[1][i] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i - 2] == '<')
            for (int j = 1; j <= n - i + 1; j++)
                d[i][j] = (d[i][j - 1] + d[i - 1][j]) % 1000000007;
        else
            for (int j = n - i + 1; j; j--)
                d[i][j] = (d[i][j + 1] + d[i - 1][j + 1]) % 1000000007;
    }
    cout << d[n][1] << '\n';
}


Measured memory_bytes: 35200
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int n;
	cin>>n;
	int K;
	cin>>K;
	map<int,int> ma;
	rep(i,n){
		int t;
		cin>>t;
		ma[t]++;
	}
	vint cnt;
	for(auto x: ma){
		cnt.PB(x.se);
	}
	sort(ALL(cnt));
	int ans = 0;
	if(cnt.size()>K) rep(i,cnt.size()-K){
		ans += cnt[i];
	}
	cout<<ans<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Measured memory_bytes: 10744
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N; cin >> N;
	int B[N-1];
	for(int i = 0; i < N; i++) cin >> B[i];
	int A[N];
	A[0] = B[0], A[N-1] = B[N-2];
	for (int i = 1; i < N-1; i++)
	{
		A[i] = min(B[i-1], B[i]);
	}
	int res = 0;
	for (int i = 0; i < N; i++)
	{
		res += A[i];
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define repr(i, n) for(int i=n-1; i>=0; i--)
#define repr1(i, n) for(int i=n; i>=1; i--)
#define all(v) v.begin(),v.end()
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 500010;

struct BinaryIndexedTree {
    int n;
    vector<int> bit;

    BinaryIndexedTree(int _n) {
        n = _n;
        bit.resize(_n+1);
    }

    void add(int i, int x) {
        while (i <= n) {
            bit[i] += x;
            i += i & -i;
        }
    }

    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }

    int getSum(int i, int j) {
        return sum(j) - sum(i-1);
    }
};

int n, q;
int c[MAX], good[MAX], ans[MAX];
vector<int> ql[MAX], qid[MAX];

int main() {
    cin >> n >> q;
    rep1(i, n) cin >> c[i];
    rep(i, q) {
        int l, r; cin >> l >> r;
        ql[r].push_back(l);
        qid[r].push_back(i);
    }

    BinaryIndexedTree BIT(n);

    rep1(i, n) {
        if (good[c[i]] > 0) BIT.add(good[c[i]], -1);
        BIT.add(i, 1);
        good[c[i]] = i;
        rep(j, ql[i].size()) {
            ans[qid[i][j]] = BIT.getSum(ql[i][j], i);
        }
    }
    rep(i, q) cout << ans[i] << endl;
}


Measured memory_bytes: 52964
def show(A):
    for i in range(N):
        if i<N-1:
            print(A[i],end=' ')
        else:
            print(A[i])

N=int(input())
A=list(map(int,input().split()))
count=0
flag=True
while flag:
    flag=False
    for j in reversed(range(1,N)):
        if A[j-1]>A[j]:
            A[j-1],A[j]=A[j],A[j-1]
            count+=1
            flag=True
show(A)
print(count)


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

using namespace std;

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long a,b;
    cin>>a>>b;
    long long p;
    p=(a*b)/__gcd(a,b);
    cout<<p;


    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream> //入出力
#include <stdio.h>
#include <map>
#include <set>
#include <string>
#include <math.h> //算術演算子
#include <vector>
#include <cstdlib>
#include <queue>
#include <stack>
#include <list>
#include <iomanip> //小数点以下を表示させる(setprecision())
//#include <bits/stdc++.h>
using namespace std;
typedef long long ll; //64bit型

#define debug(x) cerr << x << " " \
                      << "(L:" << __LINE__ << ")" << '\n'
#define PRINT(V)                                   \
        {                                          \
                for (int i = 0; i < V.size(); i++) \
                {                                  \
                        cout << V[i] << " ";       \
                }                                  \
                cout << endl;                      \
        }

int gcd(int a, int b)
{
        return b ? gcd(b, a % b) : a;
}

int main()
{
        //input->compute->output//

        int A, B, C;
        cin >> A >> B >> C;
        if (C <= B)
        {
                cout << "delicious" << endl;
        }
        else if (C - B <= A)
        {
                cout << "safe" << endl;
        }
        else
        {
                cout << "dangerous" << endl;
        }

        return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace atcoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var N = int.Parse(Console.ReadLine());
            var list = new Dictionary<string, string>();
            for (int i = 0; i < N; i++)
                list[Console.ReadLine()] = "";

            Console.WriteLine(list.Count);
        }
    }
}


Measured memory_bytes: 49888
N, M = map(int ,input().split())
X = list(map(int, input().split()))

X.sort()

subs = []
for i in range(M-1):
    subs.append(X[i+1]-X[i])
subs.sort()
if N == 1:
    print(sum(subs))
    exit()
print(sum(subs[:-(N-1)]))


Measured memory_bytes: 20576
from collections import Counter
n=int(input())
a=[input() for _ in range(n)]
cal=Counter(a)
#print(cal)
m=0
for i in cal.keys():
    val=cal[i]
    m=max(m,val)
#print(val)
ans=[]
for i in cal.keys():
    val=cal[i]
    if val==m:
        ans.append(i)
ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 35572
#include<stdio.h>
int MIN(int a,int b){return a<b?a:b;}
int MAX(int a,int b){return a<b?b:a;}
int main(){
  int a,b,c;
  scanf("%d %d %d",&a,&b,&c);
  printf("%d\n",MAX(a,MAX(b,c))-MIN(a,MIN(b,c)));
  return 0;
}


Measured memory_bytes: 128
N, K = map(int, input().split())

sunuke = [0 for _ in range(N)]
D = []
A = [[] for _ in range(K)]
for k in range(K):
    D.append(int(input()))
    A[k] = list(map(int, input().split()))
    for a in A[k]:
        sunuke[a-1] += 1

print(sunuke.count(0))

Measured memory_bytes: 67860
N, M = map(int, input().split())
ab = []
for _ in range(M):
    ab.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in ab:
    a, b = el
    G[a].append(b)
    G[b].append(a)

#print(G)
cnt = 0
seen=[False] * (N + 1)
def dfs(parent):
    global cnt
    seen[parent] = True
    if seen.count(True) == N:
        cnt += 1
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)
            seen[child] = False
dfs(1)
print(cnt)



Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
//#define mt make_tuple
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e9;
const ll INF=2e18;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	vi dp(1000010,inf);
	vi dp2(1000010,inf);
	dp[0]=dp2[0]=0;
	loop(i,1,180)rep(j,1000010){
		int t=i*(i+1)*(i+2)/6;
		if(j+t<1000010)dp[j+t]=min(dp[j+t],dp[j]+1);
		if(t%2&&j+t<1000010)dp2[j+t]=min(dp2[j+t],dp2[j]+1);
	}
	int n;
	while(cin>>n,n)cout<<dp[n]<<" "<<dp2[n]<<endl;
}

Measured memory_bytes: 10532
N = int(input())

SP = []
for i in range(N):
    tmp = list(map(str, input().split()))
    tmp[1] = int(tmp[1])
    tmp.append(i+1)
    SP.append(tmp)

SP = sorted(SP, key=lambda x: (x[0], -x[1]))

for sp in SP:
    print(sp[2])


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
import math

# 整数の入力
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

list=[A,B,C,D,E]
last=0
max_rest=0

#余りが一番でかいのを最後に頼めば良い。
#他はX/10を切り上げて*10したとなる。
for i, time in enumerate(list):
  #print(time,":",i)
  if time%10 != 0 and 10 - time%10 > max_rest:
    max_rest = 10 - time%10
    last=i

ans=0
    
for i, time in enumerate(list):
  if i != last:
    ans = ans + 10 * math.ceil(time/10)
  elif i == last:
    ans = ans + time
    
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

int main(){
    char s[4];
    cin >> s;
    sort(s, s+4);
    if(s[0] == s[1] && s[2] == s[3] && s[0] != s[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

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

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

mint comb(int n, int k) {
    mint x = 1;
    mint y = 1;
    rep(i,k) {
        x *= n-i;
        y *= i+1;
    }
    return x/y;
}

int n, k;
int blue, red;

mint solve(int i) {
    int x = blue - i;    // 自由に配れる青玉の数
    int y = red - i + 1; // 自由に配れる赤玉の数
    if (x < 0 || y < 0) return mint(0);

    return comb(x+i-1, x) * comb(y+i, y); 
}

int main() 
{
    cin >> n >> k;
    blue = k;
    red = n-k;

    for (int i=1; i<=k; i++) {
        cout << solve(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

count = N // min(A,B,C,D,E)
if N % min(A,B,C,D,E) == 0:
    count -= 1
print(count+5)

Measured memory_bytes: 3064
S = input()


if int(S[:2]) >= 1 and int(S[:2]) <= 12:
    if int(S[2:]) >= 1 and int(S[2:]) <= 12:
        print("AMBIGUOUS")
    else:
        print("MMYY")
        
else:
    if int(S[2:]) >= 1 and int(S[2:]) <= 12:
        print("YYMM")
    else:
        print("NA")


Measured memory_bytes: 2940
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int a[] = new int[n];
		for (int i=0; i<n; i++){
			a[i] = scanner.nextInt()-(i+1);
		}
		Arrays.sort(a);
		int center;
		if (n%2==0){
			center = (a[n/2-1]+a[n/2])/2;
		}else {
			center = a[(n+1)/2-1];
		}
		long ans = Long.MAX_VALUE;
		for (int d=-2; d<=2; d++){
			long anscand = 0;
			for (int i=0; i<n; i++) {
				anscand += Math.abs(a[i]-(center+d));
			}
			ans = Math.min(ans, anscand);
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 66560
#!/usr/bin/env python
n, D = map(int, input().split())
X = [[int(i) for i in input().split()] for i in range(n)]

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        sum_ = 0
        for d in range(D):
            sum_ += pow((X[i][d] - X[j][d]), 2)
        a = isqrt(sum_)
        if a * a == sum_:
            cnt += 1
print(cnt)

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


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
#define all(v) v.begin(),v.end()
#define endl "\n"
#define clr(n, r) memset(n,r,sizeof(n));

void fast() {
    cin.tie(0);
    cin.sync_with_stdio(0);
}


int main() {
    fast();
    ll n,k;cin>>n>>k;
    ll ans=k;
    for (int i = 0; i <n-1 ; ++i) {
        ans*=(k-1);
    }
    cout<<ans;
}

Measured memory_bytes: 256
def main():
    A,B,M = map(int,input().split())
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))
    # c = [[-1 for i in range(2)] for j in range(A)]
    c = []

    for i in range(M):
        cc = list(map(int,input().split()))
        c.append(cc)
    a_min = min(a)
    b_min = min(b)
    ans = a_min + b_min
    for i , c_i in enumerate(c):
        tmp = a[c_i[0]-1] + b[c_i[1]-1] - c_i[2]
        ans = min(ans,tmp)
    # for i, a_i in enumerate(a):
    #     tmp_1 = a_i + b_min
    #     tmp_2 = 10**6
    #     if c[i][0] != -1:
    #          tmp_2 = a_i + b[c[i][0]] - c[i][1]
    #     ans = min(ans,tmp_1,tmp_2)
    print(ans)
if __name__=='__main__':
    main()


Measured memory_bytes: 38564
#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int n,tmp,dp[3][2];

int main()
{Tie
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		{
			dp[j][i&1]=0;
			for(int k=0;k<3;k++)
				if(j!=k)
					dp[j][i&1]=max(dp[j][i&1],dp[k][i&1^1]);
		}
		for(int j=0;j<3;j++)
			cin>>tmp,dp[j][i&1]+=tmp;
	}
	cout << max({dp[0][n&1],dp[1][n&1],dp[2][n&1]})<<'\n';
}

Measured memory_bytes: 256
#include <stdio.h>

int A[1000000],n;

int binarysearch(int key){
    int left=0;
    int right=n;
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(key==A[mid]) return 1;
        if(key>A[mid]) left=mid+1;
        else if(key<A[mid]) right=mid;
    }
    return 0;
}

int main(){
    int i,q,k,sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&A[i]);
    }

    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&k);
        if(binarysearch(k)) sum++;
    }

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

    return 0;
}


Measured memory_bytes: 2176
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    ans = 0

    for i in range(N-1, -1, -1):
        st = B[i]
        a = A[i+1]
        b = A[i]
        if st <= a:
            A[i+1] -= st
            ans += st
            st = 0
        else:
            ans += A[i+1]
            st -= A[i+1]
            A[i+1] = 0

        if st <= b:
            A[i] -= st
            ans += st
            st = 0
        else:
            ans += A[i]
            st -= A[i]
            A[i] = 0

    print(ans)


if __name__ == "__main__":
    resolve()


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

int main(){
	char p[5][6] =
	{{'a','f','k','p','u','z'},
	 {'b','g','l','q','v','.'},
	 {'c','h','m','r','w','?'},
	 {'d','i','n','s','x','!'},
	 {'e','j','o','t','y',' '}};
	string s;	
	while(cin >> s){
		bool flag = false;
		for(size_t i=0;i<s.size();i+=2){
			if(s[i]>'6' || s[i]<'1' || s[i+1]>'5' || s[i]<'1')
				flag = true;
		}
		if(flag||s.size()%2){
			cout << "NA" << endl;
		}else{
			for(size_t i=0;i<s.size();i+=2){
				cout << p[s[i+1]-'0'-1][s[i]-'0'-1];
			}
			cout << endl;
		}
	}
}

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

int main(){
	
	int n, count = 1;
	cin >> n;
	while (true){
		if (n==1 || n== 2 || n==4) {cout << count+3; break;}
		if (n%2==0) n=n/2;
		else n = 3*n+1;
		count++;
		
	}
}



Measured memory_bytes: 256
n,m,c = map(int,input().split())
b=list(map(int,input().split()))
cnt=0

for i in range(0,n):
    sum=0
    a=list(map(int,input().split()))
    for j in range(0,m):
        sum+=b[j]*a[j]
    if sum+c>0:
        cnt+=1

print(cnt)

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

int main2() {
  int K = nextInt();
  int X = nextInt();

  if (X <= 500*K)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
bool isPalin(string s)
{
     string p=s;
    reverse(p.begin(),p.end());
    if(p==s)
    return true;
    else 
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int l;
    cin>>l;
    cout<<setprecision(10)<<fixed<<(l*l*l)/(27.0)<<'\n';
}

Measured memory_bytes: 3724
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
 
#define INF (1e9)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
 

 
int vector_finder(std::vector<int> vec, int number) {
  size_t index = std::distance( vec.begin(), std::find(vec.begin(), vec.end(), number) );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}


int main()
{
	int N, M;
	cin >> N >> M;
	vector<pair<int, int> > mp;
	int A[N]; 
	int B[N];
	REP(i,N){
		cin >> A[i] >> B[i];
		pair<int, int> p = make_pair(A[i], B[i]);
		mp.push_back(p);
	}

	sort(mp.begin(), mp.end());

	ll ans = 0;
	pair<int, int> current = mp[0];
	int idx = 0;
	REP(i, M)
	{
		if(current.second==0){
			current = mp[idx + 1];
			idx++;
		}
		ans += current.first;
		current.second--;
	}
	cout << ans << endl;

	return 0;
}

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


int main(){

    int n;cin>>n;
    vector<int> a(n);
    rep(i,n)cin>>a.at(i);
    int count = 0;

    for(int i = 0;i<n;++i){
        int x = a.at(i);
        while(x%2==0){
            count++;
            x/=2;
        }
    }
    cout<<count<<endl;


}


Measured memory_bytes: 256
/*
INP:
4 4
1 3 2 4
120 90 100
110 50 80
250 70 130
OUT: 550
*/
#include <bits/stdc++.h>
using namespace std;
long long n,m,i,l,r,ans,ct[100005],a[100005],b[100005],c[100005],p[100005];
int main(){
	scanf("%lld%lld",&n,&m);
	for (i=1;i<=m;i++) scanf("%lld",&p[i]);
	for (i=1;i<n;i++) scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
	for (i=1;i<m;i++){
		l=p[i];r=p[i+1];
		while (l!=r){
			if (l<r) {ct[l]++;l++;}
			else {ct[l-1]++;l--;}
		}
	}
	for (i=1;i<=n;i++){
		ans+=min(a[i]*ct[i],c[i]+b[i]*ct[i]);
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 7104
n=int(input())
x=list(map(int,input().split()))
l=[]
while len(x):
    index=-1
    for i,a in enumerate(x):
        if a==i+1:
            index=i
    if index == -1:
        print(-1)
        break
    l.append(x.pop(index))
else:
    for i in reversed(l):
        print(i)

Measured memory_bytes: 3060
#include <iostream>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
 
using namespace std;
typedef long long int ll;
typedef pair <int,int> pii;
typedef pair<ll,ll> pll;
 
 
/*bool compare_function(const pair<int, int> a, const pair<int, int> b)
{
    return a.first < b.first;
}*/
// use case
//sort(V.begin(), V.end(), compare_function);
 
/*struct compare
{
    bool operator ()(const pair<int, int> &a, const pair<int, int> &b) {
    if (a.second-a.first==b.second-b.first)
    {
        return a.first>b.first;
    }
    return a.second-a.first < b.second-b.first;}
};
priority_queue <pair<int,int>, vector <pair<int,int>>, compare> Q;*/
 
void print(vector <ll> X)
{
    for (int i=0; i<X.size(); i++)
    {
        cout<<X[i]<<" ";
    }
    cout<<endl;
    return;
}
 


 bool pos(vector <ll> &A1, vector <ll> &B1, int n, int m, ll c, ll k) {
	 if (c==0) {return true;}
	 if (c<=n && A1[c-1]<=k) {return true;}
	 if (c<=m && B1[c-1]<=k) {return true;}
	 for (int i=1;i<c;i++) {
		 if (i<=n && c-i<=m && A1[i-1]+B1[c-1-i]<=k) {
			 //cout<<c<<" "<<i<<" "<<c-i<<" "<<A1[i-1]<<" "<<B1[c-1-i]<<endl;
			 return true;}
		 }
		return false;
	 }
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    ll k;
    cin>>k;
    vector <ll> A(n,0);
    vector <ll> B(m,0);
    for (int i=0;i<n;i++) {cin>>A[i];}
    for (int i=0;i<m;i++) {cin>>B[i];}
    vector <ll> A1(n,0);
    A1[0]=A[0];
    vector <ll> B1(m,0);
    B1[0]=B[0];
    for (int i=1;i<n;i++) {A1[i]=A1[i-1]+A[i];}
    for (int i=1;i<m;i++) {B1[i]=B1[i-1]+B[i];}
    ll a=0;
    ll b=n+m;
    while (b-a>3) {
		ll c=(a+b)/2;
		if (pos(A1,B1,n,m,c,k)) {a=c;}
		else {b=c;}
		}
	while (!pos(A1,B1,n,m,b,k)) {b--;}
	cout<<b<<endl;
    return 0;
}


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

int main() {
	// your code goes here
	int n;
	cin>>n;
	int arr[n-1];
	for(int i = 0; i < n-1; i++){
		cin>>arr[i];
	}
	int ans[n] = { 0 };
	for(int i = 0; i < n-1; i++){
		ans[arr[i]-1]++;
	}
	for(auto el: ans)
		cout<<el<<" ";
	return 0;
}

Measured memory_bytes: 5152
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define MOD7 1000000007
#define LL_INF 1LL << 60
#define LL_MINF -1LL << 60
#define INT_INF 2000000000
#define INT_MINF -2000000000
#define all(a) (a).begin(), (a).end()
#define fi first
#define se second
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const long double PI = (acos(-1));



int main(){
    int s;
    cin >> s;
    int h = s / 3600;
    s-=3600*h;
    int m = s / 60;
    s-=m*60;
    cout << h << ':' << m << ':' << s << endl;
}


Measured memory_bytes: 3112
package main

import "fmt"

func main() {
	var n, y int
	fmt.Scan(&n, &y)

	for i := 0; i <= n; i++ {
		for j := 0; j+i <= n; j++ {
			sum := 10000*i + 5000*j + 1000*(n-i-j)
			if sum == y {
				fmt.Printf("%d %d %d\n", i, j, n-i-j)
				return
			}
		}
	}
	fmt.Println("-1 -1 -1")
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i, n) for (ll(i) = 0; (i) < (n); (i)++)
#define all(x) (x).begin(), (x).end()
#define print(x) cout << (x) << endl;

typedef long long ll;
const ll INF = 99999999999999;
const ll MOD = 1000000007;

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
ll lcm(ll number1, ll number2)
{
    return number1 * number2 / gcd(number1, number2);
}
template <class T>
bool contain(const std::string &s, const T &v)
{
    // contain(to_string(N), '3')
    return s.find(v) != std::string::npos;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
        return c - '0';
    return 0;
}
using namespace std;

void transpose(vector<vector<char>> &b)
{
    if (b.size() == 0)
        return;

    vector<vector<char>> trans_vec(b[0].size(), vector<char>());

    for (int i = 0; i < b.size(); i++)
    {
        for (int j = 0; j < b[i].size(); j++)
        {
            trans_vec[j].push_back(b[i][j]);
        }
    }

    b = trans_vec; // <--- reassign here
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h, w;
    cin >> h >> w;

    vector<vector<char>> f(h, vector<char>(w));
    vector<vector<char>> ans, ans2;

    rep(i, h)
    {
        rep(j, w)
        {
            cin >> f.at(i).at(j);
        }
    }
    rep(i, h)
    {
        vector<char> a(f[i]);
        sort(all(a));
        if (a.at(0) == '#')
            ans.push_back(f[i]);
    }

    transpose(ans);
    rep(i, w)
    {
        vector<char> a(ans[i]);
        sort(all(a));
        if (a.at(0) == '#')
            ans2.push_back(ans[i]);
    }
    transpose(ans2);

    rep(i, ans2.size())
    {
        rep(j, ans2.at(0).size())
        {
            cout << ans2.at(i).at(j);
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
N = int(input())
S = []
for _ in range(N):
    S.append(int(input()))
sums = sum(S)
if sums % 10 != 0:
    print(sums)
else:
    S.sort()
    for s in S:
        if s % 10 != 0:
            print(sums - s)
            break
    else:
        print(0)

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

using namespace std;


int main()
{
    int num;
    scanf("%d",&num);
    int s = num;
    int cnt=0;
    while (s)
    {
        cnt+=s%10;
        s/=10;
    }
    if(num%cnt==0) printf("Yes");
    else printf("No");
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>

int main(){
  int vecx[100], vecy[100];
  int n;

  scanf("%d", &n);

  for(int i = 0; i < n; i++)scanf("%d", &vecx[i]);
  for(int i = 0; i < n; i++)scanf("%d", &vecy[i]);

  double d[4];
  for( int i = 0; i < 4; i++) d[i] = 0.0;

  for (int p = 1; p < 4; p++ ){
    for ( int i = 0; i < n; i++ ){
      d[p] += pow(fabs(vecx[i]-vecy[i]), p);
    }
    d[p] = pow(d[p], 1.0/p);
  }

  for ( int i = 0; i < n; i++ ){
    d[0] = (d[0] < fabs(vecx[i]-vecy[i])?fabs(vecx[i]-vecy[i]):d[0]);
  }

  printf("%lf\n", d[1]);
  printf("%lf\n", d[2]);
  printf("%lf\n", d[3]);
  printf("%lf\n", d[0]);

  return 0;
}

Measured memory_bytes: 2908
while True:
    m, f, r = map(int, input().split())
    grading = ''
    if m == f == r == -1:
        break
    if m == -1 or f == -1:
        grading = 'F'
    elif m + f >= 80:
        grading = 'A'
    elif m + f >= 65:
        grading = 'B'
    elif m + f >= 50 or r >= 50:
        grading = 'C'
    elif m + f >= 30:
        grading = 'D'
    else:
        grading = 'F'
    print(grading)



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

using lnt = long long;
using Real = long double;

#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(lnt i=0;i<(n);++i)
#define RANGE(i, a, b) for(lnt i=(a);i<(b);++i)
#define RREP(i, n) for(lnt i=(n)-1;i>= 0;--i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define pque priority_queue
#define umap unordered_map
#define uset unordered_set
#define dcout cout<<fixed<<setprecision(20)
#define summon_tourist cin.tie(0);ios::sync_with_stdio(false)

constexpr int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
constexpr Real eps = 1e-9; const Real pi = acosl(-1);
constexpr lnt BIG = INT_MAX/10, BBIG = LLONG_MAX/10;

template<class T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<class T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<class T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<class T> inline T nHr(T a,T b){return nCr(a+b-1,b);}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}

using pint = pair<int, int>; using plnt = pair<lnt, lnt>;
using vint = vector<int>; using vlnt = vector<lnt>;
constexpr lnt MOD = 1e9+7;

int main(){
	summon_tourist;

	lnt X; cin >> X;
	for(lnt A = -200; A <= 200; A++){
		for(lnt B = -200; B <= 200; B++){
			if(pow(A, 5) - pow(B, 5) == X){
				cout << A << ' ' << B << ln;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 4112
#include<stdio.h>
int main(void)
{
	int i,j,n,x,s[53],h[53],c[53],d[53];
	char cc;
	scanf("%d",&n);
	for(j=1;j<=13;j++) {
		s[j]=0;
		h[j]=0;
		c[j]=0;
		d[j]=0;
	}
	for(i=1;i<=2*n;i++) {
		scanf("%c %d",&cc,&x);
		if(cc=='S') {
			for(j=1;j<=13;j++) {
				if(j==x) {
					s[j]++;
				}
			}
		}
		if(cc=='H') {
			for(j=1;j<=13;j++) {
				if(j==x) {
					h[j]++;
				}
			}
		}
		if(cc=='C') {
			for(j=1;j<=13;j++) {
				if(j==x) {
					c[j]++;
				}
			}
		}
		if(cc=='D') {
			for(j=1;j<=13;j++) {
				if(j==x) {
					d[j]++;
				}
			}
		}
	}
	for(j=1;j<=13;j++) {
		if(s[j]==0) {
			printf("S %d\n",j);
		}
	}
	for(j=1;j<=13;j++) {
		if(h[j]==0) {
			printf("H %d\n",j);
		}
	}
	for(j=1;j<=13;j++) {
		if(c[j]==0) {
			printf("C %d\n",j);
		}
	}
	for(j=1;j<=13;j++) {
		if(d[j]==0) {
			printf("D %d\n",j);
		}
	}
	return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<math.h>
#define INF 1000000001
#define EPS 1.0e-6

using namespace std;

typedef long long ll;

int main()
{
	vector<int>prime_number;

	int n;
	cin >> n;
	int a[10500];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int ope = 0;
		for (int j = 2; j*j <= a[i]; j++) {
			if (a[i] % j == 0) { ope = 1; break;}
		}
		if (ope == 0) ans++;
	}
	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl
#define debugvec(v)   rep(i, v.size()) cerr << "L" << __LINE__ << ": " << #v << "[" << i << "] = " << v[i] << endl;
#define debugvec2(v)  cerr << "L" << __LINE__ << ": " << #v << " = { "; rep(i, v.size()) cerr << v[i] << (i + 1 == v.size() ? "" : ", "); cerr << " }" << endl;
typedef long long ll;  /* 10^18 くらいまでいける */

int main(){
  string s,t;
  cin >> s;
  cin >> t;

  int ans = 0;
  rep(i, 3){
    if (s[i] == t[i])
      ans++;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

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

    int ansi = 1;

    rep(i,d) ansi *= 100;

    if(k == 100){
        cout << ansi * 101 << endl;
        return 0;
    }

    cout << ansi * k << endl;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] d = new int[3];
        for (int i = 0 ; i< 3 ; i++) {
            d[i] = sc.nextInt();
        }
        Arrays.sort(d);
        System.out.println(d[1] - d[0] + d[2] - d[1]);

    }

}


Measured memory_bytes: 22612
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
	int n;
	cin>>n;
	ll mod=1e9+7;
	vector<ll>a(n);
	vector<ll>pre(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		if(i==0)
		{
			pre[i]=a[i];
			continue;
		}
		pre[i]=a[i]+pre[i-1];
	}
	ll sum=0;
	for(int i=0;i<n-1;i++)
	{
		ll temp=pre[n-1]-pre[i];
		sum+=((a[i]%mod)*(temp%mod))%mod;
	}
	sum%=mod;
	cout<<sum<<endl;
}
		


Measured memory_bytes: 6364
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
typedef long double LD;

LL inf = 1000000000000;
LL mod = 1000000007;

int main()
{
	string s;
	cin >> s;

	LL x = 0, y = 0;
	for (auto e : s) {
		if (e == 'A') x++; else if (e == 'B') y++;
	}

	if (x && y) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}

}

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

int n, a[400][400], b[400][400], cnt;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char c; cin >> c;
			a[i][j] = (c - 'a' + 1);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) b[j][k] = a[(i + j) % n][k];
		}
		bool OK = false;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (b[j][k] != b[k][j]) OK = true;
			}
		}
		if (OK == false) cnt += n;
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1152
def getInput():
    return [int(i) for i in input().rstrip().split(' ')]

def swap(a, b):
    tmp = a
    a = b
    b = tmp
    return a, b

X, Y, Z = getInput()
X, Y = swap(X, Y)
X, Z = swap(X, Z)
print(X, Y, Z)

Measured memory_bytes: 3060
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
'''
def GI(V,E,DAG=False,index=0):
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[1:])
            bb=(inp[1:])
        g[a].append(b)
        if g[b].append(a)
        h.append(b)
'''

def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()
 
show_flg=False
show_flg=True

ans=0

s,t=LI()
a,c=LI()
b,d=LI()
if a*s+c*t<b*s+d*t:
    a,b,c,d=b,a,d,c
if a*s+c*t==b*s+d*t:
    print('infinity')
    exit()
p,q=(a-b)*s,(c-d)*t
if p>0 and p+q>0:
    print(0)
    exit()

#(p+q)*n+p<0
n=-p//(p+q)
ans=2*n+1
if -p%(p+q)==0:
    ans-=1

print(ans)

Measured memory_bytes: 38764
#include<bits/stdc++.h>
#define ul unsigned long
using namespace std;
int main(){
  cin.tie(0);ios::sync_with_stdio(false);
  ul n;ul tmp; ul m=0;
  cin>>n;
  vector<pair<ul,ul> >l;vector<ul long>ans(n);
  l.reserve(n+1);
  for(ul i=0;i<n;++i){cin>>tmp;l.emplace_back(make_pair(tmp,i));} 
  l.emplace_back(make_pair(0,n));
  stable_sort(l.begin(),l.end(),[](auto a,auto b){return a.first>b.first;});
  for(auto it=l.cbegin(),tar=l.cbegin();it!=l.cend()-1;){
    if(tar->second>it->second)tar=it;
    ans[tar->second]+=(it->first-(++it)->first)*++m;
  }
  for(auto x:ans)cout<< x <<'\n';cout.flush();
  return 0;
}

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

int main() {
  char b;  cin >> b;
  if(b == 'A')  cout << 'T' << endl;
  else if(b == 'T') cout << 'A' << endl;
  else if(b == 'C') cout << 'G' << endl;
  else if(b == 'G') cout << 'C' << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, a, g;
int main() {
	cin>>n>>g;
	while(--n) {
		scanf("%d", &a);
		g = __gcd(g, a);
	}
	cout<<g;
	return 0;
}

Measured memory_bytes: 256
/*****************************************************

Code by: Vichitr
Compiled On: 23rd March 2019

*****************************************************/

#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
#define pb push_back
#define pf pop_front
#define mp make_pair
#define loop(i,n) for(int i=0;i<n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;
#define ip pair<int, int>
#define N 100007
const ll MOD = 1e9+7;
const ll SZ = 107;


signed main()
{
    fast;

    int n;
    cin>>n;
    
    vector<ip> v;
    if(n%2==0)
    {
        int x = 1, y=n;
        int u = 2, w = n-1;
        v.pb({x, u});
        v.pb({x, w});
        v.pb({y, u});
        v.pb({y, w});
        x++, y--;
        for(int i=1;i<n/2-1;i++)
        {
            
            v.pb({x, y-1});
            v.pb({x, x+1});
            v.pb({y, x+1});
            v.pb({y, y-1});
            x++, y--;
        }
        if(n>4)
        {
            v.pb({1, x});
            v.pb({1, y});
            v.pb({n, x});
            v.pb({n, y});
        }
    }
    else{
        if(n==3)
        {
            v.pb({1, 3});
            v.pb({2, 3});
        }
        else{
        int x = 1, y=n-1;
        int u = 2, w = n-2;
        v.pb({x, u});
        v.pb({x, w});
        v.pb({y, u});
        v.pb({y, w});
        x++, y--;
        for(int i=1;i<n/2-1;i++)
        {
            
            v.pb({x, y-1});
            v.pb({x, x+1});
            v.pb({y, x+1});
            v.pb({y, y-1});
            x++, y--;
        }
    
            v.pb({n, x});
            v.pb({n, y});
            v.pb({n, 1});
            v.pb({n, n-1});
        }
    }
    cout<<v.size()<<endl;
    for(auto i: v)
    {
        cout<<i.first<<" "<<i.second<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
N, A, B, C, D = map(int, input().split())

a = N // A
c = N // C

if a * A < N :
    a += 1

if c * C < N :
    c += 1
    
b = a * B
d = c * D

if b < d :
    print(b)
else :
    print(d)


Measured memory_bytes: 5596
import java.util.*;
public class Main
{
    public static void main(String[] args)
    {
        int count = 0;
        boolean sw = false;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        double dMax = Double.MIN_VALUE;
        double dMin = Double.MAX_VALUE;
        //
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        for (int i=0;i<n;++i) a.add(sc.nextInt());

        String ans = "APPROVED";
        for (int i:a)
        {
            if (i%2!=0) continue;

            if (i%3 !=0 && i%5!=0)
            {
                ans = "DENIED";
                break;
            }
        }

        System.out.println(ans);

        sc.close();
    }
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
#define fil(x) memset(x, 0, sizeof(x))
#define fillb(x) memset(x,false,sizeof(x))
#define fillm(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define pll pair<int, int>
#define pf printf
#define sf scanf
#define all(x) x.begin(),x.end()
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<n;i++)
#define fof(i,a,b) for(int i=a;i<=b;i++)
#define off(i,a,b) for(int i=a;i>=b;i--)
#define of(i,n) for(int i=n-1;i>=0;i--)
#define stl(i,x) for(auto i=x.begin(); i!=x.end();i++)
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
#define nl endl

typedef unsigned long long lll;
typedef long long ll;
int knigtx8[] = {2, 2, -2, -2, 1, 1, -1, -1}; ///knight move in chess
int knigty8[] = {1, -1, 1, -1, 2, -2, 2, -2}; ///knight move in chess
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}; ///for 8 directions
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1}; ///for 8 directions
int dx4[] = {0, 0, 1, -1}; ///for 4 directions
int dy4[] = {1, -1, 0, 0}; ///for 4 directions
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}
ll pw(ll a, ll b)
{
    ll ans = 1;
    for(ll i = 1; i <= b; ++i)
        ans = (ans * a);
    return ans;
}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

int main()
{
    IOS;
    ll n,k;
    cin>>n>>k;
    ll a[n+1],pre[n+1];
    fil(pre);
    fof(i,1,n){
        cin>>a[i];
        pre[i] = pre[i-1] + a[i];
    }
    int in=1;
    ll sum=0,bef;
    fof(i,k+1,n)
    {
        bef = pre[i-1]-pre[in-1];
        sum = pre[i]-pre[in];
        if(sum>bef)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

        in++;
    }
    return 0;
}

///Alhamdulillah


Measured memory_bytes: 6768
// in the name if Allah
// YA Ali!
#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;

const ll INF = 1<<30 ;
const ll N= 1e6 ;

#define f first
#define s second

set<char> ss , tt ;

ll n , a[N] , ans = 0  , b[N] , o0 = '0' , mod = 1e9 + 7 , dp[N][14] ;

deque<char> ds1 , st1 ;

ll poww(ll a , ll b){
if(b==0)return 1 ;
ll x = poww(a,b/2)%13 ;
x %= 13 ;
if(b&1)return ((((x*x)%13)*a)%13) ;
else return (x*x)%13 ;
}

int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
/*
string s1 , t1 , s2 ,t2;
cin >> s1 >> t1 ;
s2 = s1 ;
t2 = t1 ;
for(int i = 0 ; i < s1.size() ; i ++){
    ds1.push_back(s1[i]) ;
    ss.insert(s1[i]) ;
}
for(int j = 0 ; j < t1.size() ; j ++){
    dt1.push_back(t1[j]) ;
     tt.insert(tt[j]) ;
}
if(ss.size() == 1 && tt.size() == 1 ){
    set<char> ::iterator it = ss.begin() , it2 = tt.begin() ;
    if(*it == *it2)return cout << -1 , 0 ;
}
while(s1 < t1){
    s1 += s2 ;
}
while(t1 < s1){
    t1 += t2 ;
}
if(s1 == t1)return cout << -1 , 0 ;
t1 = t2 ;
s1 = s2 ;
if(t1.size() > s1.size())return cout << 0 , 0 ;
s1 += s2 ;
*/
string s1 ;
cin >> s1 ;
ll n = s1.size() ;
if(s1[n-1] != '?'){
    ll x = s1[n-1] ;
    x -= o0 ;
    dp[n-1][x] = 1 ;
}
else{
    for(int i = 0 ; i < 10 ; i ++){
        dp[n-1][i] = 1 ;
    }
}
for(int i = n-2 ; i >= 0 ; i --){
    ll ta = poww(10,n-1-i)%mod  ;
    if(s1[i] != '?'){
        ll x = s1[i] ;
        x -= o0 ;
        for(int j = 0 ; j < 13 ; j ++){
            dp[i][(j+(x*ta))%13] += dp[i+1][j]%mod ;
        }
    }
    else{
        for(int j = 0 ; j < 10 ; j ++){
            for(int k = 0 ; k < 13 ; k ++){
                dp[i][((j*ta)+k)%13] += dp[i+1][k]%mod ;
            }
        }
    }
}
cout << dp[0][5]%mod;
    return 0;
}
 /*
              _     _   __
        /_\  (_    (_)  __)
       /   \  _) . (_) (__
 */


Measured memory_bytes: 12752