akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#define N 20
#define Max 2000

int dec(int,int);
int X[Max],Y[Max];
int m,n;

int main()
{
  int i;

  scanf("%d",&n);

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

  scanf("%d",&m);

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

  for(i=0;i<m;i++)
    {
      if(dec(0,Y[i])==1) printf("yes\n");
      else printf("no\n");
    }
  
  return 0;
}

int dec(int s, int t)
{
  int a,b;
  if(t==0) return 1;
  else if(s>=n) return 0;
  a = dec(s+1,t-X[s]);
  b = dec(s+1,t);
  if(a==1 || b==1) return 1;
    
  return 0;
}

Measured memory_bytes: 588
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
int dp[5050][5050];
string s;
int main() {
	cin >> N >> s;

	for (int i=N-1; i>=0; i--) {
		for (int j=N-1; j>i; j--) {
			if (s[i] != s[j]) continue;
			dp[i][j] = min({dp[i+1][j+1]+1, j-i, N-j});

		}
	}

	int mx = 0;
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			mx = max(mx, dp[i][j]);
		}
	}

	cout << mx;
}

Measured memory_bytes: 98688
#include <bits/stdc++.h>
#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 INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int facctorialMethod(int k){
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

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

  vector<vector<double>> x(N,vector<double>(2));
  REP(i, N){
    REP(j, 2){
      cin >> x.at(i).at(j);
    }
  }
  
  long double sum = 0;
  REP(i,N){
    FOR(j,i+1,N){
      sum+=sqrt((x.at(i).at(0)-x.at(j).at(0))*(x.at(i).at(0)-x.at(j).at(0))+(x.at(i).at(1)-x.at(j).at(1))*(x.at(i).at(1)-x.at(j).at(1)));
    }
  }
  if(N>=3){
    sum = sum*(2*facctorialMethod(N-1));
    cout << fixed << setprecision(10) << sum/facctorialMethod(N) << endl;
  }else{
    cout << fixed << setprecision(10) << sum << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

int main() {
    int n;
    int count = 0;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
        while (a.at(i) % 2 == 0) {
            a.at(i) /= 2;
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 384
import fractions
A, B, C, D = map(int, input().split())
Cdiv = B // C - (A - 1) // C
Ddiv = B // D - (A - 1) // D
gcd_CD = int(C * D / fractions.gcd(C, D))
CDdiv = B // gcd_CD - (A - 1) // gcd_CD
result = int(B - (A - 1) - Cdiv - Ddiv + CDdiv)
print(result)

Measured memory_bytes: 5048
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N,L;cin>>N>>L;
  vector<string> vec(N);
  for(int i=0;i<N;i++){
    cin>>vec[i];
  }
  
  sort(vec.begin(),vec.end());
  
  for(int i=0;i<N-1;i++){
    cout<<vec[i];
  }
  cout<<vec[N-1]<<endl;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
    ll n, m;
    cin >> n >> m;
    if(m % 2 == 1) m--;
    if(n <= m / 2) {
        cout << n + (m - 2 * n) / 4 << endl;
    }
    else {
        cout << m / 2 << endl;
    }
    return 0;
}


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

const int N = 200005;
const long double EPS = 1e-9;
const long double PI = acos(-1.);


int main()
{
//    #ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    #endif

    int r ;
    cin >> r;
    printf("%.4Lf\n" , PI*r*2);

    return 0;
}




















Measured memory_bytes: 3760
N,L = map(int,input().split())
lis =[]

for i in range(N):
    i += 1

    lis.append(L + i - 1)

#print (lis)

mini = 0


for i in range(len(lis)):

    j = max(lis[i],-lis[i])
    k = max(lis[mini],-lis[mini])
        
    if i == 0 or k >= j:

        mini = i
    
        
        #print ("最小は",lis[i],i)



ans = 0
for i in range(len(lis)):

    if i != mini:
        ans += lis[i]
   

print (ans)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res = Type()){
    ll N,K; cin >> N >> K;
    for(ll n = 1; n <= N; n++){
        double p = 1.0/N;
        ll now = n;
        while(now < K){
            now *= 2;
            p *= 0.5;
        }
        res += p;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    // solve(0);
    cout << fixed << setprecision(15) << solve<double>() << endl;
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Thanksgiving
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0227

"""
import sys


def solve(n, m, prices):
    ans = 0
    for i in range(0, n, m):
        t = prices[i:i+m]
        if len(t) == m:
            t[-1] = 0
        ans += sum(t)
    return ans


def main(args):
    while True:
        n, m = map(int, input().split())
        if n == 0 and m == 0:
            break
        prices = sorted([int(p) for p in input().split()], reverse=True)
        ans = solve(n, m, prices)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])



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

using namespace std;
long long N, D;
long long tmp = 0;
int main(){
	cin>>N>>D;
	for(int i = 0; i<N; i++){
        long long X, Y, tmpp = 0;
        cin>>X>>Y;
        tmpp += X*X + Y*Y;
        if( tmpp <= D*D){
            tmp += 1;
        }
	}
	cout<<tmp;
	return 0;
}

Measured memory_bytes: 3616
#include<iostream>
using namespace std;
#include<vector>
#define int long long int
int answer=1000000000;
void function(vector<int> &vec,int initial,int final,vector<int> &vec1,vector<int> &vec2,vector<int> &vec3,int a,int b,int c)
{
	if(initial>final)
	{
		if(!vec1.size()||!vec2.size()||!vec3.size())
		     return ;
		int val1=0,val2=0,val3=0;
		for(int x:vec1)
		    val1+=x;
		for(int x:vec2)
		   val2+=x;
		for(int x:vec3)
		   val3+=x;
		int here=0;
		here+=(10*(vec1.size()-1));
		here+=(10*(vec2.size()-1));
		here+=(10*(vec3.size()-1));
		here+=(abs(a-val1)+abs(b-val2)+abs(c-val3));
		answer=min(answer,here);
		return ;
	}
	else
	{
		function(vec,initial+1,final,vec1,vec2,vec3,a,b,c);
		vec1.push_back(vec[initial]);
		function(vec,initial+1,final,vec1,vec2,vec3,a,b,c);
		vec1.pop_back();
		vec2.push_back(vec[initial]);
		function(vec,initial+1,final,vec1,vec2,vec3,a,b,c);
		vec2.pop_back();
		vec3.push_back(vec[initial]);
		function(vec,initial+1,final,vec1,vec2,vec3,a,b,c);
		vec3.pop_back();
	}
}
int32_t main()
{
	int n,a,b,c;
	cin>>n>>a>>b>>c;
	int j;
	vector<int> vec(n);
	for(j=0;j<n;j++)
	{
		cin>>vec[j];
	}
	vector<int> vec1,vec2,vec3;
	function(vec,0,n-1,vec1,vec2,vec3,a,b,c);
	cout<<answer<<endl;
}


Measured memory_bytes: 3636
/**
 *    author:  nasimnoob
**/

#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<math.h>
using namespace std;

typedef long long                       ll;
typedef unsigned long long              ull;
typedef long double                     ld;


#define      PI                         3.141592654


int main()
{
    //string ;
    int a,b;
    cin>>a>>b;
    if(a>b)
        cout<<"safe"<<endl;
    else
        cout<<"unsafe"<<endl;
    return 0;
}




Measured memory_bytes: 3636
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A, B):
    S = sum(B)


    ab = min(A[0], B[0])
    A[0] -= ab
    B[0] -= ab
    
    for i in range(1, N):
        ab = min(A[i], B[i-1])
        A[i] -= ab
        B[i-1] -= ab

        ab = min(A[i], B[i])
        A[i] -= ab
        B[i] -= ab
    ab = min(A[N], B[N-1])
    A[N] -= ab
    B[N-1] -= ab
    
    return S - sum(B)


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(slv(N, A, B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 21020
# Kから各頂点への距離をメモする
# xからKの距離とyからKの距離を足したものが答え

import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b,c = map(int,readline().split())
  G[a-1].append((b-1,c))
  G[b-1].append((a-1,c))

dist = [-1 for i in range(N)] # Kからの距離
Q,K = map(int,readline().split())

dist[K - 1] = 0
from collections import deque
# 頂点、Kからの距離, 親
q = deque([[K - 1, 0, -1]])
while q:
  v, d, parent = q.popleft()
  dist[v] = d
  for child in G[v]:
    if child[0] == parent:
      continue
    q.append([child[0],d + child[1], v])

for i in range(Q):
  x,y = map(int,readline().split())
  print(dist[x - 1] + dist[y - 1])
  

Measured memory_bytes: 50348
#include <bits/stdc++.h>
using namespace std;
using vec = vector<char>;
using intk = int64_t;

int main() {
string S;
  cin >>S;
  int N = S.size();
  vec e = {'q','w','e','r','t','y','u','i','o','p','a','s','d','f','g','h','j','k','l','z','x','c','v','b','n','m'};
  vector<pair<int,char>> K(26);
  for(int i=0;i<26;i++) K[i] = make_pair(0,e[i]);
  for(int i=0;i<N;i++){
    for(int j=0;j<26;j++){
   if(K[j].second == S[i] ) K[j].first++; 
  }
  }
  sort(K.begin(),K.end());
  if(K[0].first >=1) cout << "None"<<endl;
  else cout << K[0].second <<endl;
}

Measured memory_bytes: 512
import math

def abc133_b():
    N, D = map(int, input().split())
    X = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i):
            sq = 0
            for k in range(D):
                sq += (X[i][k] - X[j][k]) ** 2
            rt = math.floor(math.sqrt(sq) + 0.5)
            if rt * rt == sq: ans += 1
    print(ans)

abc133_b()

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

constexpr int MAX_N=2000;

int n,z,w;
int a[MAX_N];

int dp[MAX_N][2];

int main() {

    std::cin>>n>>z>>w;

    for(int i=0;i<n;++i)
        std::cin>>a[i];

    int ans=abs(w-a[n-1]);

    if(n>1)
        ans=std::max(ans,abs(a[n-2]-a[n-1]));

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

    return 0;
}

Measured memory_bytes: 256
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

a,b,c,d = inpl()
res = 0
for i in range(a,d+1):
    if i <= b and i >= c:
        res += 1
print(max(0,res-1))

Measured memory_bytes: 38384
/*
 * 1 以上 9 以下の数字のみからなる文字列 S が与えられます。 この文字列の中で、あなたはこれら文字と文字の間のうち、いくつかの場所に + を入れることができます。 一つも入れなくてもかまいません。
 * ただし、+ が連続してはいけません。
 * 
 * このようにして出来る全ての文字列を数式とみなし、和を計算することができます。
 * 
 * ありうる全ての数式の値を計算し、その合計を出力してください。
 */

import java.util.*;
	public class Main{
		public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            // 入力
            long s = Long.parseLong(sc.next());
            int sLen = String.valueOf(s).length();
            
            // 出力
            System.out.println(makeSum(s, sLen));

            sc.close();
        }
		
		public static long makeSum(long s, int sLen){
			long ret = 0;
			
            for(int i=0; i<sLen-1; i++){
            	ret += Integer.parseInt(String.valueOf(s).substring(0, i+1)) * Math.pow(2, sLen-i-2) + makeSum(Integer.parseInt(String.valueOf(s).substring(i+1)), sLen-i-1);
            }
            
            return ret+s;
        }
    }
	

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<string,int>;

const int MOD = 1e9 + 7;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    int n, a, b;
    cin >> n >> a >> b;

    a *= n;

    cout << min(a, b) << endl;

    return 0;
}



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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line = null;
        while ((line = in.readLine()) != null) {
            int d = Integer.parseInt(line);
            int x = 0;
            int s = 0;
            while (x <= 600 - d) {
                s += x * x * d;
                x += d;
            }
            
            System.out.println(s);
        }
    }
}



Measured memory_bytes: 24008
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n,m,ans=1e11;
ll frac(ll a,ll b)
{
	if(a>b) return b;
	else return frac(a,b/a)+b%a;
}
int main ()
{
	scanf("%lld%lld",&n,&m);
	if(n==m) 
	{
		printf("%lld",n+1);
		return 0;
	}
	if(m>n)
	{
		printf("-1");
		return 0;
	}
	for(ll i=2;i<=sqrt(n)+1;i++)
		if(frac(i,n)==m)
		{
			printf("%lld",i);
			return 0;
		}
	for(ll i=1;i<=sqrt(n-m);i++)
		if(((n-m)%i==0)&&(frac((n-m)/i+1,n)==m)&&((n-m)/i+1<ans))
			ans=(n-m)/i+1;
	if(ans!=1e11)
		printf("%lld",ans);
	else
		printf("-1");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(void){

    int input;
    cin >> input ;
    
    int ac = 0, tle = 0, wa = 0, re = 0;
    string s;

    for(int i = 0; i < input; i++){
        cin >> s ;
        if(s == "AC"){
            ac++;
        } else if (s == "TLE"){
            tle++;
        } else if (s == "WA"){
            wa++;
        } else if (s == "RE"){
            re++;
        }
    }
    
    cout << "AC x " << ac << endl;
    cout << "WA x " << wa << endl;
    cout << "TLE x " << tle << endl;
    cout << "RE x " << re << endl;

}


Measured memory_bytes: 3624
import itertools
n = int(input())
l = [int(i) for i in input().split()]
ls = list(itertools.combinations(range(n),3))
ans = 0
if n < 3:
    print(0)
else:
    for i in range(len(ls)):
        index_ls = list(ls[i])
        tmp_ls = [l[index_ls[0]],l[index_ls[1]],l[index_ls[2]]]
        tmp_ls.sort()
        if tmp_ls[0] + tmp_ls[1] > tmp_ls[2]:
            if tmp_ls[0] == tmp_ls[1] or tmp_ls[1] == tmp_ls[2] or tmp_ls[0] == tmp_ls[2]:
                continue
            else:
                ans += 1
    print(ans)


Measured memory_bytes: 90564
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int N = int.Parse(str[0]);
		int K = int.Parse(str[1]);
		int ans = 0;
		string[] str2 = Console.ReadLine().Split();
		for(var i=0;i<N;i++){
			int a = int.Parse(str2[i]);
			if(a>=K){
				ans++;
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 15584
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

int main(){
  int N;
  cin >> N;
  double ret = 0;
  for(int i=0;i<N;i++){
    string x,u;
    cin >> x >> u;
    double v = 0;
    if(u == "JPY"){
      v = stod(x);
    }
    else{
      v = stod(x) * 380000;
    }
    ret += v;
  }
  cout << setprecision(10) << ret << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
char s[1100];
int w,l;
int main(){
	cin>>s>>w;
	l=strlen(s);
	for(int i=0;i<l;i+=w)printf("%c",s[i]);
	return 0;
}

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

int main(int argc, char const *argv[]) {
    int h, n;
    cin >> h >> n;
    long long asum = 0;
    for (size_t i = 0; i < n; i++) {
        int a;
        cin >> a;
        asum += a;
    }

    if (asum >= h) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3636
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    for(int i=0;i<s.length();i+=2){
      System.out.print(s.charAt(i));
    }
    System.out.println();
  }
}


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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

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

int main() {
  cout << setprecision(18);
  u32 K;
  cin >> K;
  u64 res = 0;
  for (u32 i = 1; i <= K; ++i) {
    for (u32 j = 1; j <= K; ++j) {
      u32 tmp = gcd(i, j);
      for (u32 k = 1; k <= K; ++k) {
        res += gcd(k, tmp);
      }
    }
  }
  cout << res << endl;
}


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

class Program
{
    static void Main(string[] args)
    {
        var N = sc.ReadLong();
        var divs = Divisor(N);
        var ans = int.MaxValue;
        for (int i = 0; i < divs.Length; i++)
        {
            var x = divs[i];
            var y = N / divs[i];
            var res = Math.Max(x.ToString().Length, y.ToString().Length);
            ans = Math.Min(ans, res);
        }
        Console.WriteLine(ans);
    }

    static long[] Divisor(long n)
    {
        var res = new List<long>();
        for (long i = 1; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                res.Add(i);
                if (i * i != n) res.Add(n / i);
            }
        }
        return res.ToArray();
    }

    static Scanner sc = new Scanner();
}

class Scanner
{
    string[] S = new string[0];
    int Index = 0;
    char[] Separators = new char[] { ' ' };

    public string Next()
    {
        if (this.Index < this.S.Length) return this.S[this.Index++];
        var line = "";
        while (line == "") line = Console.ReadLine();
        this.S = line.Split(this.Separators, StringSplitOptions.RemoveEmptyEntries);
        if (this.S.Length == 0) return this.Next();
        this.Index = 0;
        return this.S[this.Index++];
    }
    public string ReadStr()
    {
        return this.Next();
    }
    public char ReadChar()
    {
        return this.Next()[0];
    }
    public int ReadInt()
    {
        return int.Parse(this.Next());
    }
    public uint ReadUInt()
    {
        return uint.Parse(this.Next());
    }
    public long ReadLong()
    {
        return long.Parse(this.Next());
    }
    public double ReadDouble()
    {
        return double.Parse(this.Next());
    }
    public int[] ReadIntArray(int n)
    {
        var array = new int[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadInt();
        }
        return array;
    }
    public long[] ReadLongArray(int n)
    {
        var array = new long[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadLong();
        }
        return array;
    }
    public double[] ReadDoubleArray(int n)
    {
        var array = new double[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadDouble();
        }
        return array;
    }
    public char[] ReadCharArray(int n)
    {
        var array = new char[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadChar();
        }
        return array;
    }
    public string[] ReadStrArray(int n)
    {
        var array = new string[n];
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = this.ReadStr();
        }
        return array;
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define eb emplace_back
#define MP make_pair
#define pb push_back
#define pf push_front
#define ins insert
#define all(v) (v).begin(), (v).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define tr(c,it) for(auto it=c.begin();it!=c.end();it++)
#define fr(i,n) for(lli i=0;i<(n);i++)
#define inc(i,a,b) for(lli i=a;i<=b;i++)
#define dec(i,a,b) for(lli i=a;i>=b;i--)
#define fr2(i,n) for(int i=0;i<(n);i++)
#define inc2(i,a,b) for(int i=a;i<=b;i++)
#define dec2(i,a,b) for(int i=a;i>=b;i--)
#define ymin(a,b)  (a=min((a),(b)))
#define ymax(a,b)  (a=max((a),(b)))
#define sz(x) (lli)(x).size()
typedef long long int lli;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef vector<lli> vlli;
typedef vector<int> vi;
//typedef  vector<vector<lli> >ncr(1001,vector<lli>(1001,0))
typedef vector<plli> vplli;
long long MOD=1000000009;
double startTime;
double getCurrentTime()
{
	return ((double)clock()-startTime)/CLOCKS_PER_SEC;
}

lli pwr(lli x,lli n)
{
	lli res=1;
	for(; n!=0;n>>=1)
	{
		if(n&1)
			res=(res*x)%MOD;
		x=(x*x)%MOD;
	}
	return res;
}
lli inver(lli num)
{
	return pwr(num,MOD-2);
}
lli findncr(lli n,lli r)
{
	r=min(r,n-r);
	if(n==0||n==1||r==0)
		return 1;
	lli numer=1;
	for(lli i=n;i>=n-r+1;i--)
		numer=(numer*i)%MOD;
	lli den=1;
	for(lli i=2;i<=r;i++)
		den=(den*i)%MOD;
	den=inver(den);
	lli res=(numer*den)%MOD;
	return res;
}
lli gcd(lli a,lli b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}
int main()
{
	// 	#ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS
	string s,t;
	cin>>s>>t;
	vector<vector<int> >dp(sz(s)+1,vector<int>(sz(t)+1,0));

	//int dp[sz(s)+1][sz(t)+1]={0};
	//cout<<dp[0][0]<<" ";
	for(int i=1;i<=sz(s);i++)
	{
		for(int j=1;j<=sz(t);j++)
		{
			//cout<<s[i-1]<<" "<<t[j-1]<<endl;
			if(s[i-1]==t[j-1])
					//cout<<s[i-1];
				dp[i][j]=dp[i-1][j-1]+1;
			
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		//cout<<dp[i][j]<<" ";

		}
		//cout<<endl;
	}
	int l=dp[sz(s)][sz(t)];
		string str;
		int ii=sz(s);
		int jj=sz(t);
		while(ii>0 &&  jj>0)
		{
			if(s[ii-1]==t[jj-1])
			{
				str=s[ii-1]+str;
				ii--;
				jj--;
			}
			else if(dp[ii-1][jj]>dp[ii][jj-1])
				ii--;
			else
				jj--;
		}
		cout<<str;
	}

	//cout<<dp[sz(s)][sz(t)]<<endl;


Measured memory_bytes: 35584
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] d = new int[n];
		int i;
		for(i = 0; i < n; i++) {
			d[i] = scan.nextInt();
		}
		Arrays.sort(d);

		int low = n / 2 - 1;
		int hi = n / 2;

		int ans;
		if(d[low] == d[hi]) {
			ans = 0;
		}else {
			ans = d[hi] - d[low];
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 52828
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define ve vector
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)

int main(){
    ll n,k;
    cin >> n >> k;
    ve<ll> a(n);
    rep(i,n) cin >> a[i];
    sort(a.begin(), a.end());
    ll l = 0, r = a[n-1];
    while(r-l>1){
        ll x = (l+r)/2;
        ll cnt=0;
        rep(i,n){
            cnt += (a[i]+x-1)/x-1;
        }
        if(cnt <= k)r=x;
        else l = x;
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 4748
<?php
list($n,$p)=explode(" ",trim(fgets(STDIN)));
if($n==1){
echo $p;
}elseif($p==1){
echo 1;
}else{
$ans=1;
$i=2;
while(pow($i,$n)<=$p){
$c=pow($i,$n);
if($p%$c==0){
$p/=(int)$c;
$ans*=$i;
--$i;
}
++$i;
}
echo $ans;
}

Measured memory_bytes: 4604
"""
高橋君は N 枚の AtCoder せんべいを 
K 人の AtCoder 参加者になるべく公平に配ることにしました。
 N 枚すべてのせんべいを配るとき、
 せんべいを最も多くもらった人と
 最も少なくもらった人のもらったせんべいの
 枚数の差(の絶対値)の最小値を求めてください。
"""

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

if (N % K) == 0:
    diff = 0
else:
    diff = 1

print(diff)

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

int main(){
	string s ; cin >> s ;
	int ans = 100000 ;
	for(int i=2;i<s.size();i++){
		int sub = 100*(s.at(i-2)-'0')+10*(s.at(i-1)-'0')+(s.at(i)-'0') ;
		ans = min(ans,max(sub,753)-min(sub,753)) ;
	}
	cout << ans << endl ;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <cstdio>
#include <string>
#define FI first
#define SE second
#define PF push_front
#define PB push_back
#define PPF pop_front
#define PPB pop_back
#define MA make_pair
#define ll long long
#define PA pair<int,int>
#define VE vector<int>
#define VP vector<PA>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define POSSIBLE(i) cout<<(i?"POSSIBLE":"IMPOSSIBLE")<<endl
#define Possible(i) cout<<(i?"Possible":"Impossible")<<endl
using namespace std;
//
const int INF=1e9+7;
const int mod=998244353;
//
struct poi{
	int X;int Y;int Z;
	bool operator<(const poi&R)const{
		return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
	}
};
//
ll GCD(ll A,ll B){
  return (B==0)?(A):(GCD(B,A%B));
}
ll LCM(ll A,ll B){
  return A/GCD(A,B)*B;
}
//
int main(){
	int N;
	ll A[300][300];
	vector<pair<ll,pair<int,int> > > V;
	cin>>N;
	FOR(i,0,N){
		FOR(j,0,N){
			cin>>A[i][j];
			if(i<j){
				V.PB(MA(A[i][j],MA(i,j)));
			}
			if(i!=j){
				A[i][j]=1e15;
			}
		}
	}
	sort(V.begin(),V.end());
	ll ans=0;
	FOR(k,0,V.size()){
		ll v=V[k].FI;
		int x=V[k].SE.FI;
		int y=V[k].SE.SE;
		if(A[x][y]>v){
			ans+=v;
			FOR(i,0,N){
				FOR(j,0,N){
					A[i][j]=min(A[i][j],A[i][x]+v+A[y][j]);
					A[i][j]=min(A[i][j],A[i][y]+v+A[x][j]);
				}
			}
		}
	}
	FOR(i,0,V.size()){
		ll v=V[i].FI;
		int x=V[i].SE.FI;
		int y=V[i].SE.SE;
		if(A[x][y]!=v){
			cout<<-1<<endl;
			return 0;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1784
import numpy as np
N,M = map(int,input().split())
A = [[int(i) for i in input().split()] for _ in range(N)]

ans=0
for i in range(1,M+1):
    count=0
    for j in range(N):
        if i in A[j][1:]:
            count+=1
        if count==N:
            ans+=1
print(ans)


Measured memory_bytes: 27092
Number = list(input())

#while Number > 0:
#    list.append(Number % 10)
#    Number //= 10
#    list.reverse()

op_count = len(Number) - 1
for i in range(2**op_count):
    op = ["-"] * op_count
    for j in range(op_count):
        if((i >> j) & 1):
            op[op_count - 1 - j] = "+"

    temp = Number[0] + op[0] + Number[1] + op[1] + Number[2] + op[2] + Number[3]
    if eval(temp) == 7:
        print(temp + "=7")
        break


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

m = 0
B = []
for a in A:
    if a < 0:
        m += 1
    B.append(abs(a))

if m % 2 == 0:
    print(sum(B))
else:
    print(sum(B)-2*min(B))

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

using namespace std;
double ans=0.00000;
int anss,answ;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,d,e,f;
    cin>>a>>b>>c>>d>>e>>f;
    for(int i=0;i<=30;i++){
        for(int j=0;j<=30;j++){
            for(int k=0;k<=(3000+(c-1))/c;k++){
                for(int l=0;l<=(3000+(d-1))/d;l++){
                    int totwater = 100*(a*i+b*j);
                    int totsugar = c*k + d*l;
                    
                    if(totwater+totsugar>f){
                        break;
                    }
                    if(totwater*e/100<totsugar){
                        break;
                    }
                    
                    
                    if(totwater == 0){
                        continue;
                    }
                    
                    if((double)((double)100*(double)totsugar/((double)totwater+(double)totsugar))>=(double)ans){
                        ans = ((double)100*(double)totsugar/((double)totwater+(double)totsugar));
                        answ = totwater+totsugar;
                        anss = totsugar;
                      //  cout<<100*(i+j)<<" "<<totsugar*e<<endl;
                    }
                }
            }
        }
    }
    cout<<answ<<" "<<anss<<endl;
    //cout<<ans<<endl;
}

Measured memory_bytes: 384
n,a,b = gets.split.map &:to_i
x = gets.split.map &:to_i
m = 0
x.each_cons(2) do |x1,x2|
    r=(x2 - x1)*a
    if r > b 
        m += b
    else
        m += r
    end
end
p m

Measured memory_bytes: 8452
#include <iostream>

using namespace std;
int main(void){
    char s;
    int A[4] = {0};
    while(cin >> s){
        if(s == 'K') A[0]++;
        if(s == 'U') A[1]++;
        if(s == 'P') A[2]++;
        if(s == 'C') A[3]++;
    }
    int min = 300;
    for(int i = 0; i < 4; i++){
        if(A[i] < min) min = A[i];
    }
    cout << min << endl;

    return 0;
}



Measured memory_bytes: 3132
#include<bits/stdc++.h>
#include<chrono>
                             
using namespace std;
using namespace std::chrono;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MP make_pair
#define REP(i,a,b) for(i=a;i<=b;i++)
#define RAP(i,a,b) for(i=a;i>=b;i--)
const ll mod=10000007;
const int MX=0x3f3f3f;

int main(){
    IOS;
    int n,i;
    string s,t;
    cin>>n;
    cin>>s>>t;
    REP(i,0,n-1) cout<<s[i]<<t[i];
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,l,n) for(int i=l;i<n;i++)
#define rer(i,l,n) for(int i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

string change(string s,int a,int b){
	string ret(s);
	rep(i,0,ret.size()){
		int y=ret[i]-'a';
		if(y>=0 && y<26){
			y=(a*y+b)%26;
			ret[i]='a'+y;
		}
	}
	return ret;
}

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

int main(){
	int n;
	cin>>n;
	//string tt;
	//getline(cin,tt);
	//n = atoi(tt.c_str());
	//cout<<n<<" "<<tt<<endl;
	cin.ignore();
	string str[2]={"that","this"};
	rep(i,0,n){
		string s;
		bool f=0;
		getline(cin,s);
		//o(s);
		rep(a,0,26){
			if(gcd(a,26)!=1) continue;
			rep(b,0,26){
				string t;
				t=change(s,a,b);
				//o(t);
				rep(j,0,2){
					if(t.find(str[j]) != string::npos){
						o(t); f=1; break;
					}
				}
				if(f) break;
			}
			if(f) break;
		}

	}
}

Measured memory_bytes: 1220
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        // 入力
        var n = long.Parse(Console.ReadLine());
        long m = 0;
        long a = 0;
        long r = 0;
        long c = 0;
        long h = 0;
        for (int i = 0; i < n; i++)
        {
            string tmp = (Console.ReadLine());
            switch (tmp[0])
            {
                case 'M':
                    m++;
                    break;
                case 'A':
                    a++;
                    break;
                case 'R':
                    r++;
                    break;
                case 'C':
                    c++;
                    break;
                case 'H':
                    h++;
                    break;
            }
        }

        long[] x = new long[5];
        x[0] = m;
        x[1] = a;
        x[2] = r;
        x[3] = c;
        x[4] = h;
        long ans = 0;
        for (int i = 0; i < x.Length-2; i++)
        {
            for (int k = i+1; k < x.Length-1; k++)
            {
                for (int t = k+1; t < x.Length; t++)
                {
                    ans += x[i]*x[k]*x[t];
                }
            }
            
        }

        Console.WriteLine(ans);


    }
}


Measured memory_bytes: 15188
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG_OUTPUT
#define DEBUG_LOG(s) cout << s << endl;
#else
#define DEBUG_LOG(s) void();
#endif

class Combination {
private:
    int64_t mod; // 元, 素数でないとNG
    int64_t max_size; // 最大値, 10^7まで
    int64_t* factorial;
    int64_t* inverse;
    int64_t* inverse_factorial;
    // vector<int64_t> factorial; // 階乗
    // vector<int64_t> inverse; // 逆元
    // vector<int64_t> inverse_factorial; // 逆元の階乗

    void init() {
        // 値は1で初期化する
//        factorial.assign(max_size, 1);
//        inverse.assign(max_size, 1);
//        inverse_factorial.assign(max_size, 1);
        factorial = new int64_t[max_size];
        inverse = new int64_t[max_size];
        inverse_factorial = new int64_t[max_size];
        factorial[0] = factorial[1] = 1;
        inverse[1] = 1;
        inverse_factorial[0] = inverse_factorial[1] = 1;
        for (auto i = 2; i < max_size; i++) {
            factorial[i] = factorial[i - 1] * i % mod;
            inverse[i] = mod - inverse[mod % i] * (mod / i) % mod; // 拡張Euclidの互除法の変形版
            // inverse[i] = modinv(i); // Fermatの小定理
            inverse_factorial[i] = inverse_factorial[i - 1] * inverse[i] % mod;
            // cout << i << " " << factorial[i] << " " << inverse[i] << " " << inverse_factorial[i] << endl;
        }
    };
public:;
    Combination(int64_t mod, int64_t max_size) {
        this->mod = mod;
        assert(max_size < 1e7);
        this->max_size = max_size + 1;
        // テーブル生成
        init();
    };
    virtual ~Combination(){
        delete factorial;
        delete inverse;
        delete inverse_factorial;
    };

    int64_t modpow(int64_t a, int64_t n) {
        int64_t ret = 1;
        while(n > 0) {
            if(n & 1) ret = ret * a % mod;
            a = a * a % mod;
            n >>= 1;
        }
        return ret;
    };
    int64_t modinv(int64_t a) { return modpow(a, mod - 2); };
    int64_t combination(int64_t n, int64_t k) {
        if (n < k) return 0;
        if (n < 0 or k < 0) return 0;
        // cout << factorial[n] << " " << inverse_factorial[k] << " " << inverse_factorial[n - k] << endl;
        return factorial[n] * (inverse_factorial[k] * inverse_factorial[n - k] % mod) % mod;
    };
};

int main(){
    int x, y;
    cin >> x >> y;

    int a = x / 2, b = (x - a * 2);
    while(y != a + b * 2) {
        a--; b+=2;
        // cout << a << " " << b << " " << a * 2 + b << " " << a + b * 2 << endl;
        if(a < 0 or b > y / 2) {
            cout << 0 << endl;
            return 0;
        }
    }

    int64_t mod = 1e9+7, n = a + b;
    Combination c(mod, n);

    cout << c.combination(n, a) % mod << endl;
    return 0;
}

Measured memory_bytes: 18784
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

using namespace std;

//----------------------- Print Function ----------------------//

inline void print() {
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest) {
    cout << first << ' ';
    print(rest...);
}

//------------------------- Libraries -------------------------//

long long gcd(long long a, long long b){
    if (a < b) swap(a, b);
    return b ? gcd(b, a % b) : a;
}

long long lcm(long long a, long long b){
    return a * b / gcd(a, b);
}

//--------------------------- Solve ---------------------------//

int f(int n) {
    int res = 0;
    while (n % 2 == 0) {
        n /= 2;
        res++;
    }
    return res;
}

void solve() {
    int N, M; cin >> N >> M;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        a[i] /= 2;
    }

    int num = f(a[0]);
    long long l = 1;
    for (int i = 0; i < N; i++) {
        if (f(a[i]) != num) {
            cout << 0 << '\n';
            return;
        }

        l = lcm(l, a[i]);
        if (l > M) {
            cout << 0 << '\n';
            return;
        }
    }

    int ans = (M - l) / (2*l) + 1;
    cout << ans << '\n';
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
 
const int INF = 10000000;



int main(){
	int n;
	cin>>n;
	bool f = true;
	ll s = 0LL, a;
	char c;
	rep(i, n){
		cin>>c>>a;
		if(c == ')') a=-a;
		s += a;
		if(s < 0) f = false;
	}
	cout<<(f&&s==0?"YES":"NO")<<endl;
}

Measured memory_bytes: 1168
import sys

def reconst(pre, ino):
    if len(pre) == 0:
        return
    elif len(pre) == 1:
        print pre[0],
        return

    root = ino.index(pre[0])
    preLeft, preRight = pre[1:root + 1], pre[root + 1:]
    inLeft, inRight = ino[:root], ino[root + 1:]

    reconst(preLeft, inLeft)
    reconst(preRight, inRight)
    print pre[0],

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    pre = map(int, lines[1].split())
    ino = map(int, lines[2].split())
    reconst(pre, ino)

Measured memory_bytes: 6464
#include <stdio.h>

typedef long long int ll;
const int mod = 1000000007;

ll dp[1001];
int fact[1001];
int ifact[1001];

int modpow(int n, int k){
  int r = 1;
  for(;k;k>>=1){
    if(k&1) r = (ll) r * n % mod;
    n = (ll) n * n % mod;
  }
  return r;
}

int main(){
  int i, j, k, n, a, b, c, d;

  fact[0]=1;
  for(i=1;i<=1000;i++) fact[i] = (ll) i * fact[i-1] % mod;
  ifact[1000] = modpow(fact[1000], mod-2);
  for(i=999;i>=0;i--) ifact[i] = (ll) (i+1) * ifact[i+1] % mod;
  
  
  scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);

  for(i=1;i<=n;i++){
    if((i%a==0) && (i/a>=c) && (i/a<=d)){
      dp[i] = (ll) fact[i] * ((ll) modpow(ifact[a], i/a) * ifact[i/a] % mod) % mod;
    }
  }
  dp[0] = 1;

  for(j=a+1;j<=b;j++){
    int f = modpow(ifact[j], c);
    for(i=n;i>=0;i--){
      int tmp = f;
      ll tmp1 = 0;
      for(k=c; k<=d && k*j<=i; k++){
        tmp1 = (tmp1 + dp[i-k*j] * tmp % mod * ifact[i-k*j] % mod * ifact[k]) % mod;
        tmp = (ll) tmp * ifact[j] % mod;
      }
      dp[i] = (dp[i] + tmp1 * fact[i]) % mod;
    }
  }

  printf("%lld\n", dp[n]);
  return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
using namespace std;
int x[110][2],w[110][2],n;
bool cal[110];
int COU(int a,int b){
 while(true){
  if(a<2||b<2)return 1;
  if(a<b){int t=a;a=b,b=t;}
  a%=b;
  if(!a)return b;
 }
}
long long DFS(int q){
    if(!q)return 1;
    q--;
    long long a=DFS(w[q][0]),b=DFS(w[q][1]);
    return (a*b*(x[q][0]+x[q][1]))/COU(a*x[q][0],b*x[q][1]);
}
int main(){
 while(true){
 cin>>n;
 if(!n)break;
 for(int i=0;i<n;i++)cal[i]=false;
 for(int i=0;i<n;i++){
  cin>>x[i][0]>>x[i][1]>>w[i][0]>>w[i][1];
  cal[w[i][0]-1]=true,cal[w[i][1]-1]=true;
 }
 for(int i=0;i<n;i++){
  if(!cal[i])cout<<DFS(i+1)<<endl;
 }
 }
 return 0;
}

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

int main() {
  int N, M = 1e9+7;
  cin >> N;
  vector<int> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  sort(A.begin(), A.end());
  if (N % 2) {
    B.at(0) = 0;
    for (int i = 1, b = 0; i < N; i++) B.at(i) = (i % 2) ? b += 2 : b;
  } else {
    B.at(0) = B.at(1) = 1;
    for (int i = 2, b = 1; i < N; i++) B.at(i) = (i % 2) ? b : b += 2;
  }
  long ans = 1, cnt = N / 2;
  while (cnt--) (ans *= 2) %= M;
  cout << ((A == B) ? ans : 0) << "\n";
}

Measured memory_bytes: 1024
#define dbg(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define dpri(x) dbg(#x ": %d\n", x)
#define dprs(x) dbg(#x ": %s\n", x)
#include <stdio.h>
typedef long long ll;
const int MYINF = 1e9+7;
typedef int bool;
const bool true = 1;
const bool false = 0;

int a[50];
int fib (int n) {
	if (a[n]) return a[n];
	if (n < 2) return a[n] = 1;
	return a[n] = fib(n-1) + fib(n-2);
}

int main(int argc, char **argv)
{
	int n;
	scanf("%d", &n);
	printf("%d\n", fib(n));
	return 0;
}

Measured memory_bytes: 596
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
import math

l = []
for _ in range(4):
  l.append(int(input()))

a, b, c, x = l
# 最大使用可能回数
a_c = min(a, math.floor(x / 500) if x >= 500 else 0 )
b_c = min(b, math.floor(x / 100) if x >= 100 else 0 )
c_c = min(c, math.floor(x / 50)  if x >= 50  else 0 )

i, j, k, sum, cnt = [0] * 5  
while (i <= a_c):
  sum = x - 500 * i
  if sum < 0:
    break
  if sum == 0:
    cnt += 1

  else:
    while (j <= b_c):
      sum = x - 500 * i - 100 * j
      if sum < 0:
        break
      if sum == 0:
        cnt += 1

      else:
        while (k <= c_c):
          sum = x - 500 * i - 100 * j - 50 * k
          if sum < 0:
            break
          if sum == 0:
            cnt += 1
          k += 1
        k = 0

      j += 1
    j = 0

  i += 1

print(cnt)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
long long int __lcm(long long int a,long long int b){
  long long int n;
  n=a*b/__gcd(a,b);
  return n;
}
 //__gcd 最大公約数
 //__lcm 最小公倍数
 //double 少数（変数）
//sqrt 平方根
//ceil 天井関数
//floor 床関数
//abs 絶対値
//pow 累乗
//cbrt  立方根
//hypot 平方和の平方根
 
int main() {
  int a,b;
  cin>>a>>b;
  vector<int> c(b),d(b);
  for(int i=0;i<b;i++)
    cin>>c[i]>>d[i];
  sort(c.begin(),c.end());
  sort(d.begin(),d.end());
  cout<<max(0,d[0]-c[b-1]+1);
  }

Measured memory_bytes: 1024
/*
ID: anonymo14
TASK: wormhole
LANG: C++                 
*/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int,int>> vpii;

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back
#define REP(i,a,b) for(int i=a; i<=b; i++)
#define MOD 1000000007

void solve(int test_case) {//209
	int a,b;
	cin>>a>>b;
	if(a>0&&b>0)cout<<"Positive";
	else if((a<=0&&b>=0)||(a>=0&&b<=0))cout<<"Zero";
	else {
		a=-a;b=-b;
		a=abs(a-b)+1;
		if(a&1)cout<<"Negative";
		else cout<<"Positive";
	}
}

int main() {
	
	////// FILE BASED IO////
	//freopen("wormhole.in", "r", stdin);
	//freopen("wormhole.out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	//prefill();
	REP(i,1,t) {
		solve(i);
	}
	return 0;
}	


Measured memory_bytes: 3632
#include <cstdio>
using namespace std;

struct Node
{
	int parent, left, right;
public:
	Node() { parent = left = right = -1; }
};

Node T[30];

void Preorder(int u)
{
	printf(" %d", u);
	if (T[u].left != -1) Preorder(T[u].left);
	if (T[u].right != -1) Preorder(T[u].right);
}

void Inorder(int u)
{
	if (T[u].left != -1) Inorder(T[u].left);
	printf(" %d", u);
	if (T[u].right != -1) Inorder(T[u].right);
}

void Postorder(int u)
{
	if (T[u].left != -1) Postorder(T[u].left);
	if (T[u].right != -1) Postorder(T[u].right);
	printf(" %d", u);
}

int main()
{
	int n;
	scanf("%d", &n);

	int v, l, r;
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &v, &l, &r);
		T[v].left = l;
		T[v].right = r;
		if (T[v].left != -1) T[l].parent = v;
		if (T[v].right != -1) T[r].parent = v;
	}

	int x;
	for (int i = 0; i < n; i++) {
		if (T[i].parent == -1) {
			x = i;
			break;
		}
	}
	printf("Preorder\n");
	Preorder(x);
	printf("\n");

	printf("Inorder\n");
	Inorder(x);
	printf("\n");

	printf("Postorder\n");
	Postorder(x);
	printf("\n");

	return 0;
}

Measured memory_bytes: 1044