akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,x,n) for (int i = x;i < n;++i)

int d[5001][5001], md = 1e9 + 7;
char s[5001];

int main() {
	int n;
	scanf("%d%s", &n, s);
	int m = strlen(s);
	d[0][0] = 1;
	f(i, 1, n + 1) {
		d[0][i] += d[0][i - 1];
		if (d[0][i] >= md)d[0][i] -= md;
		f(j, 1, n + 1) {
			d[j][i] += d[j - 1][i - 1];
			if (d[j][i] >= md)d[j][i] -= md;
			d[j - 1][i] += 2 * d[j][i - 1] % md;
			if (d[j - 1][i] >= md)d[j - 1][i] -= md;
		}
	}
	printf("%d", d[m][n]);
}

Measured memory_bytes: 97920
s = input()
count = [0,0,0]
for i in range(len(s)):
    if s[i] == 'a':
        count[0] += 1
    elif s[i] == 'b':
        count[1] += 1
    else:
        count[2] += 1
if len(s)%3 == 0:
    if count[0] == count[1] == count[2]:
        print('YES')
    else:
        print('NO')
elif len(s)%3 == 1:
    count.sort()
    if count[0] == count[1] == count[2]-1:
        print('YES')
    else:
        print('NO')
else:
    count.sort()
    if count[0] == count[1]-1 == count[2]-1:
        print('YES')
    else:
        print('NO')


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<char> str(4);
  for(int i=0;i<4;i++) cin >> str[i];
  sort(str.begin(),str.end());
  if(str[0]!=str[1]||str[1]==str[2]||str[2]!=str[3]){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <sstream>
#include <climits>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define EPS 1e-12
#define pri_max 60000
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
/*
bool memo[pri_max] = {};
vector<int> pri;
void calc()
{
	for (int i = 2; i < pri_max; i++)
	{
		if (memo[i] == false)
		{
			pri.push_back(i);
			for (int l = i; l < pri_max; l += i)
			{
				memo[l] = true;
			}
		}
	}
}*/
int main()
{
	string x;
	while (cin >> x)
	{
		int d[8][3] = { {1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{3,5,7} };
		bool ok = true;
		string a = " " + x;
		for (int i = 0; i < 8&&ok; i++)
		{
			for (int l = 0; l < 2; l++)
			{
				if (a[d[i][l]] != a[d[i][l + 1]]||a[d[i][l]]=='s')break;
				if (l == 1)
				{
					cout << a[d[i][l]] << endl;
					ok = false;
					break;

				}
			}
		}
		if (ok)
		{
			cout << "d" << endl;
		}
	}
}

Measured memory_bytes: 1180
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<P,int> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define LLINF 1000000000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N,M;
vector<int> g[100100];
int col[100100];
bool used[100100];
int num[3];
bool dfs(int v,int c){
	col[v]=c;
	num[c+1]++;
	used[v]=true;
	bool flag = true;
	for(int i=0;i<g[v].size();i++){
		int u = g[v][i];
		if(col[u]==c)flag = false;
		if(used[u])continue;
		if(!dfs(u,-c))flag = false;
	}
	return flag;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++){
		int A,B;
		scanf("%d %d",&A,&B);
		A--;B--;
		g[A].pb(B);
		g[B].pb(A);
	}
	ll ans = 0ll;
	for(int i=0;i<N;i++){
		num[0]=num[2]=0;
		if(!used[i]){
			if(dfs(i,1)){
				ans += (ll)num[0]*(ll)num[2];
			}else{
				ll s = num[0]+num[2];
				ans += s*(s-1ll)/2ll;
			}
		}
	}
	cout << ans - (ll)M << endl;
	return 0;
}

Measured memory_bytes: 7808
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void){
int a;
int c;
int i;
int max;
int min;
long sum=0;

  scanf("%d",&c);
for(i=1;i<=c;i++){
  scanf("%d",&a);
  if(c==1){
    max = a;
    min = a;}
  if(max < a){
    max = a;}
  if(min > a){
    min = a;}
  sum = sum + a;
}
printf("%d %d %ld\n",min,max,sum);
return 0;
}


Measured memory_bytes: 2104
line = input().rstrip().split(' ')

a = int(line[0])
b = int(line[1])
c = int(line[2])
d = int(line[3])

while a > 0 or c > 0:
    c -= b
    if c < 1:
        print('Yes')
        break

    a -= d
    if a < 1:
        print('No')
        break

Measured memory_bytes: 9192
#include<stdio.h>
int main()
{
int n,m,x,i,r,l;
  l=0;
  r=0;
  scanf("%d %d %d",&n,&m,&x);
int a[m];
  for(i=0;i<m;++i)
  {
  scanf("%d",&a[i]);
  if(a[i]<x) l++;
  else r++;
  }
  if(r<l) printf("%d",r);
  else printf("%d",l);
return 0;
}

Measured memory_bytes: 1728
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

  u64 a;

public:
  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  using mint = modint<1000000007>;

  int n, x;
  std::cin >> n >> x;
  std::vector<int> s(n);
  for (auto &e : s) {
    std::cin >> e;
  }
  std::sort(s.begin(), s.end());

  std::vector<std::vector<mint>> dp(n + 1, std::vector<mint>(x + 1));

  for (int i = 0; i <= x; ++i) {
    dp[0][i] = i;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= x; ++j) {
      dp[i + 1][j] = dp[i][j] * i + dp[i][j % s[i]];
    }
  }

  std::cout << dp[n][x].value() << std::endl;

  return 0;
}


Measured memory_bytes: 158592
#include <iostream>
using namespace std;
int main()
{
	int N,aray[100];
	int t_count = 0;
	cin >> N;
	for (int i = 0; i < N; i++) cin >> aray[i];
	int flag = 1;
	while (flag) {
		flag = 0;
		for (int j = N-1; j >= 1; j--) {
			if (aray[j] < aray[j - 1]) {
				int temp;
				temp = aray[j];
				aray[j] = aray[j - 1];
				aray[j - 1] = temp;
				t_count += 1;
				flag = 1;
			}
		}
	}
	for (int k = 0; k < N; k++) {cout << aray[k];
        if(k != N-1)cout << " ";
}
	cout << endl << t_count << endl;
    return 0;
}

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

#define select(_1, _2, x, ...) x

#define repn(i, n) for (int i = 0; i < (n); i++)
#define repr(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, ...) select(__VA_ARGS__, repr, repn)(i, __VA_ARGS__)

#define rrepn(i, n) for (int i = (n - 1); i >= 0; i--)
#define rrepr(i, a, b) for (int i = (b - 1); i >= (a); i--)
#define rrep(i, ...) select(__VA_ARGS__, rrepr, rrepn)(i, __VA_ARGS__)

#define all(v) v.begin(), v.end()
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

const int INF = 1e9;
const ll LINF = 1e18;


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

    cout << (int)((n + 1) / 2) <<  endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    string S;
    cin >> S;
    while(!S.empty()) {
        S.pop_back();
        int l = S.size();
        if (l % 2 == 0) {
            if (S.substr(0, l/2) == S.substr(l/2, l/2)) {
                cout << l << '\n';
                return 0;
            }
        }
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int main()
{
	int n;
	cin>>n;
	int a[N],b[N],c[N];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n;i++)
		cin>>b[i];
	for(int i=1;i<=n-1;i++)
		cin>>c[i];
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		sum+=b[a[i]];
	}
	//cout<<sum<<endl;
	for(int i=1;i<=n-1;i++)
	{
		if(a[i+1]-a[i]==1)
		sum+=c[a[i]];
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3fll
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define pi acos(-1.0)
#define lowbit(x) x &(-x)
const ll maxn = 1e5 + 10;
const ll mod = 1e9;

signed main()
{
	
	db a, b;
	cin >> a >> b;
	int la = a / 0.08 + 0.5, ra = (a + 1) / 0.08 + 0.5;
	int lb = b / 0.1 + 0.5, rb = (b + 1) / 0.1 + 0.5;
	if (max(la, lb) < min(ra, rb))
		cout << max(la, lb);
	else
		cout << -1;
}


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

const int mxn=1e5+5;

ll dp[105][mxn];
int n,W,v[mxn],w[mxn];

int main()
{
    cin>>n>>W;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];

    for(int i=1;i<=n;i++)
    {
        for(int h=1;h<=W;h++)
        {
            dp[i][h]=max(dp[i-1][h],dp[i][h]);
            if(w[i]<=h)
                dp[i][h]=max(dp[i][h],dp[i-1][h-w[i]]+1ll*v[i]);
        }
    }

    cout<<dp[n][W];
    return 0;
}


Measured memory_bytes: 78592
#include<iostream>
#include<stdio.h>
using namespace std;

int main(void){
    int n;
    cin >> n;
    int count=0;
    for(int i = 1;i <= n;i++){
        if(i % 2 == 1)count += 1;
    }
    printf("%f\n",(double)count / n);
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int main(){
    
    int x, i;

    cin >> x;
    
    for ( i = 1; (i < 10001) && (x != 0); i++ ){
        cout << "Case " << i << ": " <<x << endl;
        cin >> x;
}

    return 0;		 
}


Measured memory_bytes: 3096
n = int(input())
p = []

flag = True
id = 0
for i in range(n):
    P = list(map(int, input().split( )))
    p.append(P)
    if P[2]>0:
        id = i
cand = [[-1 for y in range(101)] for x in range(101)]
 
for x in range(101):
    for y in range(101):
        cand[x][y] = p[id][2]+abs(x-p[id][0])+abs(y-p[id][1])
ans =  [[1 for y in range(101)] for x in range(101)]

for i in range(n):
    for x in range(101):
        for y in range(101):
            h = max(cand[x][y]- abs(x-p[i][0])-abs(y-p[i][1]), 0)
            if p[i][2] != h:
                ans[x][y] = 0

ans_x = -1
ans_y = -1
for x in range(101):
    for y in range(101):
        if ans[x][y] == 1:
            ans_x, ans_y = x,y

print(ans_x,ans_y,cand[ans_x][ans_y])
        
    
        

Measured memory_bytes: 47212
def factorization(n):
    L=[]
    temp=n
    print(n,end="")
    print(":",end="")
    for i in range(2,int(n**(1/2)//1)+1):
        if temp%i==0:
            c=0
            while temp%i==0:
                c+=1
                temp//=i
            L.append([i,c])
            for j in range(c):
                print("",i,end="")
    if temp!=1:
        print("",temp,end="")
    
    print()
   
n=int(input())
factorization(n)


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

using namespace std;

int const NMAX = 100;
int v[1 + NMAX + 1];

int main() {

  long long a, b = 0, c = 0;
  bool hasBeen0 = true;
  cin >> a;
  c = a;
  while(a > 0){
    b += a % 10;
    a /= 10;
  }
  if(b == 1 && c != 1){
    cout << 10;
  }else{
    cout << b;
  }
  return 0;
}


Measured memory_bytes: 3592
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String[] ymd = s.split("/");
		int y = Integer.parseInt(ymd[0]);
		int m = Integer.parseInt(ymd[1]);
		if(y<2019) System.out.println("Heisei");
		else if(y>2019) System.out.println("TBD");
		else if(m<=4) System.out.println("Heisei");
		else System.out.println("TBD");
		sc = null;
	}
}


Measured memory_bytes: 23380
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt();
		int[] s = new int[n];
		for (int i = 0; i < n; i++)
			s[i] = stdIn.nextInt();
		
		int q = stdIn.nextInt();
		int[] t = new int[q];
		for (int i = 0; i < q; i++)
			t[i] = stdIn.nextInt();
		
		int c = linearSearch(s, t);
		System.out.println(c);
	}
	
	public static int linearSearch(int[] a, int[] b) {
		int count = 0;
		for (int i = 0; i < b.length; i++)
			for(int j = 0; j < a.length; j++)
				if (b[i] == a[j]) {
					count++;
					break;
				}
		
		return count;
	}
}

Measured memory_bytes: 40384
#include <bits/stdc++.h>
 
#define ALL(l)  (l).begin(),(l).end()
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
//const ll mod =  1000000007;
//const ll maxn = 1000000000;

//---------------------------------------------------------------------------------------------------
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vll = vector<ll>; // intの1次元の型に vi という別名をつける
using vvll = vector<vll>; // intの2次元の型に vvi という別名をつける
using vs = vector<string>; // stringの1次元の型に vs という別名をつける
using pll = pair<ll, ll>; // これ以降 pii という型名はpair<ll, ll> と同じ意味で使える
//---------------------------------------------------------------------------------------------------

int main(){
    map<string, int> poll;
    vs ans;
    ll n;
    cin>>n;
    string s;
    rep(i,n){
        cin>>s;
        if(poll.count(s)){
            poll.at(s)++;
        }else{
            poll[s]=1;
        }
    }
    ll max_poll=0;
    for (auto p : poll) {
      //auto k = p.first;
      ll v = p.second;
      max_poll=max(max_poll,v);
      //cout << k << " => " << v << endl;
    }
    for (auto p : poll) {
          auto k = p.first;
          ll v = p.second;
          if(v==max_poll)ans.push_back(k);
          max_poll=max(max_poll,v);
          //cout << k << " => " << v << endl;
    }
    sort(ALL(ans));
    rep(i,ans.size()){
        cout<<ans.at(i)<<endl;
    }
    //cout<<endl;
//cout<<max_poll;
}
   



Measured memory_bytes: 26868
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    int n;
    cin >> n;
    if(n == 22) cout << "Christmas Eve Eve Eve";
    if(n == 23) cout << "Christmas Eve Eve";
    if(n == 24) cout << "Christmas Eve";
    if(n == 25) cout << "Christmas";

    return 0;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.num = [1] * (n + 1)
        self.sum = 0

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

            num = self.num[x] + self.num[y]
            self.sum += self.num[x] * self.num[y]
            self.num[x] = num
            self.num[y] = num

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = [int(_) for _ in input().split()]
T = [[int(_) for _ in input().split()] for i in range(M)]

uf = UnionFind(N)
C = (N - 1) * N // 2
ans = [C]
for a, b in reversed(T):
    uf.union(a, b)
    ans.append(C - uf.sum)

print(*reversed(ans[:-1]))

Measured memory_bytes: 33456
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;

int main() {
  int N;
  cin >> N;
  int p[N];
  for (int i = 0; i < N; i++) {
    cin >> p[i];
  }
  int streak = 0;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (p[i] == i+1) {
      streak++;
    } else {
      ans += (streak + 1) / 2;
      streak = 0;
    }
  }
  ans += (streak + 1) / 2;
  cout << ans << "\n";
  return 0;
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int N;
    cin >> N;
    vector<int> x(N);
    rep(i,0,N) cin >> x[i];
    int L;
    cin >> L;

    vector<vector<int>> jump(N,vector<int>(17));
    vector<int> pow(17);
    {
        int j=1;
        rep(i,0,N){
            while(j<N and x[j]-x[i]<=L) ++j;
            jump[i][0]=j-1;
        }
        pow[0]=1;
        rep(j,1,17){
            rep(i,0,N) jump[i][j]=jump[jump[i][j-1]][j-1];
            pow[j]=pow[j-1]*2;
        }
    }


    int Q;
    cin >> Q;
    rep(i,0,Q){
        int a,b;
        cin >> a >> b;
        --a;
        --b;
        if(a>b) swap(a,b);
        function<int(int)> ans=[&](int pos){
            for(int j=16; j>=0; --j) if(jump[pos][j]<b) return ans(jump[pos][j])+pow[j];
            return 1;
        };
        cout << ans(a) << endl;
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    solve();
    return 0;
}


Measured memory_bytes: 13184
#include <cstdio>
#include <iostream>

using namespace std;

typedef long long int ll;

const int MAXN = 400000;

ll curpos = 0;
ll X;

int main() {

    cin >> X;

    int ans = 0;
    ll delta = 1;
    while (curpos < X) {
        curpos += delta;
        ++delta;
        ++ans;
    }

    cout << ans;

    return 0;
}

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

#define ipair pair<int,int>
#define rep(i,n) for(i=0;i<n;i++)
#define repj(i,j,n) for(i=j;i<n;i++)

#define PB(a,i) (a).push_back(i)
#define ALL(a) (a).begin(),(a).end()
#define SIZE(a,n) (a).resize(n)

#define OK(i) cout<<"OK "<<i<<endl
#define Yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define NO cout<<"NO"<<endl

using namespace std;

typedef long long int lli;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector<int> > Matrix;



int main() {
	int n, k;
	string s;

	cin >> n >> k;
	cin >> s;
	k--;
	s[k] = (char)((int)(s[k]) + 32);

	cout << s;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>  //setprecision(桁)
using namespace std;
#define pb push_back
#define rep(i,n) for(int i = 0;i < n;i++)
#define INF 1e+9

struct edge {
    int to;
    double cost;
};

// <最短距離, 頂点の番号>
using P = pair<double, int>;

int V;
const int ci = 2e5+ 5;
vector<edge> G[ci];
double d[ci];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) { //cout << "On" << endl;
        P p = que.top();
        que.pop();
        int v = p.second; //cout << "v=" << v << endl;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i]; //cout << "koo" << endl;
            if (d[e.to] > d[v] + e.cost) { //cout << e.cost << endl;
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main(){
    int h1,m1,h2,m2,k; cin >> h1 >> m1 >> h2 >> m2 >> k;
    int t = 60 * h2 + m2 - 60 * h1 - m1;
    if(t >= k) cout << t - k << endl;
    else cout << 0 << endl; 
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
int b[200005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int a;
		cin>>a;
		b[--a]++;
	}
	for(int i=0;i<n;i++)
	{
		cout<<b[i]<<'\n';
	}
	return 0;
}


Measured memory_bytes: 4452
n=gets.to_i;
d=[1e18]*-~n;
g=(0..n).map{[]};
(2..n).map{a,b,c=gets.split.map &:to_i;g[a]<<[b,c];g[b]<<[a,c]};
_,k=gets.split.map &:to_i;
d[k]=0;
s=[k];
(g[I].map{|u,c|(d[u]=c;s<<u)if d[u]>c+=d[I]})while I=s.pop;
$<.map{|s|a,b=s.split.map &:to_i;p d[a]+d[b]}

Measured memory_bytes: 48364
#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 30;
const int MOD = 1e9 + 7;

const int N = 100;
int64 a[N];

int main() {
  int64 k;
  scanf("%lld", &k);
  int n = 50;
  int y = k % n;
  int64 x = (k - y) / n + n - 1;
  for (int i = 0; i < n; ++i) a[i] = x + 1;
  y = n - y;
  while (y--) {
    sort(a, a + n);
    a[n - 1] -= n;
    for (int i = 0; i < n - 1; ++i) a[i]++;
  }
  printf("%d\n", n);
  for (int i = 0; i < n; ++i) {
    printf("%lld%c", a[i], " \n"[i + 1 == n]);
  }
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
A = [[] for _ in range(K)]
a = list()

sunuke = [None] * N
for i in range(K):
  d = int(input())
  a = map(int, input().split())
  for t in a:
    sunuke[t-1] = 1

print(sunuke.count(None))

Measured memory_bytes: 67120
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long int ll;
struct edge{ int to,cost; };
#define M (1e12+1)

int main(void){
	ll v,e;
	cin>>v>>e;
vector<vector<edge> > g(v);
vector<vector<ll> > ans(v,vector<ll>(v,M));
for(int i=0;i<v;i++){
	ans[i][i]=0;
}
ll s,t,d;
for(int i=0;i<e;i++){
	cin>>s>>t>>d;
//	g[s].push_back((edge){t,d});
ans[s][t]=d;
}
for(int l=0;l<v;l++)
for(int i=0;i<v;i++){
	for(int j=0;j<v;j++){
		for(int k=0;k<v;k++){
			if(ans[i][k]!=M&&ans[k][j]!=M){
				ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);
			}
		}
	}
}
bool f=true;
for(int i=0;i<v;i++){
	if(ans[i][i]!=0)f=false;
}
if(f){
	for(int i=0;i<v;i++){
		for(int j=0;j<v;j++){
			if(ans[i][j]>=M){
				cout<<"INF";
			}else{
				cout<<ans[i][j];
			}
			if(j!=v-1)cout<<' ';
		}
		cout<<endl;
	}
}else{
	cout<<"NEGATIVE CYCLE"<<endl;
}
	return 0;
}


Measured memory_bytes: 3240
import math
import calendar
import fractions
import itertools

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

pmax = []

minimum = p[0]

for i in p:
    minimum = min(minimum, i)
    pmax.append(minimum)

ans = 0
for i in range(len(pmax)):
    if p[i] <= pmax[i]:
        ans += 1
print(ans)



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

using namespace std;
int bubbleSort(vector<int> &A)
{
    int count = 0;
    int N = A.size();
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (int j = N - 1; j >= 1; j--)
        {
            if (A[j - 1] > A[j])
            {
                swap(A[j - 1], A[j]);
                flag = true;
                count++;
            }
        }
    }
    return count;
}
void print(const std::vector<int> &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}
int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    int count = bubbleSort(A);
    print(A);
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3120
#include<iostream>

using namespace std;

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int coin,d = 1;
  while(1){
    coin = a * d + (d/7)*b;
    if(coin >= c) break;
    d++;
  }
  cout << d << endl;
  return 0;
}


Measured memory_bytes: 3108
N= int(input())
A = list(map(int,input().split()))
dict_L = {}
for i in range(N):
    if(i+1+A[i] in dict_L.keys()):
        dict_L[i+1+A[i]] += 1
    else:
        dict_L[i+1+A[i]] = 1
cnt = 0
for j in range(N):
    R = j+1-A[j]
    if(R in dict_L.keys()):
        cnt += dict_L[R]
print(cnt)

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

typedef long long ll;
typedef pair<int, int> P;

int MOD=1e9+7;
ll INF=1e18;

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

int main(){
    int n; cin>>n;
    int score[210][5];

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

    vector<int> ans(n+10, 0);
    for(int num=0; num<3; num++){
        for(int i=0; i<n; i++){
            bool f=true;
            for(int j=0; j<n; j++){
                if(i == j) continue;

                if(score[i][num] == score[j][num]) f=false;
            }
            if(f) ans[i]+=score[i][num];
        }
    }

    for(int i=0; i<n; i++){
        cout << ans[i] << endl;
    }
}


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

int main(){
  int n,k;
  cin>>n>>k;
  int a[n+1];
  a[0]=0;
  rep(i,0,n){
    int x;
    cin>>x;
    a[i+1]=a[i]+x;
  }
  int ans=0;
  rep(i,0,n-k+1) ans=max(ans,a[k+i]-a[i]);
  cout<<fixed<<setprecision(1);
  cout<<(ans+k+0.0)/2<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int A, B;
    cin >> A >> B;
    if ((A + B) % 2 == 0) cout << (A + B) / 2 << endl;
    else cout << "IMPOSSIBLE" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<long>X,Y,Z;
long N,K,x[50],y[50],ans=LONG_MAX,i,j,k,L;
int main(){
  cin>>N>>K;
  for(i=0;i<N;i++){cin>>x[i]>>y[i];X.push_back(x[i]);Y.push_back(y[i]);}
  sort(X.begin(),X.end());sort(Y.begin(),Y.end());
  for(i=0;i<N;i++){
    for(j=i+1;j<N;j++){
      Z.clear();
      for(k=0;k<N;k++)if(X[i]<=x[k]&&x[k]<=X[j])Z.push_back(y[k]);
      sort(Z.begin(),Z.end());
      L=Z.size();
      for(k=0;k<=L-K;k++)ans=min(ans,(X[j]-X[i])*(Z[k+K-1]-Z[k]));
    }
  }
  cout<<ans<<endl;
}


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

int main(){
  int a,b,c; cin>>a>>b>>c;

  if(a%2==0 && a==b && b==c)cout<<-1<<endl;
  else{
    int ans=0;
    while(true){
      int x=a, y=b, z=c;
      if(a%2==0 && b%2==0 && c%2==0){
        ++ans;
        a=(y+z)/2; b=(z+x)/2; c=(x+y);
      }else break;
    }
    cout<<ans<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <stdlib.h>
using namespace std;
typedef long long int ll;
#define INF (1e9)
#define distance(x1,y1,x2,y2) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
#define rep(i,N) for(ll i=0;i<N;i++)
using vvl=vector<vector<ll>>;
using vl=vector<ll>;
using vs=vector<string>;
using vvs=vector<vector<string>>;

bool func(vl s,vl t){
    return s[1]<t[1];
}

/*void printvl(vl v){
    rep(i,v.size()){
        cout<<i<<": "<<v[i]<<endl;}
}*/

void printvl2(vvl v){
    for(size_t i=0;i<v.size();i++){
        cout<<i<<": ";
        for(size_t j=0;j<v[0].size();j++){
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }
}

ll N;

int main(){
    cin>>N;
    vvl v(2,vl(N));
    vvl sum(2,vl(N));
    rep(i,2){
        rep(j,N){
            cin>>v[i][j];
        }
    }
    
    /*rep(i,2){
        ll s=accumulate(v[i].begin(),v[i].end(),0);
        sum[i][0]=s;
        for(ll j=1;j<N;j++){
            s-=v[i][j-1];
            sum[i][j]=s;
        }
    }*/
    
    ll s=accumulate(v[0].begin(),v[0].end(),0);
    sum[0][N-1]=s;
    for(ll j=N-2;j>=0;j--){
        s-=v[0][j+1];
        sum[0][j]=s;
    }
    
    s=accumulate(v[1].begin(),v[1].end(),0);
    sum[1][0]=s;
    for(ll j=1;j<N;j++){
        s-=v[1][j-1];
        sum[1][j]=s;
    }
    
    ll ans=0;
    ll temp;
    rep(i,N){
        temp=sum[0][i]+sum[1][i];
        if(temp>ans){
            ans=temp;
        }
    }
    cout<<ans<<endl;
          
    //printvl2(sum);
    return 0;}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#include <deque>
#include <map>
using namespace std;

#define mod 1000000007
#define ten5 100005
#define ten52 200005
#define ten6 1000005
#define PI 3.1415926
#define pb(x) push_back(x)
#define all(x) x.begin(),x.end()

typedef long long int ll;

//ll num[50];
//ll num2[50];
ll num[11];
//set<ll> sll;
//map<string,ll> mp,mp1;
//map<string,ll>::iterator iter;
//deque<char> deq;



int main(void)
{
    double ans=0.0,d,d1,d2;
    //float f,g,h;
    long long int m,n,i,j,k=1;
    long long int a,a1=0,a2=0,a3=0;
    string s;
    char c,c1;
    a=a1=a2=a3=0;
    cin>>n>>m;
    for(i=n;i>n-2;i--)
    {
        if(a==0) a=1;
        a*=i;
    }
    a/=2;
    for(i=m;i>m-2;i--)
    {
        if(a1==0) a1=1;
        a1*=i;
    }
    a1/=2;
    cout<<(a+a1);
    return 0;
}





Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
 
int main(){
    string s, t;
    cin >> s >> t;
    int a, b;
    cin >> a >> b;
    string u;
    cin >> u;

    if (s == u) cout << a-1 << " " << b << endl;
    else cout << a << " " <<  b-1 << endl;
}

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

int main() {
  int a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
	if ( c + c < a + b ) {
    if ( x > y ) {
      cout << 2 * c * y + (x - y) * min(2 * c, a) << endl;
    } else {
      cout << 2 * c * x + (y - x) * min(2 * c, b) << endl;
    }
	}	else {
    cout << a * x + b * y << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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


int main() {

  int r;
  cin >> r;

  cout << (3 * r * r) << endl;
  return 0;
}


Measured memory_bytes: 256
n=int(input())
s=str(input())
import sys
l1=[]
l2=[]
if len(s)%2!=0:
 print("No")
 sys.exit()
else:
 for i in range(n):
   if i<n/2:
     l1.append(s[i])
   if i>=n/2:
     l2.append(s[i])
if l1==l2:
 print("Yes")

else:
 print("No")


Measured memory_bytes: 3060
function main(input) {
  input=input.trim();
  var n = parseInt(input.split("\n")[0], 10);
  var k = parseInt(input.split("\n")[1], 10);
  var def=1
  for(var i=0; i<n; i++){
    if(def<k){
      def*=2
    }else{
      def+=k
    }
  }
  console.log(def);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
#define MAXN	100005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, m;
vector <int> a[MAXN];
bool visited[MAXN], colour[MAXN], circle;
long long cnt[3];
void work(int pos, int fa) {
	visited[pos] = true; colour[pos] = !colour[fa];
	for (unsigned i = 0; i < a[pos].size(); i++)
		if (!visited[a[pos][i]]) work(a[pos][i], pos);
		else if (colour[pos] == colour[a[pos][i]]) circle = true;
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		read(x), read(y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (visited[i]) continue;
		circle = false; work(i, 0);
		if (a[i].size()) {
			if (circle) cnt[1]++;
			else cnt[2]++;
		} else cnt[0]++;
	}
	long long ans = cnt[0] * cnt[0] + cnt[0] * 2 * (n - cnt[0]) + cnt[2] * cnt[2] * 2 + cnt[1] * (cnt[2] * 2 + cnt[1]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9728
N,M,X=map(int,input().split())
A=list(map(int,input().split()))
uppercost=0
lowercost=0
for i in range(M):
    if A[i]>X:
        uppercost=uppercost+1
    else:
        lowercost=lowercost+1

print(min(uppercost,lowercost))

Measured memory_bytes: 38384
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

a,b = input().split()
a,b = int(a), float(b)
b += 0.00001
b = int(b*100)
# print(b)
print(int((a*b)//100))


Measured memory_bytes: 10488
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int Q = sc.nextInt();
        int[] group = new int[N];
        for ( int i = 0; i < N; i++ ){
            group[i] = 0;
        }
        for ( int j = 0; j < Q; j++ ){
            int A = sc.nextInt();
            group[A-1] = group[A-1] + 1;
        }
        for ( int i = 0; i < N; i++ ){
            if (group[i] > Q-K){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }
}

Measured memory_bytes: 72772
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int INF = pow(2, 31) - 1;
#define ll long long
#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int main() {
  int N;
  cin >> N;
  vector<int> t(N + 1), x(N + 1), y(N + 1);
  FOR(i, 1, N) {
    cin >> t[i] >> x[i] >> y[i];
  }
  t[0] = 0;
  x[0] = 0;
  y[0] = 0;
  REP(i, N) {
    if(t[i + 1] - t[i] < abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i])) {
      cout << "No" << endl;
      return 0;
    } else {
      if((t[i + 1] - t[i] - abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i])) % 2 == 1) {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 1408
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i,s,n) for(ll i=(s);i<(ll)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;cin>>n;
    int ans=1;
    while(1){
        ans*=2;
        if(ans>n){
            ans/=2;
            break;
        }
        if(ans==n)break;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
//#include<iostream>
//#include<vector>
//using namespace std;
//
//
//
//int main() {
//
//	int n;
//
//	cin >> n;
//	int a[105];
//	for (int i = 0; i < n; i++) {
//		cin >> a[i];
//	}
//
//	int sum = 0;
//
//	for (int i = 0; i < n; i++) {
//		int minj = i;
//		for (int j = i; j < n; j++) {
//			if (a[j] < a[minj]) {
//				minj = j;
//			}
//		}
//		if (minj != i) {
//			int tmp = a[i];
//			a[i] = a[minj];
//			a[minj] = tmp;
//			sum++;
//		}
//	}
//
//	for (int i = 0; i < n; i++) {
//		if (i != n - 1)cout << a[i] << " ";
//		if (i == n - 1)cout << a[i] << endl;
//	}
//	cout << sum << endl;
//}
//


//round 2

#include<iostream>
using namespace std;


int selectionSort(int A[], int n) {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int minj = i;
		for (int j = i; j < n; j++) {
			if (A[j] < A[minj]) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(A[i], A[minj]);
				cnt++;
		};
	}

	return cnt;
}

int main() {
	int n;

	cin >> n;
	int A[105];

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

	int ans = selectionSort(A, n);

	for (int i = 0; i < n; i++) {
		if (i == n - 1)cout << A[i] << endl;
		else cout << A[i] << " ";
	}
	cout << ans << endl;

}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
long long mypow(long long x, long long y)
{
	long long result = 1;
	while (y != 0) {
		if (y%2 != 0) {
			result *= x;
			y -= 1;
		}	
		x *= x;
		y /= 2;
	}
	return result;
}
int main(void)
{
	int d, g;
	cin >> d >> g;
	int p[d], c[d];
	for (int i = 0; i < d; i++) {
		cin >> p[i] >> c[i];
	}

	long long ans = -1;
	for (int i = 0; i < mypow(2, d); i++) {
		bool all[d];
		long long count = 0;
		long long score = 0;
		for (int j = 0; j < d; j++) {
			if (((i>>j)&1) == 1) {
				all[j] = true;
				count += p[j];
				score += (100 * (j+1) * p[j] + c[j]);
			} else {
				all[j] = false;
			}
		}
		for (int j = d-1; j >= 0; j--) {
			if (score >= g)
				break;
			if (all[j])
				continue;

			long long a = min((long long)p[j], (g-score)/((j+1)*100));
			count += a;
			score += (j+1)*100*a;
			if (a == p[j])
				score += c[j];
		}
		if (score >= g) {
			if (ans == -1)
				ans = count;
			else
				ans = min(ans, count);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3624
# 入力
a, b = map(int, input().split())

# a と b の積を求める
product = a * b

# 積を2で割った余りが1ならOdd、それ以外(0しかない)ならEvenを出力する
if product % 2 == 1:
    print('Odd')
else:
    print('Even')


Measured memory_bytes: 9008
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

ll fac[200007],finv[200007],inv[200007];
void cominit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<200007;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll com(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
long long modpow(long long a, long long n) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cominit();
    ll n,x,y;
    cin>>n;
    ll a[n+1];
    for(int i=0;i<=n;i++)cin>>a[i];
    map<int,int> mp;
    for(int i=0;i<=n;i++){
    	if(mp[a[i]]){
    		x=mp[a[i]];
    		y=i+1;
    		break;
    	}else{
    		mp[a[i]]=i+1;
    	}
    }
    for(ll k=1;k<=n+1;k++){
    	cout << ((com(n+1,k)-com(n-y+x,k-1))%mod+mod)%mod <<endl;;
    }

    return 0;
}


Measured memory_bytes: 11392
// arock - 2019-02-09

#include "assert.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using i64 = long long;

template <class T> struct PSA : public std::vector<T> {
	PSA(const std::vector<T>& v) : std::vector<T>(v.size() + 1) {
		std::partial_sum(begin(v), end(v), begin(*this) + 1);
	}

	T operator()(size_t l, size_t r) const { // [l, r)
		return (*this)[r] - (*this)[l];
	}
};

template <class T> std::vector<T> read(int n) {
	std::vector<T> res(n);
	for (auto& r : res) {
		std::cin >> r;
	}

	return res;
}

int L;
std::vector<i64> A, dpf, dpg;
PSA<i64> sum(A);

// min score to clear [0, i] and come back to i - 1
i64 g(int i) {
	if (i == 0) return 0;
	if (dpg[i] != -1) return dpg[i];

	i64 ans = sum(0, i);

	if (A[i - 1] == 0) {
		ans = std::min(ans, 2 + g(i - 1));
	} else if (A[i - 1] == 1) {
		ans = std::min(ans, 1 + g(i - 1));
	} else if (A[i - 1] % 2 == 0) {
		ans = std::min(ans, g(i - 1));
	} else if (A[i - 1] % 2 == 1) {
		ans = std::min(ans, 1 + g(i - 1));
	} else {
		assert(0);
	}

	return dpg[i] = ans;
}

// min score to clear [0, i]
i64 f(int i) {
	if (i == 0) return 0;
	if (dpf[i] != -1) return dpf[i];

	i64 ans = sum(0, i);
	if (A[i - 1] % 2 == 1) {
		ans = std::min(ans, f(i - 1));
	} else if (A[i - 1] == 0) {
		ans = std::min(ans, 1 + f(i - 1));
	} else if (A[i - 1] % 2 == 0) {
		ans = std::min(ans, std::min(1 + f(i - 1), g(i - 1)));
	} else {
		assert(0);
	}

	return dpf[i] = ans;
}

int main() {
	std::cin >> L;
	A = read<i64>(L);
	sum = A;
	dpf = std::vector<i64>(L + 1, -1);
	dpg = std::vector<i64>(L + 1, -1);

	std::vector<i64> ll(L + 1);
	for (int i = 0; i <= L; i++) {
		ll[i] = f(i);
	}
	dpf = std::vector<i64>(L + 1, -1);
	dpg = std::vector<i64>(L + 1, -1);

	std::reverse(begin(A), end(A));
	sum = A;

	std::vector<i64> rr(L + 1);
	for (int i = 0; i <= L; i++) {
		rr[i] = f(i);
	}
	std::reverse(begin(rr), end(rr));

	i64 ans = 1LL << 60;
	for (int i = 0; i <= L; i++) {
		//std::cout << i << ' ' << ll[i] << ' ' << rr[i] << std::endl;
		ans = std::min(ans, ll[i] + rr[i]);
	}

	std::cout << ans << std::endl;
}


Measured memory_bytes: 15020
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
a = []
for _ in range(m):
    a.append(int(input()))
a=set(a)

memo = [0]*(n+1)
memo[0]=1
if not(1 in a):
    memo[1]=1

for i in range(2,n+1):
    #print(i)
    if i in a:
        continue
    #print(memo[i-1],memo[i-2])
    memo[i]=memo[i-2]+memo[i-1]
            

#print(memo)
print(memo[n]% 1000000007)

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

int main() {
vector<int> x(5);
 for(int i=0; i<5; i++){
  cin >> x.at(i);
 if(x.at(i)==0){
   cout << i+1 << endl;
   break;
 }
 }
  
}


Measured memory_bytes: 3544
fun main(arg: Array<String>) {
    val N = nextInt()
    val A = listOfInt()
    var b0 = 0
    var b1 = 0
    var b2 = 0
    A.forEach {
        when (Integer.numberOfTrailingZeros(it)) {
            0 -> b0 += 1
            1 -> b1 += 1
            else -> b2 += 1
        }
}
    val ans = if (b1 == 0) b0 <= b2 + 1 else b0 <= b2
    println(if (ans) "Yes" else "No")
}
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)
fun listOfInt(vararg deltas: Int) = listOfString().map { Integer.parseInt(it) }.mapIndexed { index, int -> int + deltas[index % deltas.size] }



Measured memory_bytes: 53856
// practice with Dukkha
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1000, M = 2000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int ii[M], jj[M], ww[M];
long long dp[N];

int main() {
	int n, m; cin >> n >> m;
	for (int h = 0; h < m; h++) {
		int i, j, w; cin >> i >> j >> w, i--, j--;
		ii[h] = i, jj[h] = j, ww[h] = w;
	}
	fill(dp, dp + n, -INF);
	dp[0] = 0;
	for (int k = 1; k <= n * 2; k++) {
		bool updated = false;
		for (int h = 0; h < m; h++) {
			int i = ii[h], j = jj[h];
			if (dp[i] != -INF) {
				long long d = dp[i] + ww[h];
				if (dp[j] < d) {
					dp[j] = d;
					if (j == n - 1)
						updated = true;
				}
			}
		}
		if (updated && k >= n) {
			cout << "inf\n";
			return 0;
		}
	}
	cout << dp[n - 1] << '\n';
	return 0;
}


Measured memory_bytes: 3620
N = int(input())
L = [x for x in range(1, N + 1) if x % 2 != 0]

ans = 0
for n in L:
    cnt = 0
    for i in range(1, n + 1):
        if n % i == 0:
            cnt += 1
    if cnt == 8:
        ans += 1

print(ans)

Measured memory_bytes: 3064
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
    char buf[32];
    while (fgets(buf, 32, stdin)) {
        int f[5];
        int k=0;
        char* p=strtok(buf, ",\n");
        f[0] = atoi(p);
        while (p = strtok(NULL, ",\n")) f[++k] = atoi(p);
        sort(f, f+5);

        string res = "null";
        for (int i=0; i<2; ++i) {
            if (f[0]==f[1]||f[1]==f[2]||f[2]==f[3]||f[3]==f[4])
                res = "one pair";
            if (f[0]==f[1]&&(f[2]==f[3]||f[3]==f[4]) || f[1]==f[2]&&f[3]==f[4])
                res = "two pair";
            if (f[0]==f[2]||f[1]==f[3]||f[2]==f[4]) res = "three card";
            if (f[0]+1==f[1]&&f[1]+1==f[2]&&f[2]+1==f[3]&&f[3]+1==f[4])
                res = "straight";
            if (f[0]==f[2]&&f[3]==f[4] || f[0]==f[1]&&f[2]==f[4])
                res = "full house";
            if (f[0]==f[3]||f[1]==f[4]) res = "four card";
            for (int j=0; j<5; j++) if (f[j]==1) f[j]=14;
            sort(f, f+5);
        }
        puts(res.c_str());
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 1000000007;
constexpr bool debug = 0;
//---------------------------------//

int main() {
	int A, B;
	cin >> A >> B;
	
	cout << max(0, A - 2*B) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;
 
int main(){
    int n,team1,team2,Point[101],po1,po2,cnt;
 
    for( int i = 0 ; i < 101 ; i++ ) Point[i] = 0;
   
    cin >> n;
    for( int i = 0; i < n*(n-1)/2 ; i++ ){
 
	cin >> team1 >> team2 >> po1 >> po2;
	if( po1 > po2 ) Point[team1] += 3;
	else if( po1 < po2 ) Point[team2] += 3;
	else{
	    Point[team1]++; Point[team2]++;
	}
    }
 
    for( int i = 1 ; i <= n ; i++ ){
	cnt = 1;
	for( int j = 1 ; j <= n ; j++ ){
	    if( Point[i] < Point[j] ) cnt++;
	}
	cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 3076