akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define MAX 100000
#define NIL -1

struct Node {int p,l,r;};

struct Node T[MAX];
int n,D[MAX];

void print(int u){
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if(T[u].p==NIL){
    printf("root, ");
  }
  else if(T[u].l==NIL){
    printf("leaf, ");
  }
  else{
    printf("internal node, ");
  }
  printf("[");

  for(i=0,c=T[u].l;c!=NIL;i++,c=T[c].r){
    if(i>0){
      printf(", ");
    }
    printf("%d",c);
  }
  printf("]\n");
}



int rec(int u,int p){
  D[u]=p;
  if(T[u].r !=NIL){
    rec(T[u].r,p);
  }
  if(T[u].l !=NIL){
    rec(T[u].l,p+1);
  }
}

int main(){
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    T[i].p=T[i].l=T[i].r=NIL;
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&v,&d);
    for(j=0;j<d;j++){
      scanf("%d",&c);
      if(j==0){
	T[v].l=c;
      }
      else{
	T[l].r=c;
      }
      l=c;
      T[c].p=v;
    }
  }
  for(i=0;i<n;i++){
    if(T[i].p==NIL){
      r=i;
    }
  }
  rec(r,0);
  for(i=0;i<n;i++){
    print(i);
  }

  return 0;
}



Measured memory_bytes: 6380
#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;

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

int xs[110];
       
int main(void) {
  int a, b, c, d, e, f;
  scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
  int resWater = -1;
  int resSugar = -1;
  REP(ia, 30) {
    REP(ib, 30) {
      REP(ic, 100) {
        REP(id, 100) {
          int water = 100*a*ia + 100*b*ib;
          int sugar = c*ic + d*id;
          if(water + sugar > f) {
            continue;
          }
          if(sugar * 100 > e * water) {
            continue;
          }
          if(water == 0 && sugar == 0) {
            continue;
          }
          if(resWater < 0 || (resSugar * (water + sugar) < sugar * (resWater + resSugar))) {
            // cerr << ia << " " << ib << " " << ic << " " << id << endl;
            resWater = water;
            resSugar = sugar;
          }
        }
      }
    }
  }
  printf("%d %d\n", resWater+resSugar, resSugar);
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		boolean result = true;
		//出発地点の初期化
		int t0 = 0, x0 = 0, y0 = 0;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i=0;i<n;i++) {
			//目的地の更新
			int t1 = sc.nextInt();
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			
			int t = t1-t0;
			int d = distance(x0,x1,y0,y1);
			//時間内に届くかを判定
			if (t < d) {
				result = false;
				break;
			}
			//偶奇が一致するか判定
			if (((t^d)&1)==1) {
				result = false;
				break;
			}
			//出発地点の更新
			t0 = t1;
			x0 = x1;
			y0 = y1;
		}
		System.out.println(result ? "Yes" : "No");
	}
	
	//2地点のマンハッタン距離を返す
	public static int distance(int x1, int x2, int y1, int y2) {
		x1 -= x2;
		y1 -= y2;
		if (x1<0)
			x1 *= -1;
		if (y1<0)
			y1 *= -1;
		return x1+y1;
	}
}


Measured memory_bytes: 85856
N = int(input())
S = list(map(ord, list(input())))
mod = 10**9+7
base = 1234
power = [1]*(N+1)
for i in range(1, N+1):
    power[i] = power[i-1]*base%mod
def check(m):
    if N-m<m:
        return False
    res = 0
    for i in range(m):
        res+=S[i]*power[m-i-1]
        res%=mod
    dic = {res:0}
    for i in range(N-m):
        res = ((res-S[i]*power[m-1])*base
                             +S[i+m])%mod
        if res in dic.keys():
            index = dic[res]
            if index +m<=i+1:
                return True
        else:
            dic[res] = i+1
    return False
ok = 0
ng = N+1
while ng-ok>1:
    mid = (ok+ng)//2
    
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)
        


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

#define int long long

int f(string x) {
    int res = 0;
    for(int i=0; i<x.size(); ++i) {
        res += x[i] - '0';
    }
    return res;
}

signed main() {
    string n;
    cin >> n;
    if(stoi(n)%f(n)==0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;
int main () {
int64_t N;
cin >> N;
int64_t ans = 0;
for (int i = 0;i <= N;i++) {
    if (i % 3 == 0) continue;
    else if (i%5 == 0) continue;
    else ans += i;
}

cout << ans << endl;

return 0;
}

Measured memory_bytes: 3636
function main(input) 
{
    input = input.split("\n");
    var integers = input[1].split(" ").map(Number);
    var counts = Array(integers.length).fill(0);

    for (i = 0; i < integers.length; i++)
        {
            while ((integers[i] % 2) == 0)
            {
                integers[i] /= 2;
                counts[i] += 1;
            }
        }
    console.log(Math.min.apply(null, counts));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7500
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define mod 1000000007
#define vll vector<ll>
#define pll vector<pair<ll,ll>>
#define debug(x) cout<<x<<endl

ll n,arr[3000],ti[3000][3000];

ll mx(ll a,ll b)
{
    if(a>=b) return a;
    else return b;
}

ll func(ll s,ll e)
{
    if(s>e) return 0;

    if(s==e)
        return arr[s];

    if(ti[s][e]!=-1)
            return ti[s][e];


    return ti[s][e]=mx(arr[s]-func(s+1,e),arr[e]-func(s,e-1));

}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll t;
	//cin>>t;
	t=1;
	while(t--){
    cin>>n;


    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
    }

    memset(ti,-1,sizeof ti);

    ll ans=func(0,n-1);

    cout<<ans<<endl;

	}
	return 0;
}


Measured memory_bytes: 74168
H,W,h,w = gets.split.map &:to_i

if H % h == 0 && W % w == 0
  puts "No"; exit
end

puts "Yes"

transposed = W % w == 0

aa,bb,a,b = W,H,w,h

if transposed
  aa,bb = bb,aa
  a,b = b,a
end

# assume: b == 1

xinf = (aa / a + 1) / (a - (aa % a))
x = xinf + 1
row = (0...aa).map{ |i| i % a == 0 ? x*(a-1)-1 : -x }
ans = (0...bb).map{ row.clone }

if transposed
  ans = ans.transpose
end

ans.each{ |row| puts row * " " }


Measured memory_bytes: 5372
#include<iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  int data[N];
  for(int i=0;i<N;i++){
    cin>>data[i];
  }
  int cnt = 1;
  int tmp = data[0];
  int num;
  if(tmp!=2){
    while (cnt < N)
    {
      tmp = data[tmp - 1];
      cnt++;
      if (tmp == 2)
      {
        break;
      }
      if (cnt==N&&tmp!=2)
      {
        cnt = -1;
        break;
      }
    }  
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream> 
#include <algorithm> 
#include <cstring> 
#include <cstdio>
#include <vector> 
#include <queue> 
#include <cstdlib> 
#include <iomanip>
#include <cmath> 
#include <ctime> 
#include <map> 
#include <set> 
using namespace std; 
#define lowbit(x) (x&(-x)) 
#define max(x,y) (x>y?x:y) 
#define min(x,y) (x<y?x:y) 
#define MAX 100000000000000000 
#define MOD 1000000007
#define pi acos(-1.0) 
#define ei exp(1) 
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f 
#define mem(a) (memset(a,0,sizeof(a))) 
typedef long long ll;
int n;
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        printf("ABC%d\n",n);
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
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 INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int k, x;
    cin >> k >> x;
    REP(i, x - k + 1, x + k - 1) cout << i << " ";
    cout << endl;
}

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


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/










//---------------------------------------------------------------------------------------------------
void _main() {
	vector<int> v;
	rep(i, 0, 3) {
		int x; cin >> x;
		v.push_back(x);
	}
	sort(all(v));

	if (v[0] == v[1] and v[1] == v[2]) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
// const ll MOD=998244353;

int main(){
  ll R,D,X; cin>>R>>D>>X;
  rep(i,10){
    X=R*X-D;
    cout<<X<<endl;
  }
  return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> q[i];
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }

    map<vector<int>, int> mp;
    do {
        mp[a] = mp.size();
    } while (next_permutation(a.begin(), a.end()));

    int ans = abs(mp[p] - mp[q]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5248
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<utility>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<time.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
const double EPS=1e-10;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
int main(){
	string q[10]={
	"0111111",
	"0000110",
	"1011011",
	"1001111",
	"1100110",
	"1101101",
	"1111101",
	"0100111",
	"1111111",
	"1101111",
	};
	int n;
	while(cin>>n,n+1){
		string s="0000000";
		rep(i,n){
			int a;
			cin>>a;
			rep(i,7)cout<<(s[i]!=q[a][i]);
			cout<<endl;
			s=q[a];
		}
	}
}

Measured memory_bytes: 1208
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define int long long
#define mod 1000000007
#define fi first
#define se second
#define be begin()
#define en end()
#define re reverse
#define Set setprecision 
const int INFi=2147483647;
const long long INFl=9223372036854775807LL;
template<typename T> T abs(T a,T b){
    return max(a,b)-min(a,b);
}
template<typename T> T lcm(T a,T b){//�Ǿ����ܿ�
  return (a*b)/gcd(a,b);
}
int  gcd(int a,int b){//��������
  int c=a%b;
  while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
  }
  return b;
}
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 n,m;
int sum;
int date[10000000];
void dfs(int a=0,int b=0){
  if(b>=3) date[sum]=a,sum++;
  if(b<m){
    dfs(a*10+3,b+1);
    dfs(a*10+5,b+1);
    dfs(a*10+7,b+1);
  }
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    int c=n,d=0;
    while(true){
      if(c==0) break;
      m++;
      c/=10;
    }
    dfs();
    for(int i=0;i<sum;i++){
      if(date[i]<=n&&date[i]!=0){
	int e=0,f=0,g=0;
	while(true){
	  if(date[i]==0) break;
	  if(date[i]%10==3) e=1;
	  if(date[i]%10==5) f=1;
	  if(date[i]%10==7) g=1;
	  date[i]/=10;
	}
	if(e+f+g==3) d++;
      }
    }
    cout<<d<<"\n";
}


Measured memory_bytes: 512
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
p=min(a)+min(b)
for i in range(M):
	x,y,c=map(int,input().split())
	q=a[x-1]+b[y-1]-c
	if q<=p:
		p=q
print(p)

Measured memory_bytes: 18648
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


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

uf = UnionFind(n+1)

for i in range(m):
    a, b = map(int, input().split())
    uf.union(a, b)

ans = 1
for i in range(1, n+1):
    ans = max(ans, uf.size(i))

print(ans)


Measured memory_bytes: 14792
#include<stdio.h>
#define low 100010

int main()
{
    int type,amount,i,a[100],sum,left,min,total;

    scanf("%d %d",&type, &amount);

    for(i=0, sum=0, min=low; i<type ; i++)
    {
        scanf("%d",&a[i]);

        sum = sum + a[i];

        if(a[i]<min)
            min = a[i];
    }

    left = amount - sum;

    total = type + (left/min);

    printf("%d",total);

    return 0;
}


Measured memory_bytes: 1692
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
#define CL(a,b) memset(a,b,sizeof a)
#define pb push_back
#define fi first
#define sc second
#define pi pair<int,int>
#define pii pair<int,pair<int,int>>
const int N=1e5+7,p=1e9+7;
int a[N];
ll t,sum;
ll qpow(int x,int b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*x%p;
        x=(ll)x*x%p;
        b>>=1;
    }
    return ans;
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    ll ans=0;
    if(k==1)
    {
        printf("0");
        return 0;
    }
    t=1;
    int flag=k,f=1;
    for(int i=n-k+1;i>=1;i--)
    {
        sum=(sum+t*a[i]%p)%p;
        t=(t*flag%p)*qpow(f,p-2)%p;
        flag++;
        f++;
    }
    sum=-sum;
    t=1;
    flag=k;
    f=1;
    for(int i=k;i<=n;i++)
    {
        sum=(sum+t*a[i]%p)%p;
        t=t*flag%p*qpow(f,p-2)%p;
        flag++;
        f++;
    }
    printf("%lld",(sum%p+p)%p);
    return 0;
}



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

int main() {
  int X;
  cin>>X;
  if(X>=400&&X<=599) cout<<8<<endl;
  else if(X>=600&&X<=799) cout<<7<<endl;
  else if(X>=800&&X<=999) cout<<6<<endl;
  else if(X>=1000&&X<=1199) cout<<5<<endl;
  else if(X>=1200&&X<=1399) cout<<4<<endl;
  else if(X>=1400&&X<=1599) cout<<3<<endl;
  else if(X>=1600&&X<=1799) cout<<2<<endl;
  else if(X>=1800&&X<=1999) cout<<1<<endl;
}

Measured memory_bytes: 3592
line = gets.chomp.split(' ')
a = line[0].to_i
b = line[1].to_i
c = line[2].to_i

x = line[3].to_i
y = line[4].to_i

total = 0;

min = x < y ? x : y

if c * 2 < a + b
  total = c * min * 2

  if x - min > 0
    if a < c * 2
      total += a * (x - min)
    else
      total += c * 2 * (x - min)
    end
  end

  if y - min > 0
    if b < c * 2
      total += b * (y - min)
    else
      total += c * 2 * (y - min)
    end
  end
else
  total = a * x + y * b
end

puts total

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <algorithm>
#include <iomanip> //cout << fixed << setprecision(12) << ans << endl;
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define loop(i, l, r) for(int i = l; i < r; i++)
#define rloop(i, l, r) for(int i = l; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vec_i;
typedef pair<int,int> pair_ii;
typedef pair<ull,ull> pair_ull;
 
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const int INF = 1e9;
const int MOD = 1e9+7;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int n;
	cin >> n;
	vec_i a(n);
	vec_i c(n);
	int cost = 0;

	rep(i,n){
		cin >> a[i];
		a[i]--;
	} 
	rep(i,n){
		int b;
		cin >> b;
		cost += b;
	}
	rep(i,n-1) cin >> c[i];
	
	rep(i,n-1){
		if(a[i]+1 == a[i+1]){
			cost += c[a[i]];
		}
	}
	cout << cost << endl;
}

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

int main(void){
	char str[1001];
	int i;
	
	scanf("%s",str);
	for(i=0;i<strlen(str);i++){
		if(str[i]=='C')
		str[i]=90;
		else if(str[i]=='B')
		str[i]=89;
		else if(str[i]=='A')
		str[i]=88;
		else
		str[i]-=3;
		printf("%c",str[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 524
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  map<string, int> mp;
  mp["SUN"] = 7;
  mp["MON"] = 6;
  mp["TUE"] = 5;
  mp["WED"] = 4;
  mp["THU"] = 3;
  mp["FRI"] = 2;
  mp["SAT"] = 1;
  string s;
  cin >> s;
  cout << mp[s] << endl;
  return 0;
}

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

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

	int d;
	int A;
	int num[100];
	int ans = 0;


	for (int i = 0; i < 100; i++) {
		num[i] = 0;
	}

	for (int j = 0; j < K; j++) {
		cin >> d;

		for (int i = 0; i < d; i++) {
			cin >> A;
			num[A - 1]++;
		}
	}

	for (int i = 0; i < N; i++) {
		if (num[i] == 0) ans++;
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 3676
#include <cstdio>

#define MAX_S 12

class Trie {
public:
  bool exist;
  char c;
  Trie* child[4];
  Trie(bool exist,char c);
  ~Trie();
  void addNext(Trie* trie,int id);
};
Trie::Trie(bool exist,char c) {
  this->exist = exist;
  this->c = c;
  for(int i=0;i<4;i++) {
    this->child[i] = NULL;
  }
}
Trie::~Trie() {}
void Trie::addNext(Trie* trie,int id) {
  this->child[id] = trie;
}
Trie* root = new Trie(true,'$');

int charToid(char c) {
  switch(c) {
    case 'A': return 0;
    case 'C': return 1;
    case 'G': return 2;
    case 'T': return 3;
  };
  return -1;
}

void insert(char *str) {
  Trie* t = root;
  for(int i=0;str[i]!='\0';i++) {
    int id = charToid(str[i]);
    if(t->child[id] == NULL) {
      Trie* next_t = new Trie(false, str[i]);
      t->addNext(next_t,id);
    }
    t = t->child[id];
  }
  t->exist = true;
}

bool find(char *str) {
  Trie* t = root;
  for(int i=0;str[i]!='\0';i++) {
    int id = charToid(str[i]);
    if(t->child[id] == NULL) {
      Trie* next_t = new Trie(false, str[i]);
      t->addNext(next_t,id);
    }
    t = t->child[id];
  }
  return t->exist;
}

int main(void) {
  int n; scanf("%d", &n);
  char str[MAX_S+1];
  bool exist;
  while(n--) {
    scanf("%s", str);
    if(str[0] == 'i') {
      // insert
      scanf("%s", str);
      insert(str);
    } else if(str[0] == 'f') {
      // find
      scanf("%s", str);
      if(find(str)) printf("yes\n");
      else printf("no\n");
    }
  }
}

Measured memory_bytes: 23248
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

using namespace std;

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define F(i,j,k) fill(i[0],i[0]+j*j,k)
#define P(p) cout<<(p)<<endl;
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define INF 1<<25
#define pb push_back

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

int main()
{
    int n, p;
    while (cin >> n >> p, n|p) {
        int cup = p;
        int i = 0;
        vi v(n, 0);
        while(1){
            if (cup == 0) {
                cup += v[i];
                v[i] = 0;
                i = (i+1) %n;
            } else {
                cup--;
                v[i]++;
                if (p == v[i])
                    break;
                i = (i+1) % n;
            }
        }
        cout << i << endl;
    }
    return 0;
}

Measured memory_bytes: 1196
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N,M = II()
a = III()
b = []
for a0 in a:
    b.append(a0//2)
x = lcm_list(b)

for b0 in b:
    if (x//b0)%2==0:
        print(0)
        exit()

print((M//x+1)//2)

Measured memory_bytes: 89580
main = interact $ unlines . map (show . coconut_grab . read) . init . lines

coconut_grab :: Int -> Int
coconut_grab e = coconut_grab_z e 0 ((ceiling.cbrt.fromIntegral) e)
 where
  coconut_grab_z e' n x
   | x == 0 =  coconut_grab_y e' x ((ceiling.sqrt.fromIntegral) e')
   | x^3 == e' = x
   | x^3 > e' = coconut_grab_z e' n (x-1)
   | otherwise = coconut_grab_y (e'-x^3) x ((ceiling.sqrt.fromIntegral) (e'-x^3)) `min` coconut_grab_z e' n (x-1)
  
  coconut_grab_y e' n x
   | x^2 == e' = n + x
   | x^2 > e' = coconut_grab_y e' n (x-1)
   | otherwise = n + x + (e'-x^2)
                       
cbrt q = until approx (\q' -> q' - (q'^3-q) / (3*q'^2)) (q/2)
 where approx x = abs (x^3 - q) < 0.00001*q

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

#define int long long
#define itn int
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'
#define SZ(x) ((int)(x).size())
#define bit(n) (1LL << (n))
constexpr int MOD = 1e9 + 7;

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
using P = pair<int, int>;
using vec = vector<int>;
template <typename T>
using mat = vector<vector<T>>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

// clang-format off
template<typename T>
bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T>
bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template <typename T>
int index(const T& vec, const typename T::iterator it) { return distance(vec.begin(), it); }
template <typename T = int>
mat<T> mmat(int n, int m) { return mat<T>(n, vector<T>(m)); }
template <typename T = int>
vector<T> ivec(int n) { vector<T> v(n); init(v); return v; }
// clang-format on

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;
    print(e - a > k ? ":(" : "Yay!");

    return 0;
}


Measured memory_bytes: 256
s = input()

if s == "SUN":
    s = 7
elif s == "MON":
    s = 6
elif s == "TUE":
    s = 5
elif s == "WED":
    s = 4
elif s == "THU":
    s = 3
elif s == "FRI":
    s = 2
else:
    s = 1

print(s)

Measured memory_bytes: 2940
// problem: "https://atcoder.jp/contests/abc148/tasks/abc148_c"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main()
{
    ll a,b,m;
    cin>>a>>b;

    m = min(a,b);

    while(m)
    {
        if(a%m == 0 && b%m == 0)
            break;

        m--;
    }

    cout<<a*b/m;

    return 0;
}


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

int main(){
    int x,y;
    cin >> x  >> y;
    if (x > 3){
        x = 4;
    }
    if(y > 3){
        y = 4;
    }
    int c1 = 100000*(4-x);
    int c2 = 100000*(4-y);
    cout << (c1 == 300000 && c2 == 300000 ? c1 + c2 + 400000 : c1 + c2) << endl;
}

Measured memory_bytes: 256
#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
using namespace std;
int a,b,n;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
		if(ch=='-')
			f=-1;
		ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
    }
    return x*f;
}
inline void write(int a)
{
    if(a<0)
    {
		putchar('-');
		putchar('1');
    }
    else
    {
		if(a>=10)
			write(a/10);
		putchar(a%10+'0');
    }
}

int main()
{
    a=read(),b=read();
	n=read();
	int ans=n/max(a,b);
	if(ans*max(a,b)<n)
		++ans;
	cout<<ans;
    return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

var N uint64
var K uint64
var R uint64
var S uint64
var P uint64
var T string

func main() {

	fmt.Scanf("%v", &N)
	fmt.Scanf("%v", &K)
	fmt.Scanf("%v", &R)
	fmt.Scanf("%v", &S)
	fmt.Scanf("%v", &P)
	fmt.Scanf("%v", &T)

	//fmt.Printf("N=%v K=%v R=%v S=%v P=%v\n", N,K,R,S,P)

	// 全部勝つパターンを作る
	win := make([]byte, len(T))
	for i := 0; i < len(T); i++ {
		switch T[i] {
		case 'r':
			win[i] = 'p'
		case 's':
			win[i] = 'r'
		case 'p':
			win[i] = 's'
		}
	}

	var score uint64

	for i := uint64(0); i < K; i++{
		score += maxScore(win, i, K)
	}

	fmt.Printf("%v\n", score)
}

func maxScore(win []byte, start uint64, step uint64) uint64 {
	var score uint64

	// 連続している所は、偶数番目を諦める
	var prev byte = ' '
	var n uint64 = 0
	for i := start; i < uint64(len(T)); i+=step {
		if win[i] == prev {
			n++
//			fmt.Printf("i=%d, win[i]=%v same as prev. n=%d\n", i, win[i], n)
		} else {
			// prevの点数を足す
			var base uint64
			switch prev {
			case 'r':
				base = R
			case 's':
				base = S
			case 'p':
				base = P
			}
			add := base * ((n + 1) / 2)
//			fmt.Printf("i=%d, prev %v same chars %d adding %v\n", i, prev, n, add)
			score += add
			prev = win[i]
			n = 1
		}
	}
	// prevの点数を足す
	var base uint64
	switch prev {
	case 'r':
		base = R
	case 's':
		base = S
	case 'p':
		base = P
	}
	add := base * ((n + 1) / 2)
	score += add
	//fmt.Printf("prev %v same chars %d adding %v. base=%v, n=%v\n", prev, n, add, base, n)
	return score

}



Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {
	public static int ceil(int a, int b){
		int x = (a + (b - 1))/b;
		return x;
	}

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long N = sc.nextInt();
		long ans;
		ans = N*(N-1)/2;
		// 出力
		System.out.println(ans);
	}
}

Measured memory_bytes: 21844
import itertools
n = int(input())
counters = {"M":0,"A":0,"R":0,"C":0,"H":0}

for _ in range(n):
  s = input()[0]
  
  if s in "MARCH":
  	counters[s] += 1
res = 0
for i in list(itertools.combinations(["M","A","R","C","H"],3)):
  res += counters[i[0]] * counters[i[1]] * counters[i[2]]

print(res)

Measured memory_bytes: 9116
#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {
  int w, h, n;
  cin >> w >> h >> n;
  int x[n], y[n], a[n];
  int wxl=0, wxr=w, wyb = 0, wyu = h;
  for (size_t i = 0; i < n; i++) cin >> x[i] >> y[i] >> a[i];

  for (size_t i = 0; i < n; i++) {
    if (a[i]==1) wxl = max(wxl, x[i]);
    else if (a[i]==2) wxr = min(wxr, x[i]);
    else if (a[i]==3) wyb = max(wyb, y[i]);
    else wyu = min(wyu, y[i]);
  }

  int ans = 0;
  if (wxl < wxr && wyb < wyu) ans = (wxr-wxl)*(wyu-wyb);

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define FOR(i, m, n) for(ll i = m; i < (n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>; 
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;

int main() {
    string S;
    cin >> S;
    string a = "";
    rep(i, 3){
        a += S[i];
    }
    cout << a;
}

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

int main() {
  ll x1 = 0, y1 = 0, x2 = 0, y2 = 0;
  cin >> x1 >> y1 >> x2 >> y2;
  ll x3 = 0, y3 = 0, x4 = 0, y4 = 0;
  x3 = x2 + y1 - y2;
  y3 = y2 + x2 - x1;
  x4 = x1 + y1 - y2;
  y4 = y1 + x2 - x1;
  cout << x3 << " " << y3 << " " << x4 << " " << y4;
}

Measured memory_bytes: 256
n,k = gets.split(" ").map(&:to_i)
a =  gets.split(" ").map(&:to_i).slice(0,n)


head = a[0]
for i in 1..(n-k) do
    last = a[i+k-1]
    puts last > head ? "Yes" : "No"
    head = a[i]
end


Measured memory_bytes: 33872
M, K = map(int, input().split())
if K >= 2 ** M:
    print(-1)
    exit(0)
if M == 1:
    if K == 1:
        print(-1)
    else:
        print('0 0 1 1')
    exit(0)
A = [i for i in range(2 ** M) if i != K]
print(' '.join(str(a) for a in A), K, ' '.join(str(a) for a in reversed(A)), K)


Measured memory_bytes: 101644
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define ed "\n"
void YN(bool flg){cout<<(flg?"YES":"NO")<<endl;}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<endl;}
void yn(bool flg){cout<<(flg?"yes":"no")<<endl;}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << endl;
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int64_t, int >prime_factor(int64_t n){map< int64_t, int > ret;for(int64_t i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> getDivisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    REP(i,10)REP(j,10)if(i*j==n){cout << "Yes" << endl; return 0;}
    cout << "No" << endl;

    return 0;
}

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

public class Main {
	public static void main(String[]args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String a = br.readLine();
		String[] b = a.split(" ");
		long S = Long.parseLong(b[2]); 
		long D = Long.parseLong(b[0]);
		long T = Long.parseLong(b[1]);
		double result = (double)D/S ;
		if(result <= T) 
			System.out.println("Yes");
		else
			System.out.println("No");

		
		
	}

}


Measured memory_bytes: 32708
s = input()
weather = ['Sunny', 'Cloudy', 'Rainy', 'Sunny'] 
class Weather_Prediction:
#  def __init__(self):

  def solve(self, s):
    self.s = s
    ind = weather.index(s) +1
    ans_index = weather[ind]
    return ans_index
  
solver =   Weather_Prediction()
anser = solver.solve(s)
print(anser)
    
  


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int N=100005,inf=0x3f3f3f3f;
int n,tot,dis[N],h[N],ne[N<<1],to[N<<1],w[N<<1];
deque<int> q;
void add(int x,int y,int z) {to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void bfs() {
	for(RI i=0;i<n;++i) dis[i]=inf;
	dis[1%n]=1,q.push_back(1%n);
	while(!q.empty()) {
		int x=q.front();q.pop_front();
		for(RI i=h[x];i;i=ne[i])
			if(dis[x]+w[i]<dis[to[i]]) {
				dis[to[i]]=dis[x]+w[i];
				if(!w[i]) q.push_front(to[i]);
				else q.push_back(to[i]);
			}
	}
}
int main()
{
	scanf("%d",&n);
	for(RI i=0;i<n;++i) add(i,(i+1)%n,1),add(i,i*10%n,0);
	bfs(),printf("%d\n",dis[0]);
	return 0;
}

Measured memory_bytes: 3584
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<iomanip>
using namespace std;
typedef long long ll;
ll dx[4] = {0,-1,1,0};
ll dy[4] = {-1,0,0,1};
int INF = 1e9+7,h,w,d[51][51],allw = 0,changew = 0;
char c[51][51];
queue<pair<int,int>> Q;
int main(void){
    cin >> h >> w;
    for(int i = 0;i < h;i++){
        for(int j = 0;j < w;j++){
            cin >> c[i][j];
            d[i][j] = INF;
            if(c[i][j] == '.') allw++;
        }
    }
    d[0][0] = 0;
    Q.push({0,0});
    while(!Q.empty()){
        int y = Q.front().first;
        int x = Q.front().second;
        Q.pop();
        for(int i = 0;i < 4;i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(0 <= ny && ny < h && nx >= 0 && nx < w && d[ny][nx] == INF && c[ny][nx] == '.'){
                Q.push({ny,nx});
                d[ny][nx] = d[y][x]+1;
            }
        }
    }
    if(d[h-1][w-1] == INF) cout << -1 << endl;
    else cout << allw - (d[h-1][w-1]+1);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i, n) for(int i = 1; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	string s; cin >> s;
	if (s[s.size() - 1] == 's') {
		cout << s + "es" << endl;
	}
	else {
		cout << s + "s" << endl;
	}
}

Measured memory_bytes: 3644
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int k=sc.nextInt();
        long ans=0;


        for(int i=1;i<=k;i++){
            for(int j=1;j<=k;j++){
                for(int l=1;l<=k;l++){
                    ans+=helper(i,j,l);
                }
            }
        }
        System.out.println(ans);
    }

    private static long helper(int i, int j, int k) {

        long temp=gcd(i,j);
        long ans=gcd(temp,k);
        return ans;
    }

    private static long gcd(long a, long b) {
        if(b==0) return a;
        else
            return gcd(b,a%b);
    }
}


Measured memory_bytes: 35844
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 30 09:04:16 2018

@author: Yamazaki Kenichi
"""
L,N = map(int, input().split(' '))
X = [int(input()) for i in range(N) ]

#inp = input().split()
#inp = [int(i) for i in inp]
#L, N = inp[0],inp[1]
#X = inp[2:]

X = [0] + X 
temp = L - X[1]
ans =  temp

itr1 = 0
itr2 = N

a = N%2

for i in range(-(N-1),N):
    if (i+a)%2 == 1:
        itr1 += 1
    else:
        itr2 -= 1

    if X[i]-X[i-itr1] >=0:
        minus = X[i]-X[i-itr1]
    else:
        minus = L+(X[i]-X[i-itr1])

    if X[i+itr2]-X[i] >=0:
        plus = X[i+itr2]-X[i]
    else:
        plus = L+(X[i+itr2]-X[i])
    temp = temp - minus + plus
#    print(temp)
    ans = max(ans,temp)
print(ans)

    



Measured memory_bytes: 12716
#f(r,c)=(r+c)_C_r
r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
N=2*(10**6)+10
def inv(x):
    return pow(x,mod-2,mod)
Fact=[0 for i in range(N+1)]
Fact[0]=1;
for i in range(N):
    Fact[i+1]=(i+1)*Fact[i]
    Fact[i+1]%=mod
def C(n,k):
    res=Fact[n]*inv(Fact[n-k])
    res%=mod
    res*=inv(Fact[k])
    res%=mod
    return res
ans1=(((r2+2)*inv(c2+1))%mod)*C(c2+r2+2,r2+2)
ans2=(((r2+2)*inv(c1))%mod)*C(c1+r2+1,r2+2)
ans3=(((r1+1)*inv(c2+1))%mod)*C(c2+r1+1,r1+1)
ans4=(((r1+1)*inv(c1))%mod)*C(c1+r1,r1+1)
ans1%=mod
ans2%=mod
ans3%=mod
ans4%=mod
print((ans1-ans2-ans3+ans4)%mod)


Measured memory_bytes: 82200
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int K_MAX = 1e5+5;
vector<int> dp(K_MAX,1e9);
bool update(int &x,int y){
  if(x>y){
    x = y;
    return true;
  }
  return false;
}

int solve(){
  int K;cin >> K;
  deque<int> dq(1,1);
  dp[1] = 1;
  int u;
  while(true){
    //cout << dq.front().first SP dq.front().second << endl;
    u = dq.front(); dq.pop_front();
    if(u==0) break;
    if(update(dp[u*10%K], dp[u])) dq.push_front(u*10%K);
    if(update(dp[(u+1)%K], dp[u]+1)) dq.push_back((u+1)%K);
  }
  return dp[0];
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cout << solve() << endl;
  return 0;
}


Measured memory_bytes: 896
from math import *
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

def f(p):
    if len(p) == 1:
        return 1
    i = sorted(p).index(p[0])
    return factorial(len(p)-1)*i + f(p[1:])

print(abs(f(p)-f(q)))

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <tuple>
using namespace std;
const int mod = 1000000007;

int main() {

		
	string one, two, three;
	cin >> one >> two >> three;
	if (one[one.size() - 1] == two[0] && two[two.size() - 1] == three[0]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	

}

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

int main(void)
{
    int n, d, x;
    cin >> n >> d >> x;

    int ans = x;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;

        int c = 1;
        do {
            ans++;
            c += a;
        } while(c <= d);
    }
    
    cout << ans;

    return 0;
}


Measured memory_bytes: 256
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
a = LIST()
s = sum(a)
arr = [0 for _ in range(n)]
arr[0] = a[0]
ans = [inf for _ in range(n)]
ans[0] = abs(a[0] - (s - a[0]))
for i in range(1, n - 1):
    arr[i] = arr[i - 1] + a[i]
    ans[i] = abs(arr[i] - (s - arr[i]))
print(min(ans))


Measured memory_bytes: 104600
N = int(input())
numbers = [int(n) for n in input().split(' ')]
distances = []
counter = 0
for i in range(0, len(numbers)):
    if i == len(numbers) - 1:
        distances.append(counter)
        break
    if numbers[i] >= numbers[i + 1]:
        counter += 1
    else:
        distances.append(counter)
        counter = 0
print(max(distances))

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int INF=1e9;
int main(){
	int S;cin>>S;
	int h,m,s;
	s=S%60;S/=60;
	m=S%60;S/=60;
	h=S;
	cout<<h<<":"<<m<<":"<<s<<endl;
	return 0;
}


Measured memory_bytes: 3084
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin >> n >> m;
    ll s,t;
    cin >> s >> t;
    s--; t--;
    vector<vector<pair<ll, pair<ll,ll> > > > nei(n);
    REP(i,m){
        ll u,v,a,b;
        cin >> u >> v >> a >> b;
        u--; v--;
        nei[u].pb(make_pair(v,make_pair(a,b)));
        nei[v].pb(make_pair(u,make_pair(a,b)));
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq;
    vll ds(n,LLINF);
    vll dt(n,LLINF);
    ds[s] = 0;
    pq.push(make_pair(0,s));
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        for(auto q : nei[p.se]){
            if(ds[q.fi]>ds[p.se]+q.se.fi){
                ds[q.fi] = ds[p.se]+q.se.fi;
                pq.push(make_pair(ds[q.fi], q.fi));
            }
        }
    }
    ll ini = (ll)1e15;
    dt[t] = 0;
    pq.push(make_pair(0,t));
    while(!pq.empty()){
        auto p = pq.top();
        pq.pop();
        for(auto q : nei[p.se]){
            if(dt[q.fi]>dt[p.se]+q.se.se){
                dt[q.fi] = dt[p.se]+q.se.se;
                pq.push(make_pair(dt[q.fi], q.fi));
            }
        }
    }
    vector<pair<ll,ll> > dis(n);
    REP(i,n){
        dis[i] = make_pair(ds[i]+dt[i],i);
    }
    sort(ALL(dis));
    ll now = 0;
    REP(i,n){
        while(dis[now].se+1<=i){
            now++;
        }
        printf("%lld\n", ini - dis[now].fi);
    }
    return 0;
}

Measured memory_bytes: 14328
n,k=map(int,input().split())
a=list(map(int,input().split()))
#for i in range(k):
#  syaku*=a[i]
#now=syaku
for i in range(k,len(a)):
  #pre=now
  #now=now*a[i]//a[i-k]
  if a[i]>a[i-k]:
    print("Yes")
  else:
    print("No")
  

Measured memory_bytes: 94268
# coding: utf-8
import math
A, B, H, M = map(int, input().split())
H = H * 30 + ((M / 60) * 30)
M = M * 6
deg = min(abs(H - M),360 - abs(H - M))
ans = A**2 + B**2 - (2 * A * B * math.cos(math.radians(deg)))
ans = ans**0.5
print(ans)

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

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll a, b, n;
  cin >> a >> b >> n;
  n = min(n, b - 1);
  cout << (a * n) / b;
  return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int s=0, p=n;
	while(p>0)
	{
		s+=p%10;
		p=p/10;
	}
	if(n%s==0)cout <<"Yes"<<endl;
	else cout << "No"<<endl;
	return 0; 
}


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

int main(){
	int a[9];
	int b[9];
	int c=0;
	int d=0;
	int i=0;
	int s[9];
	
	for(i=0;i<9;i=i+3){
		cin>>a[i];
		cin>>a[i+1];
		cin>>a[i+2];
		cin>>b[i];
		cin>>b[i+1];
		cin>>b[i+2];
	}
	for(i=0;i<9;i=i+3){
		c=a[i]*3600+a[i+1]*60+a[i+2];
		d=b[i]*3600+b[i+1]*60+b[i+2];
		c=d-c;
		s[i+2]=c%60;
		c=(c-s[i+2])/60;
		s[i+1]=c%60;
		c=(c-s[i+1])/60;
		s[i]=c;
	}
	for(i=0;i<9;i=i+3){
		cout<<s[i]<<" "<<s[i+1]<<" "<<s[i+2]<<endl;
	}
}
		
		

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	a.erase(unique(a.begin(), a.end()), a.end());
	int ans = 1;
	int f = a[0] > a[1] ? false : true;;
	for (int i = 2; i < a.size(); i++) {
		if (a[i - 1] > a[i]) {
			if (f) {
				ans++;
				i++;
				if (i >= n) break;
				f = a[i - 1] > a[i] ? false : true;
			}
		}
		else if (a[i - 1] < a[i]) {
			if (!f) {
				ans++;
				i++;
				if (i >= n) break;
				f = a[i - 1] > a[i] ? false : true;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 640