akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? (-(a)) : (a))

typedef long long ll;

using namespace std;

int arr[35] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

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


	int n;

	scanf("%d", &n);
	printf("%d\n", arr[n-1]);

	return 0;
}

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

typedef long long ll;

int h, w, K;
int s[11][1001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> h >> w >> K;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            char cc;
            cin >> cc;
            if (cc == '1')
                s[i][j] = 1;
            else
                s[i][j] = 0;
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i < (1 << (h - 1)); ++i) {
        int c = __builtin_popcount(i);
        vector<int> pre(c + 1, 0);
        vector<int> cur(c + 1, 0);
        bool failed = false;

        for (int j = 0; j < w; ++j) {
            int g = 0;
            bool flag = false;
            for (int k = 0; k < h; ++k) {
                cur[g] += s[k][j];
                if (cur[g] > K) {
                    failed = true;
                    break;
                }
                if (pre[g] + cur[g] > K) {
                    flag = true;
                }
                if (i & (1 << k)) {
                    ++g;
                }
            }
            if (flag) {
                ++c;
                swap(pre, cur);
                fill(cur.begin(), cur.end(), 0);
            } else {
                for (int q = 0; q < pre.size(); ++q) {
                    pre[q] += cur[q];
                }
                fill(cur.begin(), cur.end(), 0);
            }
        }
        if (failed) continue;
        ans = min(c, ans);
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
table = []

for i, a in enumerate(A):
    table.append([a,i])
table.sort()

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))

ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)


Measured memory_bytes: 137000
x, y = map(int,input().split())
ans = [["#"]*(y+2)]
s = []

for i in range(x):
    s = "#" + input() + "#"
    ans.append(list(s))

ans.append(["#"]*(y+2))

for a in ans:
    for b in a:
        print(b, end ="")
    print()

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

const int MAX = 200005;

int main() {
    int N;
    scanf("%d", &N);
    long long A[MAX], S[MAX];
    long long a, s;
    s = 0;
    for (int i = 0; i < N; i++) {
        scanf("%lld", &a);
        A[i] = a;
        s += a;
        S[i] = s;
    }

    long long b, c, d, e;
    long long ans = 1000000000000000;
    int j = 0;
    int k = 2;
    for (int i = 1; i < N - 2; i++) {
        b = S[j];
        c = S[i] - S[j];
        d = S[k] - S[i];
        e = S[N-1] - S[k];
        while (abs((b + A[j+1]) - (c -A[j+1] )) < abs(b - c) && j + 1 < i) {
            b = S[j+1];
            c = S[i] - S[j+1];
            j++;
        }
        while (abs((d + A[k+1]) - (e -A[k+1] )) < abs(d - e) && k + 1 < N -1) {
            d = S[k+1] -S[i];
            e = S[N-1] - S[k+1];
            k++;
        }
        ans = min(ans, max(max(b, c), max(d, e)) - min(min(b, c), min(d, e)));
    }
    printf("%lld", ans);
    return 0;
}



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

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n,0);
    rep(i, n) {
        scanf("%d", &a[i]);
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        int min_j = i;
        for (int j = i; j < n; j++) {
            if (a[j] < a[min_j]) min_j = j;
        }
        if (i != min_j) {
            swap(a[i], a[min_j]);
            count++;
        }
    }

    rep(i, n) {
        printf("%d", a[i]);
        if (i != n - 1) printf(" ");
    }
    printf("\n%d\n", count);
}


Measured memory_bytes: 3180
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define EPS 1e-10

using ll = long long;
using ull = unsigned long long;

int main() {
    int n, a;
    cin >> n;
    while (n--) {
        cin >> a;
        if (a % 2 == 0 && (a % 3 != 0 && a % 5 != 0)) {
            cout << "DENIED" << endl;
            return 0;
        }
    }
    cout << "APPROVED" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <cstring>

#define pb push_back
#define mp make_pair

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

bool dp[100005];

int main() {
  memset(dp, false, sizeof dp);

  int x;
  cin >> x;

  vi denom = {100, 101, 102, 103, 104, 105};
  dp[0] = true;
  dp[100] = dp[101] = dp[102] = dp[103] = dp[104] = dp[105] = true;
  for (int i = 106; i <= x; ++i) {
    for (int d : denom) {
      if (dp[i-d]) {
        dp[i] = true;
        break;
      }
    }
  }

  cout << dp[x] << endl;
  return 0;
}


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

#define what_is(x) cout << #x << " is " << x << endl;
#define PI acos(-1)
#define hell 1000000007
#define HELL 998244353
#define io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fix(n) cout << fixed << setprecision(n)
#define mset(a,n) memset(a,n,sizeof a)
#define rep(i,a,b) for (__typeof((b)) i=(a);i<(b);i++)
#define repp(i,a,b,p) for(__typeof((b)) i=(a);i<(b);i+=p)
#define ren(i,a,b) for(__typeof((a)) i=(a);i>=(b);i--)
#define renn(i,a,b,p) for(__typeof((a) i=(a);i>=(b);i-=p)
#define ADD(a,b,c) ((a)%c+(b)%c)%c
#define SUB(a,b,c) ((a)%c-(b)%c+c)%c
#define MUL(a,b,c) (((a)%c)*((b)%c))%c
#define lbd lower_bound
#define ubd upper_bound
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define all(v) (v).begin(), (v).end()
#define sz(x) (ll)x.size()
// #define out(n) cout<<n<<" "
#define outl(n) cout<<n<<endl
#define bug(n) {outl(n);return;}
#define pii pair<int,int>
#define lim 9223372036854775805
#define ninf -9223372036854775802
#define M 1000000007
#define eps 1e-9
#define MAX 10
#define N 500001
#define db(a) for(auto it:a) {cout<<it<<" ";}cout<<endl;
ll prime[MAX];
ll fact[MAX];

const long long INF64 = 1e18;
ll vpow(ll a,ll b,ll p){
    if(b==0)
        return 1;
    if(b==1)
            return a;
    ll temp=vpow(a,b/2,p);
    temp*=temp;
    temp%=p;
    if(b%2==0)
        return temp;
    temp=temp*a;
    temp%=p;
    return temp;
}

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


ll inverseMod(ll a,ll b,ll p){
    if(b==0)
        return 1;
    ll temp=vpow(b,p-2,p);
    ll ans=temp*a;
    ans%=p;
    return ans;
}
void sieve()
{
    prime[0] = prime[1] = 1;
    for (ll i = 2; i < MAX; i++) {
        if (prime[i] == 0) {
            for (int j = i * 2; j < MAX; j += i) {
                if (prime[j] == 0) {
                    prime[j] = i;
                }
            }
            prime[i] = i;
        }
    }
}
ll max(ll a, ll b)
{
    return a>b?a:b;
}
ll min(ll a, ll b)
{
    return a<b?a:b;
}

void factorial(){
    fact[0]=1;
    fact[1]=1;
    rep(i,2,MAX){
        fact[i]=(fact[i-1]*i);
        // fact[i]%=M;
    }
}
ll rand(ll a,ll b){
    return a+rand()%(b-a+1);
}


void solve(ll ttt)
{
    ll n;
    cin>>n;
    string s="ACL", t;
    ll i;
    for(i=0;i<n;i++)
        t+=s;
    cout<<t<<endl;
}

int main(){
    io;
    // sieve();
    // factorial();
#ifndef ONLINE_JUDGE
    //
    //freopen("input1.txt","r",stdin);
    // freopen("output1.txt","w",stdout);
#endif
    ll t=1;
     //cin>>t;
    fix(12);
    rep(q,1,t+1){
         //cout<<"Case #"<<q<<": ";
         //cout<<"Test Case : "<<q<<endl;
         solve(q);
    }
    return 0;

}




Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
const int MOD = 1000000007;

bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}

vector<int> sosu(0);
bool sosuu[100001]={false};
void erast(){
  REP(i,100001)sosuu[i] = true;
  for(int i=2;i<=100000;i++){
    if(sosuu[i]){
      sosu.push_back(i);
      for(int j=i;j<=100000;j+=i){
        sosuu[j] = false;
      }
    }
  }
  return;
}

int main()
{
  int N,di,n2=0,n4=0,n14=0,n24=0,n74=0,res=0;
  cin >> N;
  erast();
  vector<int> lis(0);
  for(int i=0;sosu[i]<=N;i++){
    di = 1;
    int d = 0;
    while(1){
      di *= sosu[i];
      if((N / di) == 0)
        break;
      d += N / di;
    }
    if(d)lis.push_back(d);
  }
  sort(lis.begin(),lis.end());
  for(int i=0;i<lis.size();i++){
    if(lis[i] >= 74){
      n74++;
    }else if(lis[i] >= 24){
      n24++;
    }else if(lis[i] >= 14){
      n14++;
    }else if(lis[i] >= 4){
      n4++;
    }else if(lis[i] >= 2){
      n2++;
    }
  }
  n2 += n4+n14+n24+n74;
  n4 +=    n14+n24+n74;
  n14 +=       n24+n74;
  n24 +=           n74;
  res += n74 + (n24)*(n2-1) + (n14)*(n4-1) + ((n4)*(n4-1)*(n2-2))/2;
  cout << res << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod (int)1000000007
#define pb push_back
#define endl "\n"
#define all(a) a.begin(),a.end()
#define mx(a) *max_element(all(a))
#define mn(a) *min_element(all(a))
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repe(i,a,b) for(int i=a;i<=b;i++)
#define repo(i,b) for(int i=(int)0;i<b;i++)
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

signed solve(){
	int n,k;
	cin>>n>>k;
	int a[n]={0};
	rep(i,0,n) cin>>a[i];
	int dp[n];
	for(int i=0;i<n;i++) dp[i]=INT_MAX;
	dp[0]=0,dp[1]=abs(a[0]-a[1]);
	for(int i=2;i<n;i++){
		for(int j=i-1;j>=max((int)0,i-k);j--){
			dp[i]=min(dp[i],abs(a[i]-a[j])+dp[j]);
		}
		// cout<<dp[i]<<" ";
	}
	cout<<dp[n-1]<<endl;
	return 0;
}

signed main(){
	fast;
	int tests=1;
	// cin>>tests;
	while(tests--){
		solve();
	}
}

Measured memory_bytes: 5184
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    int N,K;
    string S;
    cin >> N >> S >> K;
    char C=S[K-1];
    rep(i,S.length()) if(S[i]!=C) S[i]='*';
    cout << S << endl;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
use {
   proconio::{fastout, input, marker::*},
   std::cmp::*,
   std::collections::*,
};

#[fastout]
fn main() {
   input! {
      n:usize,
      ab:[(Usize1, Usize1); n-1],
      m:usize,
      uv:[(Usize1, Usize1); m]
   }

   let mut map = BTreeMap::new();
   map.insert((0, 0), 1);
   let mut to = vec![vec![]; n];
   for (i, &(a, b)) in ab.iter().enumerate() {
      to[a].push((b, i));
      to[b].push((a, i));
   }
   let mut eset = vec![0usize; m];
   for i in 0..m {
      let (u, v) = uv[i];
      let mut root = vec![];
      dfs(u, v, u, &to, &mut root);
      for j in root {
         eset[i] |= 1 << j;
      }
   }

   let mut ans: i64 = 0;
   for i in 0..1 << m {
      let mut mask = 0usize;
      let mut c: i64 = 1;
      for j in 0..m {
         if i >> j & 1 == 1 {
            mask |= eset[j];
            c *= -1;
         }
      }
      let white: usize = (0..n - 1).map(|i| mask >> i & 1).sum();
      ans += c * (1 << (n - 1 - white));
   }
   println!("{}", ans);
}

fn dfs(
   v: usize,
   tv: usize,
   p: usize,
   to: &Vec<Vec<(usize, usize)>>,
   root: &mut Vec<usize>,
) -> bool {
   if v == tv {
      true
   } else {
      for &(u, i) in to[v].iter() {
         if u == p {
            continue;
         }
         if dfs(u, tv, v, to, root) {
            root.push(i);
            return true;
         }
      }
      false
   }
}


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

int main() {
    int a[100], n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for (int i = n-1; i >= 0; i--) {
    cout << a[i];
    if (i !=0) {
    	cout << " ";
    } else { 
    	cout << endl;
    }
  }
	return 0;
}


Measured memory_bytes: 3088
#include<iostream>
using namespace std;
int main()
{
  int a,b,i;
  cin>>a>>b;
  if(a<b)
  {
    for(i=0;i<b;i++)
      cout<<a;
  }
  else if(b<a)
  {
    for(i=0;i<a;i++)
    cout<<b;
  }
  else
    for(i=0;i<a;i++)
      cout<<a;
  return 0;
}
  

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Main<br/>
 *
 * @author Tomo
 * @see <http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_A&lang=ja>
 */
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) {
      A[i] = sc.nextInt();
    }
    trace(A);
    insertionSort(A, N);
  }

  private static void insertionSort(int[] A, int N) {
    for (int i = 1; i < N; i++) {
      int v = A[i];
      int j = i - 1;
      while (j >= 0 && A[j] > v) {
        A[j + 1] = A[j];
        j--;
      }
      A[j + 1] = v;
      trace(A);
    }
  }

  private static void trace(int[] A) {
    StringBuffer sb = new StringBuffer();
    for (int a : A) {
      sb.append(a).append(" ");
    }
    System.out.println(sb.toString().trim());
  }
}



Measured memory_bytes: 28820
#include <bits/stdc++.h>
using namespace std;
#define l long

int main(){
     ios::sync_with_stdio(0);
     cin.tie(0);
     
     string a;
     cin >> a;
     int n = a.length();
     while(n--){
		 cout << "x";
	 }
     
     
     
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string S,T;
  cin>>S>>T;
  int Ans=0;
  for(int i=0;i<S.length();i++)
    if(S[i]!=T[i])
      Ans++;
  cout<<Ans<<endl;
  return 0;
}

Measured memory_bytes: 3912
import numpy as np

H,W=map(int,input().split())
a=np.zeros((H,W))
for i in range(H):
    tmp = input()
    for j in range(W):
        if tmp[j] == "#":
            a[i][j]=1

tmp=[]
for i in range(H):
    if np.sum(a[i])==0:
        tmp.append(i)
a = np.delete(a,tmp,0)

h=len(tmp)

a = a.T

tmp=[]
for i in range(W):
    if np.sum(a[i])==0:
        tmp.append(i)
a = np.delete(a,tmp,0)
               
a = a.T

w = len(tmp)

ans = list(a)

for i in range(H-h):
    tmp=a[i]
    for j in range(W-w):
        if tmp[j] == 1:
            print("#", end="")
        else:
            print(".", end="")
    print()


Measured memory_bytes: 13784
H, W = map(int, input().split())
bd = []

for i in range(H):
    bd.append(input())

x = set()
y = set()
for i in range(H):
    for j in range(W):
        if bd[i][j] == '#':
            x.add(j)
            y.add(i)

for i in y:
    for j in x:
        print(bd[i][j], end='')
    print()


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


def main():
    N, M = map(int, input().split())
    H = list(map(int, input().split()))
    good = [1] * N
    for _ in range(M):
        a, b = map(int, input().split())
        if H[a - 1] > H[b - 1]:
            good[b - 1] = 0
        elif H[a - 1] < H[b - 1]:
            good[a - 1] = 0
        else:
            good[a - 1] = 0
            good[b - 1] = 0
    print(sum(good))
    


if __name__ == "__main__":
    main()


Measured memory_bytes: 85852
#include <iostream>


int main()
{

  while (true)
  {
    int n;
    std::cin >> n;

    if (n == 0)
      break;
    
    int num = 0;
    
    for (int j = 2; j < n; j++)
      for (int i = 1; i < n; i++)
	if ((2*i + j - 1) * j == 2 * n)
	  num++;
    
    std::cout << num << std::endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>

using namespace std;
#define MAX 10000
#define NIL -1

struct Node
{
	int p;
	int l;
	int r;
};
struct Node T[MAX];

void preParse(int u)
{
	if (u == NIL)
	{
		return;
	}
	cout << " " << u;
	preParse(T[u].l);
	preParse(T[u].r);
}

void inParse(int u)
{
	if (u == NIL)
	{
		return;
	}
	inParse(T[u].l);
	cout << " " << u;
	inParse(T[u].r);
}

void postParse(int u)
{
	if (u == NIL)
	{
		return;
	}
	postParse(T[u].l);
	postParse(T[u].r);
	cout << " " << u;
}

void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		T[i].p = NIL;
	}
	int v, l, r;
	for (int i = 0; i < n; ++i)
	{
		cin >> v >> l >> r;
		T[v].l = l;
		T[v].r = r;
		if (l != NIL)
		{
			T[l].p = v;
		}
		if (r != NIL)
		{
			T[r].p = v;
		}
	}
	int root;
	for (int i = 0; i < n; ++i)
	{
		if (T[i].p == NIL)
		{
			root = i;
		}
	}
	cout << "Preorder" << endl;
	preParse(root);
	cout << endl;
	cout << "Inorder" << endl;
	inParse(root);
	cout << endl;
	cout << "Postorder" << endl;
	postParse(root);
	cout << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1164
#include <stdio.h>
#include <stdbool.h>
#define min(X, Y) ((X) < (Y) ? (X) : (Y))
typedef long long ll;

const ll inf = (1ll << 60ll);

ll d, g;
ll p[11], c[11];
ll ans = inf;
bool used[11];

ll dfs(ll points, ll i);

int main()
{
	scanf("%lld %lld", &d, &g);
	for (ll i = 1; i <= d; i++) {
		scanf("%lld %lld", &p[i], &c[i]);
	}

	printf("%lld\n", dfs(0, 1));

	return 0;
}

ll dfs(ll points, ll i)
{
	if (points >= g) { 
		return 0;
	}

	if (i > d) {

		ll j = d;

		while (used[j] && j > 0) {
			j--;
		}

		//(g - points) / (100 * j) + ((g - points) % (100 * j) ? 1 : 0)
		if ((g - points) / (100 * j) + ((g - points) % (100 * j) ? 1 : 0) < p[j]) {
			return (g - points) / (100 * j) + ((g - points) % (100 * j) ? 1 : 0);
		} else {
			return inf;
		}
	}

	ll ret_val;

	used[i] = true;
	ret_val = dfs(points + (100 * i) * p[i] + c[i], i + 1) + p[i];

	used[i] = false;
	ret_val = min(ret_val, dfs(points, i + 1));

	return ret_val;
}


Measured memory_bytes: 128
import sys
from pprint import pprint

import itertools

n, m = map(int, sys.stdin.readline().strip().split(" "))

edges = set()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    edges.add((a, b))
    edges.add((b, a))

ans = 0
for seq in itertools.permutations([i for i in range(1,n+1)]):
    # pprint(seq)
    flag = True
    for i in range(n-1):
        # print(seq[i], seq[i+1])
        if i == 0 and seq[i] != 1:
            # print("Not start from 1")
            flag = False
            break
        if (seq[i], seq[i+1]) not in edges:
            # print("Not")
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Measured memory_bytes: 40688
#include <vector> 
#include <list> 
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;

int main() {


	LL N, M;
	cin >> N >> M;

	// vector< vector<bool> > board(N);
	// REP(i, N) {
	// 	board[i].resize(M);
	// }

	// auto reverseing = [&](int i, int j) {

	// 	for (int x = i - 1; x <= i + 1; x++) {
	// 		if (x<0 || x >= N) { continue; }
	// 		for (int y = j - 1; y <= j + 1; y++) {
	// 			if (y<0 || y >= M) { continue; }
	// 			if (board[x][y] == false) { board[x][y] = true; }
	// 			else if (board[x][y] == true) { board[x][y] = false; }

	// 		}
	// 	}

	// };

	
	LL ans = max((N-2)*(M-2),0LL);
    LL i,j;
    i=0;
    if(i==N-1){
        ans+=max(M-2,0LL);
    }
    if(j==M-1){
        ans+=max(N-2,0LL);
    }
  
	cout << ans << endl;
}


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

 using namespace std;
 typedef long long ll;

 int main() {
   string S, T, U;
   int A, B;
   cin >> S >> T >> A >> B >> U;

   if (U == S) cout << A - 1 << " " << B << endl;
   else cout << A << " " << B - 1 << endl;

 }


Measured memory_bytes: 256
n=int(input())
l=[]
def upgrade(edge):
    s=len(edge)
    for i in range(s):
        [a,b]=edge[i]
        edge[i]=[a+1,b+1]

def odd(edge,n):
    for i in range(n-1):
        edge.append([n,i+1])

def even(edge,n):
    upgrade(edge)
    for i in range(1,n):
        edge.append([1,i+1])

def print_edge(edge):
    s=len(edge)
    for i in range(s):
        [a,b]=edge[i]
        print(a,b)

edge=[]
#3
edge.append([1,3])
edge.append([2,3])
for i in range(3,n):
    if i%2==0:
        odd(edge,i+1)
    elif i%2==1:
        even(edge,i)
#
print(len(edge))
print_edge(edge)

Measured memory_bytes: 4168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    string S,a1,a2,a3;
    cin >>S;
    a1=S.substr(0,5);
    a2=S.substr(6,7);
    a3=S.substr(14,5);
    cout << a1<<" "<<a2<<" "<<a3 << endl;


    return 0;
    

}

Measured memory_bytes: 3532
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, A, B = MAP()
S = input()
f = 0
passed = 0
for i, s in enumerate(S):
	if s == "b":
		f += 1
	if s == "a" and passed < A+B:
		print("Yes")
		passed += 1
	elif s == "b" and passed < A+B and f <= B:
		print("Yes")
		passed += 1
	else:
		print("No")


Measured memory_bytes: 6284
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <bitset>

using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef long long LL;

typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<string, int> PSI;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define REP(i,n)  for(int i=0; i<(n); i++)

//constant
//--------------------------------------------
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
const LL MOD = 1e9+7; 
//vector <vector<int>> x(20, vector<int> (20)), y(20,vector<int> (20));
/*int counter_1 (int x) {
    if(x == 0) return 0;
    return counter_1(x >> 1) + (x & 1);
}*/

//int Counter(int x)
/*int factorial(int n) {
    if (n > 0) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}*/
/*bool pairCompare(const P& firstElof, const P& secondElof)
{
    return firstElof.second > secondElof.second;
}*/
int main(){
   int n, kbr=0, ans;
   cin >> n;
   string s, t;
   cin >> s >> t;
   FOR(i,0,n){
       if(s.substr(n-1-i)==t.substr(0,i+1)){
           kbr=max(kbr, i+1);
       }
   }
    ans=2*n-kbr;
    cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    PrintWriter out = new PrintWriter(System.out);
    long mod = 1000000000+7;
    int maxN;
    long[] frac, inv;
    public static void main(String[] args) throws Exception {
        Main main = new Main();
//        main.solve();
        System.out.println(main.solve());
    }
    long solve(){
        // it's all about implementation
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        this.maxN = n+50;
        ini();
        for(int i=1;i<=k;i++){
            long cur = helper(i,n,k);
            out.println(cur);
        }
        out.flush();
        System.exit(0);
        return 0;
    }
    long helper(int i, int n, int k){
        // split k blue balls into i parts
        if(i>n-k+1) return 0;
        long ans = frac[k-1]*inv[i-1]%mod*inv[k-i]%mod;
        int red = n-k-(i-1); // first take i-1 read balls to split
        int pos = i+1;
        ans = ans*frac[pos+red-1]%mod*inv[pos-1]%mod;
        ans = ans*inv[red]%mod;
        return ans;
    }
    void ini(){
        frac = new long[maxN+1];
        inv = new long[maxN+1]; // inv[i] means the inverse of frac[i] in sense of mod
        frac[0] = 1;
        for(int i=1;i<=maxN;i++) frac[i] = i*frac[i-1]%mod;
        inv[maxN] = power(frac[maxN], mod-2);
        inv[0] = 1;
        for(int i=maxN-1;i>=1;i--){
            inv[i] = (i+1)*inv[i+1]%mod;
        }

    }
    long power(long base, long p){
        long ans = 1;
        while(p>0){
            if(p%2==1) ans = ans*base%mod;
            base = base*base%mod;
            p /= 2;
        }
        return ans;
    }
}



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

using namespace std;

#define ll long long


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

	ll sum = 0;

	for (int i = 0; i < m; i++) {
		ll temp;
		cin >> temp;
		sum += temp;
	}

	cout << (n - sum < 0 ? -1 : n - sum);
}

Measured memory_bytes: 3636
// lcmとかはg++ -std=c++17 default.cppみたいなかんじで
//vector<vector<ll>> piyo(tate,vector<ll> (yoko));

#include <bits/stdc++.h>
#define mod 1000000007
#define INF 1000000000
#define ll long long
#define ln cout<<endl;
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define double long double
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
using namespace std;

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

    ll a,b,c,d,m,n,maxi=0,f=0,mini=INF,sum=0;
    string str,str2;
    ll x;
    cin>>n;
    cin>>m>>x;
    vector<ll> v(n);
    rep(i,n) cin>>v[i];
    sum=n;
    rep(i,n){
        sum+=m/v[i];
        if(m%v[i]==0) sum--;
    }
    cout<<sum+x<<endl;
  
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
vector<long long> b;
vector<long long> c;

int binary_search_A(long long key) {
    int ok = -1;
    int ng = (int)a.size();
    while(abs(ok-ng) > 1) {
        int mid = (ok+ng) / 2;
        if(a.at(mid) < key) ok = mid;
        else ng = mid;
    }
    return ok;
}

int binary_search_C(long long key) {
    int ng = -1;
    int ok = (int)c.size();
    while(abs(ok-ng) > 1) {
        int mid = (ok+ng) / 2;
        if(c.at(mid) > key) ok = mid;
        else ng = mid;
    }
    return ok;
}

int main() {
    cin >> n;
    a = vector<long long>(n,0);
    b = vector<long long>(n,0);
    c = vector<long long>(n,0);;
    for(int i = 0; i < n; ++i) cin >> a.at(i);
    for(int i = 0; i < n; ++i) cin >> b.at(i);
    for(int i = 0; i < n; ++i) cin >> c.at(i);

    sort(a.begin(), a.end());
    sort(c.begin(), c.end());

    long long ans = 0;

    for(int i = 0; i < n; ++i) {
        long long acnt = 0;
        long long ccnt = 0;
        if(a.at(n-1) < b.at(i)) {
            acnt = n;
        }else {
            acnt = binary_search_A(b.at(i)) + 1;
        }
        if(c.at(0) > b.at(i)) {
            ccnt = n;
        }else {
            ccnt = n - binary_search_C(b.at(i));
        }
        // cout << "acnt " << acnt << " ccnt " << ccnt << endl;
        ans += acnt*ccnt;
    }

    cout << ans << endl;
}

Measured memory_bytes: 2560
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 0x3f3f3f3f;
const int maxn = 200000 + 10;
char s[maxn];
int rpos[maxn];
char t[maxn];
int n, m;
int main()
{
  scanf("%s", s);
  n = strlen(s);
  m = 0;
  for (int i = 0; i < n; i++)
  {
    if (s[i] != 'x')
    {
      rpos[m] = i;
      t[m++] = s[i];
    }
  }
  if (m == 0)
  {
      printf("0\n");
    return 0;
  }
  for (int i = 0, j = m-1; i < j; i++, j--)
  {
    if (t[i] != t[j])
    {
      printf("-1\n");
      return 0;
    }
  }

    int mid = (m / 2);
    int ans = 0, l = rpos[mid], r = rpos[mid];
    if (!(m & 1))
    {
      l = rpos[mid - 1];
    }
    while(l >= 0 && r < n)
    {
      //cout << l << " " << r << endl;
      if (s[l] == s[r])
      {
        l--;
        r++;
      }
      else if (s[l] == 'x')
      {
        l--;
        ans++;
      }
      else if (s[r] == 'x')
      {
        r++;
        ans++;
      }
    }
  ans += (l + 1 + (n - r));
  printf("%d\n", ans);
}


Measured memory_bytes: 896
#include <stdio.h>

int main(){
	char str[10000];
	
	while ( scanf( "%s", str) == 1 ){
		int j = 0, i = 0, a;
		for ( a = 0; str[a] != '\0'; a++ ){
			if( str[a] == 'J' && str[a+1] == 'O' && str[a+2] == 'I' ){
				j++;
			}
		}
		for ( a = 0; str[a] != '\0'; a++ ){
			if( str[a] == 'I' && str[a+1] == 'O' && str[a+2] == 'I' ){
				i++;
			}
		}
		printf("%d\n%d\n", j, i);
	}
	
	return 0;
}

//ポインタで実行するには？
/*
#include <stdio.h>
#include <string.h>

int main(){
	char str[10000], *p;
	
	while ( scanf( "%s", str) == 1 ){
		int j = 0, i = 0;
		for ( p = str; *p != '\0'; p++ ){
			if( *p == 'J' && *(p+1) == 'O' && *(p+1) == 'I' ){
				j++;
			}
		}
		for ( p = str; *p != '\0'; p++ ){
			if( *p == 'I' && *(p+1) == 'O' && *(p+1) == 'I' ){
				i++;
			}
		}
		printf("%d\n%d\n", j, i);
	}
	
	return 0;
}
*/

Measured memory_bytes: 556
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)

li = []
x.sort()
for i in range(N):
  li.append(x[i+1]-x[i])
  
li.sort()
while len(li) > 1:
  l = []
  div = li[0]
  for n in li:
    mod = n % div
    if mod != 0:
      l.append(mod)
  l.append(div)
  l.sort()
  li = l
print(*li)

Measured memory_bytes: 19940
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cout << #x << ": " << x << endl
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	int l = 1, r = n;
	rep(i, m){
		int a, b;
		cin >> a >> b;
		l = max(l, a);
		r = min(r, b);
	}
	cout << ((r - l + 1 >= 0) ? r - l + 1 : 0) << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


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

using namespace std;
typedef pair<int, int> P ;
bool prime[2160000];
int val[1200][1200];
P dp[1200][1200];
int xs[] = {1, 0, -1, 0}, ys[] = {0, 1, 0, -1};


bool solve(){
  int m, n;
  cin >> m >> n;
  if(m == 0 && n == 0)return false;
  for(int i = 0;i < 1200;i++)
    for(int j = 0;j < 1200;j++)
      dp[i][j] = P(0, 0);
  for(int j = 1;j < 1100;j++){
    for(int i = 1;i < 1100;i++){
      dp[i][j] = max(dp[i][j-1], dp[i-1][j-1]);
      dp[i][j] = max(dp[i][j], dp[i+1][j-1]);
      if(prime[val[i][j]] && 1 <= val[i][j]  && val[i][j] <= m){
	if(dp[i][j].first == 0){
	  dp[i][j].second = val[i][j];
	}
	dp[i][j].first++;
      }
      if(val[i][j] == n){
	cout << dp[i][j].first << " " << dp[i][j].second << endl;
	return true;
      }
    }
  }
}

int main(){
  fill(prime, prime + 1080000, true);
  prime[0] = prime[1] = false;
  for(int i = 2;i  < 1080000;i++){
    if(prime[i]){
      for(long long j = (long long)i * i;j < 1080000;j += i)
	prime[j] = false;
    }
  }
  for(int i = 0, p = 1, x = 550, y = 550;i < 2000;i++){
    if(p >= 1080000)break;
    for(int j = 0;j < (i / 2) + 1;j++){
      if(p >= 1080000)break;
      val[x][y] = p++;
      x += xs[i % 4];
      y += ys[i % 4];
    }
  }
  while(solve());
  return 0;
}

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

#ifdef LOCAL
        #include "debug.h"
        #define input freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#else
        #define debug(...) 4
        #define input 4
#endif

using ll = long long;
constexpr int N = 2e5+ 5;
constexpr int mod = 1e9 + 7;

int main() {
    input;
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int n;
    cin >> n;
    cout << (1000 -n % 1000) % 1000;

}




Measured memory_bytes: 3588
H,W,D=map(int,input().split())
l=[[] for r in range(D)]

for i in range(1,H+1):
    Ai=list(map(int,input().split()))
    for j,Aij in enumerate(Ai):
        l[Aij%D].append((Aij,i,j+1))

for lr in l:
    lr.sort()

# print(l)

d=[]
for r in range(D):
    lr=[]
    for i in range(len(l[r])-1):
        lr.append(abs(l[r][i][1]-l[r][i+1][1])+abs(l[r][i][2]-l[r][i+1][2]))
    d.append(lr)

# print(d)

s=[]
for r in range(D):
    sr=[0]
    for i in range(len(d[r])):
        sr.append(sr[i]+d[r][i])
    s.append(sr)

# print(s)

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    r=L%D
    left=(L-r)//D-(1 if r==0 else 0)
    right=(R-r)//D-(1 if r==0 else 0)

    print(s[r][right]-s[r][left])

Measured memory_bytes: 80764
#include <bits/stdc++.h>
using namespace std;
 
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

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

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

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

int main(){
  int n,m,k,a,b,c,d,ans;
  cin>>n>>m>>k;
  
  vector<int>M[n];
  vector<int>K[n];
  
  UnionFind uf(n);
  
  //フレンド登録
  for(int i=0;i<m;i++){
    cin>>a>>b;
    a--;
    b--;
    M[a].push_back(b);
    M[b].push_back(a);
    uf.unite(a,b);
  }
  //ブロック登録
  for(int i=0;i<k;i++){
    cin>>c>>d;
    c--;
    d--;
    if(uf.root(c)==uf.root(d)){
      K[c].push_back(d);
      K[d].push_back(c);
    }
  }  
  
  int flag=0;
  
  map<int,int>mp;
  for(int i=0;i<n;i++){
    //cout<<uf.root(i)<<endl;
    mp[uf.root(i)]++;
  }
    
  for(int i=0;i<n;i++){
    ans=0;
    //iの連結成分数 mp[root[i]]
    ans=mp[uf.root(i)]-1-M[i].size()-K[i].size();
    //cout<<" "<<M[i].size()<<"*"<<K[i].size()<<" ";
    if(flag){
      cout<<" "<<ans;
    }
    else{
      cout<<ans;
      flag=1;
    }
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 15676
n = int(input())
A = list(map(int, input().split()))

def CountingSort(A, B, k):
    C = [0] * k

    for j in range(n):
        C[A[j]] += 1

    for i in range(1, k):
        C[i] = C[i] + C[i-1]

    for j in range(n-1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

B = [0] * n
CountingSort(A, B, 10000)

print(' '.join(map(str, B)))



Measured memory_bytes: 240328
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
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;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  map<int,int> mp;
  rep(i,n){
    mp[a[i]]++;
  }
  bool flag=1;
  if(n%2==0){
    for(auto c:mp){
      if(c.first%2==0||c.second!=2) flag=0;
    }
  }
  else{
    for(auto c:mp){
      if(c.first%2==1||c.first==0?c.second!=1:c.second!=2) flag=0;
    }
  }
  if(flag){
    ll ans=1;
    for(auto c:mp){
      ans*=c.second;
      ans%=mod;
    }
    cout << ans << endl;
  }
  else{
    cout << 0 << endl;
  }
  //cout << flag << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define INF 2e9
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

int ctoi(const char c){
  if('0' <= c && c <= '9') return (c-'0');
  return -1;
}

int main(){
  string S;
  cin >> S;
  if(S.at(2)==S.at(3)&&S.at(4)==S.at(5)) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>
#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

struct UnionFind {
  vector<int> par;

  UnionFind(int N) : par(N) { rep(i, N) par[i] = i; }

  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    if (rx==ry) return;
    par[rx] = ry;
  }

  bool same(int x, int y) {
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }

};


int main() {
  int N, M; cin >> N >> M;
  int p[N] = {}; rep(i, N) cin >> p[i];
  UnionFind tree(N+1);
  rep(i, M) {
    int x, y; cin >> x >> y;
    tree.unite(x, y);
  }

  int result = 0;
  rep(i, N) if (tree.same(i+1,p[i])) result++;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 1024
mod = 10**6+3
def solve(left,right):
    cnt = 1
    while left < right:
        cnt = cnt*dp[left][1]%mod
        left = dp[left][0]+1
    return cnt

while True:
    n,m = map(int, input().split())
    if n == m == 0:
        break
    if n%2 == 1:
        print(0)
    else:
        dp = [[0,0]] * n
        brli = []
        for i in range(n-1):
            dp[i] = [i+1, 1]
        for i in range(m):
            a, b = map(int, input().split())
            if a > b:
                a, b = b, a
            if (b-a)%2 == 1:
                brli.append((a-1, b-1))
        brli.append((0, n-1))
        brli.sort(key=lambda x: x[1]-x[0])
        for br in brli:
            l, r = br[0], br[1]
            dp[l+1] = [r-1, solve(l+1, r-1)]
            dp[l] = [r,(dp[l+1][1]+dp[l][1]*solve(dp[l][0]+1, r))%mod]
        print(dp[0][1])


Measured memory_bytes: 15928
use std::fmt;
use std::io::stdin;
use std::io::BufRead;
use std::str;
use std::str::FromStr;
use std::vec::Vec;
use std::cmp;

fn main() {
    let stdin = stdin();
    let mut scan = InputScanner::new(stdin.lock(),256);

	let d:usize = scan.next();
	let g:usize = scan.next();

	let pc:Vec<(usize,usize)> = (0..d).map(|_| (scan.next(),scan.next())).collect::<Vec<(usize,usize)>>();
	let mut pi = pc.iter()
													.enumerate()
													.map(|(i,&(p,_))| (i,p))
													.collect::<Vec<(usize,usize)>>();

	pi.sort_by(|a,b| b.1.cmp(&a.1));

	let mut m = (0..d).map(|_| false).collect::<Vec<bool>>();

	let answer = search(g,d,&pc,&pi,0,&mut m);

	println!("{}",answer);
}
fn search(g:usize,d:usize,pc:&[(usize,usize)],pi:&[(usize,usize)],i:usize,m:&mut Vec<bool>) -> usize {
	let mut min = std::usize::MAX;

	if i < d {
		{
			let mut m = m.clone();
			min = cmp::min(min, search(g, d, pc, pi, i + 1, &mut m));
		}

		{
			let mut m = m.clone();
			m[i] = true;
			min = cmp::min(min, search(g, d, pc, pi, i + 1, &mut m));
		}

		min
	} else {
		min = 0;

		let mut sum = 0;

		for &(i,_) in pi {
			if m[i] {
				sum += (i + 1) * pc[i].0 * 100 + pc[i].1;
				min += pc[i].0;
			}
		}

		if sum >= g {
			return min;
		}
		
		for &(i,p) in pi {
			if !m[i] {
				if sum + (i + 1) * 100 * (p - 1) <= g {
					sum += (i + 1) * 100 * (p - 1);
					min += p - 1;
				} else {
					let p = (g - sum - 1) / ((i + 1) * 100) + 1;
					sum += (i + 1) * 100 * p;
					min += p;
				}

				if sum >= g {
					return min;
				}
			}
		}
		std::usize::MAX
	}
}
struct InputScanner<R: BufRead> {
	reader: R,
	buf: Vec<u8>, // Should never be empty
	pos: usize,   // Should never be out of bounds as long as the input ends with '\n'
}
impl<R: BufRead> InputScanner<R> {
	fn new(reader: R, capacity: usize) -> Self {
		InputScanner {
			reader: reader,
			buf: Vec::with_capacity(capacity),
			pos: 0,
		}
	}

	#[inline]
	fn next<T: FromStr>(&mut self) -> T
	where
		T::Err: fmt::Debug,
	{
		if self.buf.is_empty() {
			self._read_next_line();
		}
		let mut start = None;
		loop {
			match (self.buf[self.pos], start.is_some()) {
				(b' ', true) | (b'\n', true) | (b'\r', true) => break,
				(_, true) | (b' ', false) => self.pos += 1,
				(b'\n', false) | (b'\r', false) => self._read_next_line(),
				(_, false) => start = Some(self.pos),
			}
		}
		let target = &self.buf[start.unwrap()..self.pos];
		unsafe { str::from_utf8_unchecked(target) }.parse().unwrap()
	}

	#[inline]
	fn _read_next_line(&mut self) {
		self.pos = 0;
		self.buf.clear();
		if self.reader.read_until(b'\n', &mut self.buf).unwrap() == 0 {
			panic!("Reached EOF");
		}
	}
}



Measured memory_bytes: 4352
#include <iostream>
//#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <set>
#include <map>
#include <string.h>
#include <iomanip>
#include <utility>
#include <bitset>
#include <random>
#pragma warning(disable:4996)
using namespace std;


const int MAXN = 2e5 + 5, INF = 1e9;



int main() {
	int x, y;
	cin >> x >> y;
	cout << x + y / 2 << endl;
	return 0;
}

Measured memory_bytes: 256