akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

string toBinary(long long x, int n)
{
    string s;
    while (x != 0)
    {
        int r = abs(x % n);
        s += to_string(r);
        x -= r;
        x /= n;
    }
    reverse(s.begin(), s.end());

    return s;
}

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

    vector<int> l(N);
    bool finishA = false, finishB = false, finishC = false;
    long long ans = 1e18;

    for (int i = 0; i < N; i++)
    {
        cin >> l[i];
        if (l[i] == A)
        {
            finishA = true;
        }
        if (l[i] == B)
        {
            finishA = true;
        }
        if (l[i] == C)
        {
            finishA = true;
        }
    }
    if (finishA && finishB && finishC)
    {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < pow(4, N); i++)
    {
        string str = toBinary(i, 4);
        while (str.size() < N)
        {
            str = "0" + str;
        }

        int l_tmp1 = 0;
        int l_tmp2 = 0;
        int l_tmp3 = 0;

        long long ans1 = 0;
        long long ans2 = 0;
        long long ans3 = 0;
        for (int j = 0; j < str.size(); j++)
        {
            if (str[j] == '1')
            {
                if (l_tmp1 != 0)
                {
                    ans1 += 10;
                }
                l_tmp1 += l[j];
            }
            else if (str[j] == '2')
            {
                if (l_tmp2 != 0)
                {
                    ans2 += 10;
                }
                l_tmp2 += l[j];
            }
            else if (str[j] == '3')
            {
                if (l_tmp3 != 0)
                {
                    ans3 += 10;
                }
                l_tmp3 += l[j];
            }
        }
        if (l_tmp1 == 0 || l_tmp2 == 0 || l_tmp3 == 0)
        {
            continue;
        }

        long long ans_tmp = abs(A - l_tmp1) + abs(B - l_tmp2) + abs(C - l_tmp3) + ans1 + ans2 + ans3;
        ans = min(ans, ans_tmp);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
from collections import deque

N, X, Y = map(int, input().split())

to = [[] * N for i in range(N)]

for i in range(N-1):
    to[i].append(i+1)
    to[i+1].append(i)

to[X-1].append(Y-1)
to[Y-1].append(X-1)

ans = [0] * N

for i in range(N):
    dis = [0] * N
    dis[i] = 0
    visited = [False] * N
    q = deque([])
    q.append(i)
    visited[i] = True

    while len(q) != 0:
        tmp_v = q.popleft()
        for j in to[tmp_v]:
            if not visited[j]:
                dis[j] = dis[tmp_v] + 1
                visited[j] = True
                q.append(j)

    for j in range(N):
        ans[dis[j]] += 1

for i in range(1,N):
    print(ans[i]//2)


Measured memory_bytes: 49628
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(false),cin. tie(0);
using namespace std;
typedef long long ll;
ll a,b,k,n,sum;
const ll maxn=105;
ll num[maxn];
int main()
{
while(cin>>n)
{
  sum=0;
  rep1(i,n)
  {
    cin>>num[i];
    sum+=num[i];
  }
  ll ans=1000000005;
  ll now=0;
  rep1(i,n)
  {
    now+=num[i];
    ans=min(ans,abs(sum-now-now));
  }
  cout<<ans<<"\n";
}
}

Measured memory_bytes: 256
#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 ll long long
#define __   ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define mod 1000000007

ll Set(ll N,ll pos){ return N=N | (1<<pos); }
ll reset(ll N,ll pos){ return N= N & ~(1<<pos); }
bool check(ll N,ll pos){ return (bool)(N & (1<<pos)); }


ll ar[]={0,0,1,-1};
ll br[]={1,-1,0,0};

string s;
ll n,m;
ll arr[500000];
ll brr[500000];

int main()
{__
        ll i,j;
        cin>>n;
        ll ans=0;

        if(n%2==1){
            cout<<0<<endl;
            return 0;
        }
        ll temp=10;

        while(n/temp!=0){
            ans+=n/temp;
            temp*=5;
        }
        cout<<ans<<endl;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  const int MOD=1e9+7;
  int N,M,dp[100000+2]={0};
  cin >> N >> M;
  for(int i=0,a;i<M;i++){
    cin >> a;
    dp[a]=-1;
  }
  dp[0]=1;
  for(int i=0;i<N;i++){
    if(dp[i]==-1)continue;
    if(i+1<=N && dp[i+1]>=0)
      dp[i+1]=(dp[i+1]+dp[i])%MOD;
    if(i+2<=N && dp[i+2]>=0)
      dp[i+2]=(dp[i+2]+dp[i])%MOD;
  }
  cout << dp[N] << endl;
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;



int main(){
  int n; cin >> n; ll ans = 0;
  for(int i=1; i<=n; i++){
      for(int j=1; j<=n/i; j++){
          ans+=(ll)j*i;
      }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3592
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
def g(x,y,s=0,t=1):
 q,r=x//y,x%y
 return g(y,r,t,s-q*t) if r else t
for _ in[0]*int(input()):
 s=input()
 a,b=f()
 h=g(26,a)
 print(''.join(z[h*(z.index(c)-b)%26]if c in z else c for c in s))


Measured memory_bytes: 5604
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) {
        try {
            // 標準入力
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader br = new BufferedReader(isr);
            String strArr[] = br.readLine().split(" ");
            int a = Integer.parseInt(strArr[0]);
            int b = Integer.parseInt(strArr[1]);
            int c = Integer.parseInt(strArr[2]);
            if (a + b >= c) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}


Measured memory_bytes: 21076
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int N;
    cin >> N;
    vector<int> data(N);
    int A=0;
    int B=0;
    for(int i=0;i<N;i++){
        cin >> data.at(i);
        if(data.at(i)%2==0){
            A++;
            if(data.at(i)%3==0||data.at(i)%5==0){
                B++;
            }
        }
    }
    if(A==B){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
}



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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int n;
	cin >> n;
	ll h[n];
	for(int i=0; i<n; i++) cin >> h[i];

	h[0]--;
	for(int i=1; i<n; i++){
		if(h[i-1]<h[i]) h[i]--;
	}
	for(int i=1; i<n; i++){
		if(h[i-1]>h[i]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 1024
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    G=[None]
    for i in range(N):
        A=int(input())
        G.append([tuple(map(int, input().split())) for _ in range(A)])
    ans=0
    for p in range(1<<N):
        pp=[0] + [1 if p&(1<<i) else 0 for i in range(N)]
        judge=True
        for v in range(1,N+1):
            if pp[v]:
                for to,h in G[v]:
                    if pp[to]!=h: judge=False
        if judge:
            ans = max(ans, popcount(p))
    print(ans)

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

if __name__ == '__main__':
    main()

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

int main(){
  int N;
  cin >> N;
  int A[2][N];
  for(int i=0;i<N;i++) cin >> A[0][i];
  for(int i=0;i<N;i++) cin >> A[1][i];
  /*
  for(int i=0;i<N;i++) cout << A[0][i] << " ";
  cout << endl;
  for(int i=0;i<N;i++) cout << A[1][i] << " ";
  */
  int i = 0;
  int sum;
  int max;
  for(int k=0;k<N;k++){
	sum = 0;
    i = 0;
	for(int l=0;l<N;l++){
      sum += A[i][l];
	  if(k==l){
	    i++;
		sum += A[i][l];
	  }		  
	}
	//cout << sum << endl;
	if(sum > max){
	  max = sum;
	}
  }
  cout << max << endl;
  return 0;
}


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


long long GetGCD (long long C, long long D) {
   while (1) {
      if (C == 0 || D == 0) break;
      if (D>C) D -= (D/C)*C;
      else C -= (C/D)*D;
   }
   return max(C,D);
}

int main(void) {
   long long A,B,C,D;
   cin>>A>>B>>C>>D;
   long long ans = B-A+1;

   ans -= B/C - (A-1)/C;
   ans -= B/D - (A-1)/D;

   long long GCD,LCM;
   GCD = GetGCD(C,D);
   LCM = C /GCD*D;

   ans += B/LCM - (A-1)/LCM;
   cout<<ans<<endl;

   return 0;
}

Measured memory_bytes: 256
n,x = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
if a[0]>x:
  ans += a[0]-x
  a[0]=x  
else:
  pass
j = 1
while j <= n-1:
  if a[j-1]+a[j]<=x:
    j += 1
  else:
    ans += a[j]-x+a[j-1]
    a[j]=x-a[j-1]
    j += 1
print(ans)

Measured memory_bytes: 14060
#include<stdio.h>

int main(void){
    int i,j,H,W;
    while(1){
        scanf("%d %d",&H,&W);
        if(H==0 && W==0){
            break;
        }
        for(i=0;i<H;i++){
            for(j=0;j<W;j++){
                printf("#");
            }
            printf("\n");
        }
        printf ("\n");
    }
    return 0;
}


Measured memory_bytes: 2100
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int c[4][4];
    
    for(int i = 1; i < 4; i++){
        for(int j = 1; j < 4; j++){
            cin >> c[j][i];
        }
    }
    
    int a[4];
    int b[4];
    
    a[1] = 0;
    for(int i = 1; i < 4; i++){
        b[i] = c[1][i] - a[1];
    }
    for(int i = 2; i < 4; i++){
        a[i] = c[i][1] - b[1];
    }
    
    bool ok = true;
    for(int i = 1; i < 4; i++){
        for(int j = 1; j < 4; j++){
            if(c[j][i] != a[j] + b[i])ok = false;
        }
    }
    
    if(ok == true){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
use std::io::{BufRead, BufWriter, Write};

fn main() {
    let stdin = std::io::stdin();
    let stdout = std::io::stdout();
    solve(&mut stdin.lock(), &mut BufWriter::new(stdout.lock()));
}

fn solve<R: BufRead, W: Write>(stdin: &mut R, stdout: &mut BufWriter<W>) {
    let n = stdin.gets().parse::<usize>().unwrap();
    let s = stdin.gets();
    let red = s.chars().filter(|&c| c == 'R').count();
    let ans = if red * 2 > n { "Yes" } else { "No" };
    writeln!(stdout, "{}", ans).unwrap();
}

trait Gets { fn gets(&mut self) -> String; }
impl<T: std::io::BufRead> Gets for T {
    fn gets(&mut self) -> String { self.lines().next().unwrap().unwrap() } }


Measured memory_bytes: 4352
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> p;
const int inf=(1<<30);
#define rep(i,a,n)	for(int i=a;i<n;i++)
#define rrep(i,a,n) for(int i=(a-1);i>=n;i--)

	
int main(){
	ll n;
	cin>>n;
	deque<ll> v;
	rep(i,0,n){
		ll x;
		cin>>x;
		if(i%2==1)v.push_front(x);
		else v.push_back(x);
	}
	if(n%2==0){
		rep(i,0,n)cout<<v[i]<<' ';
	}
	else{
		rrep(i,n,0)cout<<v[i]<<' ';
    }
}

Measured memory_bytes: 3840
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main()
{
	int N = 0;
	std::cin >> N;

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

	std::string ans = "No";

	if (N == 1){
		ans = "Yes";
		std::cout << ans << std::endl;
		return 0;
	}

	for (int i = N - 1; i > 0; i--)
	{
		if (H[i] < H[i - 1])
		{
			H[i - 1] = H[i - 1] - 1;
			ans = (H[i] < H[i - 1]) ? "No" : "Yes";
		}
		else{
			ans ="Yes";
		}

		if (ans == "No") break;
	}

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

	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#define lol(i,n) for(ll i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;

using namespace std;

int main(){
    ll a[3];
    lol(i,3)cin>>a[i];
    sort(a,a+3);
    cout<<a[0]*a[1]/2<<endl;
    return 0;
}


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


int main ()
{
  string S,T;
  cin >>S>>T;
  int ans=0;
  for(int i=0;i<S.size();i++)
  {
    if(S==T)
    {
      ans=1;
      break;
    }
    S=S.back()+S.substr(0,S.size()-1);
  }
  if(ans==1) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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

#define mod 1000000007
#define maxn 100005

typedef pair<int, int> P;

int main()
{
    //freopen("monotonic.in", "r", stdin);
    //freopen("monotonic.out", "w", stdout);
    int m;
    cin >> m;
    ll tot = 0;
    ll cnt = 0;
    for (int i = 0; i < m; i++)
    {
        ll d, c;
        scanf("%lld%lld", &d, &c);
        tot += d * c;
        cnt += c;
    }
    cout << (tot - 1) / 9 + cnt - 1 << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define ld long double

using namespace __gnu_pbds;
using namespace std;

template <class T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>;

void usaco(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(name.size())
    {
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

int32_t main()
{
    usaco();
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cout << "ACL";
}


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

int main() {
  int N, K;
  cin >> N >> K;
  int num = 1;

  for (int i = 0; i < N; i++){

    int tmpA = num * 2;
    int tmpB = num + K;

    if(tmpA<tmpB){
      num = tmpA;
    }else{
      num = tmpB;
    }

  }

  cout << num << endl;

}


Measured memory_bytes: 256
// arock - 2019-03-09

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

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);

    int N, M;
    std::cin >> N >> M;
    std::vector<std::pair<i64, int>> AB(N);
    for (auto& row : AB) {
        std::cin >> row.first >> row.second;
    }
    std::sort(begin(AB), end(AB));

    i64 ans = 0;
    for (auto ab : AB) {
        if (ab.second < M) {
            ans += ab.first * ab.second;
            M -= ab.second;
        } else {
            ans += M * ab.first;
            break;
        }
    }

    std::cout << ans << '\n';
}


Measured memory_bytes: 1792
#include<stdio.h>

#define Num 1000000

int main(void)
{
  int a[Num+1];
  int n,i,j,count=0;
  
  for(i=0;i<Num;i++)
    {
      a[i]=1;
    }

  //printf("1\n");
  /*for(i=2;i<=n/2;i++)*/
  for(i=2;i*i<=Num;i++)
    {	  
      //printf("2\n");
      for(j=2*i;j<=Num;j+=i)
	{
	  //printf("3\n");
	  if(j%i==0)a[j]=0;
	}
    }
  
  
  
  while(scanf("%d",&n)!=EOF)
    {
    

      for(i=2;i<=n;i++)
	{
	  //printf("4\n");
	  if(a[i]==1)
	    {count++;
	      //printf("5\n");
	      
	    }
	}
      printf("%d\n",count);
      count=0;
    }
  //printf("end\n");
  return 0;
}

Measured memory_bytes: 0
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			int k = sc.nextInt();
			int p = sc.nextInt();
			int a = k % p;
			out.println(a == 0 ? p : a);
		}
		out.flush();
	}
	
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) { return false; }
		}
		return true;
	}
	
	private byte readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}
	
	private boolean isPrintableChar(int c) {
		return '!' <= c && c <= '~';
	}
	
	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}
	
	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}
	
	public int nextInt() {
		if (!hasNext()) { throw new NoSuchElementException(); }
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) { throw new NumberFormatException(); }
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}

Measured memory_bytes: 24436
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    vector<int> cnt(n+1, 0);
    for(int i=0; i<m; ++i){
        int a, b;
        cin >> a >> b;
        ++ cnt[a];
        ++ cnt[b];
    }

    for(int i=1; i<=n; ++i){
        if(cnt[i] % 2 != 0){
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 640
n,y=map(int,input().split())
for i in range(y//10000+1):
    x=y-10000*i
    for j in range(x//5000+1):
        z=(x-5000*j)//1000
        if i+j+z==n:
            print(i,j,z)
            exit()
print(-1,-1,-1)

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

void calc(string& S) {
	map<char, char> to;
	char t = 'a';
	for (auto& c : S) to.count(c) ? c = to[c] : c = to[c] = t++;
}

int main()
{
	string S, T;
	cin >> S >> T;
	calc(S); calc(T);
	puts(S == T ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 776
// ------------------------------------
// Date:2018/ 4/ 2
// Problem:D- 2017-like Number d.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

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

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

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

int Q;
int primeNum[MAX_N];

struct Eratosthenes {
  vector< bool > prime;
  Eratosthenes(int _size) {
    init(_size);
  }

  void init(int n) {
    prime.resize(n + 1);
    REP(i, prime.size()) prime[i] = true;
    prime[0] = prime[1] = false;
    for(int i = 2; i < sqrt(n); i++) {
      if (prime[i]) {
        for (int j = 0; i * (j + 2) < n; j++) {
	  prime[i * (j + 2)] = false;
	}
      }
    }
  }
};


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

  Eratosthenes e(MAX_N + 1);
  int num = 0;
  primeNum[0] = 0;
  REP(i, MAX_N) {
    if (!(i & 1) && e.prime[i + 1] && e.prime[(i + 2) / 2]) num++;
    primeNum[i + 1] = num;
  }
  /*
  REP(i, 100) {
    cout << i << " ";
    OK(e.prime[i]);
  }
  */
  cin >> Q;
  int ans;
  REP(i, Q) {
    ans = 0;
    CIN(l, r);
    ans += primeNum[r] - primeNum[l - 1];
    cout << ans << endl;
  }

  return 0;
}



Measured memory_bytes: 1024
#include<stdio.h>
#include<math.h>
int main(){
    int n, d;
    scanf("%d%d", &n, &d);
    int sum=0, inspect=0;
    while(sum<n){
        sum+=(2*d)+1;
        inspect++;
    }
    printf("%d\n", inspect);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
 
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

int main() {
    char c;
    cin >> c;
    c++;
    cout << c;
    return 0;
}

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

int main()
{
  int y1,m1,d1,y2,m2,d2;
  int m[13]={0,31,28,31,30,31,30,31,31,30,31,30,31},i;
  int days1,days2,difference;
  for(i=1;i<12;i++)m[i]+=m[i-1];
  while(cin>>y1>>m1>>d1>>y2>>m2>>d2,~y1&~m1&~d1&~y2&~m2&~d2){
    y1--;y2--;
    days1=365*y1+m[m1-1]+d1+y1/4-y1/100+y1/400;
    days2=365*y2+m[m2-1]+d2+y2/4-y2/100+y2/400;
    y1++;y2++;
    if((y1%4==0 && y1%100!=0)||(y1%400==0))if((m1==2&&d1==29)||(m1>=3))days1++;
    if((y2%4==0 && y2%100!=0)||(y2%400==0))if((m2==2&&d2==29)||(m2>=3))days2++;
    cout<<days2-days1<<endl;
  }
}

Measured memory_bytes: 0
/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   main.cpp                                           :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: monoue <marvin@student.42.fr>              +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2020/04/22 12:30:15 by monoue            #+#    #+#             */
/*   Updated: 2020/04/30 08:16:32 by monoue           ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <bits/stdc++.h>

/* #include <boost/multi_array.hpp> */
/* #include <boost/optional.hpp> */
/* #include <boost/range/irange.hpp> */
/* #include <boost/range/algorithm.hpp> */
/* #include <boost/range/adaptors.hpp> */
/* #include <boost/multiprecision/cpp_int.hpp> */
/* #include <boost/algorithm/string/classification.hpp> // is_any_of */
/* #include <boost/algorithm/string/split.hpp> */
/* #include <boost/algorithm/string/join.hpp> */
/* #include <boost/algorithm/string/replace.hpp> */
/* #include <boost/math/tools/minima.hpp> */
/* namespace adaptor = boost::adaptors; */
/* using boost::math::tools::brent_find_minima; */
/* using boost::irange; */
/* using boost::algorithm::join; */
/* using boost::algorithm::split; */
/* using boost::algorithm::replace_all; */
/* using boost::multiprecision::cpp_int; */

#define MOD 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define rrep(i, n) for (int i = (n); i >= 0; --i)

using namespace std;
using ll = long long;
using P = pair<int, int>;
static const int	N = 1000;

// TOP
void	Main()
{
	int n;
	cin >> n;

	rep(i, n)
	{
		string	sa, sb;
		cin >> sa >> sb;
		sa = ' ' + sa;
		sb = ' ' + sb;
		int	la, lb;
		la = sa.size();
		lb = sb.size();

		vector<vector<int>>	V(la + 1, vector<int>(lb + 1));
		rep2(i, 1, la)
		{
			rep2(j, 1, lb)
			{
				if (sa.at(i) == sb.at(j))
					V.at(i).at(j) = V.at(i - 1).at(j - 1) + 1;
				else
					V.at(i).at(j) = max(V.at(i - 1).at(j), V.at(i).at(j - 1));
			}
		}
		cout << V.at(la - 1).at(lb - 1) << endl;
	}
}
// END

int		main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}



Measured memory_bytes: 6828
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            cnt = 0
            for di in range(-1, 2):
                for dj in range(-1, 2):
                    tmp_i = i+di
                    tmp_j = j+dj
                    if (0 <= tmp_i <= H-1) and (0 <= tmp_j <= W-1) and (S[tmp_i][tmp_j]=="#"):
                        cnt += 1
            S[i][j] = cnt

for s in S:
    for i in s:
        print(i, end="")
    print()

Measured memory_bytes: 74560
#include <stdio.h>

int main()
{
  int x, y;
  int i, j;
  int xgroup = 0;
  int ygroup = 0;
  int a[7] = {1,3,5,7,8,10,12};
  int b[4] = {4,6,9,11};
  scanf("%d %d", &x, &y);
  if(x == y)
  {
    printf("Yes");
  }
  else
  {
    for(i=0; i<7; i++)
    {
      if(x == a[i]) xgroup = 1;
      if(y == a[i]) ygroup = 1;
    }
    for(j=0; j<4; j++)
    {
      if(x == b[j]) xgroup = 2;
      if(y == b[j]) ygroup = 2;
    }
    if(xgroup == ygroup)
    {
      printf("Yes");
    }
    else
    {
      printf("No");
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <climits> 
#include <time.h>

int main()
{
    long A,B,K;
    std::cin >> K;
    std::cin >> A >> B;
    bool  flag=1;
    for(long i=A; i<=B; i++){
        if(i%K==0){
            flag=0;
        }
    }
    if(flag){
        std::cout << "NG" << std::endl;
    }else{
        std::cout << "OK" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 3624
s=input()
t=input()


result=''
dp=[[0]*len(t) for _ in range(len(s))]

for i in range(len(s)):
    for j in range(len(t)):
        if i==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i][j-1] if j>=1 else 0
        elif j==0:
            if s[i]==t[j]:
                dp[i][j]=1
            else:
                dp[i][j]=dp[i-1][j]
        else:
            if s[i]==t[j]:
                dp[i][j]=dp[i-1][j-1]+1
            else:
                dp[i][j]=max(dp[i-1][j],dp[i][j-1])

i=len(s)-1
j=len(t)-1

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[j]
        L-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        result+=t[j]
        L-=1
        i-=1
        j-=1


print(result[::-1])
    

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

int main() {
  for(int N, M; cin >> N >> M && (N|M);) {
    vector<pair<int,int> > v;
    for(int i = 0; i < N; ++i) {
      int D, P;
      cin >> D >> P;
      v.push_back(make_pair(P, D));
    }
    sort(v.begin(), v.end(), greater<pair<int,int> >());
    int res = 0;
    for(int i = 0; i < v.size(); ++i) {
      if(M < v[i].second) {
        res += (v[i].second - M) * v[i].first;
        M = 0;        
      } else {
        M -= v[i].second;
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1328
#include <bits/stdc++.h>
using namespace std;
int main(void){
   
  int r,D,x_i;
  cin >> r >> D >> x_i;
  
  for(int i=0;i<10;i++){
      x_i = r * x_i - D;
      cout << x_i <<endl;
  }
}

Measured memory_bytes: 3568
#include<iostream>
#include<deque>
#include<queue>
#include<math.h>
#include<string>
#include<string.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<iomanip>
#include<map>
#include<bitset>
#include<algorithm>
#include<unordered_map>
 
#include<unordered_map>
#include<algorithm>
#define inf 0x3f3f3f3f
#define sup_inf 2e18
#define pb push_back
 
#define ii pair<long long,long long>
#define f first
#define s second
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define iii pair<int, ii >
#define in freopen("entrada","r",stdin);
#define out freopen("myfile.txt", "w", stdout);
#define eps 1e-9
#define id pair<int ,double > 
#define di pair<double, int>
 
#define pi 3.14159265359
#define nl (no<<1)
#define nr ( (no<<1)|1)
#define mid l + ( (r-l)>>1)
 
using namespace std;
 
 
typedef long long ll;
typedef vector< int> vi;
 
const int MAX = 24;
const int maxn = 1 << 22;


int main (){
	int n ; cin >> n;
	for(int i = 1;i < 10 ;i++)
		for(int j = 1;j < 10 ;j++)
			if ( i * j == n)
				return cout << "Yes\n", 0;
		cout << "No\n";
	
}



Measured memory_bytes: 256
def main():
    n = int(input())
    d = []

    for i in range(0, n):
        d.append(int(input()))

    backet = {}
    for i in range(0, 101):
        backet[i] = 0

    for i in range(0, n):
        backet[d[i]] += 1

    count = 0
    for i in range(0, 101):
        if backet[i] > 0:
            count += 1

    print(count)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,n){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"
#define PI 3.141592653589793

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}


int main(){
  ll N,H; cin>>N>>H;
  ll a[N], b[N];
  REP(i,N){ cin>>a[i]>>b[i];}
  sort(a,a+N,greater<ll>());
  sort(b,b+N,greater<ll>());
  ll swing = a[0];
  ll ans = 0;
  REP(i,N){
    if(b[i]>swing){
      H -= b[i];
      ++ans;
      if(H<=0){break;}
    }
    else { break;}
  }
  while(H>0){
    H -= swing;
    ++ans;
  }
  cout << ans <<"\n";
}

Measured memory_bytes: 1792
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int main(){
  int n,m;
  while(cin>>n>>m,n){
    int a,b,ans=0;
    priority_queue< pair<int,int> > c;
    for(int i=0;i<n;i++){
      cin>>a>>b;
      c.push(make_pair(b,a));
    }
    while(!c.empty()){
      if(c.top().second>m){
        c.push(make_pair(c.top().first,c.top().second-m));
        c.pop();
        break;
      }
      else {
        m-=c.top().second;
        c.pop();
      }
    }
    while(!c.empty()){
      ans+=c.top().first*c.top().second;
      c.pop();
    }
    cout<<ans<<endl;
  }
  return 0;
}

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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 60;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A[3]; rep(i, 3) cin >> A[i];
    sort(A, A+3);
    int ans = 0;
    while(A[0] != A[2]){
        if(A[2]-A[0] >= 2) A[0]+=2;
        else{
            A[0]++;
            A[1]++;
        }
        sort(A, A+3);
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
  long int a,b;
  long int c;
  int r,tmp;
  scanf("%ld %ld",&a,&b);
  
  c = a * b;
  if (a < b) {
    tmp = a;
    a = b;
    b = tmp;
  }
  
  r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  printf("%ld\n", c / b);
  
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
using P = pair<int, int>;
typedef long long ll;
template <typename T>
struct BIT
{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1)
    {
        for (i++; i <= n; i += i & -i)
        {
            d[i] += x;
        }
    }
    T sum(int i)
    {
        T x = 0;
        for (i++; i; i -= i & -i)
        {
            x += d[i];
        }
        return x;
    }
    T sum(int l, int r)
    {
        return sum(r - 1) - sum(l - 1);
    }
};

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> pi(n + 1, -1);
    vector<vector<int>> ps(n);
    for (int i = 0; i < n; i++)
    {
        int l = pi[a[i]];
        if (l != -1)
        {
            ps[l].push_back(i);
        }
        pi[a[i]] = i;
    }
    vector<vector<P>> qs(n);
    for (int qi = 0; qi < q; qi++)
    {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        qs[l].emplace_back(r, qi);
    }
    vector<int> ans(q);
    BIT<int> d(n);
    for (int x = n - 1; x >= 0; --x)
    {
        for (int y : ps[x])
        {
            d.add(y, 1);
        }
        for (P query : qs[x])
        {
            int r = query.first, i = query.second;
            ans[i] = r - x + 1 - d.sum(r);
        }
    }

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

Measured memory_bytes: 59912
N,M=map(int,input().split())
dp=[-1]*N
dp[-1]=1
dp+=[1]
mod=10**9+7
for i in range(M):
  a=int(input())
  dp[a]=0
i=N-2
while i>=0:
  if dp[i]==-1:
    dp[i]=(dp[i+1]+dp[i+2])%mod
  i-=1
print(dp[0])


Measured memory_bytes: 44620
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	ans := 0
	for i := 0; i < n; i++ {
		if i == 0 {
			ans = k
		} else {
			ans = ans * (k - 1)
		}
	}
	fmt.Println(ans)
}


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

int main(){
  int N,i,cnt=1,hakai=0;
  bool B = false;
  cin >> N;
  vector<int> a(N);

  for(i=0;i<N;i++)
  cin >> a.at(i);

  for(i=0;i<N;i++){
    if(a.at(i)!=cnt){
      hakai++;
    }else if(a.at(i)==cnt){
      cnt++;
      B = true;
    }
  }
  if(B==false){
    hakai = -1;
  }
  cout << hakai << endl;
}

Measured memory_bytes: 1024
import itertools

S = input()
T = list(itertools.product(['+',''], repeat=len(S)-1))

ans = 0
for i in range(2**(len(S)-1)):
    calc_form = S[0]
    for j in range(len(S)-1):
        calc_form += T[i][j]+S[j+1]
    ans += eval(calc_form)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	string s;
	cin >> s;
	int zero = 0, one = 0;	
	for(int i = 0; i < s.size(); i++){
		if(s[i] == '0')zero += 1;
		else one += 1;
	}
	int ans = min(one,zero)*2;
	cout << ans << endl;
}

Measured memory_bytes: 512
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

s = rs()
A, B = s.split()
A = int(A)
B = int(B.replace('.',''))

print(A*B//100)



Measured memory_bytes: 62112
#include <iostream>
#include <string>
using namespace std;
long long Ans = 0; string S;
void Sum(int a, long long b,long long sum, int len) {
	if (a == len) {
		Ans += sum;
	}
	else {
		if (a == len - 1) {
			Sum(a + 1, -1, sum + b, len);
		}
		else {
			Sum(a + 1, S[a + 1] - '0', sum + b, len);
			Sum(a + 1, 10 * b + S[a + 1] - '0', sum, len);
		}
	}
}

int main() {
	cin >> S;
	Sum(0, S[0] - '0', 0, S.length());
	cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int  main(){
	int a,b,x[4]={};
	cin>> a>> b;
	
	x[0] = a+b;
	x[1] = a-b;
	x[2] = a*b;

	sort(x,x+3,greater<int>());
	cout << x[0]<<endl;

	return(0);
}

Measured memory_bytes: 256
#include<iostream>
#include<set>
#include <bitset>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include<string.h>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
#include <limits>
#include <numeric>
#include <type_traits>
#define int long long
#define ll long long
#define mod  1000000007
#define MOD  1000000007
#define inf 1e17
#define rep(i,j,n) for(int i=j;i<n;i++)
#define P pair<int,int>
#define ps push_back

#define all(x) x.begin(),x.end()
double pi = 3.141592653589793;
using namespace std;
//ここから始めよう
signed main(){
    int n;cin>>n;
    int a,b;cin>>a>>b;
    int k[3]={};
    rep(i,0,n){
        int p;cin>>p;
        if(p<=a)k[0]++;
        else if(p<=b)k[1]++;
        else k[2]++;
    }
    int ans=mod;
    rep(i,0,3){
        ans=min(ans,k[i]);
    }cout<<ans<<endl;return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int n;
int a[105][105];
int d[105];
void bfs(int x){
  d[x]=0;
  queue<P > q;
  int y=x;
  for(int i=1;i<=n;i++){
    if(a[y][i])q.push(P(i,d[y]+1));
  }
  while(!q.empty()){
    P p=q.front();q.pop();
    y=p.first;
    if(d[y]!=-1)continue;
    d[y]=p.second;
    for(int i=1;i<=n;i++){
      if(a[y][i])q.push(P(i,d[y]+1));
    }
  }
}
int main(){
  for(int i=0;i<105;i++){
    d[i]=-1;
  }
  cin >> n;
  for(int i=0;i<n;i++){
    int u,m;
    cin >> u >> m;
    for(int j=0;j<m;j++){
      int v;
      cin >> v;
      a[u][v]=1;
    }
  }
  bfs(1);
  for(int i=1;i<=n;i++){
    cout << i<< " " <<d[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 3156
#include<bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
const lint mod=1e9+7;


int main()
{
  string s, t;
  cin >> s;
  cin >> t;

  reverse(ALL(t));

  cout << ((s == t) ? "YES" : "NO") << "\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MAX = 1000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L

int main () {
	string s, t; cin >> s >> t;
	int ls = s.length(); int lt = t.length();
	int max = 0;
	for (int ii = 0; ii <= ls-lt; ii++) {
		int cnt = 0;
		for (int jj = 0; jj < lt; jj++) {
			if (s[ii+jj] == t[jj]) {
				cnt++;
			}
		}
		if (cnt > max) max = cnt;
	}
	cout << lt - max << endl;
}

Measured memory_bytes: 3628
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def powr(i, j, d):
    p = j
    ans = 1
    while p != 0:
        if p % 2 == 1:
            ans = (ans * i) % d
        i = i**2 % d
        p >>= 1
    return ans

def div(i, j):
    # 1/i mod(j)
    # calc i**(j-2) mod(j)
    return powr(i, j-2, j)

# def make_comb(m, d):
#     fac = [0] * (m+1)
#     ifac = [0] * (m+1)
#     # nCk
#     fac[0] = 1
#     ifac[0] = 1
#     for i in range(m):
#         fac[i+1] = (fac[i] * (i+1)) % d
#         ifac[i+1] = (ifac[i] * div(i+1, d)) % d
#     def comb(n, k):
#         if n == 0 and k == 0:
#             return 1
#         if n < k or n < 0:
#             return 0
#         return (fac[n] * ifac[k] * ifac[n-k]) % d
#     return comb

def nck(n, k, d):
    ans = 1
    for i in range(n-(k-1), n+1):
        ans *= i % d
        ans %= d
    for i in range(1, k+1):
        ans *= div(i, d)
        ans %= d
    return ans % d

def main():
    n, a, b = list(map(int, input().strip().split()))
    d = 10**9+7
    # comb = make_comb(10**6, d)
    ans = (powr(2, n, d) - 1 - nck(n, a, d) - nck(n, b, d)) % d
    if ans < 0:
        print(ans + d)
    else:
        print(ans)

    # print(comb(10, 2))
    # print(comb(5, 2))


if __name__ == '__main__':
    main()


Measured memory_bytes: 43132
#include<iostream>
#include<math.h>
using namespace std;

int main(void){
    int N, K, result = 0;
    cin >> N >> K;

    for(int i = 0;; i++){
        if(N >= pow(K, i)) result++;
        else break;
    }

    cout << result << endl;
    return 0;
}

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

using namespace std;

const int max_n = 200222, inf = 1000111222;

int n, a[max_n];
long long sum[max_n];

void prec() {
    sum[0] = a[0];
    for (int i = 1; i < n; ++i) {
        sum[i] = a[i] + sum[i - 1];
    }
}

long long get_sum(int l, int r) {
    if (l == 0) {
        return sum[r];
    }
    return sum[r] - sum[l - 1];
}

long long get(int i, int j, int q) {
    long long a = get_sum(0, i);
    long long b = get_sum(i + 1, j);
    long long c = get_sum(j + 1, q);
    long long d = get_sum(q + 1, n - 1);
    long long mn = min({a, b, c, d});
    long long mx = max({a, b, c, d});
    return mx - mn;
}

long long triv() {
    long long res = 1e18;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int q = j + 1; q + 1 < n; ++q) {
                long long x = get(i, j, q);
                res = min(res, x);
            }
        }
    }
    return res;
}

int p[2][max_n];

void get_p(int p[]) {
    prec();
    int cur = 0;
    for (int i = 1; i < n; ++i) {
        while (cur + 1 < i && get_sum(0, cur + 1) <= get_sum(cur + 2, i)) {
            ++cur;
        }
        p[i] = cur;
    }
}

long long solve() {
    long long res = 1e18;
    get_p(p[0]);
    reverse(a, a + n);
    get_p(p[1]);
    reverse(a, a + n);
    prec();
    for (int j = 1; j + 2 < n; ++j) {
        for (int i = p[0][j] - 4; i < j && i <= p[0][j] + 4; ++i) {
            for (int k = n - p[1][n - j - 2] - 4; k + 1 < n && k + 1 <= n - p[1][n - j - 2] + 4; ++k) {
                if (0 <= i && i < j && j < k) {
                    res = min(res, get(i, j, k));
                }
            }
        }
    }
    return res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        prec();
        cout << solve() << endl;// << " " << triv() << endl;
        return 0;
        if (solve() != triv()) {
            cout << "WA" << endl;
            cout << n << endl;
            for (int i = 0; i < n; ++i) {
                cout << a[i] << " ";
            }
            cout << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 4096
#include <stdio.h>

void insertionsort(int*,int,int);
void shellsort(int*,int);

long cnt = 0;

int main(){

  int n,i,j;
  int a[1000024] = {};

  scanf("%d",&n);

  for(i = 0;i < n;i++){
    scanf("%d",&a[i]);
  }

  shellsort(a,n);

  for(i = 0;i < n;i++){
    printf("%d\n",a[i]);
  }
  return 0;
}
void insertionsort(int *a,int n,int g){

  int i,v,j;
  for(i = g;i < n;i++){
    v = a[i];
    j = i - g;
    while(j >= 0 && a[j] > v){
      a[j + g] = a[j];
      j = j - g;
      cnt++;
    }
    a[j + g] = v;
  }
}

void shellsort(int *a,int n){
  int i,m,c = 0;
  long g[32] = {1,4,13,40,121,364,1093,3280,9841,29524,88573,265720,797161,2391484};

  for(i = 0;i < 14;i++){
    if(g[i] > n){
      m = c;
      break;
    }
      c++;
  }

  for(i = m - 1;i >= 0;i--){
    insertionsort(a,n,g[i]);
  }

  printf("%d\n",m);
  for(i = m - 1;i >= 0;i--){  
    if(i != 0) printf("%ld ",g[i]);
    else  printf("%ld\n",g[i]);
  }
  printf("%ld\n",cnt);
}

Measured memory_bytes: 4516
#include <bits/stdc++.h>
#define ft first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=1e5+7;
static const ll MOD=1e9+7;
ll max(ll a, ll b) {return a>b?a:b;}
ll min(ll a, ll b) {return a<b?a:b;}

int main() {
  ll N, M;
  cin >> N >> M;
  ll i;
  P p[MAX];
  
  priority_queue<P> q;
  
  for(i=0; i<N; i++) {
    ll d, m;
    cin >> d >> m;
    p[i]={d, m};
  }
  sort(p, p+N);
  
  ll ans=0;
  ll x=0;
  for(ll day=1; day<=M; day++) {
    
    while(p[x].ft==day) {
      q.push({p[x].sc, p[x].ft});
      x++;
    }
    
    if(!q.size()) continue;
    P f=q.top(); q.pop();
    ans+=f.ft;
    
  }
  
  pt(ans);
  
  
}













Measured memory_bytes: 3956
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;

int main()
{
	int n; cin >> n;
	int ans = (n - 1) / 2;
	co(ans);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
main(){
    int N;
    string S;
    cin >> N >> S;
    int depth = 0;//( := +1 ) := -1
    for(int i = 0;i < S.length();i++){
        if(S[i] == ')')depth--;
        else depth++;
        if(depth < 0){
            S = string(depth*-1,'(') + S;
            i -= depth;
            depth = 0;
        }
    }
    S += string(depth,')');
    cout << S << endl;
}

Measured memory_bytes: 256
N,x=map(int,input().split())
a=[int(i) for i in input().split()]
ans=0
for i in range(N):
    if a[i]>x:
        ans+=a[i]-x
        a[i]=x
for i in range(1,N):
    if a[i-1]+a[i]>x:
        ans+=a[i-1]+a[i]-x
        a[i]=x-a[i-1]
print(ans)


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

int main() {
  string N;
  cin >> N;
  int l = N.size();
  int sum = 0;
  int tmp;
  for(int i = 0; i < l; i++) {
    tmp = N.at(i) - '0';
    sum += tmp;
  }
  if(sum % 9 == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3716
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define pf push_front
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){return (int)s.size();}
const long long INF = 1LL << 60;

int main(){
    cout << fixed << setprecision(20);
    int n,l; cin >> n >> l;
    vc<string> a(n);
    rep(i,n){
        cin >> a[i];
    }
    sort(all(a));
    for(string s: a) cout << s;
    cout << endl;
    return 0;
}


Measured memory_bytes: 256