akhauriyash/Code-Regression huggingface dataset:
///-BISMILLAHIR RAHMANIR RAHIM-///
#include <bits/stdc++.h>
#include<vector>
#include<string>
using namespace std;
#define pb push_back
#define scn(n) scanf("%lld",&n)
#define pi acos(-1)
#define ll long long
#define llu unsigned long long
#define mod 1000000007
int main()
{
    string s;
    cin>>s;
    ll n;
    cin>>n;
    while(n--)
    {
        string p,c;
        ll i,j,k,a,b;
        cin>>c>>a>>b;
        if(c=="replace")
        {
            cin>>p;
            for(i=a,j=0; i<=b; i++,j++)
                s[i]=p[j];
        }
        if(c=="reverse")
        {
            ll q=b-a+1;
            q=q/2-1;
            for(i=a,j=b; i<=a+q; i++,j--)
                swap(s[i],s[j]);
        }
        if(c=="print")
        {
            for(i=a; i<=b; i++)
                cout<<s[i];
            cout<<endl;
        }
    }
    return 0;
}



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

signed main() {
  int n,l;
  cin>>n>>l;
  int a[n],t=-1;
  cin>>a[0];
  for(int i=1;i<n;i++){
    cin>>a[i];
  if(a[i-1]+a[i]>=l){
    t=i;
  }
  }
  if(t==-1)cout<<"Impossible";
  else{
    cout<<"Possible"<<endl;
    for(int i=1;i<t;i++){
     cout<<i<<endl;
    }
     for(int i=n-1;i>t;i--){
     cout<<i<<endl;
    }
    cout<<t<<endl;
  }

  


 


    return 0;
}


Measured memory_bytes: 1536
//BISMILLAH
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    int t;
    int n,k,flag=0,sum=0;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(),v.end());
    for(int i=0;i<k;i++) sum+=v[i];

    cout<<sum<<endl;


    return 0;
}


Measured memory_bytes: 3636
n = gets.chomp.to_i
graph = Hash.new{ |h,k| h[k] = {} }

(n-1).times do |i|
  u, v, w = gets.chomp.split.map(&:to_i)
  graph[u][v] = w
  graph[v][u] = w
end

color = [0]
queue = graph[1].to_a
while q = queue.shift
  dist, weight = q
  next if color[dist-1] != nil

  color[dist-1] = weight % 2

  graph[dist].each do |d, w|
    queue << [d, weight + w]
  end
end

puts(color.join(" "))

Measured memory_bytes: 38396
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception{
		new Main(new Scanner(System.in), System.out, System.err).exec();
	}
	public final Scanner sc;
	public final PrintStream out, err;
	public Main(final Scanner sc, final PrintStream out, final PrintStream err) {
		this.sc = sc;this.out = out;this.err = err;
	}
	static public final long pair(int a, int b) {return (((long)a) << 32) + b;}
	static public final int getPair1(long v) {return (int)(v >> 32);}
	static public final int getPari2(long v) {return (int)(v & 0xFFFFFFFF);}

	static public final long quad(long a, long b, long c, long d) {
		return ((a&0xFFFF)<< 48) + ((b&0xFFFF)<< 32) + ((c&0xFFFF)<< 16) +(d&0xFFFF);}
	static public final int getQuad1(long v) {return (int)( v >> 48          );}
	static public final int getQuad2(long v) {return (int)((v >> 32) & 0xFFFF);}
	static public final int getQuad3(long v) {return (int)((v >> 16) & 0xFFFF);}
	static public final int getQuad4(long v) {return (int)( v        & 0xFFFF);}

	static public final long record(int e, int m, int i) {
		return quad(-1, e, m, i);
	}
	static public final int re(long record) {
		return getQuad2(record);
	}
	static public final int rm(long record) {
		return getQuad3(record);
	}
	static public final int ri(long record) {
		return getQuad4(record);
	}

	//------------------------------------------

	private int p;
	private int[] inv;
	private int[] fact;
	private int[] finv;
	public final int mod(long v) {
		v %= p;
		return (int)(v < 0 ? v+p : v);
	}
	public final int mul(long a, long b) {
		return mod(a*b);
	}
	public final void initFact(double limit, double p) {
		initFact((int)limit, (int)p);
	}
	public final void initFact(int limit, int p) {
		this.p = p;
		this.inv = new int[limit+1];
		this.fact = new int[limit+1];
		this.finv = new int[limit+1];
		fact[1] = finv[1] = inv[0] = inv[1] = 1;
		for(int i=2;i<=limit;i++) {
			int a = p / i;
			int b = p % i;
			inv[i]  = mul(-a, inv[b]);
			fact[i] = mul(fact[i-1], i);
			finv[i] = mul(finv[i-1], inv[i]);
		}
	}
	public final int comb(int m, int n) {
		return mul(mul(fact[m], finv[n]), finv[m-n]);
	}

	//------------------------------------------


	public void exec() throws Exception{
		final int N = sc.nextInt();
		int[][] A = new int[N][60];
		int[] BITS = new int[60];
		for(int i=0;i<N;i++) {
			long a = sc.nextLong();
			for(int s=0;s<60;s++) {
				if(((a>>s)&0x1)==1) {
					A[i][s]=1;
					BITS[s]++;
				}
			}
		}
		long mod = 1000000000 + 7;
		long sum = 0;
		long[] val = new long[60];
		for(int i=0;i<60;i++) {
			val[i] = (0x1L<<i)%mod;
		}
		int right = N;
		for(int i=0;i<N-1;i++) {
			right--;
			for(int b=0;b<60;b++) {
				// 起点分の情報を削る。
				BITS[b]-=A[i][b];
				if(A[i][b]==1) {
					// 自身が1を持つ場合、0の数だけ加算される。
					sum = (sum + (right-BITS[b])*val[b]) %mod;
				}else {
					// 自身が0の場合、1の数だけ加算される。
					sum = (sum + (BITS[b]      )*val[b]) %mod;
				}
			}
		}
		out.println(sum);
	}
}


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

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

    int ans = 0;
    for (int i = 0; (i /2)<= max(x, y); i += 2) {
        int tmp = 0, tmp_a, tmp_b;

        tmp_a = tmp_b  = (i / 2);
        tmp = i * c;
        if (x - tmp_a > 0) tmp += ((x - tmp_a) * a);
        if (y - tmp_b > 0) tmp += ((y - tmp_b) * b);

        if (i == 0) ans = tmp;
        else ans = min(ans, tmp);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        int ans = 100000;
        for (int i = 0; i < n; i ++) {
                int a;
                scanf("%d", &a);
                int cnt = __builtin_ctz(a);
                ans = min(ans, cnt);
        }
        printf("%d\n", ans);
        return 0;
}



Measured memory_bytes: 256
import math

m, d = map(int, input().split())

ans = 0
for i in range(1, m+1):
    days = []
    for j in range(1, int(math.sqrt(i))+1):
        if j==1:
            continue
        if i%j==0:
            days.append(str(j)+str(i//j))
            if i//j != j:
                days.append(str(i//j)+str(j))

    for x in days:
        if int(x)<=d:
            ans += 1

print(ans)

Measured memory_bytes: 3064
//In the name of ALLAH
#include<cstdio>
#include<cstring>
#include<bits/stdc++.h>
#include<iostream>
#include<math.h>
#include<fstream>
#define sc(x) scanf("%d",&x)
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORd(i,a,b) for(int i=a;i>b;i--)
#define ff first
#define ss second
#define reset(x) memset(x,0,sizeof x)
#define sz(x) x.size()
#define pb push_back
#define FASTIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);


using namespace std;

typedef pair<int,int> pii;
typedef vector<pii> vii;
const int con = 1e5+7;
static const int INF = 0x3f3f3f3f;
static const int MOD = 1e9+7;

int main(){

    int incoming[5],outgoing[5];
    int x,y;reset(incoming);reset(outgoing);
    FOR(i,0,3){
        cin >> x >> y;
        incoming[x]++;outgoing[y]++;
    }

    FOR(i,1,5){

        if(incoming[i]+outgoing[i] == 3){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

Measured memory_bytes: 256
N, M = [int(i) for i in input().split()]
sc = [[int(i) for i in input().split()] for _ in range(M)]
ans = ["0"]*N
f = [False]*N
for s, c in sc:
    s -= 1
    c = str(c)
    if (f[s] and ans[s] != c)or(N > 1 and s == 0 and c == '0'):
        break
    f[s] = True
    ans[s] = c
else:
    if not(N != 1 and ans[0] == '0'):
        print(''.join(ans))
    else:
        ans[0] = '1'
        print(''.join(ans))
    exit()

print(-1)


Measured memory_bytes: 38256
#include <stdio.h>

int main(void) {
    int i, j, n1, n2, n3;
    scanf("%d", &i);
    for (j=0; j<i; j++) {
        scanf("%d", &n1);
        scanf("%d", &n2);
        scanf("%d", &n3);
        if (n1 < 1 || n2 < 1 || n3 < 1) {
            printf("NO\n");
            continue;
        }
        if (n1 * n1 + n2 * n2 == n3 * n3 ||
            n2 * n2 + n3 * n3 == n1 * n1 ||
            n3 * n3 + n1 * n1 == n2 * n2) {
            printf("YES\n");
            continue;
        }
        printf("NO\n");
    }
    return 0;
}

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

#define rep(i, u) for (int i = 0; i < u; i++)

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

int main() {
  int n;
  int a[1000000] = {};
  cin >> n;
  rep(i, n) cin >> a[i];
  int cnt = 0;
  int m = 0;
  int g[1000000] = {};
  for (int i = 1; ; i = 3 * i + 1) {
    g[m] = i;
    if (g[m] > n) break;
    m++;
  }
  reverse(g, g + m);
  rep(i, m) {
    for (int j = g[i]; j < n; j++) {
      int v = a[j];
      int k = j - g[i];
      while (k >= 0 && a[k] > v) {
        a[k + g[i]] = a[k];
        k -= g[i];
        cnt++;
      }
      a[k + g[i]] = v;
    }
  }
  cout << m << endl;
  rep(i, m) {
    cout << g[i];
    if (i != m - 1) cout << ' ';
    else cout << endl;
  }
  cout << cnt << endl;
  rep(i, n) cout << a[i] << endl;

  return 0;
}



Measured memory_bytes: 10904
from math import log2, ceil


N, K = map(int, input().split())

ans = 0
for m in range(1, N + 1):
    if m >= K:
        ans += 1 / N
    else:
        y = ceil(log2(K / m))
        prob = (0.5 ** y) / N
        ans += prob

print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll          long long
#define endl        "\n"
#define si(a)       scanf("%d",&a)
#define si2(a,b)    scanf("%d%d",&a,&b)
#define sl(a)       scanf("%lld",&a)
#define sl2(a,b)    scanf("%lld%lld",&a,&b)
#define pb          push_back
#define mk          make_pair
#define loop(n)     for(int i=0; i<n; i++)
#define FOR(a,b)    for(int i=a; i<=b; i++)
#define sz          size()
#define ff          first
#define ss          second
#define mem(a,val)  memset(a, val, sizeof(a))
#define md          1000000007
#define pi          acos(-1.0)

ll a[200010];
map<ll,ll>m;
vector<ll>v;
string s,q;

int main()
{
   ll t,n,i,j,k,l,r,mn=0, mx=0;
   sl2(n,k);
   l=n*2, r=n*4;
   if(k>=l && k<=r && k%2==0)
    cout<<"Yes";
   else cout<<"No";
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1e9;
const int mod=1e9+7;
int main(void)
{
    ll N,K;
    int A[2005];
    ll ans=0;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }
    for(int i=0;i<N;i++)
    {
        ll firstinv=0;
        ll loopinv=0;
        int a=A[i];
        for(int j=i;j<N;j++)
        {
            if(A[j]<a) firstinv++;
        }
        for(int j=0;j<N;j++)
        {
            if(A[j]<a) loopinv++;
        }
        firstinv=(firstinv*K)%mod;
        ans=(ans+firstinv)%mod;
        if(K>=2) 
        {
            ll times=(((K)*(K-1))/2LL)%mod;
            loopinv=(loopinv*times)%mod;
        }
        ans=(ans+loopinv)%mod;
    }
    cout << ans << endl;
    
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String args[]) {
      	Scanner scanInputs =  new Scanner(System.in);
        
        while(scanInputs.hasNext()) {
        	Integer baseInt = Integer.parseInt(scanInputs.next());
            Integer happyLevel = 0;
              if(baseInt>=500) {
                happyLevel += 1000 * (baseInt/500);
            	baseInt = baseInt % 500;
              }
              if(baseInt>=5) {
                happyLevel += 5 * (baseInt/5);
              }
          	System.out.println(happyLevel.toString());
            }
        }
}

Measured memory_bytes: 23764
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

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

int main(){
    string s; cin >> s;
    vl cnt(2);
    ll ans = 0;
    rep(i,s.size()){
        if(s[i] == '0'){
            if(cnt[1]){
                ans += 2;
                cnt[1]--;
            }else{
                cnt[0]++;
            }
        }else{
            if(cnt[0]){
                ans += 2;
                cnt[0]--;
            }else{
                cnt[1]++;
            }
        }
    }
    cout << ans << endl;
}

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



/*int sea(string s){
	reverse(s.begin(),s.end());
	int sum=0;
	for(int i=0;i<s.size();i++){
		sum+=(s[i]-'0')*(int)pow(10,i);
	}
	return sum;
	}*/


string correct(int i){
	if(i%3==0 && i%5==0)return "FizzBuzz";
	else if(i%3==0)return "Fizz";
	else if(i%5==0)return "Buzz";
	else return to_string(i);
}

int main(){
	while(1){
	
		int m,n;
		int a[10000]={};
		set<int> done;
		cin>>m>>n;
		if(m==0 && n==0){break;}
		for(int i=0;i<m;i++){
			a[i]=i+1;
		}
		a[m]=1;
		int b=m;
		int w=1;
		int count=0;
		for(int i=1;i<=n;i++){
			string s;
			bool j=true;
			cin>>s;
			if(count<m-1){
				/*if(i%15==0 && s!="FizzBuzz"){j=false;}
				else if(i%5==0 && s!="Buzz"){j=false;}
				else if(i%3==0 && s!="Fizz"){j=false;}
				if(i%15!=0 && i%5!=0 && i%3!=0 && ){j=false;}				
				if(j){b=w; w=a[w];}
				if(!j){
				}*/
				if ( correct(i) != s ) {
					done.insert(i);
					a[b]=a[w]; done.insert(w); w=a[w]; count++;				
				} else {
					b=w; w=a[w];
				}
			}
		}
		bool d=true;
		for(int i=1;i<=m;i++){
			if(done.find(i)==done.end()){
				if(d){cout<<i; d=false;}
				else{cout<<" "<<i;}
			}
		}
		cout<<endl;




	}
	return 0;
}



Measured memory_bytes: 3304
N = int(input())
D = []
for i in range(N):
    x, l = map(int, input().split())
    D.append([x-l, x+l])
from operator import itemgetter
D = sorted(D, key = itemgetter(1))
u = -10**10 #最小値:x = 0, l = 10**10の時
cnt = 0
for a, b in D:
    if u <= a:
       cnt += 1
       u = b #つぎのロボットの範囲の下限に置きかえる
print(cnt)


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

char str[10005];

int main(void)
{
	
	int i, len, ci, cj;
	
	while (scanf("%s", str) != EOF){
		
		ci = 0;
		cj = 0;
		len = strlen(str);
		
		for (i = 0; i < len - 2; i++){
			
			if (str[i] == 'J' && str[i + 1] == 'O' && str[i + 2] == 'I'){
				cj++;
			}
			else if (str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I'){
				ci++;
			}
		}
		printf("%d\n%d\n", cj, ci);
	}
	return (0);
}
				

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

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  p.at(n - 1) /= 2;
  int res = 0;
  for (int i = 0; i < n; i++) {
    res += p.at(i);
  }
  cout << res << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    long long int a, sum, min, max;
    int n;
    scanf("%d",&n);
    min = 1000000;
    max = -1000000;
    sum = 0;
    while(n--){
        scanf("%lld",&a);
        if(a<min) min = a;
        if(a>max) max = a;
        sum+=a;
    }
    printf("%lld %lld %lld\n", min, max, sum);
return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long ,long long>pll;

ll gcd(ll a, ll b) {return (!b ? a : gcd(b, a % b));}
ll lcm(ll a, ll b) {return ((a*b)/gcd(a,b));}
bool cmp(int a,int b){return a>b;}

const ll mod = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;
const ld pi = 3.141592653589793;

long long modpow(long long n, long long k, long long mod)
{
if (k == 0) return 1;
long long r = modpow(n * n % mod, k >> 1, mod);
if (k & 1) r = r * n % mod;
return r;
}

void solve(){
    int n;
    string s;
    cin >> n >> s;
    int ans = 0;
    for(char i = '0';i<='9';i++){
        for(char j = '0';j<='9';j++){
            for(int k = '0';k<='9';k++){
                bool oki = 0,okj = 0,okk = 0;
                for(int z = 0;z<n;z++){
                    if(s[z]==i&&oki==0) {oki = 1;continue;}
                    if(s[z]==j&&oki==1&&okj==0) {okj = 1;continue;}
                    if(s[z]==k&&oki==1&&okj==1&&okk==0){okk = 1;continue;}
                }
                if(oki&&okj&&okk) ans++;
            }
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

Measured memory_bytes: 3728
X=int(input())

arr=[]
for i in range(0,640):
    arr.append(i**5)
    arr.append(-i**5)

arr2=[]
arr3=[]
import itertools
l=itertools.combinations_with_replacement(arr,2)
for i in l:
    arr2.append(i[0]-i[1])
    arr3.append([i[0],i[1]])
import math

ans=arr3[arr2.index(X)]
print(int(math.pow(abs(ans[0]), 1/5))*(1 if ans[0]>=0 else -1), int(math.pow(abs(ans[1]), 1/5))*(1 if ans[1]>=0 else -1))

Measured memory_bytes: 119352
#include <bits/stdc++.h>
using namespace std;
int main(){
        long long int n; cin >> n;
        string ans = "";
        while (n > 0){
            long long int mod = n % 26;
            if (mod == 0) mod = 26;
            ans += 'a' + mod - 1;
            n = (n - mod) / 26;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3600
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAX = 2160;
const int MAXN = 100000;
int prm[MAX + 5], pcnt = 0;
bool is_prm[MAX + 5];
void init() {
	for(int i=2;i<=MAX;i++) {
		if( !is_prm[i] )
			prm[++pcnt] = i;
		for(int j=1;i*prm[j]<=MAX;j++) {
			is_prm[i*prm[j]] = true;
			if( i % prm[j] == 0 ) break;
		}
	}
}
ll s[MAXN + 5], a[MAXN + 5], b[MAXN + 5];
ll IsSqr(ll x) {
	ll le = 1, ri = 100000;
	while( le < ri ) {
		ll mid = (le + ri) >> 1;
		if( mid * mid >= x ) ri = mid;
		else le = mid + 1;
	}
	return (ri * ri == x) ? ri : 0;
}
int siz[2*MAXN + 5];
map<ll, int>mp;
int main() {
	init(); int N;
	scanf("%d", &N);
	int ans = 0, flag = false;
	for(int i=1;i<=N;i++) {
		a[i] = b[i] = 1;
		scanf("%lld", &s[i]);
		for(int j=1;j<=pcnt;j++) {
			int cnt = 0;
			while( s[i] % prm[j] == 0 ) {
				cnt++;
				s[i] /= prm[j];
			}
			cnt %= 3;
			if( cnt == 1 ) {
				a[i] *= prm[j];
				b[i] *= prm[j] * prm[j];
			}
			else if( cnt == 2 ) {
				a[i] *= prm[j] * prm[j];
				b[i] *= prm[j];
			}
		}
		if( IsSqr(s[i]) ) {
			a[i] *= s[i];
			b[i] *= IsSqr(s[i]);
		}
		else {
			a[i] *= s[i];
			b[i] *= s[i] * s[i];
		}
		if( !flag && a[i] == 1 && b[i] == 1 )
			flag = true;
	}
	for(int i=1;i<=N;i++) {
		if( a[i] == 1 && b[i] == 1 ) continue;
		if( mp.count(a[i]) )
			siz[mp[a[i]]]++;
		else {
			mp[a[i]] = i;
			mp[b[i]] = i+N;
			siz[i]++;
		}
	}
	for(int i=1;i<=N;i++) {
		if( mp[a[i]] == i )
			ans += max(siz[i], siz[i+N]);
	}
	if( flag ) ans++;
	printf("%d\n", ans);
}

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

int main(){
  int n,m;
  cin>>n;
  vector <double> vec(n);
  rep(i,n){
    cin>>vec[i];
  }
    
  sort(vec.begin(), vec.end());   
  
  rep(i,n-1){
    vec[i+1]=(vec[i]+vec[i+1])/2;
  }
  
  cout<<vec[n-1];
}

Measured memory_bytes: 3832
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <ctime>
#include <algorithm>
#define N 5678
#define NN 401000
typedef long long ll;
template <typename T> inline void read(T &x) {
	x = 0; char c = getchar(); bool flag = false;
	while (!isdigit(c)) { if (c == '-')	flag = true; c = getchar(); }
	while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
	if (flag)	x = -x;
}
using namespace std;
const int inf = 987654321;
int n, s, t;
struct edge{
	int nxt, to, val;
	ll fare;
}e[NN];
int head[N], ecnt = 1, hcur[N];
inline void addedge(int from, int to, int val, ll fare) {
	e[++ecnt] = (edge){head[from], to, val, fare};
	head[from] = ecnt;
}
inline void Addedge(int u, int v, int w, ll f) {
	addedge(u, v, w, -f);
	addedge(v, u, 0, f);
}

int que[NN * 30], front, rear;
ll dis[N];
bool vis[N];
inline bool spfa() {
	front = rear = 0;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= t; ++i)	hcur[i] = head[i];
	
	que[++rear] = s; dis[s] = 0;
	while (front < rear) {
		int cur = que[++front]; vis[cur] = false;
		for (int i = head[cur]; i; i = e[i].nxt) {
			int to = e[i].to;
			if (!e[i].val || dis[to] <= dis[cur] + e[i].fare)	continue;
			dis[to] = dis[cur] + e[i].fare;
			if (!vis[to])	vis[to] = true, que[++rear] = to;
		}
	}
	return dis[t] <= 1e14;
}
int dfs(int cur, int limi) {
	if (cur == t || !limi)	return limi;
	int flow = 0;
	vis[cur] = true;
	for (int i = hcur[cur]; i; i = e[i].nxt) {
		int to = e[i].to; hcur[cur] = i;
		if (vis[to] || dis[to] != dis[cur] + e[i].fare)	 continue;
		int tmp = dfs(to, min(e[i].val, limi));
		if (!tmp)	continue;
		flow += tmp; limi -= tmp;
		e[i].val -= tmp; e[i ^ 1].val += tmp;
		if (!limi)	break;
	}
	vis[cur] = false;
	return flow;
}

int dx[4] = {1, -1, 1, -1};
int dy[4] = {-1, 1, 1, -1};
int main() {
	read(n);
	s = n + n + 5, t = s + 1;
	for (int i = 1; i <= n; ++i) {
		int x, y, ct; read(x), read(y), read(ct);
		for (int tp = 0; tp < 4; ++tp) {
			int xx = x * dx[tp], yy = y * dy[tp];
			Addedge(i, n + n + tp + 1, ct, xx + yy);
		}
		Addedge(s, i, ct, 0);
	}
	for (int i = 1; i <= n; ++i) {
		int x, y, ct; read(x), read(y), read(ct);
		for (int tp = 0; tp < 4; ++tp) {
			int xx = x * dx[tp] * (-1), yy = y * dy[tp] * (-1);
			Addedge(n + n + tp + 1, n + i, ct, xx + yy);
		}
		Addedge(n + i, t, ct, 0);
	}
	int mxflow = 0;
	ll res = 0;
	while (spfa()) {
		int tmp = dfs(s, inf);
		mxflow += tmp;
		res += dis[t] * tmp;
	}
	printf("%lld\n", -res);
	return 0;
}

/*
2
0 0 1
3 2 1
2 2 1
5 0 1
//8
*/

Measured memory_bytes: 3788
/*B - K-th Common Divisor*/
#include <iostream>

using namespace std;

int main(){

	int A, B, K;
	int menor, div, i, tot = 0;

	cin>>A>>B>>K;

	if(A<B)
		menor = A;
	else
		menor = B;

	div = menor;

	for (i = menor; i > 0 ; i--)
	{
		if(A%i == 0 and B%i == 0)
			tot++;

		if(tot == K)
			break;
	}

	cout<<i<<'\n';

	return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

data class Point(val x: Int, val y: Int) {
    fun distanceTo(p: Point) = Math.abs(p.x - this.x) + Math.abs(p.y - this.y)
}

fun solve(out: PrintWriter) {
    val (n, m) = readIntegerList()
    val manArray = Array(n) {
        val (a, b) = readIntegerList()
        Point(a, b)
    }
    val cArray = Array(m) {
        val (c, d) = readIntegerList()
        Point(c, d)
    }

    for (man in manArray) {
        var ans = 1
        var minDistance = man.distanceTo(cArray[0])
        for ((i, c) in cArray.withIndex()) {
            val tmp = man.distanceTo(c)
            if (tmp < minDistance) {
                minDistance = tmp
                ans = i + 1
            }
        }
        out.println(ans)
    }
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 37704
def main():

	number = int(input())
	count = 0
	for i in range(number):
		tmp = int(input())
		if isPrime(tmp):
			count +=1

	print(count)

def isPrime(number):
	import math
	if number == 2:
		return True
	if number%2==0:
		return False
	for i in range(3,int(math.sqrt(number))+1,2):
		if number%i==0:
			return False
	return True


if __name__ == '__main__':
	main()


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int main(){
    int X, N;
    cin >> X >> N;
    vector<int> p(N);
    for (int i = 0; i < N; i++) cin >> p.at(i);
    int ans = 101, min_dist = 101;
    for (int i = -1; i <= 101; i++) {
        bool flag = false;
        for (int j = 0; j < N; j++) {
            if (i == p.at(j)) {
                flag = true;
                break;
            }
        }
        if (flag) continue;
        int dist = abs(i - X);
        if (min_dist == dist) ans = min(ans, i);
        else if (dist < min_dist) {
            min_dist = dist;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}


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

bool sosu(int s){
    for(int i=2;i*i<=s;i++){
        if(s%i==0){
            return false;
        }
        
    }
    return true;
}

int main(){
    int n;
    int at=0;
    cin>>n;
    for(int i=0;i<n;i++){
        int s;
        cin>>s;
        if(sosu(s)==true){
            at++;
        }
        
    }
    cout<<at<<endl;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=200005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int N,A[MAXN];
main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N; 
	int org = 0;
	FOR(i,1,N){
		cin>>A[i];
		org = org ^ A[i];
	}
	FOR(i,1,N){
		cout << (org ^ A[i]) << " ";
	}
}


Measured memory_bytes: 4384
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main ()
{
  int n;
  string a, s;
  vector<string> str;
  cin >> n;
  for(int i = 0; i < n; ++i){
    cin >> a;
    str.emplace_back(a);
  }
  for(int i = 'a'; i <= 'z'; ++i){
    int cmin = 1000;
    for(int j = 0; j < n; ++j){
      int sum = 0;
      for(int k = 0; k < str[j].size(); ++k){
        if(str[j][k] == i){
          sum = sum + 1;
        }
      }
      if(sum <= cmin){
        cmin = sum;
      }
    }
    for(int b = 0; b < cmin; ++b){
      s += i;
    }
  }
cout << s << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
//#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template <class T> inline T gcd(T a, T b) {if(a==0) return b; return gcd(b%a,a);}
template <class T> inline T lcm(T a, T b) {return a * b / gcd(a,b);}
template <class T> inline T sum(vector<T> &vec) {T res=0; for (int i = 0; i < vec.size(); i++) res += vec[i]; return res;}
template <class T> inline T mpow(T a, T b) {if(b==0)return 1; T c = mpow(a,b/2);if(b%2==1)return c*c*a; return c*c;}
const int INF = 1 << 30;
const long long INFLL = 1LL << 60;
typedef pair<int, int> P;

#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define FOR(i,n) for (int (i)=0;(i)<(n);(i)++)
#define REPB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define FORB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define SORT(A) sort((A).begin(),(A).end())

int main() {
    /*
    int K, X;
    cin >> K >> X;
    if (500 * K >= X) {
        cout << "Yes\n";
    } else {
        cout <<  "No\n";
    }
    */
   int N; cin >> N;
   string S; cin >> S;
   int res = 0;
   for (int i = 0; i < N; i++) {
       int j = i;
       if (j+2 < N && S[j] == 'A' && S[j+1] == 'B' &&
       S[j+2] == 'C') {
           res++;
       }

   }
   cout << res << endl;
}


Measured memory_bytes: 256
h, w = map(int,input().split())
ans= [list(input()) for i in range(h)]

for i in range(h):
    for j in range(w):
        if ans[i][j] !="#": #その升が爆弾じゃなかったら
            count = 0
            for p in range(max(0,i-1), min(i+2, h)):
                for q in range(max(0,j-1), min(j+2, w)):
                    if ans[p][q] == "#":
                        count += 1
            ans[i][j] = str(count)

for l in ans:
    for c in l:
        print(c, end="")
    print()

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define llINF (long long) 9223372036854775807
#define loINF (long) 2147483647
#define shINF (short) 32767
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define TO_INT(vec,s) REP(i,s.length()){vec.push_back(s[i] - ‘0’);}
#define ENUM_v(vec) for (auto e : vec)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
using namespace std;
typedef vector<long> VI;
typedef vector<VI> VVI;

int main(void){
	long N;
	cin >> N;
	VI a(N,0),b(N,0),a_t(N,0),b_t(N,0);
	REP(i,N) cin >> a[i];
	REP(i,N) cin >> b[i];

	long T = 1;
	long long ans = 0;

	REP(k,30){
		// [T 2T) [3T 4T)
		REP(i,N) {
			a_t[i] = a[i] % (2*T);
			b_t[i] = b[i] % (2*T);
		}

		SORT(b_t);
		long bit = 0;
		REP(j,N){
			//dump(FINDU(b_t,T*3-a_t[j]-1));
			//dump(FINDU(b_t,T-a_t[j]-1));
			bit  += ((FINDL(b_t,T*4-a_t[j]) + FINDL(b_t,T*2-a_t[j]) - FINDU(b_t,T*3-a_t[j]-1) - FINDU(b_t,T-a_t[j]-1)) % 2);
		}
		//dump(k);
		//dump(bit);

		ans += ((1 << k)*(bit%2));
		T <<= 1;
	}

	cout << ans << endl;
}

Measured memory_bytes: 6528
from itertools import permutations
N = int(input())
P = list(input().split())
Q = list(input().split())


p = int("".join(P))
q = int("".join(Q))


R = []
for i in range(N):
    R.append(str(i+1))

r = int("".join(R))

count = 1
for i in permutations(R):
    j = int("".join(i))
    if j == p:
        a = count
    if j == q:
        b = count
    count += 1

print(abs(b-a))


Measured memory_bytes: 40944
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		int N=sc.nextInt();
		int[] num=new int[N+1];
		for(int i=0; i<N-1; i++) {
			num[i]=sc.nextInt();
		}
		int ans=sc.nextInt();
		long[][] dp=new long[N+1][21];
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=20; j++) {
				dp[i][j]=0;
			}
		}
		dp[0][0]=1;
		dp[1][num[0]]=1;
		for(int i=1; i<N-1; i++) {
			for(int j=0; j<=20; j++) {
				if(dp[i][j]>0) {		//少なくとも1つは答えがあるとき
					if(j-num[i]>=0) {
						dp[i+1][j-num[i]]+=dp[i][j];	//引き算をするとき
					}
					if(j+num[i]<=20) {
						dp[i+1][j+num[i]]+=dp[i][j];	//引き算をするとき
					}
				}
			}
		}
		pl(dp[N-1][ans]);
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new UncheckedIOException(e);
			}
		}
	}
}


Measured memory_bytes: 24236
#include <iostream>

using namespace std;

#define INF 200000000

int main(){
  int H, N;
  cin >> H >> N;
  int A[N], B[N];
  for(int i=0; i<N; i++)
    cin >> A[i] >> B[i];

  int dp[H+1];
  //dp配列をINFで初期化
  fill(dp, dp+H+1, INF);
  dp[0] = 0;
  
  //体力をi減らすのにかかる魔力の最小値を考える
  for(int i=1; i<=H; i++){
    //cout << "N = " << i << endl;
    for(int j=0; j<N; j++){
      if(i<=A[j])
	dp[i] = min(dp[i], B[j]);
      else
	dp[i] = min(B[j] + dp[i-A[j]], dp[i]);
    }
    //cout << dp[i] << endl << endl;
  }

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


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, m, x, y int
	fmt.Scan(&n, &m, &x, &y)
	mx := make([]int, n)
	my := make([]int, m)
	for i := range mx {
		fmt.Scan(&mx[i])
	}
	for i := range my {
		fmt.Scan(&my[i])
	}
	sort.Ints(mx)
	sort.Ints(my)
	for i := x + 1; i <= y; i++ {
		if mx[len(mx)-1] < i && i <= my[0] {
			fmt.Println("No War")
			return
		}
	}
	fmt.Println("War")
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;
#define long int64_t

struct Solver {
	void solve() {
		long S;
		cin >> S;

		const long n = 1e9;
		long x2 = n;
		long y2 = 1;
		long x3 = (n - S%n) % n;
		long y3 = (S + x3) / n;
		cout << "0 0 " << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << endl;
	}
};

int main() {
	ios::sync_with_stdio( false );
	cout << fixed << setprecision( 10 );
	Solver().solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

map<pair<ll,ll>,char> memo;

char solve(ll X, ll Y){
  if(X>Y) swap(X,Y);
  if(memo.count(make_pair(X,Y)) > 0) return memo[make_pair(X,Y)];
  bool flg = false;
  if(X>=2){
    ll i=1;
    while(2*i<=X){
      if(solve(X-2*i,Y+i) == 'B'){
        flg = true;
        break;
      }
      i++;
    }
  }
  if(Y>=2){
    ll i=1;
    while(2*i<=Y){
      if(solve(Y-2*i,X+i) == 'B'){
        flg = true;
        break;
      }
      i++;
    }
  }
  if(flg){
    return memo[make_pair(X,Y)] = 'A';
  }
  return memo[make_pair(X,Y)] = 'B';
}


int main(){

  ll X, Y;
  cin >> X >> Y;

  if(X>Y) swap(X,Y);
  if(X==Y || X+1==Y){
    cout << "Brown" << endl;
  }else{
    cout << "Alice" << endl;
  }

  /*
  memo[make_pair(0,0)] = 'B';
  memo[make_pair(0,1)] = 'B';
  memo[make_pair(1,1)] = 'B';

  rep(X,100){
    REP(Y,X,10){
      cout << X << " " << Y << " " << solve(X, Y) << endl;
    }
  }
  */
  return 0;
}



Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define size(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

void dout() { cerr << '\n'; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << " " << H;
    dout(T...);
}

#ifdef LOCAL
    #define dbg(...) cerr << #__VA_ARGS__, dout(__VA_ARGS__)
#else
    #define dbg(...) ;
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int MOD = 1e9 + 7;

int binpow(int x, int y) {
    int res = 1;
    while (y > 0) {
        if (y & 1) {
            res = (ll)res * x % MOD;
        }
        x = (ll)x * x % MOD;
        y /= 2;
    }
    return res;
}

int c(int n, int k) {
    if (k > n) {
        return 0;
    }
    int res = 1;
    for (int i = n - k + 1; i <= n; i++) {
        res = (ll)res * i % MOD;
    }
    for (int i = 1; i <= k; i++) {
        res = (ll)res * binpow(i, MOD - 2) % MOD;
    }
    return res;
}

void sub(int & x, int y) {
    x -= y;
    if (x < 0) {
        x += MOD;
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif

    int n, a, b;
    cin >> n >> a >> b;
    int ans = binpow(2, n);
    sub(ans, 1);
    sub(ans, c(n, a));
    sub(ans, c(n, b));
    cout << ans;
}


Measured memory_bytes: 256
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize,
        mut a: [u64; n],
    }

    let mut ans: u64 = 0;
    loop {
        let mut min = (1000000001 as u64, 0 as usize);
        for i in 0..a.len() {
            min = if min.0 > a[i] && a[i] != 0 {
                (a[i], i)
            } else {
                min
            };
        }

        let mut count_0 = 0;
        for i in 0..a.len() {
            a[i] = if i == min.1 { a[i] } else { a[i] % min.0 };
            //println!("a[{}]={}", i, a[i]);
            count_0 += if a[i] == 0 {
                0
            } else {
                ans = a[i];
                1
            };
        }
        if count_0 == 1 {
            break;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 3720
#include <iostream>

using namespace std;

int main()
{
	long a, b, c, k;
	cin >> a >> b >> c >> k;
	while (a >= b)
	{
		k--;
		b *= 2;
	}
	while (b >= c)
	{
		k--;
		c *= 2;
	}
	cout << (k < 0 ? "No" : "Yes") << endl;
	return 0;
}

Measured memory_bytes: 3140
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    string s;
    cin>>s;
    if(s[2]==s[3] and s[4]==s[5])
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
}

Measured memory_bytes: 256
N, K = map(int, input().split())
for i in range(N):
    j = (N+(N+1)//2-i-1)%N
    k = N+(N+2*i)%N+(2*i>=N)*(N+1)%2
    if 2*K-1>N:
        print(-1)
        break
    print(j+K, k+K, 2*N+i+K)


Measured memory_bytes: 49880
import java.util.*;

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

	public Main(){
		new AOJ1172().doIt();
	}
	
	class AOJ1172{
		int N = 123456*2+5;
		void doIt(){
			boolean[] prime = new boolean[N];
			Arrays.fill(prime, true);prime[0] = false;prime[1] = false;
			for(int i=2;i<N;i++)if(prime[i]){
				for(int s=i+i;s<N;s+=i)prime[s] = false;
			}
			while(in.hasNext()){
				int input = in.nextInt();
				if(input==0)break;
				int cnt = 0;
				for(int i=input+1;i<=input*2;i++)if(prime[i])cnt++;
				System.out.println(cnt);
			}
		}
	}
	
}

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

int tab[600][600];
struct node
{
    int a,b,c,d;
    node(){};
    node(int _a,int _b,int _c,int _d)
    {
        a=_a;b=_b;c=_c;d=_d;
    };
};
int main() {
    memset(tab,0,sizeof(tab));
    int h,w;cin>>h>>w;
    vector <node> ans;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            cin>>tab[i][j];
        }
    }
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<w;j++)
        {
            if(tab[i][j]%2==1)
            {
                tab[i][j]--;
                 tab[i][j+1]++;
                 ans.push_back(node(i,j,i,j+1));
            }
        }
        if(tab[i][w]%2==1&&i!=h)
        {
            tab[i][w]--;
            tab[i+1][w]++;
            ans.push_back(node(i,w,i+1,w));
        }
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        printf("%d %d %d %d\n",ans[i].a,ans[i].b,ans[i].c,ans[i].d);
    }
    return 0;
}


Measured memory_bytes: 5616
#include<vector>
#include <algorithm>
#include<iostream>
int main(void) {
	std::ios::sync_with_stdio(false);
	long long n;
	std::cin >> n;
	std::vector<long long>ValueOnTime(n, 0);
	for (int i = 0; i < ValueOnTime.size(); ++i) {
		std::cin >> ValueOnTime[i];
	}
	int MaxSub = -1e9, Min = ValueOnTime[0];
	for (int i = 1; i < ValueOnTime.size(); ++i) {
		if (MaxSub < ValueOnTime[i] - Min) {
			MaxSub = ValueOnTime[i] - Min;
		}
		if (Min > ValueOnTime[i]) {
			Min = ValueOnTime[i];
		}
	}
	std::cout << MaxSub << std::endl;
	//	system("pause");
	return 0;
}

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

int d[40320];
int fac[8];
int u[8];

int cantor()
{
    int re = 0;
    for(int i = 0; i < 8; i++){
        int inv = 0;
        for(int j = i; ++j < 8; ){
            if(u[i]>u[j]) inv++;
        }
        re += fac[7-i]*inv;
    }
    return re;
}

void invCantor(int x)
{
    bool vis[8] = {};
    for(int i = 0; i < 8; i++){
        int w = x/fac[7-i];
        x %= fac[7-i];
        int j = 0;
        for( ; j < 8; j++){
            if(!vis[j]){
                if(!w) break;
                w--;
            }
        }
        u[i] = j; vis[j] = true;
    }
}

int cur;
queue<int> q;

inline void updata(int p0,int p1)
{
    swap(u[p0],u[p1]);
    int s = cantor();
    if(!d[s]){
        d[s] = d[cur]+1;
        q.push(s);
    }
    swap(u[p0],u[p1]);
}

void bfs()
{
    d[0] = 1;
    q.push(0);
    while(q.size()){
        invCantor(cur = q.front()); q.pop();
        int p;
        for(int i = 0; i < 8; i++)
            if(!u[i]){ p = i; break; }
        int r = p%4;
        if(r) {
            updata(p-1,p);
        }
        if(r<3){
            updata(p+1,p);
        }
        updata(p,p+(p>3?-4:4));
    }
}

void preDeal()
{
    fac[0] = 1;
    for(int i = 1; i < 8; i++){
        fac[i] = fac[i-1]*i;
    }
    bfs();
}

int read()
{
    if(scanf("%d",u)<0) return -1;
    for(int i = 1; i < 8; i++) scanf("%d",u+i);
    return cantor();
}

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    preDeal();
    int s;
    while( ~(s = read()) ){
        printf("%d\n",d[s]-1);
    }
    return 0;
}


Measured memory_bytes: 3324
n, k = map(int, input().split())
p = list(map(int, input().split()))

p_sum = [0] * (n + 1)

for i in range(n):
    p_sum[i + 1] = p_sum[i] + p[i]

ans = 0
for i in range(n - k + 1):
    ans = max(ans, p_sum[i + k] - p_sum[i])

ans = (ans + k) / 2
print(ans)


Measured memory_bytes: 25060
N = int(input())
H = list(map(int,input().split()))
m = 0
c = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    c+=1
  else:
    m = max(m,c)
    c = 0
m = max(m,c)
print(m)

Measured memory_bytes: 20360
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n;
int a[101];
long long dp[101][21];

int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    memset(dp,0,sizeof(dp));
    dp[0][a[0]]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<=20;j++){
            if(j+a[i]<=20) dp[i][j] += dp[i-1][j+a[i]];
            if(j-a[i]>=0) dp[i][j] += dp[i-1][j-a[i]];
        }
    }
    cout << dp[n-2][a[n-1]] << endl;
    return 0;
}

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

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

    int a[n];
    int first_poji = -1;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] == 1){
            first_poji = i;
        }
    }

    int cou = 0;
    int now = first_poji + 1;
    int m = 0;
    if(now == 1){
        cou = 0;
    }else if(now == k){
        cou = 1;
    }else{
        while(1){
            now -= k;
            cou++;
            if(now == 0){
                break;
            }else if(now < 0){
                m = 0 - now;
                break;
            }else{
                now++;
            }
        }
    }
    
    now = first_poji + 1 + m;
    if(now < n){
        while(1){
            now += k - 1;
            cou++;
            if(now >= n){
                break;
            }
        }
    }
    
    cout << cou << endl;
}

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();
        int x = sc.nextInt();

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

        Arrays.sort(A);

        int ret = 0;
        for (int i = 0; i < N; i++) {
            if (x - A[i] >= 0 && i < N - 1) {
                x -= A[i];
                ret++;
            } else if (i == N - 1 && x == A[N - 1]) {
                ret++;
            } else {
                break;
            }
        }

        System.out.println(ret);
    }
}

Measured memory_bytes: 22612
# -*- coding: utf-8 -*-
import heapq

N, M = map(int, input().split())
Wlist = []
for i in range(N):
    A, B = map(int, input().split())
    Wlist.append([A,B])
Wlist.sort(key=lambda x:x[0])

h = []
Ans = 0
Index = 0
for day in range(1,M+1):
    while Index < N:
        if Wlist[Index][0] <= day:
            heapq.heappush(h, -Wlist[Index][1])
            Index += 1
        else:
            break
    if len(h):
        Ans += -heapq.heappop(h)

print(Ans)


Measured memory_bytes: 24172