akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll; 
typedef long double ld;
typedef pair<ll, ll> pll;

const ll N = 2e5 + 30, Mod = 1e9 + 7;
const ll SQ = 330;

int main () {
	ios::sync_with_stdio(0), cin.tie(0);
  	ll n;
  	cin >> n;
  	string s;
  	ll k = 1;
  	while (pow(26, k) < n) {
  		n -= pow(26, k);
  		k ++;
	}
	n --;
  	while (n) {
  		ll res = n % 26;
  		s += char('a' + res );
  		n /= 26;
	}
	while (s.size() < k) s += 'a';
	reverse(all(s));
	cout << s;
}

Measured memory_bytes: 4060
/**
 *    DP
 *    24.04.2020 08:30
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, h;
  vector<int> v;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> h;
    v.push_back(h);
  }
  int sz = v.size();
  vector<int> dp (sz + 1, 1e9);
  dp[1] = 0, dp[2] = abs(v[1] - v[0]);
  for (int i = 3; i <= sz; i++) {
    dp[i] = min(dp[i - 1] + abs(v[i - 1] - v[i - 2]), 
                dp[i - 2] + abs(v[i - 1] - v[i - 3]));
  }
  cout << dp[sz] << "\n";
  return 0;
}


Measured memory_bytes: 1144
using System;
using System.Collections.Generic;
using System.Linq;

namespace CSharpSample01
{

    

    class Program
    {
        
        
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int K = int.Parse(input[0]);
            int S = int.Parse(input[1]);

            long cnt_pair = 0;

            for(int x = 0; x <= K; x++)
            {
                for(int y = 0; y <= K; y++)
                {
                    int z = S - (x + y);
                    if(0 <= z && z <= K)
                    {
                        cnt_pair++;
                    }
                }
            }

            Console.WriteLine(cnt_pair);
            
        }
    }
}

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

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;

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; }

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

inline bool inside(int y, int x, int H, int W) {
    return (y >= 0 && x >= 0 && y < H && x < W);
}

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

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  int n,p; cin>>n>>p;
  int e=0; int o=0;
  rep(i,n){
    int a; cin>>a;
    if(a%2) o++;
    else e++;
  }
  ll ans=0;
  if(o){
    ans=round(pow(2,n-1));
  }else{
    if(p==0) ans=round(pow(2,n));
  }
  
  cout<<ans<<endl;
}

Measured memory_bytes: 512
program maximize
  implicit none
  integer :: a, b, c
  integer :: lower, middle, upper
  read(*,*) a, b, c

  upper = max(a,b,c)
  lower = min(a,b,c)
  middle = a+b+c-upper-lower

  write(*,'(i0)') 10*upper+middle+lower
  stop
end program maximize


Measured memory_bytes: 768
#include <iostream>
#define INF 2000000000

using namespace std;

long long merge(int a[],int left,int mid,int right){
  long long cnt=0;
  int n1=mid-left;
  int n2=right-mid;
  int L[n1+1],R[n2+1];
  for(int i=0;i<n1;i++) L[i]=a[left+i];
  for(int i=0;i<n2;i++) R[i]=a[mid+i];
  L[n1]=INF; R[n2]=INF;
  int i=0,j=0;
  for(int k=left;k<right;k++){
    if(L[i]<=R[j]){
      a[k]=L[i];
      i++;
    }else{
      a[k]=R[j];
      cnt=cnt+(n1-i);
      j++;
    }
  }
  return cnt;
}
long long mergeSort(int a[],int left,int right){
  long long v1,v2,v3;
  if(left+1<right){
    int mid=(left+right)/2;
    v1=mergeSort(a,left,mid);
    v2=mergeSort(a,mid,right);
    v3=merge(a,left,mid,right);
    return v1+v2+v3;
  }else return 0;
}

int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0;i<n;i++) cin >> a[i];
  long long ans=mergeSort(a,0,n);
  cout << ans << endl;
}

Measured memory_bytes: 4648
#include <bits/stdc++.h>
#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 chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

//const ll INF = 1e18L + 5;
//const int INF = 1e9 + 5;
//const double pi = 3.14159265358979323846;

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

	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	rep(i, m) {
		int k;
		cin >> k;
		while (k--) {
			int s;
			cin >> s;
			s--;
			a[s] |= 1 << i;
		}
	}
	int p = 0;
	for (int k = 0; k < m; k++) {
		int x;
		cin >> x;
		p |= x << k;
	}
	int ans = 0;
	for (int s = 0; s < (1 << n); s++) {
		int t = 0;
		for (int i = 0; i < n; i++) {
			if (s >> i & 1) {
				t ^= a[i];
			}
		}
		if (t == p) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import copy
h, w, k =map(int,input().split())
masu = []

for i in range(h):
    line = list(input())
    masu.append(line)

masu_tmp = copy.deepcopy(masu)
res=0
for i in range(2 ** h):
    masu_tmp = copy.deepcopy(masu)
    binary_i = format(i, 'b')
    i_len=len(binary_i)
    binary_i = "0"*(h-i_len)+binary_i
    for ii in range(len(binary_i)):
        if binary_i[ii] == "1":
            masu_tmp[ii]=list("-"*w)
    masu_tmp_2 = copy.deepcopy(masu_tmp)
    for j in range(2 ** w):
        masu_tmp_2 = copy.deepcopy(masu_tmp)
        counter = 0
        binary_j = format(j, 'b')
        i_len=len(binary_j)
        binary_j = "0"*(w-i_len)+binary_j
        # print(binary_j)
        for l in range(len(binary_j)):
            if binary_j[l] == "1":
                for m in range(h):
                    masu_tmp_2[m][l]="-"
                # print(m,l)
        for n in range(h):
            for o in range(w):
                if masu_tmp_2[n][o] == "#":
                    counter +=1
                # print(n,o)
        if counter == k:
            res += 1
        # print(masu_tmp_2)
print(res)
# print(masu_tmp)


Measured memory_bytes: 9360
#include<iostream>
using namespace std;
int main(){
	bool prime=true;
	long long int N,n,k,count=0,ans=0,sum;
	cin>>N;
	n=N;
	for(long long int i=2;i*i<=n;i++){
		if(N%i==0){
			k=N/i;
			prime=false;
			count=0;
			while(N%i==0){
				count++;
				N/=i;
			}
			for(int j=1;;j++){
				count-=j;
				if(count>=0)ans++;
				else break;
			}
		}
	}
	if(N!=1)ans++;
	if(n==1)cout<<0;
	else if(prime)cout<<1;
	else cout<<ans;
	return 0;
}

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

long long abs(long long a) { return (a>0)?a:-a; }

int main() {
    long long h, w, ret;
    std::cin >> h >> w;

    if (h % 3 == 0 || w % 3 == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    ret = std::min(h, w);
    for (auto i = 1ll; i < w / 2 + 1; i++) {
        auto ini = { i * h, (w - i) * (h / 2), (w - i) * (h / 2 + (h % 2)) };
        auto tmp = std::max(ini) - std::min(ini);
        ret = std::min(ret, tmp);
    }

    for (auto i = 1ll; i < h / 2 + 1; i++) {
        auto ini = { i * w, (h - i) * (w / 2), (h - i) * (w / 2 + (w % 2)) };
        auto tmp = std::max(ini) - std::min(ini);
        ret = std::min(ret, tmp);
    }

    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 256
N,C,K = map(int,input().split())
T = [int(input()) for i in range(N)]

T.sort()

ans = 1
bus = [T[0]]
l = 1
for i in range(1,N):
    if T[i]-bus[0] <= K and l <= C-1:
        l += 1
    else:
        bus = [T[i]]
        l = 1
        ans += 1
print(ans)


Measured memory_bytes: 7384
N=int(input())
a=list(map(int,input().split()))
l=[0]*N
for i in range(N):
    if a[i]%4:
        if a[i]%2:l[i]=1
        else:l[i]=2
    else:l[i]=4
print('Yes'if l.count(1)+(1 if l.count(2)else 0)<=1+l.count(4)else'No')

Measured memory_bytes: 20004
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    x,y = i_map()
    if (x+y)%3 != 0:
        print(0)
        exit()

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

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

    def fur(n,r):
        p,q = 1, 1
        for i in range(r):
            p = p*(n-i)%MOD
            q = q*(i+1)%MOD
        return (p * pow(q,MOD-2,MOD)) % MOD

    print(fur(n+m,n))



if __name__=="__main__":
    main()


Measured memory_bytes: 66816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
typedef long double ld ;
const int N = 2e5;
ld a[N];
void solve(){
    cout<<fixed<<setprecision(12);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i] = (a[i]+1)/2;
        a[i]+=a[i-1];
    }
    ld ans = 0;
    for(int i=k;i<=n;i++){
        ans = max(ans,a[i]-a[i-k]);
    }
    cout<<ans<<endl;

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


Measured memory_bytes: 3456
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
	ll N, K;
	cin >> N >> K;

	N %= K;
	cout << min(N, K-N) <<endl;
     
  	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
	long long a, b;
	scanf("%lld%lld", &a, &b);
	if (a % 2 == 0 and b % 2) {
		if ((b - a + 1) / 2 % 2)
			printf("%d\n", 1);
		else
			printf("%d\n", 0);
	} else if (a % 2 == 0) {
		if ((b - a) / 2 % 2)
			printf("%lld\n", b ^ 1);
		else
			printf("%lld\n", b);
	} else if (b % 2) {
		if ((b - a) / 2 % 2)
			printf("%lld\n", a ^ 1);
		else
			printf("%lld\n", a);
	} else {
		if ((b - a - 1) / 2 % 2)
			printf("%lld\n", a ^ b ^ 1);
		else
			printf("%lld\n", a ^ b);
	}
	return 0;
}

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

void gauss(vector<ll>& a){
  ll n=a.size();
  ll rank=0;
  for(ll b=(1LL<<60LL);b>=1;b>>=1){
    ll p=rank;
    while(p<n&&!(a[p]&b))p++;
    if(p==n)continue;
    swap(a[rank],a[p]);
    rep(i,n){
      if(i==rank)continue;
      if(a[i]&b)a[i]^=a[rank];
    }
    rank++;
  }
  a.resize(rank);
  sort(all(a));
  reverse(all(a));
}

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

  ll n;
  vector<ll> a;
  cin>>n;
  ll sum=0;
  a.resize(n);
  rep(i,n){
    cin>>a[i];
    sum^=a[i];
  }

  rep(i,n){
    rep(j,60){
      if((sum>>j)&1LL){
        if((a[i]>>j)&1LL){
          a[i]^=(1LL<<j);
        }
      }
    }
  }

  sort(all(a)); 
  gauss(a);

  ll mx=0;
  rep(i,a.size()){
    if(mx<(mx^a[i])){
      mx^=a[i];
    }
  }
  cout<<mx*2+sum<<endl;

  return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, m;
	cin >> n >> m;
	string s, t;
	cin >> s >> t;
	if (s.size() > t.size()) {
		swap(n, m);
		swap(s, t);
	}
	ll g = gcd(n, m);
	ll l = n / g * m;
	string a, b;
	REP(i, g) {
		a += s[i*n / g];
		b += t[i*m / g];
	}
	if (a != b) {
		cout << -1 << endl;
	}
	else {
		cout << n*m/g << endl;
	}
}

Measured memory_bytes: 640
N = int(input())
A = list(map(int,input().split()))

D = {}

for a in A :
    if a not in D :
        D[a] = 1
    else :
        D[a] += 1


odd = 0
even = 0

for v in D.values() :
    if v % 2 == 1 :
        odd += 1
    else :
        even += 1

if even % 2 == 1 :
    ans = odd + even - 1
else :
    ans = odd + even

print(ans)


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

using namespace std;

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

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

  long long ans = 0;
  for (int i = 0; i < n; i++) {
    if (i == n - 1) {
      ans += a[i] / 2;
    } else {
      if (a[i] > a[i + 1]) {
        ans += a[i] / 2;
        a[i] %= 2;
      }
      if (a[i + 1] == 0) continue;
      ans += a[i];
      a[i + 1] -= a[i];
      a[i] = 0;
    }
  }

  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}

vector<ll> t;
int n;

ll gcd(ll a, ll b){
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

ll lcm(ll a, ll b){
  ll g = gcd(a,b);
  return a / g * b;
}

int main(){
  cin >> n;
  t.resize(n);
  rep(i,n) cin >> t[i];
  
  ll ans = t[0];
  for(int i = 1; i < n;i++){
    ans = lcm(ans,t[i]);
    //printf("i=%d,ans=%d\n",i,ans);
  }
  cout << ans;
  return 0;
}

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

int main(){
int n;
long long a;
long long min=1000000;
long long max=-1000000;
long long sum=0;

cin>>n;

for(int i=0;i<n;i++){
cin>>a;
if(a<min)min=a;
if(a>max)max=a;
sum+=a;
}
cout<<min<<" "<<max<<" "<<sum<<endl;
return 0;
}


Measured memory_bytes: 3088
#include<iostream>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int k[n],a[99999],sum=0,b[m+1];
	for(int i=1;i<=m;i++)
	{
		b[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		cin>>k[i];
		for(int j=0;j<k[i];j++)
		{
			int x;
			cin>>x;
			b[x]++;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		if(b[i]==n)
		{
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}
int main(){
	int n;scanf("%d",&n);
	long long ans=1;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);ans=ans*x/gcd(ans,x);
	}
	printf("%lld\n",ans);
	return 0;
}



Measured memory_bytes: 3232
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<fstream>
#include<stdlib.h>
#include<set>
#include<climits>
#include<cmath>  
#include<memory.h> 
#include<sstream>
#include<time.h>
#include<iomanip>
using namespace std;
const unsigned long long BIGEST=1000000000000000000+1000000000000000000;
const long long BIGER=1000000000000000000;
const int BIG=1000000000;
const long long MOD=998244353;
const long long LMOD=154590409516822759;
//const long long LMOD=1000000007;
#define Fi first
#define Se second
#define P2 pair
#define Pii pair<int,int>
#define Pll pair<long long,long long>
#define Cb make_pair
#define ll long long
#define Ull unsigned long long
#define Sf scanf
#define Pf printf
#define Pb push_back
#define Psh push
#define Stc stack
#define Vct vector
#define Ret return
#define Re0 return 0
#define Sz size
#define Is insert
#define Que queue
#define Emp empty
#define Fro front
#define Rv reverse
#define Er erase
#define Bg begin
#define Srt sort
#define Pq priority_queue
#define Ins insert
#define Ite iterator
#define Cou count
#define Cot continue
#define Beg begin
int main()
{
	int l,r,n;
	cin>>l>>r>>n;
	cout<<(r/n)-((l+n-1)/n)+1;
	return 0;
}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

template<class T> inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
void cmps(vector<int>&v,int &i){
	i=lower_bound(all(v),i)-v.begin();
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;

int mod_pow(int x,int y,int m=mod){
	int res=1;
	while(y>0){
		if(y&1)res=res*x%m;
		y>>=1;x=x*x%m;
	}
	return res;
}
int perm[1000001],inv[1000001];
void init_perm(){
	perm[0]=1;
	REP(i,1000001)perm[i]=perm[i-1]*i%mod;
	inv[1000000]=mod_pow(perm[1000000],mod-2);
	for(int i=999999;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
int nCk(int x,int y){
	if(x<y)return 0;
	return perm[x]*inv[x-y]%mod*inv[y]%mod;
}


signed main(){
	int N,p;
	int one=0,zero=0;
	cin>>N>>p;
	rep(i,N){
		int a;cin>>a;
		if(a%2)one++;
		else zero++;
	}
	if(one==0){
		if(p==0)cout<<(1ll<<N)<<endl;
		else cout<<0<<endl;
	}
	else {
		cout<<(1ll<<N-1)<<endl;
	}
}


Measured memory_bytes: 384
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    char[] c = s.toCharArray();
    int sum = 0;
    for(int i=0; i<c.length; i++){
      if(c[i] == '1'){
        sum++;
      }
    }
    System.out.println(sum);
  }
}

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

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

  string G[h];
  for (int i = 0; i < h; i++) cin >> G[i];

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

  bool can = true;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (G[i][j] == '#') {
        bool sharp = false;
        for (int d = 0; d < 4; d++) {
          if (i + dy[d] < 0 || h <= i + dy[d]) continue;
          if (j + dx[d] < 0 || w <= j + dx[d]) continue;
          if (G[i + dy[d]][j + dx[d]] == '#') sharp = true;
        }
        if (sharp == false) can = false;
      }
    }
  }

  if (can)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


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

int main(){
    int N;
    cin >> N ;
    int n = 0;
    vector<int> vec(N);
    for(int i = 0;i < N;i++){
        cin >> vec.at(i);
    }
    sort(vec.begin(),vec.end());
    for(int i = 0;i < N-1;i++){
        if(vec.at(i) == vec.at(i+1)){
            cout << "NO" << endl;
            n++;
            break;
        }
    }
    if(n == 0){
        cout << "YES" << endl;
    }
    
    
}


Measured memory_bytes: 1024
def kaibun?(str)
  n=str.size
  return true if n==1
  if n % 2 == 0
    return str[0..(n/2-1)] == str[(n/2)..(n-1)].reverse
  else
    return str[0..(n/2-1)] == str[(n/2+1)..(n-1)].reverse
  end
end
string = gets.chomp
l=string.size
strh = string[0..(l/2-1)]
strt = string[(l/2+1)..(l-1)]
if kaibun?(string)
  if kaibun?(strh) && kaibun?(strt)
    puts "Yes"
  else
    puts "No"
  end
else
  puts "No"  
end

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using ll = long long;
using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> v;
    v.resize(m);

    for (int i=0; i<m; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), cmp);
    int res=0, endtime=0;
    for (int i=0; i<m; i++){
        if (v[i].first >= endtime) {
            endtime = v[i].second;
            res++;
        }
    }
    cout << res << endl;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
	#define debug(...) printf(__VA_ARGS__)
#else
	#define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN=100050;
int A[MAXN];

int main() {
	int N;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
		scanf("%d",A+i);
	ll ans=A[0]-1;
	int cur=2;
	for(int i=1;i<N;i++) {
		if(A[i]==cur) cur++;
		else if(A[i]>cur) {
			ans+=(A[i]-1)/cur;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 768
use std::cmp::{max, min};
use std::io::*;
use std::str::FromStr;

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

fn main() {
    let n:usize = read();
    let m:usize = read();
    let mut left:i64 = read();
    let mut right:i64 = read();
    for _ in 1..m {
        left = max(left, read());
        right = min(right, read());
    }
    println!("{}", max(right-left+1, 0));
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
int main(){
  int h,w;
  cin >> h >> w;
  char c[h][w];
  rep(i,h){
    rep(j,w){
      cin >> c[i][j];
    }
  }
  vector<bool> is(h,false),no(w,false);
  rep(i,h){
    rep(j,w){
      if(c[i][j]=='#'){
        is.at(i)=true;
      }
    }
  }
  rep(i,w){
    rep(j,h){
      if(c[j][i]=='#'){
        no.at(i)=true;
      }
    }
  }
  rep(i,h){
    if(is.at(i)){
      rep(j,w){
        if(no.at(j)){
          cout << c[i][j];
        }
      }
      cout << endl;
    }
  }
}

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

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void vprint(vector<ll> A){
    ll L = A.size();
    FOR(i, 0, L){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
}

vector<ll> A;

ll simulate(ll num){
    for(ll a : A){
        num -= num%a;
    }
    return num;
}

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

    // input
    ll N;
    cin >> N;
    A.resize(N);

    FOR(i, 0, N){
        cin >> A.at(i);
    }
    ll sum = 0;
    for(ll a : A){
        sum += a;
    }

    // g(N) ≥ 2 であるような最小の N
    ll left = 1;
    ll right = 2 + sum - N;
    while(left+1!=right){
        ll center = (left+right)/2;
        if(simulate(center)>=2){
            right = center;
        }else{
            left = center;
        }
    }
    ll mi = right;

    // g(N) ≤ 2 であるような最大の N
    left = 1;
    right = 2 + sum - N + N; // over
    while(left+1!=right){
        ll center = (left+right)/2;
        if(simulate(center)<=2){
            left = center;
        }else{
            right = center;
        }
    }
    ll ma = left;

    if(mi>ma){
        p(-1);
    }else{
        p2(mi, ma);
    }
    
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static String[] grid;
    static int h, w;
    static int[] dy = {1, 0, -1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int[][] dist;

    public static void main(String[] args) {
        h = sc.nextInt();
        w = sc.nextInt();
        grid = new String[h];
        for(int y = 0; y < h; ++y) grid[y] = sc.next();
        dist = new int[h][w];

        bfs(0, 0);
        if(dist[h - 1][w - 1] < 0) {
            System.out.println(-1);
            return;
        }
        
        int white = countWhiteGrid();
        int passedWhite = dist[h - 1][w - 1] + 1;
        int ans = white - passedWhite;
        System.out.println(ans);
    }
    
    static int countWhiteGrid() {
        int white = 0;
        for(int y = 0; y < h; ++y) {
            for(int x = 0; x < w; ++x) {
                if(grid[y].charAt(x) == '.') ++white;
            }
        }
        return white;
    }
    
    static void initializeDist(int sy, int sx) {
        for(int y = 0; y < h; ++y) {
            for(int x = 0; x < w; ++x) dist[y][x] = (y == sy && x == sx) ? 0 : -1;
        }
    }

    static void bfs(int sy, int sx) {
        initializeDist(sy, sx);
        ArrayDeque<Coordinate> coordinates = new ArrayDeque<>();
        coordinates.add(new Coordinate(sy, sx));

        while(coordinates.size() > 0) {
            Coordinate fc = coordinates.remove();
            for(int i = 0; i < 4; ++i) {
                int ny = fc.y + dy[i];
                int nx = fc.x + dx[i];
                if(isOutOfMaze(ny, nx) || grid[ny].charAt(nx) != '.' || dist[ny][nx] >= 0) continue;
                dist[ny][nx] = dist[fc.y][fc.x] + 1;
                coordinates.add(new Coordinate(ny, nx));
            }
        }
    }

    static boolean isOutOfMaze(int y, int x) {
        return y < 0 || h <= y || x < 0 || w <= x;
    }
}

class Coordinate {
    int y;
    int x;
    
    public Coordinate(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

Measured memory_bytes: 21844
import java.util.Arrays;

public class Main {
  private static void solve() {
    int n = ni();
    int[] a = na(n);
    
    int[][] b = new int[n][2];
    for (int i = 0; i < n; i ++) {
      b[i][0] = a[i];
      b[i][1] = i;
    }
    
    Arrays.sort(b, (o1, o2) -> o1[0] - o2[0]);

    int pre = -1;;
    int now = 0;
    int ret = -1;
    for (int[] v : b) {
      if (pre < v[1]) {
        now ++;
        ret = Math.max(now, ret);
      } else {
        now = 1;
      }
      pre = v[1];
    }
    
    
    System.out.println(n - ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}




Measured memory_bytes: 47016
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}
int sgn(const double&r){return (r>EPS)-(r<-EPS);} // a>0  : sgn(a)>0
int sgn(const double&a,const double&b){return sgn(a-b);} // b<=c : sgn(b,c)<=0

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	cout<<n*n<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
	long long n,k,h[100005],ans=10000000000;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>h[i];
	}
	sort(h,h+n);
	for(int i=0;i<n-k+1;i++){
		if(h[i+k-1]-h[i]<ans)
			ans=h[i+k-1]-h[i];
	}
	cout<<ans<<endl;
    return(0);
}

Measured memory_bytes: 4340
#include<bits/stdc++.h>
using namespace std;
void fnc(int a,int b)
{
	if(b==0)
    ;
    else
    {
	 cout<<a;
     fnc(a,b-1);
    }
}
int main()
{
 int a,b;
 cin>>a>>b;
 if(a<b)
 {
	fnc(a,b);
 }
 else
 {
	fnc(b,a);
 }
 return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int N, M, s[10], c[15], X[10], i;
    scanf("%d%d", &N, &M);
    for (i=0; i<N; i++) X[i]=-1;
    for (i=0; i<M; i++) {
        // printf("[%d]\n", i);
        scanf("%d%d", &s[i], &c[i]);
        s[i]--;
        if (X[s[i]]!=-1 && X[s[i]]!=c[i]) {
            printf("-1");
            return 0;
        }
        else X[s[i]]=c[i];
    }
    if (X[0]==0 && N!=1) {
        printf("-1");
        return 0;
    }
    if (X[0]==-1) {
        if (N==1) X[0]=0;
        else X[0]=1;
    }
    for (i=0; i<N; i++) {
        if (X[i]==-1) X[i]=0;
        printf("%d", X[i]);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)


ll cnt;
void insertionSort(vector<ll> &A,ll n,ll g){
	FOR(i,g,n){
		ll v = A[i];
		ll j = i-g;
		while(j>=0 && A[j]>v){
			A[j+g] = A[j];
			j = j-g;
			cnt++;
		}
		A[j+g] = v;
	}
}
void shellSort(vector<ll> &A , ll n){
	cnt = 0;
	ll m = 0;
	ll k = 1;
	vector<ll> G;
	while(k<=(ll)n){
		G.push_back(k);
		k = k*2;
	}
	reverse(G.begin(), G.end());
	m = G.size();
	cout << m << "\n" << G[0];
	FOR(i,1,m)cout<<" "<<G[i];
	cout<<'\n';
	FOR(i,0,m){
		insertionSort(A,n,G[i]);
	}
	cout << cnt << "\n";
}



int main () {
	ll n;
	cin >> n;
	vector<ll> A(n);
	FOR(i,0,n)cin >> A[i];
	shellSort(A,n);
	FOR(i,0,n){
		cout << A[i] << "\n";
	}
}


Measured memory_bytes: 10680
#coding:utf-8

words = ['dream', 'dreamer', 'erase', 'eraser']

s = input()

for i in range(len(words)):
    words[i] = words[i][::-1]
s = s[::-1]
count = 0
ans = 'YES'
while(count < len(s)):
    for word in words:
        if s[count:count+len(word)] == word:
            count += len(word)
            break
    else:
        ans = 'NO'
        break

print(ans)


Measured memory_bytes: 3188
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        boolean[] used = new boolean[1001];
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            for (int j = start; j < end; j++) {
                used[j] = true;
            } 
        }
        int canUse = 0;
        for (int i = a; i < b; i++) {
            if (used[i]) {
                canUse = 1;
                break;
            }
        }
        System.out.println(canUse);
    }
}



Measured memory_bytes: 26556
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
//#define int long long  ←保留
#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279; //円周率
/*---------------------便利な関数--------------------------------------*/
int fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
 
int gcd(int a, int b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
 
int lcm(int a, int b) {      //最小公倍数
    return a * b / gcd(a, b);
}
 
int keta(int n) {        //桁数を求める
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
 
int ketasum(int n) {    //各桁の和
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
 
/*-------------ここまで---------------------------------------------*/
 
//C++(GCC9.2.1)
 
/*signed*/int main(void) {
  int a,b;
  cin >> a >> b;
  if(a==1) a+=13;
  if(b==1) b+=13;
  if(a>b) cout << "Alice" << endl;
  else if(a<b) cout << "Bob" << endl;
  else cout << "Draw" << endl;
  return 0;
}


Measured memory_bytes: 3624
// Created by sz
#include <bits/stdc++.h>
using namespace std;

int nxt[100005];
int pre[100005];
int temp[100005];

typedef  long long ll;

int main(){
#ifdef LOCAL
    freopen("./input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, H, W, tempa, tempb, ans = 0;
    cin>>N>>H>>W;
    for(int i =0; i <N; i++){
        cin>>tempa>>tempb;
        if(tempa>=H&&tempb>=W) ++ans;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

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

    long long ans = 0;
    map<string, int> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        ans += m[s]++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11136
#include <cstdio>

int main(){
	int n;
	scanf("%d",&n);
	if(n/10%9==0)printf("Yes\n");
	else if((n-(n/10*10))%9==0 && (n-(n/10*10))!=0) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES // for C++  
#include <cmath> 
void call(int n);
using namespace std;
int main(){
	
	int n,m;
	cin>>n>>m;
	int ar1[n][m];
	int ar2[m];
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>ar1[i][j];
		}
	}
	for(int i=0;i<m;i++){
		cin>>ar2[i];
	}
	
	for(int i=0;i<n;i++){
		int ans=0;
		for(int j=0;j<m;j++){
			ans=ans+ar1[i][j]*ar2[j];
		}
			cout<<ans<<endl;
	}
	
}


Measured memory_bytes: 3112
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if(a * b % 2 == 0) {
			System.out.println("Even");
		} else {
			System.out.println("Odd");
		}
	}
}


Measured memory_bytes: 21204
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>

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

using namespace std;
typedef long long ll;

int main() {

    ll r;
    cin >> r;
    cout << 3*r*r << endl;
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<random>
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint 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)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18;

lint N;
int main() {
	cin >> N;
	cout << (1000 - (N - 1) % 1000) - 1 << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  
  vector<int> x(n);
  
  for(int i=2;i<=n;i++){
    int a=i;
    for(int j=2;j<=i;j++){	//iを素因数分解
      while(a%j==0){
        a=a/j;
        x.at(j-1)++;
      }
    }
  }
  
  long long int p=1;
   
  for(int i=0;i<n;i++){
    p*=x.at(i)+1;
    p%=1000000007;
  }
  
  cout << p%1000000007 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
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 DEB 0

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

int w,h,field[22][22];
int memo[22][22];
int ans,sx,sy,gx,gy;

inline bool inside(int x, int y){
  return (!(x<0 || x>=w || y<0 || y>=h));
}

void dfs(int x, int y, int cnt){
  int tx,ty;
  if( cnt>=ans ) return;
  
#if DEB
  printf("(%d,%d)  cnt:%d\n",x,y,cnt);
  rep(i,h){
    rep(j,w){
      printf("%d ",field[i][j]);
    }
    puts("");
  }
#endif

  rep(k,4){
    tx = x + dx[k];
    ty = y + dy[k];	
    if( !inside(tx,ty) || field[ty][tx]==1 )continue;
    REP(j,1,30){
      int tx = x + dx[k]*j;
      int ty = y + dy[k]*j;
      if( !inside(tx,ty) ) break;
      if( field[ty][tx]==1 ){
	field[ty][tx] = 0;
	dfs(tx-dx[k], ty-dy[k], cnt+1);
	field[ty][tx] = 1;
	break;
      }else if( field[ty][tx]==3 ){
	ans = cnt+1;
	return;
      }
    }
  }
}

int main(){
  
  while(scanf("%d%d",&w,&h),w|h){
    ans = 11;
    rep(i,h){
      rep(j,w){
	scanf("%d",&field[i][j]);
	if( field[i][j]==2 ){
	  sx=j; sy=i;
	}else if( field[i][j]==3 ){
	  gx=j; gy=i;
	}
      }
    }
    dfs(sx,sy,0);
    printf("%d\n",ans==11?-1:ans);
  }
  return 0;
}

Measured memory_bytes: 888
dir_dict = {'N': (0, 1), 'E': (1, 0), 'S': (0, -1), 'W': (-1, 0)}

while True:
    jewel_num = int(input())
    
    if jewel_num == 0:
        break
    
    jewel_coor_set = set()
    for i in range(jewel_num):
        jewel_coor_set.add(tuple(map(int, input().split(' '))))
    
    
    cmd_num = int(input())
    curr_coor = [10, 10]
    
    jewel_coor_set -= {(10, 10)}
    for i in range(cmd_num):
        move_cmd = input().split(' ')
        move_vec = dir_dict[move_cmd[0]]
        move_dist = int(move_cmd[1])
        
        for i in range(move_dist):
            curr_coor[0] += move_vec[0]
            curr_coor[1] += move_vec[1]       
            jewel_coor_set -= {tuple(curr_coor)}
            
    if not jewel_coor_set:
        print('Yes')
    else:
        print('No')



Measured memory_bytes: 5728
S = gets.chomp
N = S.size

ans = Array.new(N, 0)

counter = Hash.new(0)

(0).upto(N - 2) do |idx|
  if S[idx] == 'R' && S[idx + 1] == 'L'
    ans[idx] += 1

    if idx.even?
      ans[idx] += counter[0]
      ans[idx + 1] += counter[1]
    else
      ans[idx] += counter[1]
      ans[idx + 1] += counter[0]
    end

    counter = Hash.new(0)
  elsif S[idx] == 'R'
    counter[idx % 2] += 1
  end
end

counter = Hash.new(0)

(N - 1).downto(1) do |idx|
  if S[idx - 1] == 'R' && S[idx] == 'L'
    ans[idx] += 1

    if idx.even?
      ans[idx] += counter[0]
      ans[idx - 1] += counter[1]
    else
      ans[idx] += counter[1]
      ans[idx - 1] += counter[0]
    end

    counter = Hash.new(0)
  elsif S[idx] == 'L'
    counter[idx % 2] += 1
  end
end

puts ans.join(' ')


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

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define debug(x) cerr << #x << " = " << (x) << endl;
template<typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    for (auto& x : v) o << x << ' ';
    return o;
}

int main(){
    std::ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vi arr(n);
    ll Ma = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        arr[i] %= m;
    }
    vector<ll> acc(m+10), dec(m+10), cnst(m+10);

    for (int i = 1; i < n; i++){
        int a = arr[i-1], b = arr[i];
        if (a < b) {
            Ma += b-a;
            acc[a+2]++;
            dec[b]++;
            int c = b-(a+1);
            cnst[b+1] -= c;
        } else {
            Ma += (b + m - a);
            acc[a+2]++;
            //
            int c = m-(a+2);
            acc[0]++;
            cnst[0] += c;
            // minus
            dec[b]++;
            cnst[b+1] -= (b+m - (a+1));
        }
    }
    ll best = LLONG_MIN/2;
    ll accum = 0;
    ll sum = 0;
    for (int i = 0; i < m; i++){
        accum += acc[i];
        sum += accum;
        sum += cnst[i];
        best = max(best, sum);
        accum -= dec[i];
    }
    cout << Ma - best << endl;
}


Measured memory_bytes: 3072
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let q: usize = read();
    let s: Vec<char> = read::<String>().chars().collect();

    let mut rui = vec![0; n];
    for i in 0..n-1 {
        rui[i+1] = rui[i];
        if s[i] == 'A' && s[i+1] == 'C' {
            rui[i+1]  += 1;
        }
    }

    for _ in 0..q {
        let l: usize = read();
        let r: usize = read();
        println!("{}", rui[r-1] - rui[l-1]);
    }
}

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


Measured memory_bytes: 4860
#include <stdio.h>

int main(void)
{
    int a, b;
    int sum;

    scanf("%d %d", &a, &b);
    sum = a + b;

    if (a % 3 == 0 || b % 3 == 0 || sum % 3 == 0)
        printf("Possible");
    else
        printf("Impossible");

    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main() {
	long long a,b,c,d,e;
	cin>>a>>c>>b>>d>>e;
	if(llabs(a-b)<=(c-d)*e){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	} 
	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007

using namespace std;

ll power(ll n, ll k){
  ll res = 1;
	while(k > 0){
		if (k & 1) 
      res = res * n % MOD;
		n = n * n % MOD;
		k >>= 1;
	}
	return res;
}



ll fact(ll n){

  ll res = 1;
  while (n > 0){
    res = res * n % MOD;
    n--;
  }

  return res;
}

ll inv(ll n){
  return power(n, MOD - 2);
}


ll ncr(ll r, ll c){
  if (c == 0)
    return 1;

  return (((fact(r + c) * inv(fact(r))) % MOD) * inv(fact(c))) % MOD;
}


int main(void){
  ll x, y;

  cin >> x >> y;

  if (x > 2*y || y > 2*x || (x + y) % 3 != 0){
    cout << 0 << endl;
    return 0;
  }


  ll t = x;
  x -= (t + y)/3;
  y -= (t + y)/3;

  cout << ncr(x, y) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int div_ct(int n) { 
  int c = 0;
  int k;
  for ( k = 1; k <= n; k++ ) { 
    if ( n % k == 0 ) { c++; } 
  }
  return c;
}
int main()
{
    int N;
    cin >> N;
    int count = 0;
    for(int i = 1;i <= N;i += 2)
    {
        if(div_ct(i) == 8)
            count++;
    }
    cout << count << '\n';
}

Measured memory_bytes: 256