akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>

using namespace std;

static const int N = 100;

int main() {
    int n, p[N + 1], m[N + 1][N + 1];
    
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> p[i - 1] >> p[i];
    }
    
    for (int i = 1; i <= n; i++) {
        m[i][i] = 0;
    }
    
    for (int l = 2; l <= n; l++) {
        for (int i = 1; i <= n - l + 1; i++) {
            int j = i + l - 1;
            
            m[i][j] = (1 << 21);
            
            for (int k = i; k <= j - 1; k++) {
                m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
            }
        }
    }
    
    cout << m[1][n] << endl;
    
    return 0;
}



Measured memory_bytes: 3120
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

// #define FL fflush(stdout)

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
  return scanf("%lld", &x);
}

int GI(int& x) {
  return scanf("%d", &x);
}

LL A, B, C, a, b, c;
int main() {
  GLL(A);
  GLL(B);
  GLL(C);

//  LL d = 2;
  int cnt = 0;

  if (A&1 || B&1 || C&1) {
    printf("%d\n", cnt);
    return 0;
  }

  FORN(i, 31) {
    a = A;
    b = B;
    c = C;

    A = (b/2 + c/2);
    B = (a/2 + c/2);
    C = (a/2 + b/2);
    cnt++;
//    d <<= 1;

    if (A&1 || B&1 || C&1) {
      printf("%d\n", cnt);
      return 0;
    }
  }

  printf("-1\n");
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 998244353;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int A, B, C;
    while (cin >> A >> B >> C) {
        swap(A, B);
        swap(A, C);
        cout << A <<' '<<B<<' '<<C<<endl;
    }
    
}


Measured memory_bytes: 892
n = int(input())
a = []
m1, m2, m3, m4 = [-10**10]*4

def maxAbsValExpr(x, y, n):
    res, n = 0, len(x)
    for p, q in [[1, 1], [1, -1], [-1, 1], [-1, -1]]:
        smallest = p * x[0] + q * y[0] + 0
        for i in range(n):
            cur = p * x[i] + q * y[i] 
            res = max(res, cur - smallest)
            smallest = min(smallest, cur)
    return res

x = []
y = []
for _ in range(n):
    u, v = [int(x) for x in input().strip().split()]
    x.append(u)
    y.append(v)
    # if x+y>
    # m1 = max(m1, x+y)
    # m2 = max(m2, y-x)
    # m3 = max(m3, x-y)
    # m4 = max(m4, -1*y-x)

res = maxAbsValExpr(x, y, n)
print(res)

Measured memory_bytes: 97024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin>>a>>b;
    if(a%3==0 || b%3==0 || (a+b)%3==0) cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define res register ll
#define inf 2e18
#define N 2005
using namespace std;
ll n,a[N],ans=inf,x,b[N];
inline ll read(){
	res X=0,w=0;char ch=0;
	while(!isdigit(ch)){w|ch=='-';ch=getchar();}
	while(isdigit(ch)){X=(X<<1)+(X<<3)+(ch^48);ch=getchar();}
	return w?-X:X;
}
int main(){
	n=read(),x=read();
	for(res i=0;i<n;i++)
	  a[i]=read();
	for(res i=0;i<n;i++)
	  b[i]=inf;
	for(res i=0;i<n;i++){
		res sum=0;
		for(res j=0;j<n;j++)
		  b[j]=min(b[j],a[(j-i+n)%n]);
		for(res j=0;j<n;j++)
		  sum+=b[j];
		ans=min(ans,sum+i*x);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] a = new long[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextLong();
		long[] sum = new long[n + 1];
		for(int i = 0 ; i < n ; i++) sum[i + 1] = sum[i] + a[i];
		Map<Long, Integer> map = new HashMap<>();
		for(int i = 0 ; i < n + 1 ; i++) {
			if(map.containsKey(sum[i])) {
				map.put(sum[i], map.get(sum[i]) + 1);
			} else {
				map.put(sum[i], 1);
			}
		}
		long ans = 0;
		for(long key : map.keySet()) {
			ans += 1L * map.get(key) * (map.get(key) - 1) / 2L;
		}
		System.out.println(ans);
 	}
}


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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 1e5;
int n, r, c;
num ans;
pair<int, pair<int, int>> e[nsz + 5];

struct union_find {
    int pr[2 * nsz + 5], siz[2 * nsz + 5], usd[2 * nsz + 5];
    
    void inline init() {
        cont (i, 2 * nsz) {
            pr[i] = i;
            siz[i] = 1;
        }
    }
    
    int qry(int u) {
        return pr[u] == u ? u : pr[u] = qry(pr[u]);
    }
    
    bool inline unite(int u, int v) {
        int pu = qry(u), pv = qry(v);
        if (pu == pv) {
            if (usd[pu] >= siz[pu])  return 0;
            ++usd[pu];
            return 1;
        }
        if (usd[pu] + usd[pv] >= siz[pu] + siz[pv])  return 0;
        pr[pv] = pu;
        siz[pu] += siz[pv];
        siz[pv] = 0;
        usd[pu] += usd[pv];
        usd[pv] = 0;
        ++usd[pu];
        return 1;
    }
};
union_find uf;

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> r >> c;
    cont (i, n) {
        int x, y, val;
        cin >> x >> y >> val;
        e[i] = make_pair(val, make_pair(x, y));
    }
    sort(e + 1, e + n + 1, greater<pair<int, pair<int, int>>>());
    uf.init();
    cont (i, n) {
        int x = e[i].second.first, y = e[i].second.second, val = e[i].first;
        if (uf.unite(x, y + nsz)) {
            ans += val;
        }
    }
    cout << ans << ln;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	cout<<max(a+b,max(a-b,a*b));
	return 0;
}

Measured memory_bytes: 256
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 +7
    
K = int(readline())
S = readline().decode().rstrip()
s = len(S)-1

n = s+K
fact = [1] * (n+1)
fact_inv = [1] * (n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1] * i % mod 
fact_inv[n] = pow(fact[n],mod-2,mod)
for i in range(n,0,-1):
    fact_inv[i-1] = (i * fact_inv[i]) % mod 

def comb(n,r):
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

ans = 0
for i in range(K+1):
    ans += (comb(i+s,s) * pow(25,i,mod) % mod * pow(26,K-i,mod)) % mod
print(ans%mod)

Measured memory_bytes: 122156
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a, b, c;
	cin >> a >> b >> c;
	int k;
	cin >> k;
	if(k <= a) cout << k << endl;
	else if(k <= a + b) cout << a << endl;
	else cout << a - (k - (a + b)) << endl;
	return 0;
}

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

int main(){	
  ll K,A,B,n=1;
  cin>>K>>A>>B;
  while(K){
    if(n>=A&&K>1&&B-A>2){K-=2;n+=B-A;}
    else{K--;n++;}
  }
  cout<<n<<endl;
}


Measured memory_bytes: 256
from collections import deque

n, m, p = list(map(int, input().split()))

# edge: from, to, cost
edges = [list(map(int, input().split())) for i in range(m)]
for edge in edges:
    edge[0] -= 1
    edge[1] -= 1
    edge[2] -= p

start = 0
goal = n - 1

# dist: cost from start
dist = [-float("inf")] * n
dist[start] = 0

# cut edges
reachable = [False] * n
reachable[goal] = True
d = deque()
d.append(goal)
reachable[goal] = True
while len(d) > 0:
    x = d.popleft()
    for edge in edges:
        if edge[1] == x and reachable[edge[0]] is False:
            d.append(edge[0])
            reachable[edge[0]] = True

cant_reach = []
for i in range(n):
    if reachable[i] is False:
        cant_reach.append(i)

for edge in edges:
    if edge[0] in cant_reach or edge[1] in cant_reach:
        edges.remove(edge)

# bellman-ford

# relaxing
negative_cycle = False
for i in range(n):
    # 各辺操作
    for edge in edges:
        if dist[edge[0]] != -float("inf") and dist[edge[1]] < dist[edge[0]] + edge[2]:
            dist[edge[1]] = dist[edge[0]] + edge[2]
            if i == n - 1:
                negative_cycle = True

print(-1 if negative_cycle else max(dist[n - 1], 0))


Measured memory_bytes: 52312
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int x, ans=0;
    
    cin >> x;
    
    ans = (x/500) * 1000;
    x = x % 500;
    ans += (x/5) * 5;
    
    cout << ans << endl;
    
    return 0;
    
}

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

using namespace std;

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

  int min = INT_MAX;
  for(int t=0; t<n; t++){
    int lsum = 0;
    int rsum = 0;
    for(int j=0; j<t; j++){
      lsum += w[j];
    }
    for(int j=t; j<n; j++){
      rsum += w[j];
    }
    if( min > abs(lsum - rsum) ){
      min = abs(lsum - rsum);
    }
  }

  std::cout << min << '\n';
  return 0;
}


Measured memory_bytes: 384
{-# LANGUAGE RankNTypes #-}
    
import Control.Monad.State
import Control.Monad.ST
import Data.Array.ST
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Foldable
--import Debug.Trace

main :: IO ()
main = readLine >>= print . solve

solve :: [Int] -> Int
solve [h, w, a, b] = runST (initialize >>= stAction)
    where
        initialize :: ST s (Table s Int Int)
        initialize = newArray (0, h + w) Nothing
        
        stAction = evalStateT calc 

        calc = sum' <$> mapM count [1..(h - a)]

        count i = mul <$> cmb (i - 1) (b - 1) <*> cmb (h - i) (w - b - 1)

        cmb x y = prod <$> sequence [frac $ x + y, inv <$> frac x, inv <$> frac y]

        frac = memoizeFix memFrac
            where
                memFrac f n
                    | n > 0 = mul n <$> f (n - 1)
                    | otherwise = return 1

        prod = foldl' mul 1
        sum' = foldl' add 0

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

infixl 6 `add`
infixl 7 `mul`

add :: Int -> Int -> Int
add x y = val $ x + y

mul :: Int -> Int -> Int
mul x y = val $ x * y

inv :: Int -> Int
inv x = pow x $ modVal - 2

pow :: Int -> Int -> Int
pow b e
    | e == 0 = 1
    | odd e = mul b . pow b $ e - 1
    | otherwise = mul v v
    where
        v = pow b $ e `div` 2

val :: Int -> Int
val = (`mod` modVal)

modVal :: Int
modVal = 10 ^ 9 + 7

primes :: [Int]
primes = build [2..]
    where
        build (x : xs) = x : build (filter (\n -> n `mod` x /= 0) xs)
        
isPrime :: Int -> Bool
isPrime n = check primes
    where
        check (x : xs)
            | x == n = True
            | x > n = False
            | otherwise = check xs

type Table s a b = STArray s a (Maybe b)
type Memo s a b = a -> StateT (Table s a b) (ST s) b

evalMemo :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> a -> Table s a b -> ST s b
evalMemo f k = evalStateT (memoizeFix f k)

runMemo :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> a -> Table s a b -> ST s (b, Table s a b)
runMemo f k = runStateT (memoizeFix f k)

memoizeFix :: (Ix a) => (forall s. Memo s a b -> Memo s a b) -> forall s. Memo s a b
memoizeFix f k = get >>= (\arr -> lift (readArray arr k) >>= maybe (f (memoizeFix f) k >>= ((<$) <*> (lift . writeArray arr k . Just))) return)

Measured memory_bytes: 128892
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define INF 1e9
#define MAXN 100005
#define MAXM 100005
#define MOD 1000000007
#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define pii pair<int, int>

ll ans;
int N;
bool flag = false;

void solve(){
    if(N % 10 == 9) flag = true;

    N /= 10;

    if(N % 10 == 9) flag = true;

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

int main(){
    cin >> N;

    solve();
}


Measured memory_bytes: 256
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s=input()
t=input()
ans=0
for i in range(len(s)):
    if s[i]!=t[i]:
        ans+=1

print(ans)

Measured memory_bytes: 74720
#include <stdio.h>

int main()
{
	int n;
	int a;
	double sum=0;

	scanf("%d",&n);

	for(int i=0; i<n; i++){
		scanf("%d",&a);
		sum+=(double)1/a;
	}

	printf("%lf\n",1/sum);

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int main()
{
   string s;
    int a[26]={0},b,i,f=0;
   cin>>s;
   for(i=0;i<4;i++)
   {
       b=s[i]-65;
       a[b]++;

   }
   for(i=0;i<26;i++)
   {
       if(a[i]>=2)
       {
         f++;

       }


   }
  if(f==2)
  {
      cout<<"Yes"<<endl;
  }
  else
  {
      cout<<"No"<<endl;
  }
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};
using mint = Fp<1000000007>;

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    vector<long long> num(1100000, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        auto pf = prime_factorize(A[i]);
        for (auto p : pf) num[p.first] = max(num[p.first], p.second);
    }

    mint LCM = 1;
    for (int v = 2; v < 1100000; ++v) {
        LCM *= modpow(mint(v), num[v]);
    }

    mint res = 0;
    for (auto a : A) {
        res += LCM / a;
    }
    cout << res << endl;
}


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

int main(){

    int h,w;
    cin >> h >> w;
    string s[h];

    rep(i,h){
        cin >> s[i];
    }

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

    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='#'){
                cout << '#';
                continue;
            }
            int cnt=0;
            for(int k=0;k<8;k++){
                if(j+dx[k]<0||i+dy[k]<0||j+dx[k]>w||i+dy[k]>h) continue;
                if(s[i+dy[k]][j+dx[k]]=='#'){
                    cnt++;
                }
            }
            cout << cnt;
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int cnt[26];
signed main() {
    int H,W;
    cin >> H >> W;
    vector<vector<char>>a(H,vector<char>(W));
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            cin >> a[i][j];
            cnt[a[i][j]-'a']++;
        }
    }
    int B = 0,C = 0;
    if(H%2 == 1 && W%2 == 1) {
        C++;
        B = (H+W-1)/2;
    }
    else if(H%2 == 1 && W%2 == 0) {
        B = W/2;
    }
    else if(H%2 == 0 && W%2 == 1) {
        B = H/2;
    }
    for(int i = 0; i < 26; i++) {
        if(cnt[i]%2 == 1) {
            if(C) {
                cnt[i]--;
                C--;
            }
        }
        if(cnt[i]%4 == 2) {
            if(B) {
                cnt[i]-=2;
                B--;
            }
        }
        cnt[i]%=4;
    }
    for(int i = 0; i < 26; i++) {
        if(cnt[i] != 0) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

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

int main()
{
  string s;cin>>s;
  string ans="AKIHABARA";
  int i,j;
  bool ok=false;
  for(i=0;i<(1<<4);i++)
  {
    string nam="";
    int counta=0;
    for(j=0;j<ans.size();j++)
    {
      if(ans.at(j)=='A')
      {
        if(i&(1<<counta))nam+=ans.at(j);
        counta++;
      }
      else nam+=ans.at(j);
    }
    if(nam==s)ok=true;
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

searched = set()
for dup, x in enumerate(a):
    if x in searched:
        break
    else:
        searched.add(x)
first = a.index(a[dup])

for k in range(1, n+2):
    ans = comb(n+1, k)
    if k - 1 <= n - dup + first:
        ans -= comb(n - dup + first, k - 1)
    print(ans % mod)

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

int main() {
  int N; cin >> N;
  map<int, int> m;
  set<int> s;
  for (int i = 0; i < N; i++) {
    int a; cin >> a;
    if (m.count(a)) m[a]++;
    else m[a] = 1;
    s.insert(a);
  }
  vector<long long> v;
  while (v.size() < 2) {
    if (s.empty()) {
      cout << 0 << endl;
      return 0;
    }
    int e = *rbegin(s);
    if (m[e] >= 2) v.push_back(e);
    if (m[e] < 4) s.erase(e);
  }
  long long ans = v.at(0) * v.at(1);
  cout << ans << endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=1000005;
const ll INF=0x3f3f3f3f3f3f3f;
const ll MOD=1000000007;
ll n;
int main(){
    scanf("%lld",&n);
    for(ll i=0;;i++){
        if(i*(i+1)/2>=n){
            printf("%lld\n",i);
            return 0;
        }
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] a = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		int[][] b = new int[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				b[i][j] = sc.nextInt();
			}
		}
		sc.close();

		int x = 160 * 80;
		boolean[][][] dp = new boolean[h][w][x];
		dp[0][0][Math.abs(a[0][0] - b[0][0])] = true;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (i == 0 && j == 0) {
					continue;
				}
				int abs = Math.abs(a[i][j] - b[i][j]);
				if (i > 0) {
					for (int k = 0; k < x; k++) {
						dp[i][j][k] |= dp[i - 1][j][Math.abs(k - abs)];
						if (k + abs < x) {
							dp[i][j][k] |= dp[i - 1][j][k + abs];
						}
					}
				}
				if (j > 0) {
					for (int k = 0; k < x; k++) {
						dp[i][j][k] |= dp[i][j - 1][Math.abs(k - abs)];
						if (k + abs < x) {
							dp[i][j][k] |= dp[i][j - 1][k + abs];
						}
					}
				}
			}
		}
//		for (int i = 0; i < h; i++) {
//			for (int j = 0; j < w; j++) {
//				StringBuilder sb = new StringBuilder();
//				sb.append(i).append(':').append(j).append('\t');
//				for (int k = 0; k < x; k++) {
//					if (dp[i][j][k]) {
//						sb.append(k).append(',');
//					}
//				}
//				System.out.println(sb);
//			}
//		}
		for (int k = 0; k < x; k++) {
			if (dp[h - 1][w - 1][k]) {
				System.out.println(k);
				return;
			}
		}
	}
}


Measured memory_bytes: 118984
using namespace std;

#include <iostream>
#include <unordered_set>

#define MAXN 1000005

int spf[MAXN];
bool table[MAXN];
int arr[MAXN];

void sieve() {
	spf[1] = 1;
	for(int i = 2;i < MAXN;++i) {
		spf[i] = i;
	}

	for(int i = 2;i * i < MAXN;++i) {
		// cout << i << endl;
		if(spf[i] != i) continue;
		for(int j = i * i;j < MAXN;j += i) {
			if(spf[j] == j) spf[j] = i;
		}
	}
	return;
}

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


int main() {
	sieve();
	int N;
	cin >> N;
	for(int i = 0;i < N;++i) {
		cin >> arr[i];
	}

	long long gcd = arr[0];
	for(int i = 0;i < N;++i) {
		gcd = _gcd(arr[i],gcd);
	}

	bool first = true;
	for(int i = 0;i < N;++i) {
		unordered_set<int> us;
		int cur = arr[i];
		while(cur != 1) {
			int next = spf[cur];
			if(us.find(next) == us.end()) {
				us.insert(next);
				if(table[next]) {
					first = false;
					break;
				}
				table[next] = true;
			}
			cur = cur / next;
		}
	}
	if(first) {
		cout << "pairwise coprime" << endl;
	}else if(gcd == 1) {
		cout << "setwise coprime" << endl;
	}else{
		cout << "not coprime" << endl;
	}
}

Measured memory_bytes: 12380
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(solve(N, K));

        sc.close();
    }

    static long solve(int N, int K) {
        long result = 0;
        for (int b = K + 1; b <= N; ++b) {
            result += N / b * (b - K) + Math.max(0, N % b - Math.max(0, K - 1));
        }

        return result;
    }
}

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

ll dist[2][50][500][50];

struct S {
	int rev, sv, pos, v;
	ll d;

	bool operator <(const S& x) const {
		return d > x.d;
	}
};

ll rec(S s) {
	return dist[s.rev][s.sv][s.pos][s.v];
}

void save(S s) {
	dist[s.rev][s.sv][s.pos][s.v] = s.d;
}

struct edge {
	int to;
	ll t;
};

vector<edge> G[500];

int n, m, a, b, c, v0;

void dijkstra(int rev, int spos, int sv) {
	S s = { rev, sv, spos, sv, 0 };
	save(s);
	priority_queue<S> q;
	q.push(s);
	while(q.size()) {
		s = q.top();
		q.pop();
		ll d = rec(s);
		if(d < s.d) continue;
		//cout << d << endl;
		for(auto e : G[s.pos]) {
			S ns = { rev, sv, e.to, (a * s.v + b) % c, d + e.t * s.v };
			if(rec(ns) > ns.d) {
				save(ns);
				q.push(ns);
			}
		}
	}
}

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

	cin >> n >> m;

	for(int i = 0; i < m; i++) {
		int x, y;
		ll t;
		cin >> x >> y >> t;
		x--, y--;
		G[x].push_back({ y, t });
		G[y].push_back({ x, t });
	}
	cin >> v0 >> a >> b >> c;

	const ll INF = 1LL << 60;
	fill((ll*)begin(dist), (ll*)end(dist), INF);

	dijkstra(0, 0, v0);
	for(int sv = 0; sv < 50; sv++) {
		dijkstra(1, n - 1, sv);
	}

	ll ans = INF;
	for(int v1 = 0; v1 < 50; v1++) {
		for(int v2 = 0; v2 < 50; v2++) {
			S s1 = { 0, v0, n - 1,v1 };
			S s2 = { 1, v1, 0,v2 };
			ans = min(ans, rec(s1) + rec(s2));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 28216
H = int(input())
W = int(input())
N = int(input())

co = 0
ans = 0

if H >= W:
    for i in range(W):
        co += H
        ans += 1
        if co >= N:
            break
else:
    for i in range(H):
        co += W
        ans += 1
        if co >= N:
            break

print(ans)



Measured memory_bytes: 39748
using System;

class MyClass
{
    static void Main(string[] args)
    {
        string str = "";
        while ((str = Console.ReadLine()) != "0 0 0")
        {
            string[] str2 = str.Split(' ');
            int m = int.Parse(str2[1]);
            int a = int.Parse(str2[2]);
            int[] h = new int[m];
            int[] p = new int[m];
            int[] q = new int[m];
            int hmax = 0;
            for (int i = 0; i < m; i++)
            {
                str2 = Console.ReadLine().Split(' ');
                h[i] = int.Parse(str2[0]);
                p[i] = int.Parse(str2[1]);
                q[i] = int.Parse(str2[2]);
                if (hmax < h[i])
                {
                    hmax = h[i];
                }
            }
            for (int i = hmax; i > 0; i--)
            {
                for (int j = 0; j < m; j++)
                {
                    if (i == h[j])
                    {
                        if (a == p[j])
                        {
                            a = q[j];
                        }
                        else if (a == q[j])
                        {
                            a = p[j];
                        }
                    }
                }
            }
            Console.WriteLine(a);
        }
    }
}


Measured memory_bytes: 5816
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int a, b;
    cin >> a >> b;
    stringstream ss;
    ss << a << b;
    int c;
    ss >> c;
    for (int i = 1; i * i <= c; ++i)
    {
        if (i * i == c)
        {
            cout << "Yes" << endl;
            return;
        }
    }
    cout << "No" << endl;
}


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

int main() {
    int n;
    cin >> n;
    int b[n - 1];
    for(int i = 0; i < n - 1; i++) cin >> b[i];

    int a[n];
    a[0] = b[0];

    for(int i = 1; i < n - 1; i++) {
        a[i] = min(b[i - 1], b[i]);
    }
    a[n - 1] = b[n - 2];

    int ans = accumulate(a, a + n, 0);

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

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

using namespace std;

int main(void) {
	int n;
	cin >> n;
	int d[n];
	for(int i = 0; i < n; i++) {
		cin >> d[i];
	}
	
	sort(d, d + n);
	
	int tmp = d[0];
	int count = 1;
	for(int i = 0; i < n; i++) {
		if(tmp < d[i]) {
			tmp = d[i];
			count++;
		}
	}
	
	cout << count << endl;
}


Measured memory_bytes: 256
h,w = input().split()
h = int(h)
w = int(w)
n = int(input())
a_list = input().split()
a_list = [int(a) for a in a_list]

c_list = []
for i,a in enumerate(a_list):
    for j in range(a):
        c_list.append(i+1)
        
for i in range(h):
    p_list = c_list[w*i:w*(i+1)]
    p_list = [str(p) for p in p_list]
    if i % 2 == 0:
        print(" ".join(p_list))
    else:
        print(" ".join(p_list[::-1]))

Measured memory_bytes: 3572
#include <math.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#include <climits>
using namespace std ;
#define ld long double
#define int unsigned long long
#define _ ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL);
#define dbg(x) cerr << #x << " is " << x << endl;
#define F(i,b) for(int i = 0 ; i < (int)(b) ; i++)
#define RF(j,b) for(int j = (int)(b)-1 ; j >= 0 ; j--)
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
const int N = 2e5+7 ;
const int INF = 1e9 ;
const int MOD = INF + 7 ;
string s ;
int solve(int x ,int y){
	return x / y ;
}

void solve(){
	int a , b , c , d ;
	cin >> a >> b >> c >> d ;
	cout << b - a + 1 - (solve(b,c) - solve(a-1,c) ) - (solve(b,d) - solve(a-1,d) ) + (solve(b,(c*d)/__gcd(c,d)) - solve(a-1, (c*d)/ __gcd(c,d) ) ) << endl ;

}

int32_t main(){_
	int t = 1 ;
//	cin >> t ;
	while(t--){
		solve() ;
	}

}


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

// using ll = long long;
#define int long long

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, r, n) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
/***** MAIN *****/
signed main() {
  int n, m;
  cin >> n >> m;
  cout << (1<<m) * (n+18*m) * 100;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

const double EPS = 1e-8;
const double INF = 1e12;
const double PI = acos(-1);

using Point = complex<double>;
using Polygon = vector<Point>;

inline int sgn(const double &a) { return (a < -EPS ? -1 : (a > EPS ? 1 : 0)); }

inline bool eq(const Point &a, const Point &b) { return abs(a - b) < EPS; }

inline bool operator<(const Point &a, const Point &b){
    if (sgn(a.real() - b.real()))
        sgn(a.real() - b.real()) < 0;
    return sgn(a.imag() - b.imag());
}

double dot(const Point &a, const Point &b) { return real(conj(a) * b); }

double det(const Point &a, const Point &b) { return imag(conj(a) * b); }

struct Line {
    Point p1, p2;

    Line(Point p1 = Point(), Point p2 = Point()) : p1(p1), p2(p2) {}

    bool operator<(const Line &rhs) const {
        if (eq(p2, rhs.p2))
            return p1 < rhs.p1;
        return p2 < rhs.p2;
    }
    bool operator==(const Line &rhs) const {
        return (eq(p1, rhs.p1) && eq(p2, rhs.p2)) ||
               (eq(p1, rhs.p2) && eq(p2, rhs.p1));
    }
};

Point circumcenter(Point p1, Point p2, Point p3) {
  double a1, b1, c1, a2, b2, c2, cx, cy;
  a1 = real(p2 - p1);
  b1 = imag(p2 - p1);
  c1 = norm(p2) - norm(p1);
  a2 = real(p3 - p2);
  b2 = imag(p3 - p2);
  c2 = norm(p3) - norm(p2);
  cx = (b2 * c1 - b1 * c2) / (2.0 * (a1 * b2 - a2 * b1));
  cy = (a1 * c2 - a2 * c1) / (2.0 * (a1 * b2 - a2 * b1));
  return Point(cx, cy);
}

int main(){
    int n;
    cin >> n;
    for(int i=0;i<n;++i){
        double x1, y1, x2, y2, x3, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        Point c = circumcenter(Point(x1,y1),Point(x2,y2),Point(x3,y3));
        double r = abs(Point(x1,y1) - c);
        printf("%.3f %.3f %.3f\n",c.real(),c.imag(),r);
    }

    return 0;
}



Measured memory_bytes: 3196
import math
N = int(input())
As = list(map(int, input().split()))

def check():
    return all([a <= N-1 for a in As])

ans = 0
while not check():
    n = 0
    for i in range(N):
        a = As[i]
        t = a // N
        n += t
        As[i] -= t * (N+1)
    for i in range(N):
        As[i] += n
    ans += n
print(ans)


Measured memory_bytes: 9128
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>

using namespace std;
typedef long long int ll;

int main(int argc, char const *argv[])
{
    ll a, b, c;
    cin >> a >> b >> c;
    if (a <= c && c <= b)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::cmp::min;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("faild to read char") as char)
        .take_while(|c| !c.is_whitespace())
        .collect();
    token
        .parse()
        .ok()
        .expect("faild to parse token")
}

fn main(){
    let n: usize = read();
    let m: usize = read();
    let a: Vec<f64> = (0..n).into_iter().map(|_| read()).collect();
    let s = (&a).into_iter().fold(0.0, |a, b| a + b);
    let limit = s / (4.0 * m as f64);
    let ret = (&a).into_iter().fold(0, |sum, &i| if i < limit { sum } else { sum + 1 });
    if ret >= m {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>
#include<cmath>

using namespace std;

const int N = (pow(10,5)+50);

vector<bool> isp(N+1, true);

void sieve() {
  isp[0] = false;
  isp[1] = false;
  for (int i=2; pow(i,2)<=N; i++) {
    if (isp[i]) for(int j=2; i*j<=N; j++) isp[i*j] = false;
  }
}

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

	for(int i=n;i<N;i++)
	{
		if(isp[i])
		{
			cout << i << endl;
			return 0;
		}
	}




}


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

using namespace std;

int main(){
  int c[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>c[i][j];
    }
  }

  bool check=false;
  int a1,a2,a3,b1,b2,b3;
  for(int i=0;i<=100;i++){
    a1=i;
    b1=c[0][0]-a1;
    b2=c[0][1]-a1;
    b3=c[0][2]-a1;
    a2=c[1][0]-b1;
    a3=c[2][0]-b1;

    if((a2+b2)==c[1][1]&&(a2+b3)==c[1][2]&&(a3+b2)==c[2][1]&&(a3+b3)==c[2][2]){
      check=true; 
      break;
    }
  }

  if(check) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;

int N, A;
int x[111];
ll coudp[111][111][5555];

int main() 
{
	int H, W;
	cin >> H >> W;
	vector<vector<char>> data(H, vector<char>(W));
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j<W; j++)
		{
			cin >> data[i][j];
		}
	}
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			if (j == W - 1)
			{
				cout << data[i][j] << endl;;
			}
			else
			{
				cout << data[i][j];
			}
			
		}
		for (int j = 0; j < W; j++)
		{
			if (j == W - 1)
			{
				cout << data[i][j] << endl;;
			}
			else
			{
				cout << data[i][j];
			}

		}
		
	}
	

	return 0;
	
}

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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100010;
const double eps = 1e-6;

int n;
int a[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);

    cout << a[n / 2 + 1] - a[n / 2] << endl;
    return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string>
#include<set>
using namespace std;

int main() {
	string s; cin >> s;
	int x = 0;
	int y = 0;
	int idx;
	int i = 1;
	for (i; i < s.length(); i++) {
		if (s[i] != s[i - 1]) {
			idx = i;
			break;
		}
	
	}
	if (i == s.length()) {
		cout << "No";
		exit(0);
	}
	for (int m = 0; m < s.length(); m++) {
		if (s[m] == s[0]) {
			x++;
		}
		if (s[m] == s[idx]) {
			y++;
		}
	}
	if (x == 2 && y == 2) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define REP(i, n) FOR(i, 0, n - 1)
#define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
////////////////////////////////////////

int main() {
	ll N; cin >> N;
	ll res = 0;
	for (ll i = 1; i*i < N; ++i) {
		if ((N-i)%i==0&&(N-i)/i>i) {
			res += (N-i)/i;
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int D, G;
vector<pii> P;
//=============================
void input()
{
    cin >> D >> G;
    P.resize(D);
    rep(i, D)
    {
        cin >> P[i].first >> P[i].second;
    }
}

void solve()
{
    int ans = INF;
    for (int i = 0; i < (1 << D); ++i)
    {
        bool br = false;
        int score = 0;
        int ans_sub = 0;
        for (int j = 0; j < D; ++j)
        {
            if ((i >> j) & 1LL)
            {
                ans_sub += P[j].first;
                score += P[j].second + P[j].first * 100 * (j + 1);
            }
        }

        if (score >= G)
        {
            ans = min(ans, ans_sub);
            continue;
        }

        for (int j = D - 1; j >= 0; --j)
        {
            if (br)
            {
                break;
            }

            if (!((i >> j) & 1LL))
            {
                for (int k = 0; k < P[j].first - 1; ++k)
                {
                    ans_sub += 1;
                    score += (j + 1) * 100;
                    if (score >= G)
                    {
                        ans = min(ans, ans_sub);
                        br = true;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    while(cin>>n,n){
        int m[1000],p[1000],q[1000],r[1000],P,Q,R,C;
        for(int i=0;i<n;i++)
            cin>>m[i]>>p[i]>>q[i]>>r[i];

        cin>>P>>Q>>R>>C;
        bool Flag=true;
        for(int i=0;i<n;i++){
            int _P,_Q,_R,_C;
            _P=p[i];
            _Q=q[i];
            _R=r[i];
            _C=_P*4+_Q*9+_R*4;
            if(_C<=C&&_Q<=Q&&_R<=R&&_P<=P){
                cout<<m[i]<<endl;
                Flag=false;

            }
        }
        if(Flag)cout<<"NA"<<endl;
    }
}

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

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n;
vector<int > e[maxn];

int dfs(int x,int fa) {
    int s=0;
    for(auto v:e[x])
        if(v!=fa) s^=dfs(v,x)+1;
    return s;
}

int main() {
    read(n);
    for(int i=1,x,y;i<n;i++) read(x),read(y),e[x].pb(y),e[y].pb(x);
    puts(dfs(1,0)?"Alice":"Bob");
    return 0;
}


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

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;

int N; int a[MAXN+1]; 
struct Seg{
	int mx[MAXN<<2];
	inline void build(int rt,int l,int r){
		mx[rt]=-1; if(l==r) return ; int mid=(l+r)>>1;
		build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); 
	}
	inline int Query(int rt,int l,int r,int L,int R){
		if(L<=l&&R>=r) return mx[rt]; int mid=(l+r)>>1,ans=-1;
		if(L<=mid) ans=max(ans,Query(rt<<1,l,mid,L,R));
		if(R>mid) ans=max(ans,Query(rt<<1|1,mid+1,r,L,R)); return ans;
	}
	inline void Set(int rt,int l,int r,int k,int n){
		if(l==r) { mx[rt]=n; return ; } int mid=(l+r)>>1;
		if(k<=mid) Set(rt<<1,l,mid,k,n); else Set(rt<<1|1,mid+1,r,k,n);
		mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
	}
}T0,T1;
int N1;
inline bool Check(int lv,int c){
	if(c<0) return 0;
	if(c&1) return (T1.Query(1,1,N1,lv,N1)>=c);
	else return (T0.Query(1,1,N1,lv,N1)>=c);
} int val[MAXN+1],mx;
int q[MAXN+1],mxa,mxb,la,lb,lena,lenb;
char s[MAXN+1];

int main(){
	//freopen("void.out","r",stdin);
	//freopen(".out","w",stdout);
	N=read(); N1=N+1; int Sum=0;
	for(int i=1;i<=N;i++) {
		val[i]=1; a[i]=read(); mx=max(mx,a[i]);
		if(mx==a[i]) val[i]=2,++Sum;
		q[i]=Sum;
	} T0.build(1,1,N1); T1.build(1,1,N1);
	T0.Set(1,1,N1,N1,0);
	for(int i=N;i>=1;i--){
		int x0=T0.Query(1,1,N1,a[i],N1),x1=T1.Query(1,1,N1,a[i],N1);
		if(val[i]==1){
			if(x0!=-1) T1.Set(1,1,N1,a[i],x0+1); 
			if(x1!=-1) T0.Set(1,1,N1,a[i],x1+1);
		} else{
			if(x1!=-1) T1.Set(1,1,N1,a[i],x1+2); 
			if(x0!=-1) T0.Set(1,1,N1,a[i],x0+2);
		}
	} for(int i=1;i<=N;i++) q[i]=Sum-q[i];
	if((Sum&1)&&T1.Query(1,1,N1,1,N1)<Sum){ puts("-1"); return 0;}
	if(!(Sum&1)&&T0.Query(1,1,N1,1,N1)<Sum){ puts("-1"); return 0; }
	for(int i=1;i<=N;i++){
		T0.Set(1,1,N1,a[i],0); T1.Set(1,1,N1,a[i],-1);
		int tma=max(mxa,a[i]),tmb=max(mxb,a[i]),la=lena,lb=lenb;
		if(tma==a[i]) ++la;
		if(Check(mxb,la+q[i]-lb)||Check(tma,lb+q[i]-la)) {
			s[i]='0'; lena=la; lenb=lb; mxa=tma;
		} else{
			la=lena,lb=lenb; if(tmb==a[i]) ++lb; lena=la; lenb=lb; mxb=tmb;
			s[i]='1';
		}
	} puts(s+1);
	return 0;
}

Measured memory_bytes: 9344
n, k = map(int, input().split())
p = list(map(int, input().split()))
a = []
for i in p:
    a.append((1 + i) / 2)

buf=0
for i in range(k):
    buf+=a[i]

ans = buf

for i in range(k, n):
    buf += a[i]
    buf -= a[i - k]
    ans = max(ans, buf)

print(ans)
    


Measured memory_bytes: 24804
#include <stdio.h>
main(){
  int t,s,sum=0,aave;
  double ave=0,tsum=0;

  while(scanf("%d,%d",&t,&s) !=EOF){
    sum+=t*s;
    ave+=s;
    tsum+=1;
  }
  ave/=tsum;
  ave*=10;
  ave+=5;
  aave=ave/10;

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

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

int main(){
  int N,M;
  cin >> N >> M;
  for(int i=0;i<100000;i++){
    if(1+i<M-i)
      cout << 1+i << " " << M-i << endl;
    else
      break;
  }
  for(int j=0;j<100000;j++){
    if(M+1+j<2*M+1-j)
      cout << M+1+j << " " << 2*M+1-j << endl;
    else
      break;
  }
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define P pair
using ll = long long;
const int MOD = 1e9 + 7;

int main()
 {
    ll q, h, s, d;
    cin >> q >> h >> s >> d;
    ll n; cin >> n;
    h = min(2 * q, h);
    s = min(2 * h, s);
    if(2 * s <= d){
        cout << min(2 * min(2 * q, h), s) * n << endl;
    }else{
        cout << (n / 2) * min({8 * q, 4 * h, 2 * s, d}) + (n % 2) * min({4 * q, 2 * h, s}) << endl;
    }
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define MM 1e9

int N,K;
char S[51];

void input() {
    cin >> N >> K;
    rep (i,0,N) {
        cin >> S[i] ;
        if (i==K-1) S[i] = tolower(S[i]);
    }
}

void solve(){
    rep (i,0,N) cout << S[i];
    cout << endl;
}

int main() {
    input();
    solve();
}

Measured memory_bytes: 256