akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main(){
	while(1){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==0)return 0;
		int e[50];
		for(int i=0;i<a;i++){
			e[i]=a-i;
		}
		for(int i=0;i<b;i++){
			int c,d;
			int f[50];
			scanf("%d%d",&c,&d);
			int j;
			for(j=0;j<d;j++){
				f[j]=e[c+j-1];
			}
			for(;j<c+d-1;j++){
				f[j]=e[j-d];
			}
			for(;j<a;j++){
				f[j]=e[j];
			}
			for(int j=0;j<a;j++)e[j]=f[j];
		}
		printf("%d\n",e[0]);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int A,B;
  cin>>A>>B; 
    if(A==2 && B==2) cout<<"Yes";
    else if(A==4||A==6||A==9||A==11){
      if(B==4||B==6||B==9||B==11)cout<<"Yes";
      else cout<<"No";
    }
    else if(A==1||A==3||A==5||A==7||A==8||A==10||A==12){
      if(B==1||B==3||B==5||B==7||B==8||B==10||B==12)cout<<"Yes";
      else cout<<"No";
    }
    else cout<<"No";
}

Measured memory_bytes: 256
#include <cstdio>

int N;
int P;
int A[100];
long long nCr[51][51];



long long ret(int n,int r){
	if(r>n) return 0;
	if(nCr[n][r]!=-1) return nCr[n][r];
	if(n==r || r==0){
		nCr[n][r] = 1;
		return 1;
	}else if(n<r){
		nCr[n][r] = 0;
	}else{
		nCr[n][r] = ret(n-1,r-1)+ret(n-1,r);
		return nCr[n][r];
	}
}

long long kai(int n){
	if(n==0) return 1;
	else return 2*kai(n-1);
}

int main(){
	for(int i=0;i<=50;i++){
		for(int j=0;j<=50;j++){
			nCr[i][j] = -1;
		}
	}

	//printf("%lld\n",ret(50,25));

	scanf("%d %d",&N,&P);
	for(int i=0;i<N;i++){
		scanf("%d",&A[i]);
	}

	int odd = 0;
	int even = 0;
	for(int i=0;i<N;i++){
		if(A[i]%2==0) even++;
		if(A[i]%2==1) odd++;
	}

	long long ans = 0;
	if(P==0){
		for(int i=0;i<=odd;i+=2){
			ans += ret(odd,i);
		}
	}else{
		for(int i=1;i<=odd;i+=2){
			ans += ret(odd,i);
		}
	}
	ans *= kai(even);

	printf("%lld\n",ans);

	return 0;
}


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

int main() {
  int N;
  cin >> N;
  string S;
  bool a, b, c, d = false;
  for(int i = 0; i < N; i++){
    cin >> S;
    if(S == "P"){
      a = true;
    }
    else if(S == "W"){
      b = true;
    }
    else if(S == "G"){
      c = true;
    }
    else if(S == "Y"){
      d = true;
    }
  }
  
  if(a && b && c && d){
    cout << "Four" << endl;
  }
  else if(a && b && c){
    cout << "Three" << endl;
  }
}

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

int main() {
  ll N; cin >> N;
  vector<ll> A(N),B(N),C(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) cin >> B[i];
  for (int i = 0; i < N; i++) C[i] = A[i] - B[i];
  
  ll sum = 0;
  for (int i = 0; i < N; i++) sum += C[i];
  
  if (sum >= 0) {
    sort(C.begin(),C.end());
  
    int k = lower_bound(C.begin(),C.end(),0) - C.begin();
  
    ll summ = 0;
    for (int i = 0; i < k; i++) summ += C[i];
  
    int j = N-1;
    int count = 0;
    while (summ < 0) {
      summ += C[j];
      count++;
      j--;
    }
    
    cout << k + count << endl;
  } else cout << -1 << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
int a[111];
ll C(ll a,ll b){
    ll res=1,tt=1;
    while(b--){
        res=res*a%mod;
        res=res*inv(tt)%mod;
        a--;
        tt++;
    }
    return res;
}
int main(){
    ll n,i,j,t,x,y,ma=0,mi=1e17;
    cin>>n>>x>>y;
    cout<<(power(2,n)-C(n,x)-C(n,y)-1+mod*10)%mod;
}
/*
7
140 1
120 2
100 3
120
100
-1
100
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define REP(i,x) for(ll i=0;i<(ll)(x);i++)

int main()
{
    ios::sync_with_stdio(false);
    string S, T;
    int A, B;
    string U;

    cin >> S >> T;
    cin >> A >> B;
    cin >> U;

    if(S == U)
    {
        A--;
    }
    else
    {
        B--;
    }
    
    cout << A;
    cout << " ";
    cout << B;
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
//Created by Kira

#include<bits/stdc++.h>
using namespace std;

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);
    
const int N = 2e5 + 10;
int a[N];

int n, k;
bool f(ll x){
    priority_queue<int> pq;
    for(int i = 0; i < n; i++){
        pq.push(a[i]);
    }

    ll rem, sub;
    ll tk = k;

    while(!pq.empty() && pq.top() > x && tk >= 0){
        rem = pq.top();
        pq.pop();
        sub = ((rem + x - 1)/x) - 1;
        if(sub > tk)return false;
        tk -= sub;
    }

    return true;
}


int main(){
   IOS

    cin>>n>>k;

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

    ll lo = 1, hi = 1e12, mid, ans = -1;

    while(lo <= hi){
        mid = lo + (hi - lo)/2;
        if(f(mid)){
            ans = mid;
            hi = mid - 1;
        }else{
            lo = mid + 1;
        }
    }

    cout<<ans<<"\n";

    

}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
    if(b&1) res = res * a % mod;
        a = a * a % mod;
    b >>= 1;
    }

    return res;
}



Measured memory_bytes: 5792
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

std::vector<int> eratosthenes() {
  bool is_prime[55556];
  std::vector<int> ret;

  std::fill(is_prime, is_prime + 55555, true);

  is_prime[0] = is_prime[1] = false;

  for (int i = 2; i <= 55555; ++i) {
    if (is_prime[i]) {
      ret.push_back(i);
      for (int j = 2; i * j <= 55555; ++j) {
        is_prime[i * j] = false;
      }
    }
  }

  return ret;
}


int main() {
  int n;

  cin >> n;

  std::vector<int> prime = eratosthenes(), ans;

  for (int i = 0; i < int(prime.size()); ++i) {
    if (prime[i] % 5 == 1) {
      ans.push_back(prime[i]);
      if (int(ans.size()) == n) {
        break;
      }
    }
  }

  for (int i = 0; i < int(ans.size()); ++i) {
    cout << ans[i] << " \n"[i == n - 1];
  }

  return 0;
}


Measured memory_bytes: 384
n=int(input())  
ans = 0
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        # print('----',i)
        a = i
        x1 = n//i
        x = x1-1
        # print(a,x)
        if a < x:
            ans += x
        
        a = n//i
        x1 = i
        x = x1 - 1
        if a < x:
            ans += x

print(ans)

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

using namespace std;
int main() {
  int n;
  cin >> n;

  for (int i = 1; i <= n; i++) {
    int ans = 0;
    int flag = 0;
    for (int j = 1; j <= sqrt(n); j++) {
      for (int k = 1; k <= sqrt(n); k++) {
        if (j * j > i || k * k > i) continue;
        double x = (-j - k +
                    sqrt((j + k) * (j + k) - 4 * (j * j + k * k + j * k - i))) /
                   2;
        if (x >= 1 && floor(x) == x) ans++;

        // if ((j * j + k * k + l * l + j * k + k * l + l * j) == i) ans++;
      }
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 3648
n = int(input())
word = input()
list1 = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
new = ""
for char in word:
    new+=list1[(list1.index(char)+n)%26]
print(new)


Measured memory_bytes: 3060
H, W = [int(i) for i in input().split()]
S = ['.' * (W + 2)]
for i in range(H):
  S.append('.' + input() + '.')
S.append('.' * (W + 2))

mine = [[0 for _ in range(W)] for _ in range(H)]
for j in range(H):
  for i in range(W):
    if S[j + 1][i + 1] == '#':
      mine[j][i] = '#'
    else:
      mine[j][i] = sum([s[i:i + 3].count('#') for s in S[j:j + 3]])
      
for m in mine:
  print(''.join([str(i) for i in m]))


Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(1000000)
N, Q = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(N-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]
 
rin = [[] for _ in range(N)]
for v in a_b:
    rin[v[0]-1].append(v[1]-1)
    rin[v[1]-1].append(v[0]-1)
    
score = [0 for _ in range(N)]
for ele in p_x:
    score[ele[0]-1] +=ele[1]
#print(score)
 
def dfs(p, bp=-1):
    for c in rin[p]:
        if c != bp:
            #print(c)
            score[c]+= score[p]
            dfs(c, p)
 
dfs(0)
print(*score)


Measured memory_bytes: 350248
#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int x) {
   if(x==2) return true;
   if(x<2 || x%2==0 ) return false;
   int i=3;
   while(i<=sqrt(x)){
       if(x%i==0) return false;
       i += 2;
   }
   return true;
}

int main() {

    int n,a,Count=0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (isPrime(a)) {
            Count++;
        }
    }
    cout<< Count <<endl ;
   
    return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define dup(x,y) (((x)+(y)-1)/(y))
#define v(T) vector<T>
#define vv(T) v(v(T))
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(v.size())o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const double eps = 1e-6;
const ll LINF = 100200300400500600ll;
const int INF = 1001001001;
//--------------------------------------------------------
#define fastio cin.tie(nullptr); std::ios::sync_with_stdio(false);
#define myio ifstream iofi; if(argc>1){iofi.open(argv[1]); std::cin.rdbuf(iofi.rdbuf());}
#define myloopset int loop = 1; if(argc>2) loop =stoi(argv[2]); rep(i,loop)
//--------------------------------------------------------------
template <class T> T chmin(T &a,T b){if(a>b){a=b; return 1;}else return 0;}
template <class T> T chmax(T &a,T b){if(a<b){a=b; return 1;}else return 0;}
const int dx[4] = {0,1,0,-1};
const int dy[4] = {-1,0,1,0};
const int mod = 1000000007;
#define Yes(ifeq) cout<<(( ifeq )? "Yes":"No")<<endl;

void Main(){
  ll n,k;
  cin>>n>>k;
  if(n<k){
    n = min(abs(n-k),n);
    cout<<n<<endl;
  }else{
    n -= n/k*k;
    n = min(abs(n-k),n);
    cout<<n<<endl;
  }
} signed main(int argc,char** argv)
{fastio; myio; myloopset Main();}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, ans = 1;
char s[100010];
int main() {
	scanf("%d", &n);
	scanf("%s", s);
	for(int i = 1; i < n; i ++) {
		if(s[i] != s[i - 1]) ans ++;
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>
char s[101];
int main(void) {
scanf("%s", s);
int res = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] != s[n - 1 - i]) res++;
}
printf("%d\n", res / 2);
}

Measured memory_bytes: 128
import java.util.*;

public class Main {

    public static void main(String[] args) {
        exec();
    }

    static void exec() {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        if (Character.isUpperCase(n.charAt(0))) {
            System.out.println("A");
        } else {
            System.out.println("a");
        }
    }
}

Measured memory_bytes: 26976
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <sstream>

#define fi first
#define se second
#define pb push_back
#define fore(i, a, b) for (int i = (a), _b = (b); i < (_b); ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= (_b); ++i)
#define ford(i, a, b) for (int i = (a), _b = (b); i >= (_b); --i)

using namespace std;

typedef long long LL;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const int INF = 1e9 + 3;
const int MOD = 1e9 + 7;
const int N = 5003;
const int B = 37;
const LL M = 1e9 + 9;

int n;
string s;
LL p[N], h[N];

LL get(int i, int j) {
    return (i == 0 ? h[j] : (h[j] - h[i - 1] * p[j - i + 1] + M * M) % M);
}

void preprocess() {
    p[0] = 1;
    fort(i, 1, n) p[i] = (p[i - 1] * B) % M;
    fore(i, 0, n) h[i] = (i == 0 ? s[0] - 'a' + 1 : (h[i - 1] * B + s[i] - 'a' + 1) % M);
}

bool solve(int sz) {
    fore(i, 0, n - sz + 1) fore(j, i + sz, n - sz + 1)
        if (get(i, i + sz - 1) == get(j, j + sz - 1)) return 1;
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> s;
    preprocess();
    int l = 0, r = n, m;
    while (l < r) {
        m = (l + r + 1) >> 1;
        if (solve(m)) l = m;
        else r = m - 1;
    }
    cout << l << '\n';
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int bs(ll s[],ll a,ll x){
  int l=0,r=a,m;
  while(r-l>1){
    m=(l+r)/2;
    if(s[m]>x) r=m;
    else l=m;
  }
  return l;
}

int main(){
  ll a,b,q,s[100010],t[100010],x,u,v,k;
  cin>>a>>b>>q;
  fr(i,a) cin>>s[i];
  s[a]=1e11;
  fr(i,b) cin>>t[i];
  t[b]=1e11;
  fr(i,q){
    cin>>x;
    u=bs(s,a,x);
    v=bs(t,b,x);
    ll p[4]={s[u],t[v],s[u+1],t[v+1]};
    k=1e18;
    fr(I,4){
      fr(J,4){
        if((I+J)%2) k=min(k,abs(p[I]-x)+abs(p[J]-p[I]));
      }
    }
    cout<<k<<endl;
  }
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
#include <cstdio>
#include<stdio.h>
#include<string.h>

int count(unsigned int num){
    int cnt = 0;
    while(num%2==0){  
        if (num % 2 != 0){
            return cnt;
        }
        num /= 2;
        cnt++;
    }
  return cnt;
}

int main(void){

    unsigned int n, temp;
    scanf("%u", &n);

    unsigned int num[n];
    int i;
    unsigned int min = 10000000000;

    for (i = 0; i < n;i++){
        scanf("%u", &num[i]);

        temp = count(num[i]);
        if(min > temp)
            min = temp;
    }
    printf("%u", min);
    return 0;
}

Measured memory_bytes: 256
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let x: i32 = read();
    let y: i32 = read();
    println!("{}", if group(x) == group(y) { "Yes" } else { "No" });
}

fn group(x: i32) -> i32 {
    match x {
        1 | 3 | 5 | 7 | 8 | 10 | 12 => 0,
        4 | 6 | 9 | 11 => 1,
        2 => 2,
        _ => 3,
    }
}

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

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll n, p = 0;
ll f[50];
 
void init() {
	f[0] = 1;
	for (int i = 1; i <= 45; i++)
		f[i] = 2 * f[i - 1];
}
 
int main() {
	init();
	scanf("%lld", &n);
	while (n >= f[p]) p++;
	printf("%lld\n", f[p] - 1);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <assert.h>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 998244353

#define N_MAX 400010

long long fact[N_MAX];
long long rfact[N_MAX];

long long modpow(long long a, long long b){ 
  long long r = 1LL;

  while(b){
    if(b & 1LL)r *= a;
    if(r >= MOD)r %= MOD;
    a *= a;
    if(a >= MOD)a %= MOD;
    b >>= 1LL;
  }
  return r;
}

long long nCr(long long n, long long r){ 
  long long ret = 1LL;
  ret *= fact[n];
  ret %= MOD;
  ret *= rfact[r];
  ret %= MOD;
  ret *= rfact[n-r];
  ret %= MOD;
  return ret%MOD;
}

ll dp[200010];

int main(){

clr(fact,0);
fact[0]=1;
rep(i,1,N_MAX){
  fact[i] = fact[i-1]*i;
  fact[i] %= MOD;
}
clr(rfact,0);
rfact[0]=1;
rep(i,1,N_MAX){
  rfact[i] = rfact[i-1]*modpow(i,MOD-2);
  rfact[i] %= MOD;
}
  ll n,m,k;
  cin>>n>>m>>k;
  dp[0] = m;
  rep(i,1,200010){
    dp[i] = dp[i-1]*(m-1);
    dp[i] %= MOD;
  }
  ll ans = 0;
  rep(i,0,k+1){
    ll b = nCr(n-1,n-1-i);
    b %= MOD;
    ans += (dp[n-1-i]*b)%MOD;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 11428
#!/usr/bin/env python3

def main():
    h, w = map(int, input().split())
    rows = [input() for i in range(h)]
    rows = filter(rows)
    cols = transpose(rows)
    cols = filter(cols)
    rows = transpose(cols)
    for r in rows:
        print("".join(r))

def transpose(rows):
    h = len(rows)
    w = len(rows[0])
    cols = [[rows[i][j] for i in range(h)] for j in range(w)]
    return cols

def filter(rows):
    rows = [r for r in rows if "#" in r]
    return rows

main()


Measured memory_bytes: 3188
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	a := nextInt()
	b := nextInt()
	fmt.Println(a * b)
}


Measured memory_bytes: 1756
#include<stdio.h>
int n,a[110],ans,t=1;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    while(t==1)
    {
        t=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i-1]==0&&a[i]!=0)
            {
                ans++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]!=0)
            {
                a[i]--;
                t=1;
            }
        }
    }
    printf("%d",ans);
}

Measured memory_bytes: 128
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <tuple>
#include <map>
#include <iomanip>
using namespace std;
typedef long long ll;

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

    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        cout << char('A' + ((s[i] - 'A') + n) % 26);
    }
    cout << endl;
}


Measured memory_bytes: 256
mod = 998244353

# 貰うDP
def main(N, S):
    dp = [0 if n != 0 else 1 for n in range(N)]     # dp[i]はマスiに行く通り数． (答えはdp[-1]), dp[0] = 1 (最初にいる場所だから1通り)
    A = [0 if n != 0 else 1 for n in range(N)]      # dp[i] = A[i] - A[i-1] (i >= 1), A[0] = dp[0] = 1 (i = 0) が成り立つような配列を考える．

    for i in range(1, N):   # 今いる点 (注目点)
        for l, r in S:  # 選択行動範囲 (l: 始点, r: 終点)
            if i - l < 0:   # 注目点が選択行動範囲の始点より手前の場合 → 注目点に来るために使用することはできない．
                break
            else:           # 注目点に来るために使用することができる場合
                dp[i] += A[i-l] - A[max(i-r, 0)-1]  # lからrの間で，注目点に行くために使用できる点を逆算． そこに行くことができる = 選択行動範囲の値を選択することで注目点に達することができる通り数．
        dp[i] %= mod
        A[i] = (A[i-1] + dp[i]) % mod
    print(dp[-1])

if __name__ == '__main__':
    N, K = list(map(int, input().split()))
    S = {tuple(map(int, input().split())) for k in range(K)}
    S = sorted(list(S), key = lambda x:x[0])    # 始点でsort (範囲の重複がないため)
    main(N, S)

Measured memory_bytes: 24588
import java.util.Scanner

object Main extends App  {
  val sc = new Scanner(System.in)

  val n = sc.nextInt

  val res = factorial(n, 1000000007)

  println(res)

  def factorial(n: Int, mod: Int): Long ={
    (1 to n).foldLeft(1L){(fact, k) =>

      fact * k % mod
    }
  }
}


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

int main() {
  int N;
  cin >> N;
  int kind = 0;
  set<int> s;
  
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if (x/400 > 7) kind += 1;
    else {
      s.insert(x/400);
    }
  }
  
  int k = s.size();
  cout << max(k,1) << " " << k + kind << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int A,B,C,D;
    scanf("%d%d%d%d",&A,&B,&C,&D);

    int min=10000;
    if(A+C < min){
        min = A+C;
    }
    if(A+D < min){
        min = A+D;
    }
    if(B+C < min){
        min = B+C;
    }
    if(B+D < min){
        min = B+D;
    }
    printf("%d",min);

    return 0;
}

Measured memory_bytes: 128
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx


using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);   
ll a[1000];
int main(){
    std::ios::sync_with_stdio(false);
    ll k;
    cin>>k;
    ll i;
    ll val=k/50;
    
    val+=49;
    rep(i,50){
    	a[i]=val;
    }
    //cout<<val<<endl;
    val=k%50;
    rep(i,val){
    	a[i]+=50-val+1;
    }
    f(i,val,50){
    	a[i]-=val;
    }
    cout<<50<<endl;
    rep(i,50){
    	cout<<a[i]<<" ";
    }

    return 0;      

}



Measured memory_bytes: 256
N = input()
rates = [int(i) for i in input().split()]

color = [0] * 9
for rate in rates:
    if rate/400 < 8:
        color[int(rate/400)] += 1
    else:
        color[8] += 1

num = 0
for i in color[:8]:
    if i:
        num += 1

if num:
    mi = num
    ma = num + color[8]
else:
    mi = 1
    ma = num + color[8]

print("{} {}".format(mi,ma))

Measured memory_bytes: 3064
#include<stdio.h>
int main(void){

  int x, N, y;

  scanf("%d", &N);

  if(1<=N && N<=100)
    {
      int i = N/15;
      
      
     
	x = 800*N;
        y = 200*i;
  
	
    }

 
  printf("%d\n", x-y);

      return 0;
    }
  


Measured memory_bytes: 128
import sys
input = sys.stdin.readline

#立っている場所の個数
def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

def main():
    n = int(input())
    edge = [[] for i in range(n)]
    for _ in [0]*(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    m = int(input())
    dg = 100
    uv = []
    for _ in [0]*m:
        u,v = map(int,input().split())
        uv.append(u*dg-dg+v-1)

    #各点の親を求める
    par = [-2]*n
    root = 0
    par[0] = -1

    tank = [0]
    order = []
    orderIdx = [0]*n
    cnt = 0
    while tank:
        now = tank.pop()
        for nxt in edge[now]:
            if par[nxt] == -2:
                par[nxt] = now
                tank.append(nxt)
        order.append(now)
        orderIdx[now] = cnt
        cnt += 1
    
    res = pow(2,n-1)
    #1ビットだけ立っているもの
    bitOne = set()
    for i in range(m):
        bitOne.add(1<<i)

    #dp
    dp = [0]*(1<<m)
    for i in range(1,1<<m):
        pc = popcnt(i)
        if pc == 1:
            #idx:iで立っているbitの内最後のもののindex
            idx = (-i&i).bit_length()-1
            
            u,v = uv[idx]//dg,uv[idx]%dg

            
            #u,v間の経路の辺を立てたものがdp[i]
            tmp = 0
            while u != v:
                if orderIdx[u] < orderIdx[v]:
                    tmp |= (1<<v)
                    v = par[v]
                else:
                    tmp |= (1<<u)
                    u = par[u]
            dp[i] = tmp
        
        else:
            dp[i] = dp[(-i)&i] | dp[((-i)&i)^i]
    
        res += (-1)**(pc%2)*pow(2,n-1-popcnt(dp[i]))

    print(res)

if __name__ == '__main__':
    main()










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

int main() {
	int N;
	cin >> N;
	int A = N % 10;
	if (A == 0 || A == 1 || A == 6 || A == 8)
		cout << "pon" << endl;
	else if (A == 3)
		cout << "bon" << endl;
	else
		cout << "hon" << endl;
}

Measured memory_bytes: 3620
from collections import deque
import bisect
n = int(input())
q = deque()

for _ in range(n):
    a = int(input())
    if len(q) == 0:
        q.appendleft(a)
    elif a <= q[0]:
        q.appendleft(a)
    else:
        i = bisect.bisect_right(q, a-1) - 1
        q[i] = a
print(len(q))

Measured memory_bytes: 7364
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		sc.close();

		int a = s.length;
		int b = t.length;
		int[][] dp = new int[a + 1][b + 1];
		for (int i = 1; i <= a; i++) {
			for (int j = 1; j <= b; j++) {
				if (s[i - 1] == t[j - 1]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}

		char[] lcs = new char[dp[a][b]];
		while (a > 0 && b > 0) {
			if (dp[a][b] == dp[a - 1][b]) {
				a--;
			} else if (dp[a][b] == dp[a][b - 1]) {
				b--;
			} else {
				a--;
				b--;
				lcs[dp[a][b]] = s[a];
			}
		}
		System.out.println(lcs);
	}
}


Measured memory_bytes: 81632
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    int tmp;
    int count = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> tmp;
        if (i & 1 and tmp & 1) ++count;
    }
    cout << count;
}

Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main() {
    string s;
    for(int i=0;i<9;i++){
        int am=0,pm=0;
        cin>>s;
        cin>>am>>pm;
        cout<<s<<" "<<am+pm<<" "<<am*200+pm*300<<endl;;
    }
	return 0;
}

Measured memory_bytes: 1200
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String ss = sc.next();
		StringBuilder s = new StringBuilder(ss);
		boolean bre = false;
		while (s.length() > 0) {
			if (s.substring(s.length() - 5).equals("dream") || s.substring(s.length() - 5).equals("erase")) {
				s.delete(s.length() - 5, s.length());
			} else if (s.substring(s.length() - 6).equals("eraser")) {
				s.delete(s.length() - 6, s.length());;
			} else if (s.substring(s.length() - 7).equals("dreamer")) {
				s.delete(s.length() - 7, s.length());
			} else {
				bre = true;
				break;
			}
		}
		if (bre) {
			System.out.println("NO");
		} else {
			System.out.println("YES");
		}
	}
}

Measured memory_bytes: 29192
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <cfloat>
#include <map>
using namespace std;
int main(){
	
	int n;
	map<int,string> d;
	
	d[0]="0111111";
	d[1]="0000110";
	d[2]="1011011";
	d[3]="1001111";
	d[4]="1100110";
	d[5]="1101101";
	d[6]="1111101";
	d[7]="0100111";
	d[8]="1111111";
	d[9]="1101111";
	
	while(cin>>n,n!=-1){
		int a;
		cin>>a;
		cout<<d[a]<<endl;
		n--;
		for(int i=0;i<n;i++){
			int b;
			cin>>b;
			string s;
			for(int j=0;j<7;j++){
			if(d[a][j]==d[b][j])
				s+="0";
			else
				s+="1";
			}
			cout<<s<<endl;
			a=b;
		}
	}
}

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

using namespace std;

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

  map<unsigned int, int> dict;
  bool distinct = true;
  for (int i = 0; i < n; i++)
  {
    unsigned int ai;
    cin >> ai;
    dict[ai]++;

    if (dict[ai] > 1) distinct = false;
  }

  cout << (distinct ? "YES" : "NO") << endl;
}

Measured memory_bytes: 9600
#include <stdio.h>

int main(){

int A,B,C,D;
int bus;
int train;
int sum;

scanf("%d\n",&A);
scanf("%d\n",&B);
scanf("%d\n",&C);
scanf("%d\n",&D);

if(A < B){

 train = A;
 

}else{

 train = B;

}

if(C < D){

 bus  = C;

}else{

 bus = D;

}

sum = bus + train;

printf("%d",sum);



}

Measured memory_bytes: 128
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
vint adj[100001],adjout[100001];
int color[100001]={};
int jun[100001];
vint L;
void dfs_visit(int u){
	if(color[u]==0){
		color[u]=1;
		rep(i,adj[u].size()){
			int v=adj[u][i];
			dfs_visit(v);
		}
		L.push_back(u);
		jun[u]=L.size();
	}
}
int main(){
	int N,M;
	int A[100001],B[100001];
	int p[100001];
	int count[100001]={};
	scan(N);scan(M);
		fill(p,p+N,-1);
	rep(i,N+M-1){
		scan(A[i]);scan(B[i]);
		A[i]--; B[i]--;
		adj[A[i]].push_back(B[i]);
		adjout[B[i]].push_back(A[i]);
		count[B[i]]++;
	}
	/*int ne;
	rep(i,N) if(count[i]==0) ne=i;*/
	rep(i,N) dfs_visit(i);
	rep(i,N){
		int maxjun=INF;
		rep(j,adjout[i].size()){
			if(jun[adjout[i][j]]<maxjun){
				maxjun=jun[adjout[i][j]];
				p[i]=adjout[i][j];
			}
		}
	}
	rep(i,N) prin(p[i]+1);
	return 0;
}


Measured memory_bytes: 16380
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<pair<ll, ll>>> vvpll;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 1100010;

// aのn乗を求める。計算量はO(logn)
ll modpow(ll a, ll n) {
    if(n == 0) {
        return 1;
    }
    if(n%2 == 1) {
        return (a * modpow(a, n-1))%mod;
    }
    return (modpow(a, n/2) * modpow(a, n/2))%mod;
}

ll inv(ll a) {
    return modpow(a, mod-2);
}

ll fact[MAX_N];
ll invfact[MAX_N];

// main関数でinit()を呼び出してからComb()を使用する
void init() {
    fact[0] = 1;
    invfact[0] = 1;
    for(ll i = 1; i < MAX_N; i++) {
        fact[i] = (i*fact[i-1])%mod;
        invfact[i] = inv(fact[i]);
    }
}
 
ll Comb(ll n, ll r) {
    if(r < 0 || n < 0 || n < r) {
        return 0;
    }
    ll res = fact[n];
    res = (res * invfact[r])%mod;
    res = (res * invfact[n-r])%mod;
    return res;
}

int main() {
    ll x, y;
    cin >> x >> y;
 
    if((x+y)%3 != 0) {
        out(0);
        re0;
    }
 
    ll n = (x+y)/3; 
    if(x < n || y < n) {
        out(0);
        re0;
    }

    init();
 
    out(Comb(n, x-n));
    re0;
}

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

int main()
{
    int a[100] = {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 i;
    cin >> i;
    cout << a[i-1] << endl;
}

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

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

  vector<int> v(n);
  for (int& e : v) cin >> e;

  int total = accumulate(v.begin(), v.end(), 0);
  cout << ((total >= h) ? "Yes": "No") << endl;

  return 0;
}


Measured memory_bytes: 640
import java.util.*;
 
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        long a[] = new long[n+1];
        long b[] = new long[n];

        for (int i = 0; i < n+1; i++) {
            a[i] = sc.nextLong();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextLong();
        }

        long sum = 0;

        for (int i = 0; i < n; i++) {
            if (b[i] <= a[i]) {
                sum += b[i];
            } else {
                if (b[i] <= a[i] + a[i+1]) {
                    sum += b[i];
                } else {
                    sum += a[i] + a[i+1];
                }
                a[i+1] -= b[i] - a[i];
                if (a[i+1] < 0) {
                    a[i+1] = 0;
                }
            }
        }

        System.out.println(sum);
	}
}


Measured memory_bytes: 66588
N = int(input())
A = list(map(int, input().split()))
M = 10**9+7

from collections import Counter
cd = Counter(A)
# A.sort()

if N & 1:
    # odd
    if cd[0] != 1:
        print(0)
        exit(0)
    ng = False

    for ix in range(2, N//2 + 1, 2):
        if cd[ix] != 2:
            ng = True
            break

    if len(cd) != N//2 + 1:
        ng = True
    
    if ng:
        print(0)
    else:
        # print(pow(2,(N//2),M))
        ans = 1
        for ix in range(N//2):
            ans *= 2
            ans %= M
        print(ans)

else:
    # even
    ng = False
    for ix in range(1, N//2+1, 2):
        if cd[ix] != 2:
            ng = True
            break
    
    if len(cd) != N//2:
        ng = True
    
    if ng:
        print(0)
    else:
        # print(pow(2,(N//2),M))
        ans = 1
        for ix in range(N//2):
            ans *= 2
            ans %= M
        print(ans)


Measured memory_bytes: 20412
while True:
  try:
    a = int(input())
    primes = [1] * (a+1)
    for i in range(2, int(a**0.5)+1):
      if primes[i] == 1:
        for j in range(i*i, a+1, i):
          primes[j] = 0
    print(sum(primes)-2) 
  except EOFError:
    break


Measured memory_bytes: 22152
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    r = []
    for i in range(N):
        r.append(input())
    r = Counter(r)
    print('AC x',r['AC'])
    print('WA x',r['WA'])
    print('TLE x',r['TLE'])
    print('RE x',r['RE'])


    
main()

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

int main()
{
	int i,n,m,hon[100],max,dan,temp;
	while(cin >> m >> n, n || m){
		max = 0;
		for(i = 0;i < n;i++){
			cin >> hon[i];
			if(max < hon[i])
				max = hon[i];
		}
		dan = m + 1;
		for(i = max;dan > m;i++){
			dan = 1;
			temp = 0;
			for(int j = 0;j < n;j++){
				if(temp + hon[j] <= i){
					temp += hon[j];
				} else {
					temp = hon[j];
					dan++;
				}
			}
		}
		cout << i - 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
import java.util.Scanner;

class Main {
  public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    int m = scan.nextInt();

    long res = 0;
    for (int i = 0; i < m; i++) {
      res += scan.nextInt();
    }

    if (res > n) {
      System.out.println(-1);
    } else {
      System.out.println(n - res);
    }

  }

}


Measured memory_bytes: 46200
#coding:utf-8
import bisect
from collections import deque
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    s = input()
    if s[0] == s[1] == s[2]:
        print("No")
    elif s[0] == s[1] and s[2] == s[3]:
        print("Yes")
    elif s[0] == s[2] and s[1] == s[3]:
        print("Yes")
    elif s[0] == s[3] and s[1] == s[2]:
        print("Yes")
    else:
        print("No")




if __name__ == '__main__':
    main()



Measured memory_bytes: 3316
n,k = map(int,input().split())



mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*n+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

def nHr(n,r,mod):
    return nCr(n+r-1,r,mod)



ans = 0

m = min(k,n-1)
for i in range(m+1):
    ans += nCr(n,i,mod)*nHr(n-i,i,mod)%mod
print(ans%mod)


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

using namespace std;

string solve(string s)
{
  int sz = s.size();
  int b = 0;
  for(int i = 1; i < sz; i++) b += (s[i] == 'B');
  int a = sz - b - 1;
  if (a == 0) return "N";
  if (b >= 2) return "Y";
  if (b == 1 && a == 1) return "Y";
  return "N";
}

const int maxn = 110;

int n, W;
int w[maxn], v[maxn];
int f[maxn][100010];

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

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= sumOfVi; j++) 
      f[i][j] = W + 1;
  f[1][0] = 0;
  f[1][v[1]] = w[1];
  
  int cur = v[1];
  for(int i = 2; i <= n; i++) {
    cur += v[i];
    for(int j = 1; j <= cur; j++) {
      f[i][j] = min(f[i][j], f[i-1][j]);
    }
    for(int j = v[i]; j <= cur; j++)  {
      f[i][j] = min(f[i][j], f[i-1][j-v[i]] + w[i]);
    }
  }
  int res = 0;
  for(int j = 1; j <= sumOfVi; j++)
    if (f[n][j] <= W) res = j;
  cout << res << '\n';

  return 0;
} 

Measured memory_bytes: 40832
N, K = map(int, input().split())
A = list(map(int, input().split()))
visited = [False]*N
path = [0]
at = 0
loop = 0
visited[0]=True
for i in range(N):
    at = A[at]-1
    if visited[at]:
        loop = i+1-path.index(at)
        break
    else:
        visited[at]=True
        path.append(at)
if K < path.index(at):
    print(path[K]+1)
else:
    print(path[(K-path.index(at))%loop+path.index(at)]+1)

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    int START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    i32 n; cin >> n;
    minheap<ld> v;
    rep(i,n) {
        i32 tmp;
        cin >> tmp;
        v.push(tmp);
    }

    while(v.size() > 1) {
        ld a,b;
        a = v.top(); v.pop();
        b = v.top(); v.pop();
        v.push((a+b)/2);
    }

    cout << v.top() << '\n';



    // printf("ExecutionTime: %d /ms\n",1000*(int)((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 3848
# C - Walk on Multiplication Table
# https://atcoder.jp/contests/abc144/tasks/abc144_c

import math

n = int(input())
sqr = int(math.sqrt(n)) + 1
for i in range(sqr, 0, -1):
         if (n % i) == 0:
            print(i + (n//i) - 2)
            exit()


Measured memory_bytes: 40044
import java.util.Scanner;
 
public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final String s = scanner.next();
        int right = 0;
 
        for (final char c : s.toCharArray()) {
            if (c == 'E') {
                right++;
            }
        }
 
        int answer = Integer.MAX_VALUE;
        int left = 0;
        for (int i = 0; i < n; i++) {
            final boolean isLeft = s.charAt(i) == 'W';
            if (!isLeft) {
                right--;
            }
 
            answer = Math.min(answer, right + left);
 
            if (isLeft) {
                left++;
            }
        }
 
        System.out.println(answer);
    }
}

Measured memory_bytes: 30664
n,y = map(int, input().split())
ans = [-1,-1,-1]
for i in range(n+1):
    for j in range(n+1):
        z = n-(i+j)
        s = 10000*i + 5000*j + 1000*z
        if z < 0:
            continue
        if s == y:
            ans[0] = i
            ans[1] = j
            ans[2] = z
print(ans[0],ans[1],ans[2])

Measured memory_bytes: 3064
from itertools import permutations, combinations,combinations_with_replacement,product

x, y = map(int, input().split())
MOD = 1000000007

if (x + y) % 3 != 0:
  print(0)
  exit()

m = int((2 * y - x) / 3)
n = int((2 * x - y) / 3)

def combination(n, r):
    r = min(r, n - r)
 
    num = 1
    den = 1
 
    for i in range(1, r + 1):
        num = num * (n + 1 - i) % MOD
        den = den * i % MOD
 
    return num * pow(den, MOD - 2, MOD) % MOD

if m < 0 or n < 0:
    print(0)
    exit()

print(int(combination(m + n, n)) % MOD)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

deque<int> f(long long n){
	if(n==1) return deque<int>();
	if(n&1){
		deque<int> q=f(n-1); 
		q.push_front((int)q.size()+1); 
		return q;
	}else{
		deque<int> q=f(n/2); 
		q.push_back((int)q.size()+1); 
		return q;
	}
}

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	//freopen("dat.in","r",stdin);
	//freopen("my.out","w",stdout);
#endif
	long long n;
	cin>>n;
	auto ans=f(n+1); 
	printf("%d\n",(int)ans.size()*2);
	for(int x:ans)printf("%d ",x);
	rep(i,1,(int)ans.size())printf("%d ",i);
	puts(""); 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(x) x.begin(),x.end()
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

ll n,k;
vector<ll>a;
ll solve(){
   ll ans=0;
   

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

    cin>>n>>k;
    a.resize(n);
    rep(i,n)cin>>a[i];
    for(int i=k;i<n;i++){

        if(a[i]>a[i-k])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    //cout<<solve()<<endl;
    return 0;
}

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;


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

  string raw = "YAKI";
  SCIN(s);
  if (s.size() < 4) {
    OK(false);
    return 0;
  }
  bool ok = true;
  REP(i, 4) {
    if (s[i] != raw[i]) ok = false;
  }
  OK(ok);
  
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <utility>

using namespace std;
typedef long long ll;

int main() {
    string s;
    cin >> s;
    vector<bool> alpha(26, false);
    for(int i=0;i<s.size();i++) {
        alpha[s[i]-'a'] = true;
    }

    bool isNone = true;
    for(int i=0;i<alpha.size();i++) {
        if(!alpha[i]) {
            cout << char(i + 'a') << endl;
            isNone = false;
            break;
        }
    }
    if(isNone)
        cout << "None" << endl;
}


Measured memory_bytes: 512
#include<stdio.h>

int main(){

    int n,d,min,max,i;
    long long sum;

    scanf("%d%d",&n,&d);

    min = d;
    max = d;
    sum = d;
  
    for( i = 0; i < n-1;i++){

    scanf("%d",&d);

    if( d < min){
        min = d;
   }else if( d > max){
        max = d;
   }

    sum += d;
    }
   
    printf("%d %d %lld\n",min,max,sum);

    return 0;
}







Measured memory_bytes: 2096