akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 17 09:42:24 2017

@author: syaga
"""

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    flag = 1
    num = 0
    while flag:
        flag = 0
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                temp = A[j]
                A[j] = A[j-1]
                A[j-1] = temp
                flag = 1
                num += 1
    print(" ".join(map(str, A)))
    print(num)

Measured memory_bytes: 7672
N, K = [int(i) for i in input().split()]

if ((N - 1) * (N - 2)) / 2 < K:
    print(-1)
else:
    point = range(1, N + 1)
    base_line = [[v, point[-1]] for v in point[:-1]]
    add = ((N - 1) * (N - 2)) // 2 - K
    edges = [[i, j] for i in point[:-1] for j in point[i:-1]]

    print(len(base_line) + add)

    for a, b in (base_line + edges[:add]):
        print(a, b)


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;
const ll INF = (1LL << 62);

int main() {
  ll N, M, C;
  scanf("%lld %lld %lld", &N, &M, &C);

  vector<ll> b_list(M);
  for (ll i = 0; i < M; i++) {
    ll v;
    scanf("%lld", &v);
    b_list[i] = v;
  }

  ll ans = 0;
  for (ll i = 0; i < N; i++) {
    ll sum = C;
    for (ll j = 0; j < M; j++) {
      ll a;
      scanf("%lld", &a);

      sum += a * b_list[j];
    }
    if (sum > 0) {
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
a, b, c = map(int,input().split())

if a==b:
    if a==c:
        print(1)
    else:
        print(2)

elif b==c:
    if a==b:
        print(1)
    else:
        print(2)

elif a==c:
    if a==b:
        print(1)
    else:
        print(2)


else:
    print(3)


Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
signed main(){
	double a;
	while( scanf("%lf", &a) != EOF ){
		double sum = a;
		for(int i=1;i<10;i++){
			if(i%2 == 0) a /= 3;
			else a *= 2;
			sum += a;
		}
		printf("%f\n",sum);
	}
	return 0;
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<55;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=998244353;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
string s;

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

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int N, a[1111111];

  std::cin >> N;

  memset(a, 0, sizeof(a));

  for (int i = 1; i <= 100; i ++)
    for (int j = 1; j <= 100; j ++)
      for (int k = 1; k <= 100; k ++) {
        int x = i * i + j * j + k * k + i * j + j * k + k * i;

        if (x <= 10000)
          a[x] ++;
      }

  for (int i = 1; i <= N; i ++)
    std::cout << a[i] << std::endl;
  
  return 0;
}


Measured memory_bytes: 7988
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    double x[10],y[10],sum=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&x[i],&y[i]);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            sum+=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
        }
    }
    int s=1;
    for(int i=1;i<=n;i++)
    {
        s*=i;
    }
    printf("%.10lf",sum/n*1.0);
    return 0;
}


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

int main() {
  
  int n;
  cin >> n;
  
  vector<int> a(n);
  for ( int i = 0; i < n; i++){
    cin >> a[i];
    if ( a[i] % 2 != 0 ){
      cout << 0 << endl;
      return 0;
    }
  }
  
  int count = 0,flag = 1;
  
  while(true){
    for( int i = 0; i < n; i++){
      if ( a[i] % 2 != 0 ){
        cout << count << endl;
        return 0;
      }
    }
    
    count++;
    for( int i = 0; i < n; i++){
      a[i] /= 2;
    }
  }
  
  
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
#define out(a) cout << a << " "
#define ALL(a) (a).begin(), (a).end()
#define upper_index(v, a) (int)distance(v.begin(), upper_bound((v).begin(), (v).end(), a))
#define lower_index(v, a) (int)distance(v.begin(), lower_bound((v).begin(), (v).end(), a))

template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

int main()
{
    ll INF=10000000000000;
    int n,m,l;
    cin>>n>>m>>l;
    vector<vector<ll>> d(n,vector<ll>(n,INF));
    rep(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        d[a-1][b-1]=c;
        d[b-1][a-1]=c;
    }
    rep(i,n) d[i][i]=0;
    rep(part,2){
        rep(k,n)rep(i,n)rep(j,n){
            chmin(d[i][j],d[i][k]+d[k][j]);
        }
        if (part==0){
            rep(i,n)rep(j,n){
                if (i!=j && d[i][j]<=l) {
                    d[i][j]=1;
                }else{
                    d[i][j]=INF;
                }
            }
        }else{
            rep(i,n)rep(j,n){
                if (d[i][j]==INF) d[i][j]=0;
            }
        }
    }
    int q;
    cin>>q;
    rep(i,q){
        int x,y;
        cin>>x>>y;
        cout<<d[x-1][y-1]-1<<endl;
    }
    return 0;
}

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

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int fanc(int a,int b,int c,int d){
  return COM(a,b)*COM(c,d)%MOD;
}

int main(){
  //テーブルの前処理。
  COMinit();
  int64_t h,w,a,b;
  cin >> h >> w >> a >> b;
  int index = min(h-a,w-b);//index of sum;
  h--;
  w--;
  int k = h-a+b,l = h-a,m = w+a-b,n = a;
  int64_t ans = 0;
  for(int i = 0; i < index; i++){
    int64_t tmp =  fanc(k,l,m,n);
    l--;
    n++;
    ans+=tmp;
    ans%=MOD;
  }
  cout << ans << endl;
}

Measured memory_bytes: 12160
#include <iostream>
//#include <string>
using namespace std;

int main() {
    int r, g, b;
    cin >> r >> g >> b;
    int rgb = (100*r) + (10*g) + (b);
    if(rgb%4 ==  0){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
}


Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let p = read_vec::<usize>();
    let mut ans = 0;
    for j in 1..n - 1 {
        let i = j - 1;
        let k = j + 1;
        if (p[i] > p[j] && p[j] > p[k]) || p[i] < p[j] && p[j] < p[k] {
            ans += 1;
        }
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 2180
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
//for(int i = 0; i<n; i++)
 
 
int main()
{
    int k,t;cin>>k>>t;
    vector<int> a(t);
    int b = 0;
    int sum = 0;
    for(int i = 0; i < t; i++) {
        cin>>a[i];
        if(a[i] > b) b = a[i];
        sum += a[i];
    }
    sum -= b;
    cout << (b - sum <= 1 ? 0:b - sum - 1) << endl;
    
    return 0;
    
}


Measured memory_bytes: 256
N=int(input())
L=[]
count=0
for i in range(N):
	L.append(input())
M=len(set(L))
for i in range(N-1):
	if L[i][-1]==L[i+1][0]:
		count+=1
if M==N and count==N-1:
	print("Yes")
else:
	print("No")

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
 
#define NIL -1
#define MAX 101
 
int main(){
  int A[MAX][MAX];
  int V[MAX]={0};
  int Aij[MAX];
  int E[MAX]={NIL};
  int i,j,n,sum=0,max=0,min=0;
 
  scanf("%d",&n);
  for(i=0 ; i<n ; i++){
    for(j=0 ; j<n ; j++){
      scanf("%d",&A[i][j]);
    }
  }
 
  Aij[0] = 0;
  for(i=1; i<n; i++) Aij[i] = 2001;
 
  while(max != 2001){
    max = 2001;
    for(i=0 ; i<n ; i++){
      if(V[i] != 2 && Aij[i] < max){
        max = Aij[i];
        min = i;
      }
    }
    V[min] = 2;
    for(i=0 ; i<n ; i++){
      if(A[min][i] != NIL && V[i] != 2 && A[min][i] < Aij[i]){
        E[i] = min;
        Aij[i] = A[min][i];
        V[i] = 1;
      }
    }
  }
 
  for(i=0 ; i<n ; i++){
    if(E[i] != NIL) sum += A[i][E[i]];
  }
 
  printf("%d\n",sum);
 
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
typedef long long ll;

int n, a, x[50];
ll dp[51][51][2501];

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

	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i+1; j++) {
			for (int k = 0; k <= 2500 - x[i]; k++) {
				dp[i + 1][j][k] += dp[i][j][k];
				dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
			}
		}
	}

	ll ans = 0;
	for (int i = 1; i <= n;i++) {
		ans += dp[n][i][i*a];
		//cout << dp[n][i][i*a] << " ";
	}
	cout << ans << endl;
}

Measured memory_bytes: 49152
#include <stdio.h>

int main(){
	int t;
	scanf("%d", &t);
	long long int sum=0;
	long long int min =0;
	for (int i=1; i<= t; i++){
		if (i%3==0 || i%5==0){
			min += i;
		}
		sum+=i;
	}
	printf("%lld", sum-min);
	return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

class Cups {
public:
    Cups(int, int);
    void setInputData();
    void move();
    bool isGoal();
    bool canMove(char, char);
    int getStep();
private:
    stack<int> sA, sB, sC;  // startA, B, C
    stack<int> gA, gB, gC;  // goalA, B, C
    int n, m;
    int step;
    string prev;
};

Cups::Cups(int n, int m) {
    this->step = 0;
    this->n = n;
    this->m = m;
    // Default cups
    for (int i=1; i<=n; ++i) {
        sA.push(i);
    }
}
int Cups::getStep() {
    return step;
}
void Cups::setInputData() {
    int n, cup;
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> cup; 
        gA.push(cup);
    }
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> cup; 
        gB.push(cup);
    }
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> cup; 
        gC.push(cup);
    }
}
bool Cups::isGoal() {
    if ((sA == gA && sB == gB && sC == gC) ||
        (sA == gC && sB == gB && sC == gA)) {
        return true;
    }
    return false;
}
void Cups::move() {
    if (canMove('A','B')) {
        sB.push(sA.top()); sA.pop();
        prev = "AtoB";
    } else if (canMove('C', 'B')) {
        sB.push(sC.top()); sC.pop();
        prev = "CtoB";
    } else if (canMove('B', 'A')) {
        sA.push(sB.top()); sB.pop();
        prev = "BtoA";
    } else if (canMove('B', 'C')) {
        sC.push(sB.top()); sB.pop();
        prev = "BtoC";
    }
    step ++;
}
bool Cups::canMove(char from, char to) {
    stringstream way;
    way << to << "to" << from;
    if (prev == way.str()) {
        return false;
    }

    int cup[3];
    cup[0] = sA.empty() ? 0 : sA.top();
    cup[1] = sB.empty() ? 0 : sB.top();
    cup[2] = sC.empty() ? 0 : sC.top();

    if (cup[from-'A'] > cup[to-'A']) {
        return true;
    }
    return false;
}

int main() {
    int n, m;
    while (cin >> n >> m && n!=0 && m!=0) {
        Cups cups(n, m);
        cups.setInputData();

        int res = -1;
        if (cups.isGoal()) {
            res = 0;
        } else {
            for (int i=0; i<m; i++) {
                cups.move();
                if (cups.isGoal()) {
                    res = cups.getStep();
                    break;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1240
n = gets.chomp.to_i
s = Array.new(n).map { gets.chomp }
m = gets.chomp.to_i
t = Array.new(m).map { gets.chomp }

s_text_and_counts = s.group_by(&:itself).map { |k, v| [k, v.length] }

max_x_without_s = 0
max_x_with_s = s_text_and_counts.map do |s_text_and_count|
  s_text = s_text_and_count[0]
  s_count = s_text_and_count[1]
  x = s_count - t.count { |ti| ti == s_text }
end.max
max_x = [max_x_without_s, max_x_with_s].max

puts max_x


Measured memory_bytes: 1788
def spaceinput():
    return list(map(int,input().split(" ")))




N=int(input())
a=spaceinput()

def warisu(x):
    count=0
    for i in range(10**10):
        if x%2!=0:
            break
        x=x/2
        count+=1
    return count


res=0
for sa in a:
    res+=warisu(sa)

print(res)


Measured memory_bytes: 4148
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin >> N >> K;
  vector<int> price(N);
  for(int i=0;i<N;i++){
    cin>>price.at(i);
  }
  sort(price.begin(),price.end());
  int total=0;
  for(int i=0;i<K;i++){
    total+=price.at(i);
  }
  cout << total << endl;
}

Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;

int main(){
    int n; cin >> n;
    vector<int> s(n);
    for(int i=0;i<n;i++){
        cin >> s[i];
    }
    int q; cin >> q;
    vector<int> t(q);
    for(int i=0;i<q;i++){
        cin >> t[i];
    }
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    int ans=0;
    for(int i=0;i<q;i++){
        int left=-1,right=n;
        while(right-left>1){
            int mid=(left+right)/2;
            if(s[mid]>t[i]){
                right=mid;
            }
            else{
                left=mid;
            }
        }
        if(s[left]==t[i])ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3356
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string.h>
#include <stdio.h>
#define LL long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<int, pii >
#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define vi vector<int>
#define vpi vector< pii >
#define INF 2147483647
#define big 19260817
#define pb push_back
#define mp make_pair
using namespace std;
const int Maxk=1005;
string mul(string a,string b){
	int res[Maxk];
	memset(res,0,sizeof(res));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	for (int i=0;i<a.length();i++){
		for (int j=0;j<b.length();j++){
			res[i+j]+=(a[i]-'0')*(b[j]-'0');
		}
	}
	for (int i=0;i<Maxk;i++){
		if (res[i]>=10) {
			res[i+1]+=(res[i]/10);
			res[i]%=10;
		}
	}
	string ret;
	bool flag=false;
	for (int i=Maxk-1;i>=0;i--){
		if (flag || res[i]){
			flag=true;
			ret=ret+(char)(res[i]+'0');
		}
	}
	if (ret=="") ret="0";
	return ret;
}
string add(string a,string b){
	if (a.length()<b.length()) swap(a,b);
	while (a.length()!=b.length()){
		b='0'+b;
	}
	for (int i=a.length()-1;i>=0;i--){
		a[i]+=(b[i]-'0');
		if (a[i]>'9' && i){
			a[i]-=10;
			a[i-1]++;
		}
	}
	if (a[0]>'9'){
		a[0]-=10;
		a='1'+a;
	}
	return a;
}
// cf IO: I64d
// atcoder IO: ｌｌｄ
const int Maxn=100005;
LL a[Maxn];
LL b[Maxn];
int main(){
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%lld %lld",&a[i],&b[i]);
	}
	long long now=0;
	for(int i=n-1;i>=0;i--){
		a[i]+=now;
		a[i]=(a[i]-1+b[i])%b[i]+1;
		a[i]=b[i]-a[i];
		now+=a[i];
	}
	printf("%lld\n",now);
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <list>
#include <math.h>
#include <iomanip>
#include <map>
#include <cstdlib>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

int static const N_MAX = 1000 * 1000;
int N;
int dp[N_MAX];
int h[N_MAX];

int main(){

  int INF = 1000 * 1000 * 1000;
  cin>>N;
  rep(i,N){
    cin>>h[i];
    dp[i] = INF;
  }
  dp[N + 1] = INF;
  dp[N + 2] = INF;
  dp[N + 3] = INF;
  dp[N + 4] = INF;
  dp[N + 5] = INF;

  dp[0] = 0;
  rep(i,N){
    dp[i+1] = min(dp[i] + abs(h[i+1]-h[i]), dp[i+1]);
    dp[i+2] = min(dp[i] + abs(h[i+2]-h[i]), dp[i+2]);
  }

  cout<< dp[N-1] << endl;

}

Measured memory_bytes: 4736
# -*- coding: utf-8 -*-


s = input().strip()
#----------
loc_A=len(s)+1
loc_Z=-1
for i in range(len(s)):
    if s[i] == "Z" and loc_Z < i:
        loc_Z = i
    elif s[i] == "A" and i < loc_A:
        loc_A = i

print( loc_Z - (loc_A - 1) )


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

#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;

int main() {
    ll N,t,r1=0,r2=0;
    map<ll,int> A;
    cin >> N;

    rep(i,N) {
        cin >> t;
        if(A.count(t))
            A.at(t)++;
        else
            A[t] = 1;
    }

    for(auto p : A) {
        if(p.second > 3) {
            r1 = p.first;
            r2 = p.first;
        } else if(p.second > 1) {
            r1 = r2;
            r2 = p.first;
        }
    }

    cout << r1*r2 << endl;
}

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

#define N 1100

char s[N], t[N];

int main() {
    int n, i;
    scanf("%s", s);
    scanf("%s", t);
    n = strlen(s);
    for (i = 0; i < n; ++i) {
        int flag = 1;
        for (int j = 0; j < n; ++j) {
            if (s[(i + j) % n] != t[j]) flag = 0;
        }
        if (flag) break;
    }
    if (i == n) puts("No");
    else puts("Yes");
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int w = sc.nextInt();
    int[] num = new int[w];
    for(int i = 0; i < w; i++) {
      num[i] = i+1;
    }
    int n = sc.nextInt();
    for(int i = 0; i < n; i++) {
      String str = sc.next();
      String[] strArr = str.split(",");
      int a = Integer.parseInt(strArr[0]);
      int b = Integer.parseInt(strArr[1]);
      int wk = num[a-1];
      num[a-1] = num[b-1];
      num[b-1] = wk;
    }
    for(int i = 0; i < w; i++) {
      System.out.println(num[i]);
    }
  }
}

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

ll divi(ll a,ll b){
  return (a+b-1)/b;
}

ll K;
ll A[100000];

int main(){
  cin>>K;
  for(int i=0;i<K;i++)cin>>A[i];
  
  if(A[K-1]!=2){
    cout<<-1<<endl;
    return 0;
  }

  
  ll left=2,right=2;
  for(int i=K-1;i>=0;i--){
    ll a=A[i];
    left=divi(left,a)*a;
    right=right/a*a+a-1;
  }
  if(left<=right) cout<<left<<' '<<right<<endl;
  else cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main (void){
    int h[10000],w[10000];
    int i,j,k,l;
    i = 0;
    while(1){
        scanf("%d %d",&h[i],&w[i]);
        if(h[i]==0 & w[i]==0){
            break;
        }
        i++;
    }

    for(j=0;j<i;j++){
        for(k=0;k<h[j];k++){
            for(l=0;l<w[j];l++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    
    return 0;
}


Measured memory_bytes: 2128
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<vector<int>> pos(200005);
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        pos[a].push_back(i);
    }
    
    if(pos[1].size() == 0){
        cout << -1 << endl;
        return 0;
    }
    
    int now_pos = pos[1][0];
    for(int i = 2; i < 200005; ++i){
        auto it = upper_bound(pos[i].begin(), pos[i].end(), now_pos);
        if(it == pos[i].end()){
            cout << n - i + 1 << endl;
            return 0;
        }
        now_pos = *it;
    }
}

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


int main() {
  string S;
  cin >> S;
  ll Q;
  cin >> Q;
  vector<string> str1, str2;
  str1.reserve(Q);
  str2.reserve(Q);
  bool reverse = false;
  int T, F;
  string C;
  for (auto i = 0;i < Q;i ++) {
    cin >> T;
    if (T == 1) {
      reverse = !reverse;
      continue;
    }
    cin >> F;
    cin >> C;
    if (F == 1) {
      if (reverse) {
        str1.push_back(C);
      } else {
        str2.push_back(C);
      }
      continue;
    }
    if (reverse) {
      str2.push_back(C);
    } else {
      str1.push_back(C);
    }
  }
  /*
  cout << "str2" << endl;
  for (auto i = 0; i < str2.size(); i++) {
    cout << str2[i] << endl;
  }
  cout << "str1" << endl;
  for (auto i = 0; i < str1.size(); i++) {
    cout << str1[i] << endl;
  }
  cout << reverse << endl;
  */
  if (!reverse) {
    for (auto i = str2.size();i > 0; i--) {
      cout << str2[i - 1];
    }
    cout << S;
    for (auto i = 0;i < str1.size(); i++) {
      cout << str1[i];
    }
  } else {
    for (auto i = str1.size();i > 0; i--) {
      cout << str1[i - 1];
    }
    for (auto i = S.size();i > 0; i--) {
      cout << S[i - 1];
    }
    for (auto i = 0;i < str2.size(); i++) {
      cout << str2[i];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 11648
#include<bits/stdc++.h>
using namespace std;
long long n,k,i,j,ans;
long long a[2000001],dp[2000001];
main(){
    cin>>n>>k;
    for(i=1;i<=n;i++)cin>>a[i];
    dp[2]=abs(a[2]-a[1]);
    for(i=2;i<n;i++){
        ans=1e9;
        for(j=0;j<min(i,k);j++){
            ans=min(ans,dp[i-j]+abs(a[i+1]-a[i-j]));
        }
        dp[i+1]=ans;
    }
    cout<<dp[n]<<endl;
}

Measured memory_bytes: 5120
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

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

long long int lcm(long long int a, long long int b){
	return a * b / gcd(a,b);
}

int main(){
	long long int a[3], m[3], p[3] = {1,1,1}, c[3] = {0};
	while(1){
		memset(c,0,sizeof(c));
		cin >> a[0] >> m[0] >> a[1] >> m[1] >> a[2] >> m[2];
		if(!a[0])break;
		for(int i=0;i<3;i++){
			do{
			p[i] = (a[i] * p[i]) % m[i];
			//cout << "Turn " << c[i] << ": " << p[i] << endl;
			c[i] += 1;
			}while(p[i] != 1);
		}
		//cout << c[0] << c[1] << c[2] << endl;
		//int gcd = rec(c[0],rec(c[1],c[2])),
		//lcm = rec(c[0],gcd) * rec(c[1],gcd) * rec(c[2],gcd) * gcd;
			//cout << gcd << " " << lcm << endl;
		cout << lcm(lcm(c[0],c[1]),c[2]) << endl;
	}
	return 0;
}

Measured memory_bytes: 0
def resolve():
  n, m = map(int, input().split())
  l = []
  for i in range(n):
    a, b = map(int, input().split())
    l.append([a, b])
  l.sort()
  ans = 0
  for ab in l:
    if ab[1] < m:
      m -= ab[1]
      ans += ab[0] * ab[1]
    else:
      ans += ab[0] * m
      m = 0
      break
  print(ans)
  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 20072
fun main(args: Array<String>) {
    val words = listOf("dream", "dreamer", "erase", "eraser")
    val s = readLine()!!
    val sb = StringBuilder(s)
    while (sb.isNotEmpty()) {
        var deleted = false
        for (word in words) {
            if (sb.endsWith(word)) {
                sb.delete(sb.length - word.length, sb.length)
                deleted = true
            }
        }
        if (!deleted) break
    }
    println(if (sb.isEmpty()) "YES" else "NO")
}

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

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define F first
#define S second
#define pb push_back
#define pii pair <int, int>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define reunique(a) (a).resize(unique(all(a)) - (a).begin())
#define ld long double
#define int long long

int a[200500];

int chk(int mid, int n){ // how much pairs <= mid
    int ct = 0;
    for (int i = 0; i < n; i++){
        if (a[i] == 0){
            if (mid >= 0)
                ct += n - i - 1;
        }
        else{
            if (a[i] > 0){
                int L = i, R = n;
                while (R - L > 1){
                    int MID = (R + L) >> 1;
                    if (a[i] * a[MID] > mid)
                        R = MID;
                    else
                        L = MID;
                }
                ct += L - i;
            }
            else{
                int L = i, R = n;
                while (R - L > 1){
                    int MID = (R + L) >> 1;
                    if (a[i] * a[MID] > mid)
                        L = MID;
                    else
                        R = MID;
                }
                ct += n - R;
            }
        }
    }
    return ct;
}
void SOLVE(){
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a, a + n);
    int l = -1e18, r = 1e18;
    while (r - l > 1){
        int mid = (r + l) >> 1;
        if (chk(mid, n) >= k)
            r = mid;
        else
            l = mid;
    }
    cout << r << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(6);
    int Q = 1;
    //cin >> Q;
    while (Q--){
        SOLVE();
    }

    return 0;
}


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

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	vector <int> cnt(26);
	for (int i = 0; i < s.length(); ++i) cnt[s[i]-'a']++;
	for (int i = 0; i < 26; ++i){
		if (cnt[i] == 0) {
			char c = 'a' + i;
			cout << c  << "\n";
			return 0;
		}
	}
	cout << "None" << "\n";	
	return 0;
}


Measured memory_bytes: 3680
#include <iostream>

using namespace std;

int main()
{
	int n, d, x, a, ans = 0;

	cin >> n >> d >> x;

	for(int s=0; s<n; s++)
	{
		cin >> a;
		for(int i=0; i*a+1 <= d; i++) ans++;
	}

	ans += x;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
        #define ll long long
        #define rep(i,a,b) for(i=a;i<b;i++)
        #define pb push_back
        #define all(v) v.begin(),v.end()
        #define F first
        #define S second
        #define hell 1000000007
        using namespace std;

        void solve()
        {
          ll n,m,i,j,k,c=0,y=0,ams=0,a,b;
          string s;
   cin>>n>>k;
   vector < ll > v(n);
   rep(i,0,n) cin>>v[i];
   sort(all(v));
   rep(i,0,k) y+=v[i];
   cout<<y;



    }

        int main()
        {
            ios::sync_with_stdio(false);
            cin.tie(0);
            cout.tie(0);
            int t=1;
            //cin>>t;
            while(t--)
            solve();
        }


Measured memory_bytes: 3652
#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>;

const int A = 1e6 + 7;

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

vector<int> prime;
vector<int> factor(A, 0);

void enum_prime() {
  factor[1] = 1;
  for (int i = 2; i < A; ++i) {
    if (factor[i] != 0) continue;
    prime.push_back(i);
    for (int j = i; j < A; j += i) factor[j] = i;
  }
  return;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  enum_prime();
  vector<int> cnt(A, 0);
  vector<int> b(n);
  rep(i, n) b[i] = a[i];
  rep(i, n) {
    set<int> st;
    while (b[i] > 1) {
      st.insert(factor[b[i]]);
      b[i] /= factor[b[i]];
    }
    for (auto itr = st.begin(); itr != st.end(); ++itr) cnt[*itr]++;
  }
  bool p = true;
  rep(i, A) if (cnt[i] > 1) {
    p = false;
  }
  if (p) {
    cout << "pairwise coprime" << endl;
    return 0;
  }
  int g = a[0];
  rep(i, n) g = gcd(g, a[i]);
  if (g == 1) cout << "setwise coprime" << endl;
  else cout << "not coprime" << endl;
  return 0;
}

Measured memory_bytes: 19192
def m(L,R):
 global c;c+=len(L)+len(R)
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):s=len(A)//2;return m(d(A[:s]),d(A[s:]))if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)


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

char a,b,c,d;

int main(){
    cin>>a>>b>>c>>d;
    if(a==b&&b==c)cout<<"Yes"<<endl;
    else if(b==c&&c==d)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define INF 10000000
using ll = long long ;
ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}
template< int id > struct CompTupleBy
{
  template<class T> 
  bool operator()( const T& a, const T& b ) const {
    return std::get<id>(a) < std::get<id>(b);
  }
};

using namespace std;

int main(){
    ll n;
    cin >> n;
    string s;
    cin >> s;
    ll w_sum[n+1];
    w_sum[0] = 0;
    rep(i,n){
        if (s[i]=='W'){
            w_sum[i+1] = w_sum[i] + 1;
        }else{
            w_sum[i+1] = w_sum[i];
        }
    }
    ll ans[n];
    ll answer = INF;
    rep(i,n){
        ll left = w_sum[i];
        ll right = (n-i-1)- w_sum[n] + w_sum[i+1];
        ans[i] = w_sum[i] + (n-i-1)- w_sum[n] + w_sum[i+1];
        if (ans[i] <= answer){
            answer = ans[i];
        }
    }
    cout << answer << endl;
    

    
}

Measured memory_bytes: 5380
#include <stdio.h>
#include <math.h>
 
typedef struct{
  double x;
  double y;
}XY;

void kock( int , XY , XY );
 
 
int main(){
 
  XY p1 = { 0.0 , 0.0 } , p2 = { 100.0 , 0.0 };
  int n;
 
  scanf("%d",&n);
 
  printf("%f %f\n",p1.x,p1.y);
  kock(n,p1,p2);
  printf("%f %f\n",p2.x,p2.y);
 
 return 0;
 
}
 
 
void kock( int n , XY p1 , XY p2 ){
 
  XY s,t,u;
 
  if( n == 0 ) return;
 
  s.x = ( p2.x - p1.x ) / 3 + p1.x;
  s.y = ( p2.y - p1.y ) / 3 + p1.y;
  t.x = 2 * ( p2.x - p1.x ) / 3 + p1.x;
  t.y = 2 * ( p2.y - p1.y ) / 3 + p1.y;
  u.x = ( t.x - s.x ) / 2 - sqrt(3.0) / 2 * ( t.y - s.y ) + s.x;
  u.y = ( t.y - s.y ) / 2 + sqrt(3.0) / 2 * ( t.x - s.x ) + s.y;
 
 
  kock( n-1 , p1 , s );
  printf("%f %f\n",s.x,s.y);
   
  kock( n-1 , s , u );
  printf("%f %f\n",u.x,u.y);
   
  kock( n-1 , u ,t );
  printf("%f %f\n",t.x,t.y);
 
  kock( n-1 , t , p2 );

}

Measured memory_bytes: 636
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
add_s = 0
for idx in range(N-1):
  cur_f = A[idx]
  nxt_f = A[idx+1]
  add_s += C[cur_f-1] if nxt_f == cur_f + 1 else 0

print(sum(B) + add_s)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define mod 1000000007
const int MAX=1e6+1;
ll fac[MAX],finv[MAX],inv[MAX];
 
void COMinit() {
  fac[0]=fac[1]=1;
  finv[0]=finv[1] = 1;
  inv[1]=1;
  for (int i=2; i<MAX; 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;
  }
}
int main()
{
 	COMinit(); 
	int x,y;
    cin>>x>>y;
    int sum=x+y;
    ll ans=0;
    if(sum%3==0)
    {
        ll count=sum/3;
        for(int i=0;i<=count;i++)
        {
            ll one=i;
            ll two=count-i;
            ll s=one+two*2;
            if(s==x||s==y)
            {
                ans=(((fac[count]*finv[one])%mod)*finv[two])%mod;
                break;
            }
        }
    }
    cout<<ans%mod<<endl;//cout<<3*infact[2]%mod<<endl;
	return 0;
}

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

int main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;

  if (X > Y) {
    swap(X, Y);
    swap(A, B);
  }
  C *= 2;

  int ans = 0;
  if (A + B > C) {
    ans += C * X;
    if (B > C) ans += C * (Y - X);
    else ans += B * (Y - X);
  } else {
    ans += A * X + B * Y;
  }

  cout << ans << endl;
}

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

int main() {
	int H,N;
	cin >> H >> N;

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

	for(int i=0;i<N;i++){
		H -= A[i];
		if(H<=0) break;
	}
	if(H>0){
		cout << "No" << endl;
	}else{
	int cnt = 0;
		cout << "Yes" << endl;
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int n; cin >> n;
    map<string, int> cnt;
    vector<string> a(n);
    set<string> all;
    for (string &s : a) {
        cin >> s;
        sort(s.begin(), s.end());
        all.insert(s);
        cnt[s]++;
    }
    ll res = 0;
    for (auto it : all) {
        ll x = cnt[it];
        res += x * (x - 1);
    }
    cout << res / 2ll << "\n";
}


Measured memory_bytes: 25984
fun main(args: Array<String>) {
	val n = (readLine() ?: return).toInt()
	val xy = Array(n) { (readLine() ?: return).split(" ").map { it.toInt() }.toIntArray() }
	var sum = 0.0
	var count = 0
	for (i in 0 until n) for (j in i + 1 until n) {
		sum += Math.sqrt((xy[i][0] - xy[j][0]) * (xy[i][0] - xy[j][0]) + (xy[i][1] - xy[j][1]) * (xy[i][1] - xy[j][1]).toDouble())
		count++
	}
	println(sum * (n - 1) / count)
}

Measured memory_bytes: 37732
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <set>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;
ll max(ll a, ll b) {
	if (a < b)
		return b;
	else
		return a;

}
ll min(ll a, ll b) {
	if (a < b)
		return a;
	else
		return b;

}



int main() {
	ll N, M;

	cin >> N >> M;

	vector<ll> A(N);
	priority_queue<ll> pq;
	
	rep(i, N) {
		cin >> A[i];
		pq.push(A[i]);
		
	}

	rep(i, M) {
		ll a = pq.top();
		pq.pop();
		pq.push(a / 2);
	}
	ll sum = 0;
	rep(i, N) {
		sum += pq.top();
		pq.pop();
	}

	cout << sum << endl;
	return 0;
}

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

int main() {
  vector<int> ABC(3, 0);
  for (int i = 0; i < 3; i++) {
    scanf("%d", &ABC.at(i));
  }

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

  if (ABC.at(0) == ABC.at(1))
    printf("%d", ABC.at(2));
  else if (ABC.at(1) == ABC.at(2))
    printf("%d", ABC.at(0));

  return 0;
}

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

using namespace std;

int main(void) {
  int n;
  scanf("%i", &n);
  
  vector<long long> c(n), s(n), f(n);
  for (int i = 0; i < n - 1; i++) {
    scanf("%lld %lld %lld", &c[i], &s[i], &f[i]);
  }
  
  for (int i = 0; i < n - 1; i++) {
    long long cur = s[i];
    for (int j = i; j < n - 1; j++) {
      long long x = (cur + f[j] - 1) / f[j];
      cur = max(s[j], x * f[j]) + c[j];
    }
    printf("%lld\n", cur);
  }
  puts("0");
  
  return 0;
}

Measured memory_bytes: 888
<?php
fscanf(STDIN,"%d",$n);
fscanf(STDIN,"%s",$str);

if($n % 2 == 1)
{
	echo("No");
}
else
{
	if(substr($str, 0, $n/2) == substr($str, ($n/2), $n/2))
	{
		echo("Yes");
	}
	else
	{
		echo("No");
	}
}

Measured memory_bytes: 3828
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;


int main(int argc, const char * argv[]) {
  	int X,A;
    cin >> X >> A;
  	if(X<A)printf("0");
  	else printf("10");
    return 0;
}

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

int main () {
  ios_base::sync_with_stdio(0);
  int m1, d1, m2, d2;
  cin >> m1 >> d1;
  cin >> m2 >> d2;

  int ans = 0;
  if (m1 == 1 && d1 == 31) ans = 1;
  if (m1 == 2 && d1 == 28) ans = 1;
  if (m1 == 3 && d1 == 31) ans = 1;
  if (m1 == 4 && d1 == 30) ans = 1;
  if (m1 == 5 && d1 == 31) ans = 1;
  if (m1 == 6 && d1 == 30) ans = 1;
  if (m1 == 7 && d1 == 31) ans = 1;
  if (m1 == 8 && d1 == 31) ans = 1;
  if (m1 == 9 && d1 == 30) ans = 1;
  if (m1 == 10 && d1 == 31) ans = 1;
  if (m1 == 11 && d1 == 30) ans = 1;
  if (m1 == 12 && d1 == 31) ans = 1;
  cout << ans;

  return 0;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val five_yen = readLine()!!.toInt()
    val one_hund = readLine()!!.toInt()
    val fifty = readLine()!!.toInt()
    val ans = readLine()!!.toInt()
    var con = 0

    for(i in 0..five_yen){
        for(n in 0..one_hund){
            for(y in 0..fifty){
                if(500 * i + 100*n + 50 * y == ans){
                    con++
                }
            }
        }
        
    }
    println(con)

}

Measured memory_bytes: 31712
import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder builder = new StringBuilder();
        int data = Integer.parseInt(reader.readLine());

        for(int i = 1; i <= data; i++){
            if(i % 3 == 0){
                builder.append(" ").append(Integer.toString(i));
                continue;
            }
            int x = i;
            do{
                if(x % 10 == 3){
                    builder.append(" ").append(Integer.toString(i));
                    break;
                }
                x /= 10;
            }while(x != 0);
        }

        System.out.println(builder);

    }
}

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

using namespace std;
long long dp[51][51][2551];

int main(){
	memset(dp,0,sizeof(dp));
	int mod = 1e9 + 7;
	int n,K;
    cin>>n>>K;
	dp[0][0][0] = 1;

	for(int i=0;i<n;++i){
		for(int j=0;j<=i;++j){
			for(int k=0;k<=K;++k){
				long long curr = dp[i][j][k]%mod;

				// connect current
				dp[i+1][j][k+j*2] += curr;
				dp[i+1][j][k+j*2] %= mod;

				// connect down
				dp[i+1][j+1][k+j*2+2] += curr;
				dp[i+1][j+1][k+j*2+2] %= mod;

				// connect down connect up
				dp[i+1][j][k+j*2] += 2 * j * curr;
				dp[i+1][j][k+j*2] %= mod;

 				
				// connect up  connect up
				dp[i+1][j-1][k+j*2-2] += j * j * curr;
				dp[i+1][j-1][k+j*2-2] %= mod;					
				

				//cout<<dp[i+1][j][k+j*2]<<" "<<dp[i+1][j+1][k+j*2+2]<<" "<<dp[i+1][j-1][k+j*2-2]<<endl;
			}
		}
	}

	cout<<(dp[n][0][K]%mod)<<endl;
	return 0;
}


Measured memory_bytes: 52224
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll a[100001];
int b[100001];
int c[100001];

int main(void){
	scanf("%d",&n);
	ll ans=0;
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		int tmp=0;
		while(a[i]>=(1<<tmp))tmp++;
		tmp--;
		b[i]=tmp;
		if(a[i]>(1<<tmp))c[i]=1;
		ans+=b[i]+c[i];
	}
	int last=0;
	for(int i=0;i<n;i++){
		int m1=min(last,b[i]);
		ans-=m1;
		last-=m1;
		if(last>0 && c[i]>0){
			ans--;
			c[i]--;
		}
		last=b[i]+c[i];
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")

//# include <x86intrin.h>
# include <bits/stdc++.h>

# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
 
template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
// ROAD to...                                                                                                                                                                                                                Red

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}

const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
 
int rnd (int l, int r) {
	return uniform_int_distribution<int> (l, r)(gen);
}
 
int n, m, k;
int cnt[N];
string s;
int a[N];
vector < int > g[N];
int u[N];
int ans, res;
int cur;



int main () {
	SpeedForce;
	setIO();
	cin >> s;
	cout << s.substr(0, 3);

	return Accepted;
}

// B...a

Measured memory_bytes: 17736
r = 10001
sqrt = int(r**0.5)
p = [1]*r
twin = [0]*r
p[0] = 0
p[1::2] = [0 for x in range(1,r,2)]
for i in range(2,r,2):
	if p[i]:
		p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]
		if p[i-2]:
			twin[i] = 1
		
while True:
	n = int(raw_input())
	if n == 0: break
	i = n - twin[:n][::-1].index(1)
	print i-2,i

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

int main() {
  int N;
  cin >> N;
  string rep;
  string sw = "NN";
  for (int i=2; i<N; i++) {
    sw += "N";
  }
  cin >> rep;
  vector<int> vsw(N);
  int repl = -1;
  if (rep[N-1] == 'o') {
    repl += 2;
  }
  
  int repl2 = -1;
  if (rep[0] == 'o') {
    repl2 += 2;
  }
  
  bool can = false;
  
  vsw[0] = 1;
  vsw[1] = 1;
  for(int i=0; i<N-2; i++) {
    if (rep[i+1] == 'o') {
      vsw[i+2] = vsw[i] * vsw[i+1];
    }
    else {
      vsw[i+2] = vsw[i] * vsw[i+1] * -1;
    }
  }
  if (vsw[N-2] * vsw[N-1] * vsw[0] * repl == 1
     && vsw[N-1] * vsw[0] * vsw[1] * repl2 == 1) {
    can = true;
    for (int i=0; i<N; i++) {
      if (vsw[i] == 1) {
        sw[i] = 'S';
      }
      else {
        sw[i] = 'W';
      }
    }
  }
  
  vsw[0] = -1;
  vsw[1] = -1;
  for(int i=0; i<N-2; i++) {
    if (rep[i+1] == 'o') {
      vsw[i+2] = vsw[i] * vsw[i+1];
    }
    else {
      vsw[i+2] = vsw[i] * vsw[i+1] * -1;
    }
  }
  if (vsw[N-2] * vsw[N-1] * vsw[0] * repl == 1
     && vsw[N-1] * vsw[0] * vsw[1] * repl2 == 1) {
    can = true;
    for (int i=0; i<N; i++) {
      if (vsw[i] == 1) {
        sw[i] = 'S';
      }
      else {
        sw[i] = 'W';
      }
    }
  }
  
  vsw[0] = 1;
  vsw[1] = -1;
  for(int i=0; i<N-2; i++) {
    if (rep[i+1] == 'o') {
      vsw[i+2] = vsw[i] * vsw[i+1];
    }
    else {
      vsw[i+2] = vsw[i] * vsw[i+1] * -1;
    }
  }
  if (vsw[N-2] * vsw[N-1] * vsw[0] * repl == 1
     && vsw[N-1] * vsw[0] * vsw[1] * repl2 == 1) {
    can = true;
    for (int i=0; i<N; i++) {
      if (vsw[i] == 1) {
        sw[i] = 'S';
      }
      else {
        sw[i] = 'W';
      }
    }
  }
  
  vsw[0] = -1;
  vsw[1] = 1;
  for(int i=0; i<N-2; i++) {
    if (rep[i+1] == 'o') {
      vsw[i+2] = vsw[i] * vsw[i+1];
    }
    else {
      vsw[i+2] = vsw[i] * vsw[i+1] * -1;
    }
  }
  if (vsw[N-2] * vsw[N-1] * vsw[0] * repl == 1
     && vsw[N-1] * vsw[0] * vsw[1] * repl2 == 1) {
    can = true;
    for (int i=0; i<N; i++) {
      if (vsw[i] == 1) {
        sw[i] = 'S';
      }
      else {
        sw[i] = 'W';
      }
    }
  }
  if (can) {
    cout << sw << endl;
  }
  else {
    cout << -1 << endl;
  }
}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int fiveHundred = sc.nextInt();
			int hundred = sc.nextInt();
			int five = sc.nextInt();
			int x = sc.nextInt();
			int result = 0;
			for (int i = 0 ; i <= fiveHundred; i++) {
				for (int j = 0 ; j <= hundred ; j++) {
					for (int k=0; k <=five; k++) {
						if(i*500+j*100+50*k == x) {
							result++;
						}
					}
				}
			}
			System.out.println(result);
		}
	}
}

Measured memory_bytes: 23764
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#pragma warning(disable : 4996)
using namespace std;
int N, b, v[109], p[109][109];
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> b;
			v[i] |= b << j;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= 10; j++) {
			cin >> p[i][j];
		}
	}
	int ret = -1012345678;
	for (int i = 1; i < 1 << 10; i++) {
		int res = 0;
		for (int j = 0; j < N; j++) {
			int bc = 0;
			for (int k = 0; k < 10; k++) {
				if ((v[j] & i) & (1 << k)) bc++;
			}
			res += p[j][bc];
		}
		ret = max(ret, res);
	}
	cout << ret << endl;
	return 0;
}

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

#define INF 1 << 29
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)

using namespace std;

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

void gen_sosuu(int sosuu[]){
  REP(i,100010){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(100000)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<=100000;j++){
      //printf("%d %d %d\n",i*j,i,j);
      sosuu[i*j] =false;
    }
  }
}

int x,a,b;

int main(){
  scanf("%d %d %d",&x,&a,&b);
  if(b-a<=0){
    printf("delicious\n");
  }else if(b-a<=x){
    printf("safe\n");
  }else{
    printf("dangerous\n");
  }
}


Measured memory_bytes: 256