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

#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    string word;
    string text;
    vector<string> ttt;

    cin >> word;

    while (1) {
        cin >> text;
        if (text=="END_OF_TEXT") {
            break;
        }
        ttt.push_back(text);
    }

    int n = ttt.size();

    int j = 0;
    for (int i = 0; i < n; i++) {
        string tt = ttt[i];
        transform(tt.begin(), tt.end(), tt.begin(), ::tolower);

        if (tt==word) {
            j = j + 1;
        }
    }

    cout << j << endl;

    return 0;
}


Measured memory_bytes: 3160
// inputに入力データ全体が入る

function Main(input) {
  input = input.split("\n");
  tmp1 = input[0].split(" ");
  tmp2 = input[1].split(" ");

  
  if (tmp1[0] == tmp2[0]) {
    console.log(0);
  } else {
    console.log(1);
  }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 11468
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int n =Integer.parseInt(in.readLine());
    String[] d = new String[n];
    HashSet hs = new HashSet();
    for(int i=0; i<n; i++) {
      d[i] = in.readLine();
      hs.add(d[i]);
    }
    System.out.println(hs.size());
  }
}

Measured memory_bytes: 32480
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <deque>
#include <unordered_set>
#include <functional>
 
using namespace std;

int main() {
    int l;
    cin>>l;
    cout<<fixed<<setprecision(12) <<(double)(l*l*l)/27;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class Program {
    static void Main() {
        while(true) {
            string[] stdin = Console.ReadLine().Split();
            int h = int.Parse(stdin[0]);
            int w = int.Parse(stdin[1]);
            if((h | w) == 0) break;
            for(int i = 0; i < h; i++) {
                for(int j = 0; j < w; j++) Console.Write(i == 0 || i == h - 1 || j == 0 || j == w - 1? "#" : ".");
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }
}


Measured memory_bytes: 17916
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

N = int(sys.stdin.readline().strip())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

if N == 1:
    print(0)
    exit(0)

e = factorization(N)
#print(e)

ans = 0
for p, q in e:
    c = 0
    j = 1
    while c+j <= q:
        c += j
        j += 1

    ans += (j-1)
    #print(j-1)

print(ans)



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

using namespace std;

int main()
{
   int n,i;

   long long res = 0,prev;

   cin>>n;

   int a[n],b[n],c[n-1];

   for(i = 0;i < n;i++)
   {
     cin>>a[i];
   }
   for(i = 0;i < n;i++)
   {
     cin>>b[i];
   }
   for(i = 0;i < n-1;i++)
   {
     cin>>c[i];
   }


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

   cout<<res<<"\n";

}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <queue>
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define mp make_pair
#define forn(i,n) for(int i=0;i<n;i++)

using namespace std;

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a==1&&b==2)printf("3\n");
    if(a==1&&b==3)printf("2\n");
    if(a==2&&b==3)printf("1\n");
    if(b==1&&a==2)printf("3\n");
    if(b==1&&a==3)printf("2\n");
    if(b==2&&a==3)printf("1\n");
    return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}

ll MOD = (ll)(1e9 + 7);

const int MAX_N = 1010;

const int SZ = 312345;

ll inv[SZ];
ll fact[SZ];
ll fact_inv[SZ];
ll choose(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * fact_inv[n-r] % MOD * fact_inv[r] % MOD;
}

ll mod_pow(ll a, ll b, ll p) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

ll f(int m, int k) {
  ll res = fact[m*k];
  (res *= mod_pow(fact_inv[m], k, MOD)) %= MOD;
  (res *= fact_inv[k]) %= MOD;
  return res;
}

ll A, B, C, D;
ll dp[MAX_N][MAX_N];

ll rec(int n, int m) {
  if (n < 0) return 0;
  if (m == 0 && n == 0) return 1;
  if (m == 0 && n > 0) return 0;
  if (dp[n][m] != -1) return dp[n][m];
  ll res = rec(n, m-1);
  if (A <= m && m <= B) {
    for (int k = C; k <= D; k++) {
      if (n - k*m < 0) break;
      ll cur = rec(n - k*m, m-1);
      (cur *= choose(n, k*m)) %= MOD;
      (cur *= f(m, k)) %= MOD;
      res += cur;
    }
  }
  res %= MOD;
  return dp[n][m] = res;
}

int main2() {
  CLR(dp, -1);
  int N = nextInt();
  A = nextInt();
  B = nextInt();
  C = nextInt();
  D = nextInt();
  ll ans = rec(N, N);
  cout << ans << endl;
  return 0;
}

int main() {
  {
    inv[1] = 1;
    for (int i = 2; i < SZ; i++) inv[i] = inv[(int) (MOD % i)] * (MOD - MOD / i) % MOD;
    fact[0] = 1;
    for (int i = 1; i < SZ; i++) fact[i] = fact[i-1] * i % MOD;
    fact_inv[0] = 1;
    for (int i = 1; i < SZ; i++) fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
  }
#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Measured memory_bytes: 15616
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int N=sc.nextInt();
    int A[] =new int[N];
    long B[] =new long[N];
    long C[] =new long[N+1];
    long D[] =new long[N];
    long W[] =new long[N];
    C[0]=0;
    for(int i=0;i<N;i++){
      A[i]=sc.nextInt();
      B[A[i]-1]=B[A[i]-1]+1;}
    int X=0;
    for(int x=0;x<N;x++){
      if(!(B[x]==0)){X=X+1;}}
    for(int j=0;j<N;j++){
      if(!(D[A[j]-1]==0)){C[j+1]=C[j];continue;}
       D[A[j]-1]=B[A[j]-1]*(B[A[j]-1]-1)/2;
       C[j+1]=C[j]+D[A[j]-1];}
        for(int k=0;k<N;k++){
           W[k]=C[N]-D[A[k]-1]+(B[A[k]-1]-1)*(B[A[k]-1]-2)/2;
      System.out.println(W[k]);}
  }
}


Measured memory_bytes: 99764
hoge = input().split()
a,b,c,d = int(hoge[0]), int(hoge[1]), int(hoge[2]), int(hoge[3])

while True:
  if c - b <=0:
    print("Yes")
    break
  else:
    c -=b
  if a - d <=0:
    print("No")
    break
  else:
    a -=d

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

using ll = long long;
#define mod 1000000007
#define init ios::sync_with_stdio(0), cin.tie(0);
typedef vector<int> vi;
typedef pair<int, int> pi;
#define MS(x, y) memset(x, y, sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair

int main()
{
    init;
    int t;
    cin >> t;

    if (t % 1000)
    {
        cout << 1000 - t % 1000;
    }
    else
        cout << 0;
}

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

#define F first
#define S second
#define MP make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define LCM(a, b) (a) / __gcd((a), (b)) * (b)
#define CEIL(a, b) (a)/(b)+(((a)%(b))?1:0)
#define ln '\n'

using namespace std;
using LL = long long;
using ldouble = long double;
using P = pair<int, int>;
using LP = pair<LL, LL>;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1e9 + 7;
static const int SIZE = 200005;

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

vector<LL> Div(LL n) {
    vector<LL> ret;
    for(LL i = 1; i * i <= n; ++i) {
        if(n % i == 0) {
            ret.pb(i);
            if(i * i != n) ret.pb(n / i);
        }
    }
    sort(all(ret));
    return ret;
}

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

    int N;
    cin >> N;
    vector<P> v(N + 1);
    v[0].F = INF;
    v[0].S = INF;
    int num[505];
    int pos[505];
    int res[250005] = {};
    for(int i = 1; i <= N; ++i) {
        cin >> v[i].F;
        v[i].S = i;
        pos[i] = v[i].F;
        num[i] = N - 1;
        res[v[i].F] = i;
    }
    sort(all(v));

    int np = 1;
    for(int i = 0; i < v.size() - 1; ++i) {
        for(int j = 1; j < v[i].S; ++j) {
            if(res[np] == v[i].S) {
                cout << "No" << endl;
                return 0;
            }
            if(res[np] != 0) {
                ++np;
                --j;
                continue;
            }
            num[v[i].S]--;

            res[np] = v[i].S;
            ++np;
        }
    }

    sort(all(v), greater<P>());
    np = N * N;
    for(int i = 1; i <= N; ++i) {
        while(num[v[i].S] > 0) {
            if(v[i].F == np) {
                cout << "No" << endl;
                return 0;
            }
            if(res[np] != 0) {
                --np;
                continue;
            }
            res[np] = v[i].S;
            --np;
            --num[v[i].S];
        }
    }

    cout << "Yes" << endl;
    for(int i = 1; i <= N * N; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 4596
#3 Range Flip Find Route
h,w = map(int,input().split())
s= [None for i in range(h)]
for i in range(h):
    s[i] = input()
    
dp = [[0]*w for i in range(h)]

dp[0][0] = int(s[0][0]=="#")
for i in range(1,w):
    dp[0][i]=dp[0][i-1] + (s[0][i-1]=="." and s[0][i]=="#")

for i in range(1,h):
    dp[i][0]=dp[i-1][0] + (s[i-1][0]=="." and s[i][0]=="#")

for i in range(1,h):
    for j in range(1,w):
        cand1 = dp[i-1][j] + (s[i-1][j]=="." and s[i][j]=="#")
        cand2 = dp[i][j-1] + (s[i][j-1]=="." and s[i][j]=="#")
        dp[i][j]=min(cand1,cand2)
        
print(dp[-1][-1])

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

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>
#include <queue>
#define mp make_pair
#define pb push_back
#define p push
#define FOR(a,c) for(int a = 0;a<c;a++)
#define ll long long
#define abs(x) (x<0 ? (-x) : x)
#define getI(a) scanf("%d",&a)
#define getII(a,b) scanf("%d %d",&a,&b)
#define getIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a,b) scanf("%lld %lld",&a,&b)
#define getLLL(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define fi first
#define se second
#define PI 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfi(a) printf("%d",a);
#define pfii(a,b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a,b) printf("%lld%lld",a,b);
#define SIZE 1000000007

using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<long long> vl;
typedef vector<pair<int,int>> vpi;
typedef vector<pair<long long,long long>> vpl;
typedef vector<vector<pair<long long,long long>>> vvpl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair <ll,ll> pll;
const  double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
/*ios_base::sync_with_stdio(false);cin.tie(0);*/

ll gcd(ll n,ll m){
    if (n==0)return m;
    return gcd(m%n,n) ;
}

long long fast_exp(long long n,long long k){
    if(k == 0)
        return 1;
    if(k==1)
        return n;

    long long temp = fast_exp(n,k>>1);

    if((k&1)==1)
        return (n*temp*temp)%SIZE;
    return (temp*temp)%SIZE;

}

int main() {
 ll n,k ;
 cin >> n>>k;
 ll res = max ( n*k , n -k);
 res = max (res,n+k);
 cout << res;


    return 0;
}


Measured memory_bytes: 256
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, a, b;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> a >> b;
    cout << max(0LL, (a + (n - 1) * b) - ((n - 1) * a + b) + 1) << "\n";
    return 0;
}


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

class Main{
	public static void main(String[] args)throws NumberFormatException, IOException{
	    InputStreamReader input = new InputStreamReader (System. in);
	    BufferedReader buffer = new BufferedReader(input);
	    String stringT = buffer.readLine();
	    long processStart = System.currentTimeMillis();
    	String stringP = buffer.readLine();
    	
    	char[] charT = stringT.toCharArray();
    	for(int x=0; x<stringT.length() - stringP.length() +1 ; x++){
    		StringBuilder compare = new StringBuilder();
	    	for(int i=0; i<stringP.length(); i++){
	    		compare.append(charT[x+i]);
	    	}
	    	String temp = compare.toString();
//	    	System.out.println("text is  "+temp);
	    	if(temp.equals(stringP)){
	    		System.out.println(x);
	    	}
    	}


    	long processEnd = System.currentTimeMillis();
//    	System.out.println("???????????????" + (processEnd - processStart)  + "ms");
	}
}

Measured memory_bytes: 26056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(),v.end()

int main() {
  int t;
  cin >> t;
  if(t>=30){
  	cout << "Yes" << endl;
  }else{
  	cout << "No" << endl;
  }
}



Measured memory_bytes: 3520
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll R,C,K;
ll r[200005],c[200005],v[200005];
ll t[3005][3005];
ll dp[3005][3005][5];
int main(void){
    cin>>R>>C>>K;
    for(int i=0;i<K;i++){
        cin>>r[i]>>c[i]>>v[i];
        t[r[i]][c[i]]=v[i];
    }
    if(t[1][1]>0){
        dp[1][1][1]=t[1][1];
        dp[1][1][2]=t[1][1];
        dp[1][1][3]=t[1][1];
    }
    for(int i=2;i<=R;i++){
        dp[i][1][0]=dp[i-1][1][3];
        dp[i][1][1]=dp[i-1][1][3]+t[i][1];
        dp[i][1][2]=dp[i-1][1][3]+t[i][1];
        dp[i][1][3]=dp[i-1][1][3]+t[i][1];
    }
    for(int i=1;i<=C;i++){
        for(int j=1;j<=3;j++){
            dp[1][i][j]=max({dp[1][i][j-1],dp[1][i-1][j],dp[1][i-1][j-1]+t[1][i]});
        }
    }
    for(int i=2;i<=R;i++){
        for(int j=2;j<=C;j++){
            for(int k=0;k<=3;k++){
                if(k==0){
                    dp[i][j][k]=max(dp[i-1][j][3],dp[i][j-1][k]);
                }else{
                    dp[i][j][k]=max({dp[i][j][k-1],dp[i][j-1][k],dp[i-1][j][3]+t[i][j],dp[i][j-1][k-1]+t[i][j]});
                }
            }
        }
    }
    cout<<dp[R][C][3]<<endl;

}



Measured memory_bytes: 430752
#include<map>
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  string s,t;
  map<string,bool> b;
  b["a"]=1;
  cout<<"?a"<<endl;fflush(stdout);
  cin>>t;
  while(t[0]=='a'&&b[t]==0){
    b[t]=1;
    s=t[t.length()-1];
    char c[9];
    memset(c,0,sizeof(c));
    while(b[s+c+'a']){
      if(0){
      }else if(c[0]==0){
	c[0]='a';
      }else if('a'<=c[0]&&c[0]<'z'){
	c[0]++;
      }else{
	c[0]='a';
	if(0){
	}else if(c[1]==0){
	  c[1]='a';
	}else if('a'<=c[1]&&c[1]<'z'){
	  c[1]++;
	}
      }
    }

    cout<<"?"<<s+c+'a'<<endl;fflush(stdout);
    cin>>t;
  }
  cout<<"!OUT"<<endl;fflush(stdout);
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
long long h,w,n,x,y;
long long ans[10];
long long a[9]={+0,+0,+0,+1,+1,+1,+2,+2,+2};
long long b[9]={+0,+1,+2,+0,+1,+2,+0,+1,+2};
map<pair<long long,long long>,long long>M;
long long read()
{
    long long re=0;
    char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) re=re*10+ch-'0',ch=getchar();
    return re;
}
int main()
{
    h=read(),w=read(),n=read();
    ans[0]=(h-2)*(w-2);
    while(n--)
    {
        x=read(),y=read();
        for(long long i=0;i<9;i++)
        {
            long long dx=x+a[i],dy=y+b[i];
            if(dx>=3&&dx<=h&&dy>=3&&dy<=w)
            {
                ans[M[make_pair(dx,dy)]]--;
                ans[++M[make_pair(dx,dy)]]++;
            }
        }
    }
    for(long long i=0;i<10;i++) printf("%lld\n",ans[i]);
    return 0;
}


Measured memory_bytes: 56448
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

K,A,B = map(int,input().split())

change = (B - A) > 2

bisket = 1
t = min(A-1,K)
bisket += t
K -= t
if not change:
    bisket += K
else:
    q,r = divmod(K,2)
    bisket += (B-A) * q + r

print(bisket)

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

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


Measured memory_bytes: 256
#include <cstdio>
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#define rep(i,n) for (int i=0;i<n;i++)
using ll = long long;
using namespace std;


void solve(){

}
int main (){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a,b;
    cin >> a >> b;
    cout << (a-1)*(b-1);

    return 0;
}

Measured memory_bytes: 256
n,l = map(int,input().split())
p = [l+i for i in range(n)]
ans1 = 0
q = 10**9
y = 0
for i in range(n):
    ans1 += p[i]
for i in range(n):
    if q>p[i] :
        y = i
    q = min(q,abs(p[i]))
print(ans1-p[y])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;cin >> s;
	int n=s.size();
	rep(i,n-1){
		if(s.at(i)==s.at(i+1)){
			cout << i+1 << " " << i+2 << endl;
			return 0;
		}
	}
	rep(i,n-2){
		if(s.at(i)==s.at(i+2)){
			cout << i+1 << " " << i+3 << endl;
			return 0;
		}
	}
	cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 512
n = int(input())
def dfs(i,s):
    if i == n:
        print(s)
        return
    ma = 0
    for j in s:
        ma = max(ma,ord(j))
    for j in range(ma - 95):
        dfs(i+1,s+chr(97+j))
    return
dfs(1,"a")

Measured memory_bytes: 46680
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


const ll MOD=998244353;
const int N=510000;

struct UnionFind{
    vector<int> par,sizes;
    UnionFind(int n):par(n+1),sizes(n+1,1){
        rep2(i,1,n)par[i]=i;
    }
    int find(int x){
        return (x==par[x]?x:par[x]=find(par[x]));
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return ;
        if(sizes[x]<sizes[y]){
            swap(x,y);
        }
        par[y]=x;
        sizes[x]+=sizes[y];
    }
    bool same(int x,int y) {return (find(x)==find(y));}
    int size(int x) {return sizes[find(x)];}
};
main(){
    string s;cin>>s;
    int n=s.size();
    vec b;
    rep(i,n/2){
        b.pb((26+s[i]-s[n-1-i]));
        if(b.back()>=26)b.back()-=26;
    }
    vector<vec> p(n);
    UnionFind uf(n);
    int q=in();
    rep(i,q){
        int l=in(),r=in();
        if(r<=n/2){
            uf.unite(l-1,r);
            // p[l-1].pb(r-1);
        }
        else if(l>n/2){
            // p[n-r].pb(n-l);
            uf.unite(n-r,n-l+1);
        }
        else {
            r=n-r;
            uf.unite(r,l-1);
            // p[r].pb(l-2);
        }
    }
    map<int,vec> mp;
    rep(i,n/2+1){
        mp[uf.find(i)].pb(i);
    }
    for(auto ee:mp){
        auto e=ee.second;
        if(e.size()<=1)continue;
        sort(all(e));
        // print(e);
        p[e[0]].pb(e[1]-1);
        rep(i,e.size()-2){
            p[e[i+1]].pb(e[i+2]-1);
        }
    }
    vec rui(n);
    rep(i,n/2){
        // cout<<b[i]<<" "<<rui[i]<<endl;
        b[i]+=rui[i];
        b[i]%=26;
        if(b[i]){
            if(p[i].size()==0){
                cout<<"NO";return 0;
            }
            else{
                rui[i]+=26-b[i];
                rui[p[i][0]+1]-=26-b[i];
            }
        }
        rui[i+1]+=rui[i];
        if(rui[i+1]>=26)rui[i+1]-=26;
    }
    cout<<"YES";return 0;
}

Measured memory_bytes: 9468
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
#define PI 3.141592653589793238462643383279
typedef long long int ll;
typedef unsigned long long ull;
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;}
typedef pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;

bool isPrime(int x){
int i;
if(x < 2)return 0;
else if(x == 2) return 1;
if(x%2 == 0) return 0;
for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
return 1;
}



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

}


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

int main()
{
	int64_t n, k;
	cin >> n >> k;
	vector<int64_t> as(n);
	for (auto &&a : as)
	{
		cin >> a;
	}

	for (int64_t i = k; i < n; i++)
	{
		cout << ((as[i - k] < as[i]) ? "Yes" : "No") << endl;
	}

	return 0;
}

Measured memory_bytes: 4840
import qualified Data.Vector.Unboxed as VU
import Data.Bits
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy.Char8 as BSL
import Data.List


-- 1 <= damageOther < damageTarget <= 10^9
isPossibleWith :: VU.Vector Int -> Int -> Int -> Int -> Bool
isPossibleWith hps damageTarget damageOther numMagics
  = (<= numMagics) $ VU.sum
    $ VU.map (\hp -> max 0 $ (hp - damageMin + damageDiff - 1) `div` damageDiff)
    $ hps
  where
    damageMin = damageOther * numMagics
    damageDiff = damageTarget - damageOther

query :: VU.Vector Int -> Int -> Int -> Int
query hps damageTarget damageOther = binSearch 0 (10 ^ 9)
  where
    binSearch ng ok
      | ok - ng <= 1 = ok
      | isPossibleWith hps damageTarget damageOther mid = binSearch ng mid
      | otherwise = binSearch mid ok
      where
        mid = (ng + ok) `shiftR` 1

main :: IO ()
main = do
  [n, damageTarget, damageOther]
    <- unfoldr (BS.readInt . BS.dropWhile (==' ')) <$> BS.getLine
  hps <- VU.unfoldrN n (BSL.readInt . BSL.dropWhile (`elem` " \n\r"))
         <$> BSL.getContents
  print $ query hps damageTarget damageOther

Measured memory_bytes: 2684
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
typedef pair<int, int> S;
typedef pair<int, S> P;
map<S, vector<P>> E;
map<S, int> dist;
int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int p, q, c;
		cin >> p >> q >> c;
		E[S(p, -1)].emplace_back(1, S(p, c));
		E[S(q, -1)].emplace_back(1, S(q, c));
		E[S(p, c)].emplace_back(0, S(p, -1));
		E[S(q, c)].emplace_back(0, S(q, -1));
		E[S(p, c)].emplace_back(0, S(q, c));
		E[S(q, c)].emplace_back(0, S(p, c));
	}
	priority_queue<P, vector<P>, greater<P>> Q;
	Q.push(P(0, S(1, -1)));
	dist[S(1, -1)] = 0;
	while (!Q.empty()) {
		P p = Q.top(); Q.pop();
		if (dist[p.second] < p.first) continue;
		for (P e : E[p.second]) {
			int cost = e.first + p.first;
			if (dist.find(e.second) == dist.end() || dist[e.second] > cost) {
				dist[e.second] = cost;
				Q.push(P(cost, e.second));
			}
		}
	}
	if (dist.find(S(N, -1)) == dist.end()) {
		cout << -1 << endl;
		return 0;
	}
	cout << dist[S(N, -1)] << endl;
}

Measured memory_bytes: 91700
package main
import (
    "fmt"
)

func solveMeFirst(a uint32,b uint32) uint32{
    if (a < b) {
        return 0
    } else {
        return a - b
    }
}

func main() {
    var n int
    fmt.Scanf("%v\n", &n)
    var r int = 0
    for i := 0; i < n; i++ {
        var a, b int
        fmt.Scanf("%v %v\n", &a, &b)
        r += b - a + 1 
    }
    fmt.Println(r)
}



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

int main() {
    char n[3];
    cin >> n;

    for (int i = 0; i < 3; i++) {
        if (n[i] == '9') {
            n[i] = '1';
        } else {
            n[i] = '9';
        }
    }
    cout << n << endl;
}

Measured memory_bytes: 256
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;
use std::iter::FromIterator;
use std::cmp::min;

fn main() {
    let cin = stdin();
    let mut scan = Scanner::new(cin.lock());
    let n = scan.read::<usize>();
    let mut a = arr(n, |i| (scan.read::<i64>(), i));
    a.sort();
    let mut ret = vec![0i64;n];
    let mut min_index = n;
    for i in (0..n - 1).rev() {
        let d = a[i+1].0 - a[i].0;
        let k = n - (i + 1);
        min_index = min(min_index, a[i+1].1);
        ret[min_index] += k as i64 * d;
    }
    ret[0] += n as i64 * a[0].0;
    for i in 0..n {
        println!("{}", ret[i]);
    }
}

// region template
#[allow(dead_code)]
fn iu(i: i64) -> usize { i as usize }

#[allow(dead_code)]
fn ui(i: usize) -> i64 { i as i64 }

#[allow(dead_code, deprecated)]
fn join<T: std::fmt::Display>(slice: &[T], sep: &str) -> String {
    let strings = slice.iter().map(|t| format!("{}", t)).collect::<Vec<_>>();
    strings.connect(sep)
}

#[allow(dead_code)]
fn arr<'a, S, T>(n: usize, mut f: S) -> Vec<T> where S: FnMut(usize) -> T + 'a {
    (0..n).map(|i| f(i)).collect::<Vec<T>>()
}

#[allow(dead_code)]
fn alt<S, T>(v: Vec<S>) -> T where T: FromIterator<S> {
    v.into_iter().collect::<T>()
}

#[allow(dead_code)]
fn dup<S, T>(v: &[S]) -> T where T: FromIterator<S>, S: Clone {
    v.iter().cloned().collect::<T>()
}

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }

    fn readn<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect()
    }

    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
// endregion

Measured memory_bytes: 9212
import math
#N=int(input())
A,B,H,M = map(int,input().split())
#N=int(input())
#A = list(map(int,input().split()))
#S=str(input())

chou=6*M
tan=(H*60+M)*360/(12*60)

d=abs(chou-tan)
if d>180:
    d=360-d
ra=math.radians(d)
co=math.cos(ra)
a=A**2 + B**2 - 2*A*B*co

a=math.sqrt(a)
print(a)


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

int main(){
  string s; cin>>s;
  int dif = 650;
  for(int i=0;i<s.size()-2;i++){
    int a = (s[i] - '0')*100 + (s[i+1] - '0')*10 + (s[i+2] - '0');
    a = abs(753-a);
    dif = min(a,dif);
  }
  cout<<dif<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
using namespace std;

//ABC133 B
int main() {
	int N, D;
	cin >> N >> D;

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

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

			int dist = 0;
			for (int k=0; k<D; k++){
				dist += pow(abs(A[i][k] - A[j][k]), 2.0);
			}
			int x = sqrt(dist);
			if (pow(x, 2.0) == dist) {
				cnt++;
			}
		}
	}
	cout << cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define pvec(v) rep(i,(int)v.size()){cout << v[i] << " ";};cout<<endl;
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define Endl cout << endl
#define SIZE(s) (int)s.size()
#define Cout(n) cout<<(n)<<endl

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
const double pi = acos(-1.0);

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

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<v.size(); i++) {
		if (i)ost << ", ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}
 
ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

bool IsPrime(int num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2){
        if (num % i == 0){
            return false;
        }
    }
    return true;
}

int main()
{
	ll n,ans=1;
	cin >> n;
	vll v(n+1,0);
	for(ll i=1;i<=n;++i){
		for(ll j=2;j<=i;++j){
			ll tmp=i;
			while(tmp%j==0 && IsPrime(j)){
				v[j]++;
				tmp/=j;
			}
		}
	}
	rep(i,n+1){
		ans*=(v[i]+1);
		ans%=mod;
	}
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>mp;
    int a[n];
vector<int>v;

    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        mp[a[i]]++;
        v.push_back(a[i]);
    }
    sort(v.rbegin(),v.rend());
    v.erase(unique(v.begin(), v.end()), v.end());

    int ans=0;
    for(int i=0; i<v.size(); i++)
    {
        for(int j=30; j>=0; j--)
        {
            if(mp[v[i]]==0)
                continue;
            int x=  (1<<j)-v[i];
            if(mp.find(x)==mp.end()) continue;
            int now=mp[x];
            if(v[i]==x){
                now/=2;
            }
            else{
                now=min(mp[x],mp[v[i]]);
            }
            ans+=now;
            mp[v[i]]-=now;
            mp[x]-=now;

        }

    }
    cout<<ans<<endl;


}


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

const ll Mod = 1e9+7;

int main() {
  int N;
  cin >> N;
  map<int, int> prime;
  for (int i = 1; i <= N; ++i) {
    int m = i;
    for (int j = 2; j*j <= m; ++j) {
      while (m%j == 0) {
        prime[j]++;
        m /= j;
      }
    }
    if (m > 1) prime[m]++;
  }
  ll ans = 1;
  for (auto x : prime) ans = ans * (ll)(x.second + 1) % Mod;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <complex>
#include <assert.h>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS (1e-7)

typedef complex<double> P;
struct Line : public vector<P>
{
  Line() {
  }
  Line(P a, P b) {
    push_back(a);
    push_back(b);
  }
};

double cross(P const& a, P const& b) {
  return imag(conj(a)*b);
}

bool is_cross_ss(Line const& a, Line const& b) {
  return ( cross(a[1]-a[0], b[0]-a[0]) * cross(a[1]-a[0], b[1]-a[0]) < EPS )
    && ( cross(b[1]-b[0], a[0]-b[0]) * cross(b[1]-b[0], a[1]-b[0]) < EPS );
}

P crosspoint_ss(Line const& a, Line const& b) {
  P vb = b[1]-b[0];
  double d1 = abs(cross(vb, a[0]-b[0]));
  double d2 = abs(cross(vb, a[1]-b[0]));
  double t = d1 / (d1+d2);
  return a[0] + (a[1]-a[0]) * t;
}

bool operator == (P const& a, P const& b) {
  return ( abs(a.real()-b.real()) < EPS && abs(a.imag()-b.imag()) < EPS );
}

int main() {
  
  while(1) {
    Line l[3];
    rep(i, 3) {
      double sx, sy, gx, gy;
      cin >> sx >> sy >> gx >> gy;
      if(i == 0 && sx == 0 && sy == 0 && gx == 0 && gy == 0) return 0;
      l[i] = Line(P(sx, sy), P(gx, gy));
    }
    
    
    vector<P> ps;
    rep(i, 3) {
      if(is_cross_ss(l[i], l[(i+1)%3])) {
        P cp = crosspoint_ss(l[i], l[(i+1)%3]);
        bool ok = 1;
        rep(j, (int)ps.size())
          if(ps[j] == cp) { ok = 0; }
        if(ok) {
          ps.push_back(cp);
        }
      }
    }
    
    if(ps.size() < 3) {
      cout << "kyo\n";
      continue;
    }
    if(ps.size() > 3) {
      assert(false && "sine");
    }
    
    double ans = abs(cross(ps[2]-ps[0], ps[1]-ps[0])) / 2.;
    if(ans >= 1900000.) {
      cout << "dai-kichi\n";
    }
    else if(ans >= 1000000.) {
      cout << "chu-kichi\n";
    }
    else if(ans >= 100000.) {
      cout << "kichi\n";
    }
    else if(ans > EPS) {
      cout << "syo-kichi\n";
    }
    else {
      cout << "kyo\n";
    }
  }
  
  return 0;
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

vector<char> ans;
int main(){
    ans.clear();
    ll n;
    scanf("%lld",&n);
    while(n--){
        char tmp='a'+n%26;
        ans.push_back(tmp);
        n/=26;
    }
    for(int i=ans.size()-1;i>=0;i--) printf("%c",ans[i]);
}


Measured memory_bytes: 3724
/*                                                  Alpha_The_Coder
                                                  Created on 20/08/2020                                                     */

#include <bits/stdc++.h>
using namespace std;
#define iamalpha ios_base::sync_with_stdio(false);cin.tie(NULL);
#define loop(a,n) for(int i=a;i<n;i++)
#define nloop(a,n) for(int j=a;j<n;j++)
#define lli long long int
void solve();
int main()
{
    iamalpha;
    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }

    return 0;
}
void solve()
{
    string s;
    cin>>s;
    int consecutive_days=0;
    int i=0;
    if(s[0]=='R' && s[1]=='R' && s[2]=='R')
        consecutive_days=3;
    else if(s[0]=='R' && s[1]=='R' && s[2]=='S')
        consecutive_days=2;
    else if(s[0]=='S' && s[1]=='R' && s[2]=='R')
        consecutive_days=2;
    else if(s[0]=='S' && s[1]=='R' && s[2]=='S')
        consecutive_days=1;
    else if(s[0]=='S' && s[1]=='S' && s[2]=='S')
        consecutive_days=0;
    else if(s[0]=='R' && s[1]=='S' && s[2]=='R')
        consecutive_days=1;
     else if(s[0]=='S' && s[1]=='S' && s[2]=='R')
        consecutive_days=1;
       else if(s[0]=='R' && s[1]=='S' && s[2]=='S')
        consecutive_days=1; 
    else
        consecutive_days=0;
    cout<<consecutive_days;
}

// Solely contributed by Subhojeet Sahoo aka Alpha


Measured memory_bytes: 3608
/* Simplicity and Goodness */

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) { cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=a; i<(int)b; i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int maxN = 3e6+2;

int fac[maxN], inv[maxN];

int me(int x, int n) 
{
   int res = 1;
   while(n) {
      if(n & 1) 
         res = (1LL * res * x) % mod;
      x = (1LL * x * x) % mod;
      n >>= 1;
   }
   return res;
}

int mi(int x, int m)
{
    return me(x, m-2);
}

void fact() 
{
   fac[0] = 1;

   rep(i, 1, maxN) {
      fac[i] = (1LL * fac[i - 1] * i) % mod;
   }

   inv[maxN-1] = mi(fac[maxN-1], mod);

   for(int i = maxN - 1; i > 0; i --) {
      inv[i - 1] = (1LL * inv[i] * i) % mod;
   }
}

int nCr(int n, int k) 
{
   if(k > n)
      return 0;

   int ans = (1LL * fac[n] * inv[k]) % mod;
   ans = (1LL * ans * inv[n - k]) % mod;

   return ans;
}

int main()
{
   fact();

   int S;
   scn(S);

   int mxT = S / 3;

   ll ans = 0;

   for(int i = 1; i <= mxT; i ++) {
      ll here = S - 3 * i;

      ll ways = nCr(here + i - 1, here);

      ans = (ans + ways) % mod;
   }

   lprin(ans);

   return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln "\n"
#define show(x) cout << #x << " = " << x ln
#define dbg(x) cout<<#x"="<<x ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

string s;

int main() {
	cin >> s;
	for (int i = 0; i < s.length(); i+=2) cout << s[i];
	cout << ln;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long long ll;

template <typename T> void max_self(T& a, T b){
  a = max(a,b);
}

template <typename T> void min_self(T& a, T b){
  a = min(a,b);
}

void solve(){	
  int a,b,c,k;
  cin>>a>>b>>c>>k;

  ll sum;
  if(a < k){
    sum = a;
    k-=a;
    if(b < k){
      k-=b;
      sum -= min(c,k);
    }
  }else{
    sum = k;
  }
  cout<<sum<<endl;
  
}

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


Measured memory_bytes: 3668
#include <bits/stdc++.h>
#define fi first
#define se second
#define inf 1000000000000000000
using namespace std;

long long n, q, k;
long long dis[100005] = {0};
vector<pair<long long, long long>> edge[100005];

void solve();

int main() {
  cin >> n;
  for(int i = 0; i < n - 1; ++i) {
    long long a, b, c;
    cin >> a >> b >> c;
    --a;
    --b;
    edge[a].push_back(make_pair(b, c));
    edge[b].push_back(make_pair(a, c));
  }
  cin >> q >> k;
  --k;
  solve();
  for(int i = 0; i < q; ++i) {
    long long x, y;
    cin >> x >> y;
    cout << dis[--x] + dis[--y] << endl;
  }
  return 0;
}

void solve() {
  priority_queue<pair<long long, long long>,
                 vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      pq;
  for(int i = 0; i < n; ++i) dis[i] = inf;
  dis[k] = 0;
  pq.push(make_pair(0, k));
  while(!pq.empty()) {
    pair<long long, long long> now;
    now = pq.top();
    pq.pop();
    for(int i = 0; i < edge[now.se].size(); ++i) {
      pair<long long, long long> nextp = now;
      nextp.se = edge[now.se][i].fi;
      nextp.fi += edge[now.se][i].se;
      if(nextp.fi < dis[nextp.se]) {
        dis[nextp.se] = nextp.fi;
        pq.push(nextp);
      }
    }
  }
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
typedef unordered_map<ll,unordered_map<ll,ll>> graph;

const ll e5 = 1 << 21;
const ll mod = 1000000007;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;

ll a,b,c;

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


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define veci vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vec>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))


using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
//template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
//template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x:vec) is >> x;
    return is;
}
const ll INF=1e9+7;
class DisjointSet{
    public:
    vector<ll> rank,p;
    DisjointSet(){}
    DisjointSet(ll size){
        rank.resize(size,0);
        p.resize(size,0);
        rep(i,size) makeSet(i);
    }
    void makeSet(ll x){
        p[x]=x;
        rank[x]=0;
    }
    bool same(ll x,ll y){
        return findSet(x)==findSet(y);
    }
    void unite(ll x,ll y){
        link(findSet(x),findSet(y));
    }
    void link(ll x,ll y){
        if(rank[x]>rank[y]){
            p[y]=x;
        }
        else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }
    ll findSet(ll x){
        if(p[x]!=x){
            p[x]=findSet(p[x]);
        }
        return p[x];
    }
    
};
class Edge{
    public:
    ll source,target,cost;
    Edge(ll source=0,ll target=0,ll cost=0):
    source(source),target(target),cost(cost){}
    bool operator < (const Edge &e) const{
        return cost < e.cost;
    }
};

ll kruskal(ll n,vector<Edge> edges){
    ll totalCost=0;
    sort(edges.begin(),edges.end());
    DisjointSet dset=DisjointSet(n);
    ll source,target;
    rep(i,edges.size()){
        Edge e = edges[i];
        if(!dset.same(e.source,e.target)){ //sourceとtargetが同じ木でないとき
            totalCost += e.cost;
            dset.unite(e.source,e.target);
            
        }
    }
    return totalCost;
}
int main()
{
    ll n,m,cost;
    ll source,target;
    cin >> n >> m;
    vector<Edge> edges;
    rep(i,m){
        cin >> source >> target >> cost;
        //2つの頂点と、それを結ぶ辺の重み。sourceとtargetの順番は特に意味がない。
        edges.push_back(Edge(source,target,cost));
        
    }
    cout << kruskal(n,edges) << endl;
    return 0;
} 


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

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(all(a));
	map<int, int> mp;
	rep(i, n) {
		mp[a[i]]++;
	}
	int ans = 0;
	for(auto t: mp) {
		int k = t.first;
		int v = t.second;
		if(k  > v) {
			ans += v;
		} else {
			ans += v - k;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5120
#include<stdio.h>
#define Prime 1000000007
int main(void){
  int n,i,j;
int cnt;
  char c[202][20];
  long long dp[202][202]={{1}};
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++)
    scanf("%s",&c[i]);
cnt=0;
for(i=0;i<n;i++){
if(c[i][0]=='-')cnt++;
for(j=0;j<n+1;j++){
    if(c[i][0]=='D'){
      dp[i-cnt+1][j-cnt]+=dp[i-cnt][j-cnt]*(j-cnt);
      if(j)dp[i+1-cnt][j-1-cnt]+=dp[i-cnt][j-cnt]*(j-cnt)*(j-cnt);
      dp[i+1-cnt][j-cnt]%=Prime;
      if(j)dp[i+1-cnt][j-1-cnt]%=Prime;
    }else if(c[i][0]=='U'){
      dp[i+1-cnt][j+1-cnt]+=dp[i-cnt][j-cnt];
      dp[i+1-cnt][j-cnt]+=dp[i-cnt][j-cnt]*(j-cnt);
      dp[i+1-cnt][j+1-cnt]%=Prime;
      dp[i+1-cnt][j-cnt]%=Prime;
    }
  }}
  printf("%lld\n",dp[i-cnt][0]);
  return 0;}

Measured memory_bytes: 928