akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

void printArray(int* A, int n) {
    for (int i = 0; i < n; ++i) {
        if (i != 0) { cout << " "; }
        cout << A[i];
    }
    cout << endl;
}

void countingSort(int* A, int* B, int n, int k) {
    int* C = new int[k+1];
    for (int i = 0; i <= k; ++i) {
        C[i] = 0;
    }
    for (int i = 0; i < n; ++i) {
        ++C[A[i]];
    }
    //printArray(C, k+1);
    for (int i = 1; i <= k; ++i) {
        C[i] += C[i-1];
    }
    //printArray(C, k+1);
    for (int i = n-1; i >= 0; --i) {
        B[--C[A[i]]] = A[i];
    }
    delete[] C;
}

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    int* A = new int[n];
    int* B = new int[n];

    int k = 0;
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        if (k < A[i]) {
            k = A[i];
        }
    }

    countingSort(A, B, n, k);
    printArray(B, n);

    return 0;
}

Measured memory_bytes: 18800
#include<iostream>
using namespace std;
int main()
{
	long long k;
	int i;
	long long a,b;
	cin>>k>>a>>b;
	for(i=1;;i++)
	{
		if(a<=i*k&&i*k<=b) 
		{
			puts("OK");
			return 0;
		}
		if(i*k>b)
		{
			puts("NG");
			return 0;
		}
	}
}

Measured memory_bytes: 3124
def main():
    N = int(input())

    checked = [0]*(N+1)

    print(0)
    A = input()
    if A == 'Vacant':
        return
    elif A == 'Male':
        checked[0] = 1
        checked[N] = 1
    else:
        checked[0] = -1
        checked[N] = -1
    l = 0
    r = N
    m = (l+r)//2
    while l < r:
        print(m)
        A = input()
        if A == 'Vacant':
            return
        elif A == 'Male':
            checked[m] = 1
        else:
            checked[m] = -1

        if (m - l) % 2 == 1:
            if checked[l] != checked[m]:
                l = m
            else:
                r = m
        else:
            if checked[l] == checked[m]:
                l = m
            else:
                r = m
        m = (l+r)//2



if __name__ == "__main__":
    main()

Measured memory_bytes: 4424
#include<bits/stdc++.h>
 
using namespace std;
 
 
#define mod(cans) cans%10**9+7
#define cin_pl(x,y) for(int i=0;i<x;i++){cin>>y[i];}
#define debug(x) cout << "Debug" << x << "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define prians(Answer) cout<<Answer<<"\n"
#define TF(X) X==1?cout<<"Yes\n":cout<<"No\n"
#define elcon else{continue;}
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<vector<int>> matrix;
typedef pair<int,int> pr;
typedef vector<pr> vpt;
typedef greater<int> gi;
 
int main()
{
    string s;
    cin>>s;
    if(s=="Sunny")
    cout<<"Cloudy";
    else if(s=="Cloudy")
    cout<<"Rainy";
    else
    {
        cout<<"Sunny";
    }
    
}

Measured memory_bytes: 256
n = int(input())
from cmath import phase
xy = sorted([list(map(int,input().split())) for i in range(n)],key=lambda x: phase(x[0]+x[1]*1j))
#x+yiのargument[-pi,pi]の小さい方から順に並べる
xy += xy
#同じものを複製
ans = 0
for l in range(n):
    a = [0,0] # 最後にたどり着く座標
    for r in range(l,min(2*n,l+n)):#l番目含めlからn個について
        a[0] += xy[r][0]
        a[1] += xy[r][1]
        ans = max(ans,abs(a[0]+a[1]*1j))
print(ans) 

Measured memory_bytes: 3188
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];


int main(){
  ll n,ans=0;cin>>n;
  rep(i,1,n+1){
    ll tmp=n/i;
    ans+=i*((tmp*(tmp+1))/2);
  }
  cout<<ans<<endl;
}






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

#define endl '\n'
#define int long long

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

	return 0;
}

Measured memory_bytes: 3540
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
#define int ll
 
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif
 
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
 
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
 
using pi=pair<int,int>;
using vi=vc<int>;
 
template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}
 
template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}
 
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n;cin>>n;
	vc<pi> lr;
	const int inf=LLONG_MAX/3;
	int mx=-inf,mn=inf;
	rep(i,n){
		int l,r;cin>>l>>r;
		l--;
		chmax(mx,l);
		chmin(mn,r);
		lr.eb(l,r);
	}
	
	int ans=0;
	for(auto z:lr){
		chmax(ans,max(int(0),mn-mx)+z.b-z.a);
	}
	vc<pi> t;
	rep(i,n){
		int a=max(int(0),mn-lr[i].a);
		int b=max(int(0),lr[i].b-mx);
		t.eb(b,-a);
	}
	sort(all(t));
	int w=inf;
	rep(i,n){
		auto z=t[i];
		z.b=-z.b;
		if(i)
			chmax(ans,w+z.a);
		chmin(w,z.b);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 4848
S = list(map(int,input()))
K = int(input())
ans = 1
if K == 1 or S.count(S[0]) == len(S) or S.count(1) == len(S):
    ans = S[0]
else:
  for x in range(K):
    if S[x] != 1:
      ans = S[x]
      break
print(ans)


Measured memory_bytes: 2940
#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;
	
	int t = 0, result = 0;
	for (int i = 0; i < n; ++i) {
		int h;
		cin >> h;
		
		if (h >= t)
			t = h;
		else {
			result += t - h;
			t = h;
		}
	}
	
	result += t;
	
	cout << result << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;

std::vector<int> ta[51], tb[51];
int n, pa[51], pb[51];
void dfsa(int u, int p) {
	pa[u]=p;
	for(int v: ta[u]) if(v!=p) dfsa(v, u);
}
void dfsb(int u, int p) {
	pb[u]=p;
	for(int v: tb[u]) if(v!=p) dfsb(v, u);
}
u32 solve(int root, u32 res) {
	std::queue<int> q;
	std::vector<int> e[51];
	int ideg[51]={};
	dfsa(root, 0);
	dfsb(root, 0);
	for(int i=1; i<=n; ++i) if(pa[i]==pb[i]&&pa[pa[i]]!=pb[pa[i]]) return -1;
	for(int i=1; i<=n; ++i)
		if(pa[i]!=pb[i]) {
			if(pa[pa[i]]!=pb[pa[i]]) e[i].push_back(pa[i]), ++ideg[pa[i]];
			if(pa[pb[i]]!=pb[pb[i]]) e[pb[i]].push_back(i), ++ideg[i];
		}
	for(int i=1; i<=n; ++i) if(ideg[i]==0) q.push(i);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		for(int v: e[u]) if(--ideg[v]==0) q.push(v);
	}
	for(int i=1; i<=n; ++i) if(ideg[i]!=0) return -1;
	for(int i=1; i<=n; ++i) res+=pa[i]!=pb[i];
	return res;
}
void work() {
	u32 ans=-1;
	n=rd();
	for(int i=1; i<=n; ++i) {
		ta[i].clear();
		tb[i].clear();
	}
	for(int i=1; i<n; ++i) {
		int u=rd(), v=rd();
		ta[u].push_back(v);
		ta[v].push_back(u);
	}
	for(int i=1; i<n; ++i) {
		int u=rd(), v=rd();
		tb[u].push_back(v);
		tb[v].push_back(u);
	}
	for(int i=1; i<=n; ++i) cmin(ans, solve(i, 0));
	for(int i=1; i<=n&&ans==-1; ++i)
		if(ta[i].size()==1) {
			int j=ta[i][0];
			std::remove(ta[j].begin(), ta[j].end(), i);
			ta[j].pop_back();
			for(int k=1; k<=n&&ans==-1; ++k)
				if(k!=i&&k!=j) {
					ta[i][0]=k;
					ta[k].push_back(i);
					ta[k].pop_back();
					cmin(ans, solve(i, 1));
				}
			ta[i][0]=j;
			ta[j].push_back(i);
		}
	printf("%d\n", ans);
}
int main() {
	int t=rd();
	while(t--) work();
	return 0;
}


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


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


int main() {
    string S;
    cin >> S;
    ll q;
    cin >> q;
    deque<char> s;
    REP(i, S.size()) {
        s.push_back(S[i]);
    }
    ll t_num = 0;
    REP(i, q){
        int t;
        cin >> t;
        if(t == 1){
            t_num += 1;
            //cout << t_num << endl;
        }
        else {
            int f = 0;
            cin >> f;
            char c;
            cin >> c;
            if((f + t_num) % 2 == 1) {
                s.push_front(c);
            }
            else {
                s.push_back(c);
            }
        }
    }
    if(t_num % 2 == 0) {
        REP(i, s.size()){
            cout << s[i];
        }
    }
    else {
        REPR(i, s.size()-1){
            cout << s[i];
        }
    }
    cout << endl;
}


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

using namespace std;

#define MOD 1000000007
#define ll long long int
#define ld long double
#define pb push_back
#define mkp make_pair
#define pii pair<int, int> 
#define pll pair<long long int, long long int>
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define fi first
#define sc second
#define deb 0

ll fact[1000000], A[1000000], mark[1000000];

ll mod_inv(ll a)
{
	ll ans = 1, b = MOD-2;
	while (b) {
		if (b&1) ans = (ans * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	}
	return ans;
}

ll ncr(ll n, ll r)
{
	ll a = fact[n];
	ll b = mod_inv(fact[r]);
	ll c = mod_inv(fact[n-r]);
	return ((a * b) % MOD * c) % MOD;
}

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

	ll n, m, i, j, k, x, y, z, a, b, c;

	fact[0] = 1;
	for (i = 1; i <= 100005; ++i) {
		fact[i] = (i * fact[i-1]) % MOD;
	}

	cin >> n;
	n++;

	for (i = 0; i < n; ++i) cin >> A[i], mark[A[i]]++;

	for (i = 1; i <= n; ++i) if (mark[i] > 1) break;

	a = i;
	c = 0;
	for (i = 0; i < n; ++i) {
		if (A[i] == a) {
			x = i;
			break;
		}
	}
	i++;
	for (; i < n; ++i) {
		if (A[i] == a) {
			y = i;
			break;
		}
	}
	y = n - i - 1;

	for (i = 1; i <= n; ++i) {
		if (i <= x+y+1) {
			cout << (ncr(n, i) - ncr(x+y, i-1) + MOD) % MOD << endl;
		} else {
			cout << ncr(n, i) << endl;
		}
	}

	return 0;
}

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

int main(){
    int n,cnt=0;
    string s;
    vector<int> v;
    cin >> n >> s;
    for(int i=0;i<n;i++){
        if(s[i]=='W') cnt++;
        v.push_back(cnt);
    }
    cnt=0;
    reverse(s.begin(),s.end());
    reverse(v.begin(),v.end());
    for(int i=0;i<n;i++){
        if(s[i]=='E') cnt++;
        v[i]+=cnt;
    }
    sort(v.begin(),v.end());
    cout << v.front()-1 << endl;
    return 0;
}


Measured memory_bytes: 2812
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100009];
int b[100009];
int c[100009];
long long dpb[100009];
int check1(int x)
{
    int l=-1,r=n,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(c[mid]>x)
            r=mid;
        else
            l=mid;
    }
    if(l!=-1&&c[l]>x)return l;
    else return r;
}
int check2(int x)
{
    int l=-1,r=n,mid;
    while(r-l>1)
    {
        mid=(l+r)/2;
        if(b[mid]>x)
            r=mid;
        else
            l=mid;
    }
    if(l!=-1&&b[l]>x)return l;
    else return r;
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n;i++)
        cin>>c[i];
    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);
    for(int i=0;i<n;i++)
    {
        int x=b[i];
       dpb[i]=n-check1(x);
       if(i>0)
       dpb[i]=dpb[i-1]+dpb[i];
    }
    long long ans=0;
    for(int i=0;i<n;i++)
    {
       int x=a[i];
       int y=check2(x);
       long long ans1=dpb[n-1]-dpb[y-1];
       ans=ans+ans1;
    }
    cout<<ans;
}


Measured memory_bytes: 2176
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 

public class Main{
          
     static int[][] map = new int[8][8];
     static void bomb(int x, int y){
         if(map[y][x]==0)return ;
         else{// map[y][x]==1
             map[y][x]=0;
             if(y!=0)bomb(x,y-1);
             if(y>=2)bomb(x,y-2);
             if(y>=3)bomb(x,y-3);
             if(y!=7)bomb(x,y+1);
             if(y<=5)bomb(x,y+2);
             if(y<=4)bomb(x,y+3);
             if(x!=0)bomb(x-1,y);
             if(x>=2)bomb(x-2,y);
             if(x>=3)bomb(x-3,y);
             if(x!=7)bomb(x+1,y);
             if(x<=5)bomb(x+2,y);
             if(x<=4)bomb(x+3,y);
         }
     }
     public static void main(String args[]){
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
         try{
             String line;
             
            while((line=br.readLine())!= null){if(line.isEmpty())break;
                int n=Integer.parseInt(line);
                for(int i=0;i<n; i++){
                    line=br.readLine();
                    for(int y=0;y<8;y++){
                        line=br.readLine();
                        for(int x=0;x<8;x++)map[y][x]=Integer.parseInt(line.charAt(x)+"");
                    }
                    line=br.readLine(); int bX  =Integer.parseInt(line);
                    line=br.readLine(); int bY  =Integer.parseInt(line);
                    bomb(bX-1,bY-1);
                    System.out.println("Data "+(i+1)+":");
                    for(int y=0;y<8;y++){
                        for(int x=0;x<8;x++){
                            System.out.print(map[y][x]+"");
                        }
                        System.out.println("");
                    }
                }
                break;

            }br.close();
         }catch(Exception e){e.printStackTrace();}         
     }
     
    
}
  

Measured memory_bytes: 17036
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int x=n%10;
    if(x==2||x==4||x==5||x==7||x==9)
    {
        cout<<"hon"<<endl;
    }
    else if(x==0||x==1||x==6||x==8)
    {
        cout<<"pon"<<endl;
    }
    else
    {
        cout<<"bon"<<endl;
    }
}


Measured memory_bytes: 3636
n = int(input())
r = []
b = []
for _ in range(n):
    x,y = map(int,input().split())
    r.append([x,y,0])
for _ in range(n):
    x,y = map(int,input().split())
    b.append([x,y])
r.sort(key=lambda x: x[1], reverse=True)
b.sort()
cnt = 0
for i in range(n):
    for j in range(n):
        if r[j][0] < b[i][0] and r[j][1] < b[i][1] and r[j][2]==0:
            cnt += 1
            r[j][2] = 1
            break
print(cnt)


Measured memory_bytes: 3064
use itertools::Itertools;
use proconio::input;

fn main() {
    input!(len: [u64]);
    let ans = len
        .iter()
        .sorted()
        .tuple_combinations()
        .filter(|&(&a, &b, &c)| {
            a + b > c && a != b && b != c && c != a
        })
        .count();
    println!("{}", ans);
}


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

int main() {
  string w1,w2;
  cin >> w1 >> w2;

  int count=0;
  
  rep(i,w1.length()){
    if (w1.at(i) == w2.at(i)){
      count++;
    }
  }
  cout << count<<endl;

}

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

void solve() {
    ll a, b ,n;
    cin >> a >> b >> n;
    if(n >= b) {
        cout << floor((a * (b - 1)) / b);
    }
    else {
        cout << floor((a * (n)) / b);
    }
}    

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

Measured memory_bytes: 3796
#pragma region Template
#include <bits/stdc++.h>
using namespace std;
struct ios_accelerate { ios_accelerate() { ios::sync_with_stdio(false); cin.tie(nullptr); } } CALL;

#define REP(i, n) for(int i = 0; i < n; i++)
#define RNG(i, a, b) for(int i = a; i < b; i++)
#define RBF(i, v) for(auto& i : v)
#define ALL(x) x.begin(), x.end()

using LL = long long;
using UL = unsigned long;
using ULL = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
template<typename T> using P = pair<T, T>;
template<typename T> using VP = vector<pair<T, T>>;

const double PI = 3.141592653589793;
const int MOD = 1000000007;
const LL INF64 = INT64_MAX >> 1;
const int INF = INT_MAX >> 1;

template<typename T> inline void upsort(vector<T>& x) { sort(x.begin(), x.end()); }
template<typename T> inline void downsort(vector<T>& x) { sort(x.begin(), x.end(), greater<T>()); }
template<typename T> inline void col(T x) { cout << x << '\n'; }
template<> inline void col(double x) { cout << fixed << setprecision(12) << x << '\n'; }
#pragma endregion

signed main()
{
	int N;
	cin >> N;
	vector<vector<pair<int,int>>> side(N);
	int i = N - 1;
	while (i-- > 0) {
		int u, v, w;
		cin >> u >> v >> w;
		side[u-1].emplace_back(make_pair(v-1, w));
		side[v-1].emplace_back(make_pair(u-1, w));
	}

	int col = 1;
	vector<int> paint(N, 0);
	paint[0] = 1;
	stack<int> st;

	st.push(0);
	while (!st.empty()) {
		int u = st.top();
		st.pop();

		for (auto& v : side[u]) {
			if (paint[v.first] == 0) {
				if (v.second % 2) paint[v.first] = -paint[u];
				else paint[v.first] = paint[u];
				st.push(v.first);
			}
		}
	}

	for (auto& p : paint) {
		if (p > 0) cout << "1\n";
		else cout << "0\n";
	}

	return 0;
}


Measured memory_bytes: 6784
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N = int(input())
    H = list(map(int, input().split()))

    ans = 0
    count = 0

    now = H[0]
    for i in range(1, N):
        if H[i] <= now:
            count += 1
        else:
            ans = max(ans, count)
            count = 0
        now = H[i]
    else:
        ans = max(ans, count)

    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 14252
#include<stdio.h>
#include<stdlib.h>


 int main()
 {
 	int a,b,c,d;
 	scanf( "%d %d", &a,&b);
	c=a*b;
	d=a+a+b+b;
 	printf("%d %d\n",c ,d);
 	
	

 	return 0;
 }


Measured memory_bytes: 2608
##部屋の移動は隣とは限らない
##部屋ごとに出入りを割り当てる
##出る<=入る+1
##出入りは相殺させて、たかだかk回の移動で、各人はたかだか1回移動とみなす
##別の部屋なので1回を0回とみなすのは不可能だが、2回以上は交代も可
##交代による相殺を別として、出た部屋に入る人はいない
##k>=nならば任意
#出に割り当てるx人をn-x部屋に割り当てる

n,k  = map(int,input().split( ))
mod = 10**9+7
if k==1:
    print(n*(n-1))
    exit()
rev = [0]+[pow(i,mod-2,mod) for i in range(1,n+3)]
chs_nx = [0]
def chs(t,s):
    res = 1
    for i in range(t,t-s,-1):
        res *= i
        res %=mod
    for i in range(1,s+1):
        res *= rev[i]
        res %=mod
    return res
res = 1
mn = min(n,k)
for i in range(1,mn+1):
    res *= n-i+1
    res *= rev[i]
    res %=mod
    chs_nx.append(res)
ans = 1

for i in range(1,mn+1):
    ans += chs_nx[i]**2*(n-i)*rev[n]
print(ans%mod)


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

int main() {
  
  int N,A,B;
  cin >> N >> A >> B;
  
  int t=0;
  for (int i=0; i<N; i++) {
    int s=0;
    int j=i+1;
    while (j>0) {
      s += j%10;
      j/=10;
    }
    if (A<=s && s<=B) t+=i+1;
  }
  
  cout << t << endl;
}

Measured memory_bytes: 256
using System;

namespace AtCoder
{
	public class ProblemA
	{
		public static void Main(string[] args)
		{
			string[] line = Console.ReadLine().Split(' ');
			int n = int.Parse(line[0]);
			int w = int.Parse(line[1]);

			long[,] dp = new long[n, w + 1];

			for (int i = 0; i < n; i++)
			{
				bool isTop = i == 0;
				line = Console.ReadLine().Split(' ');
				int curW = int.Parse(line[0]);
				int curV = int.Parse(line[1]);

				for (int j = 1; j <= w; j++)
				{
					bool include = j - curW >= 0;
					long a = 0;
					long b = 0;
					if (include)
						b += curV;
					if (!isTop)
					{
						a = dp[i - 1, j];
						if (include)
							b += dp[i - 1, j - curW];
					}
					dp[i, j] = Math.Max(a, b);
				}
			}
			
			Console.WriteLine(dp[n - 1, w]);
		}
	}
}


Measured memory_bytes: 105428
#include <algorithm>
#include <cmath>
#include <complex>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;
using Arrow = complex<LL>;

class Solution {
public:
	/* time: O(n*log(n)), space: O(1) auxiliary (i.e. does not count input itself) */
	double engines(vector<Arrow>& arrows) {
		const int n = arrows.size();
		/*
		 * Assume the final answer is v = Arrow(x, y), where len = abs(v), degree = arg(v)
		 * All the arrows within (degree - 90) ~ (degree + 90) will contribute to this len.
		 * Therefore, if we sort the array of arrows by degree, the answer is one of its subarrays.
		 */
		auto compareAngle = [](const Arrow& a, const Arrow& b) {
			return atan2(imag(a), real(a)) < atan2(imag(b), real(b));
		};
		make_heap(arrows.begin(), arrows.end(), compareAngle);
		sort_heap(arrows.begin(), arrows.end(), compareAngle);

		Arrow window(0, 0);
		LL ans = 0;
		int R = 0;
		for (int L = 0; L < n; ++L) {
			if (R < L)
				R = L, window = Arrow(0, 0);
			while (R - L < n && norm(window + arrows[R % n]) >= norm(window))
				window += arrows[R % n], ++R;
			ans = max(ans, norm(window)), window -= arrows[L % n];
		}
		return sqrt(ans);
	}
};

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

	vector<Arrow> arrows(n);
	for (int i = 0; i < n; ++i) {
		LL x, y;
		cin >> x >> y;
		arrows[i] = Arrow(x, y);
	}

	Solution sol;
	double ans = sol.engines(arrows);
	cout << fixed << setprecision(10) << ans << endl;
	return 0;
}


Measured memory_bytes: 384
n_vertex, n_edge = gets.split.map(&:to_i)
#puts "#{n_vertex} #{n_edge}"
edges = n_vertex.times.map { Array.new(n_vertex, -1) }
for i in 0...n_edge do
  u, v, d = gets.split.map(&:to_i)
#  puts "#{u} #{v} #{d}"
  edges[u - 1][v - 1] = d
  edges[v - 1][u - 1] = d
end
#for i in 0...n_vertex do
#  puts edges[i].join(" ")
#end
f = gets.split.map(&:to_i)
#puts f.join(" ")

for i in 1...n_vertex do
  if edges[0][i] > 0
    targ_v = i
    targ_d = edges[0][i]
    break
  end
end
#puts "#{targ_v} #{targ_d}"

t_max = gets.to_i
t_last = (t_max.to_f * 0.95).to_i
#puts "#{t_max} #{t_last}"
count = 0
for t in 0...t_max do
  n_new = gets.to_i
#  puts "#{n_new}"
  for i in 0...n_new do
    new_id, dst = gets.split.map(&:to_i)
#    puts "#{new_id} #{dst}"
  end
  n_put = gets.to_i
#  puts "#{n_put}"
  for i in 0...n_put do
    put_id = gets.to_i
#    puts "#{put_id}"
  end
  
  if t < t_last
    command = -1
  else
    if count < targ_d
      command = targ_v + 1
      count += 1
    else
      command = -1
    end
  end
  puts command
  $stdout.flush
  
  verdict = gets.chomp
  break if verdict == "NG"
  n_achieve = gets.to_i
#  puts "#{n_achieve}"
  for i in 0...n_achieve do
    achieve_id = gets.to_i
#    puts "#{achieve_id}"
  end
end


Measured memory_bytes: 4428
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		int ans = 3000;
		for (int i = 0; i < 3; i++)
			ans = Math.min(ans, scanner.nextInt());
		ans += Math.min(scanner.nextInt(), scanner.nextInt());
		System.out.println(ans - 50);
	}
}

Measured memory_bytes: 17164
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,x;
    cin>>n>>x;
    int a[100];
    for (int i = 0; i < n; ++i) {
        cin>>a[i];
    }
    sort(a,a+n);
    int ans=0;
    for (int i = 0; i < n-1; ++i) {
        if(x-a[i]>=0){
	    x-=a[i];
	    ans++;
	}
    }
    if(x==a[n-1]) ans++;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  int n, m;
  int count = 0;

  scanf("%d %d", &n, &m);

  if (n >= 2) {
    count += n * (n - 1) / 2;
    if (m >= 2) count += m * (m - 1) / 2;
  }else if(m >= 2) count += m * (m - 1) / 2;
  
  printf("%d", count);

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

struct edge{
	int to,dis,cost;
	edge(){}
	edge(int to,int dis,int cost) : to(to),dis(dis),cost(cost){}
	bool operator>(const edge& rhs) const{
		return dis != rhs.dis ? dis>rhs.dis : cost>rhs.cost;
	}
};

int V,M;
bool vis[maxn];

vector<edge> G[maxn];

int dijkstra(int s){
	int res = 0;
	priority_queue<edge,vector<edge>,greater<edge> > Q;

	Q.push(edge(0,0,0));

	while(!Q.empty()){
		edge p = Q.top(); Q.pop();
		int v = p.to;
		if(vis[v]) continue;
		vis[v] = true;
		res += p.cost;
		for(int i=0; i<G[v].size(); i++){
			Q.push(edge(G[v][i].to,p.dis+G[v][i].dis,G[v][i].cost));
		}
	}

	return res;
}


int main(){
	while(scanf("%d%d",&V,&M) && V){
		memset(vis,0,sizeof(vis));
		for(int i=0; i<=V; i++) G[i].clear();

		for(int i=0; i<M; i++){
			int u,v,d,c;
			scanf("%d%d%d%d",&u,&v,&d,&c);
			--u,--v;
			G[u].push_back(edge(v,d,c));
			G[v].push_back(edge(u,d,c));
		}

		printf("%d\n",dijkstra(0));

	}
}

Measured memory_bytes: 7644
use std::io::prelude::*;

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

fn main() {
    let n = input::<i64>();
    let k = input::<i64>();
    let _a = (0..n).map(|_| input()).collect::<Vec<i64>>();

    println!("{}", (n - 1 + k - 1 - 1) / (k - 1));
}


Measured memory_bytes: 4352
#include <iostream>

using namespace std;

long long GCD(long long a, long long b) {
    if (a % b == 0)
        return b;
    else
        return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
    return a / GCD(a, b) * b;
    //CAUTION: a * b / GCD(a, b) would bring overflow hence calculates `a*b`, which can be very large number.
}

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

    int N;
    cin >> N;

    long long res;
    for (int i = 0; i < N; ++i) {
        long long T;
        cin >> T;
        if (i)
            res = LCM(res, T);
        else
            res = T;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
	string s = Console.ReadLine();
  int k = int.Parse(Console.ReadLine());

  List<string> checkList = new List<string>();

    for(int i = 0; i < k; i++)
    {
      for(int j = 0; j < s.Length - i; j++)
      {
        //Console.WriteLine(s.Substring(j, i+1));
        checkList.Add(s.Substring(j, i+1));//j文字目からi文字
      }
    }

    checkList.Sort((a, b) => a.CompareTo(b));//ソート

    string memo = "aaaaaa";
    long check = 0;
    
      for(int i = 0; i < checkList.Count(); i++)
      {
        if(checkList[i] != memo) 
        {
          check ++;
          if(check == k) Console.WriteLine(checkList[i]);
          memo = checkList[i];
        }
      }
    
      
	}
}


Measured memory_bytes: 13920
#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

// 多次元 vector 生成
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

int N, M, K, Q, W, H, R, C;
string S;

int main() {
    vector<int> ans;
    while (true) {
        cin >> N;
        if (N == 0) break;
        vector<int> A(24 * 3600 + 5);
        REP(i, N) {
            int h, m, s;
            scanf("%2d:%2d:%2d ", &h, &m, &s);
            A[h * 3600 + m * 60 + s]++;
            scanf("%2d:%2d:%2d\n", &h, &m, &s);
            A[h * 3600 + m * 60 + s]--;
        }
        int sum = A[0];
        REP(i, 24 * 3600) {
            A[i + 1] += A[i];
            chmax(sum, A[i + 1]);
        }
        ans.push_back(sum);
    }
    for (auto i : ans) {
        cout << i << endl;
    }
    return 0;
}



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

void enum_divisor(ll n,map<int,ll> &mp){
    for(ll i = 1;i*i <= n;i ++){
        if(n%i==0){
            mp[i] ++;
            if(i*i!=n) mp[n/i] ++;
        }
    }
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int,ll> mp;
    bool isp = true;
    vector<int> b;
    for(int i = 0;i < n;i ++){
        cin >> a[i];
    }
    for (int i = n;i >= 1;i --){
        if(a[i-1]%2!=mp[i]%2){
            b.push_back(i);
            enum_divisor(i,mp);
        }
    }
    sort(b.begin(),b.end());
    cout << b.size() << endl;
    for(int i = 0;i < b.size();i ++){
        cout << b[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 14584
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,a,b;
int main()
{
	cin>>n>>m>>a>>b;
	for(int i=1;i<=b;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<(j<=a?1:0);
		}
		puts("");
	}
	for(int i=b+1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cout<<(j<=a?0:1);
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define nl cout<<endl

#define pii pair<ll,ll>
#define vi  vector<ll>
#define vii vector<pii>
#define mi  map<ll,ll>
#define all(a)  (a).begin(),(a).end()

#define pb push_back
#define ff first
#define ss second
#define hell 1000000007

#define test4(x,y,z,a) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<"		a is "<<a<<endl;
#define test3(x,y,z) cout<<"x is "<<x<<"		y is "<<y<<"		z is "<<z<<endl;
#define test2(x,y) cout<<"x is "<<x<<"		y is "<<y<<endl;
#define test1(x) cout<<"x is "<<x<<endl;
#define N 300009

ll power(ll a,ll b,ll m)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}
int main()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
        ll a,b;cin>>a>>b;
	cout<<max(0LL,a-b-b)<<endl;
}

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

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

const int MOD = 1E9 + 7;

int binpow(int base, int e) {
	int ret = 1;
	while(e) {
		if(e & 1)
			ret = (long long) ret * base % MOD;
		base = (long long) base * base % MOD;
		e >>= 1;
	}
	return ret;
}

int main() {
	int n;
	int k;
	cin >> n >> k;
	vector<int> freq(k + 1, 1);
	// for(int i = 0; i < n; i++) {
	// 	int a;
	// 	cin >> a;
	// 	freq[a]++;
	// 
	for(int i = 1; i <= k; i++) {
		// for(int j = i + i; j < k; j += i)
		// 	freq[i] += freq[j];
		// if(freq[i])
		// 	debug(i, freq[i]);
		freq[i] = binpow(k / i, n);
	}
	for(int i = k; i >= 1; i--) {
		for(int j = i + i; j <= k; j += i) {
			freq[i] = ((freq[i] - freq[j]) % MOD + MOD) % MOD;
		}
		// debug(i, freq[i]);
	}
	int res = 0;
	for(int i = 1; i <= k; i++)
		res = (res + (long long) freq[i] * i % MOD) % MOD;
	cout << res << '\n';
}


Measured memory_bytes: 3788
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int n,k,tab[101];
int dp[2][100002];
bool solve(int turn , int k){
    if(!k)return 1-turn;
    if(dp[turn][k]!=-1)
        return dp[turn][k];
    for (int i = 0; i < n; ++i)
    {
        if(tab[i]<=k)
            if(solve(1-turn,k-tab[i])==turn)
                return dp[turn][k]=turn;
    }
    return dp[turn][k]=1-turn;
}
int main(){
    boost;
    memset(dp,-1,sizeof dp);
    cin>>n>>k;
    for (int i = 0; i < n; ++i)
        cin>>tab[i];
    cout<<(!solve(0,k)?"First":"Second");
    return 0;
}
//long long
//array bounds
//special cases
//binary search

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



int N, M;
vector<ll> A;



ll gcd( ll a, ll b ){
	if ( a < b )
		return gcd( b, a );
	
	int k = a / b;
	if ( a - k * b == 0 )
		return b;
	return gcd( b, a - k * b );
}



int main2(){
	cin >> N >> M;
	A.resize(N);
	
	for ( int i = 0; i < N; i++ ){
		cin >> A[i];
		A[i] /= 2;
	}
	
	int div = 1;
	{
		ll x = A[0];
		while ( x % 2 == 0 ){
			div *= 2;
			x /= 2;
		}
	}
	
	ll X = A[0];
	for ( int i = 1; i < N; i++ ){
		if ( A[i] % div != 0 || A[i] % (div*2) == 0 )
			return 0;
		X = X * A[i] / gcd( X, A[i] );
		if ( X > M )
			return 0;
	}
	int result = (M / X + 1)/2;
	return result;
}

int main(){
	int result = main2();
	cout << result << endl;
	return 0;
}




Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll mod=1e9+7;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n+2);
  for(ll i=0;i<n;i++) {
    cin >> a[i+1];
  }
  ll ans=0;
  for(ll i=0;i<n+1;i++) {
    ans+=abs(a[i+1]-a[i]);
  }
  for(ll i=1;i<n+1;i++) {
    ll tans=ans;
    tans-=(abs(a[i+1]-a[i])+abs(a[i]-a[i-1])-abs(a[i+1]-a[i-1]));
    cout << tans << endl;
  }
}

Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
struct _I { _I() {cin.tie(0);ios::sync_with_stdio(false);}} __I;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i < (n); i++)
#define all(a) begin(a),end(a)
template<class F, class S> istream& operator >> (istream& s, pair<F, S>& p)
{ cin >> p.first >> p.second; return s;}
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_h(const vector<T>& c, int n=INT_MAX)
{ rep(i, min(n, (int)c.size())) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
#define D1(a) cout<<#a<<":"<<a<<"\n"
#define D2(a,b) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<endl 
#define D3(a,b,c) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c <<endl
#define D4(a,b,c,d) cout<<#a<<":"<<a<<","<<#b<<":"<<b<<","<<#c<<":"<<c<<","<<#d<<":"<<d<<endl 
#define MOD 1000000007

int main()
{
    int N, T; cin >>N >> T;
    vector<int> A(N); cin >> A;
    vector<int> A_max(N);
    int ma = 0;
    for (int i = N-1; i >= 0; i--) {
        if (A[i] > ma) ma = A[i];
        A_max[i] = ma;
    }

    int c = 0;
    int d_max = 0;
    rep(i, N-1) {
        int d = A_max[i+1] - A[i];
        if (d > d_max) {
            c = 1;
            d_max = d;
        } else if (d == d_max && d_max != 0) {
            c++;
        }
    }

    cout << c*1 << endl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
#define pb push_back
#define mp make_pair



int main(){
	string s;
	cin>>s;
	map <string,int> ans;
	ans["SUN"] = 7;
	ans["SAT"] = 1;
	ans["FRI"] = 2;
	ans["THU"] = 3;
	ans["WED"] = 4;
	ans["TUE"] = 5;
	ans["MON"] = 6;
	printf("%d\n",ans[s] );
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int get_uint() {
    int n = 0;
    int c = getchar_unlocked();
    if(c < 48 || 57 < c) return c;
    while(47 < c && c < 58) {
        n = 10 * n + (c & 0xf);
        c = getchar_unlocked();
    }
    return n;
}
void put_uint(int n) {
    if(!n) {
        putchar_unlocked('0');
        return;
    }
    char buf[11];
    int i = 0;
    while(n) buf[i++] = (char)(n % 10 + '0'), n /= 10;
    while(i--)putchar_unlocked(buf[i]);
}
void put_str(char *str) { while(*str) putchar_unlocked(*str++); }

typedef struct Node { int parent, left, right, depth; } Node;
void tree_depth(Node *tree, int node, int depth) {
    tree[node].depth = depth;
    for(int i = tree[node].left; ~i; i = tree[i].right) {
        tree_depth(tree, i, depth + 1);
    }
}
int main(int argc, char **argv) {
    int n = get_uint();
    Node tree[n];
    for(int i = 0; i < n; ++i) tree[i].parent = tree[i].left = tree[i].right = -1;
    for(int i = 0; i < n; ++i) {
        int id = get_uint();
        int k = get_uint();
        for(int j = 0, d; j < k; ++j) {
            int c = get_uint();
            tree[c].parent = id;
            if(j) tree[d].right = c;
            else tree[id].left = c;
            d = c;
        }
    }
    for(int i = 0; i < n; ++i) {
        if(tree[i].parent == -1) {
            tree_depth(tree, i, 0);
            break;
        }
    }
    for(int i = 0; i < n; ++i) {
        put_str("node ");
        put_uint(i);
        put_str(": parent = ");
        if(~tree[i].parent) put_uint(tree[i].parent);
        else put_str("-1");
        put_str(", depth = ");
        put_uint(tree[i].depth);
        put_str(~tree[i].parent ? ~tree[i].left ? ", internal node, [" : ", leaf, [" : ", root, [");
        if(~tree[i].left) {
            int j = tree[i].left;
            put_uint(j);
            for(j = tree[j].right; ~j; j = tree[j].right) {
                put_str(", ");
                put_uint(j);
            }
        }
        put_str("]\n");
    }
    return 0;
}



Measured memory_bytes: 3196
N = int(input())
A,B = map(int,input().split())
P = list(map(int,input().split()))

Ans = [0]*3
for i in range(N):
    if P[i]<=A:
        Ans[0] += 1
    elif P[i]<=B:
        Ans[1] += 1
    else:
        Ans[2] += 1

print(min(Ans))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define lol long long
using namespace std;
int main(){
  lol n,m,ans;
  string s,t,a;
  cin>>s;
  size_t size=s.length();
  for(int i=0;i<size;i++){
    cout<<"x";
  }
  cout<<"\n";
  return(0);
}


Measured memory_bytes: 256
import collections

n,k=(int(i) for i in input().split())
a=[int(i) for i in input().split()]

mydata=collections.Counter(a)
mylist=list(mydata.values())
mylist.sort(reverse=True)
#print(mylist)

if len(mylist)<k:
  print(0)
else:
  val=sum(mylist[:k])
  print(n-val)

Measured memory_bytes: 32520
#include <iostream>

using namespace std;

int tax(int rate, int price){
	return (int) price * (100 + rate) / 100;
}

int solve(int x, int y, int s){
	int maximum = 0;
	for (int i = 1; i < s; i++)
		for (int j = i; j < s; j++)
			if (tax(x, i) + tax(x, j) == s)
				maximum = max(maximum, tax(y, i) + tax(y, j));
	return maximum;
}

int main(){
	int x, y, s;
	while (cin >> x >> y >> s && x > 0)
		cout << solve(x, y, s) << endl;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+10;
char str[N];
int a[30];
int main() {
	cin >> str;
	for(int i = 0; str[i]; i ++) a[str[i]-'a']++;
	for(int i = 0; i < 26; i ++) {
		if(a[i] == 0) return 0*printf("%c\n",i+'a');
	}
	printf("None\n");
	return 0;
}

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

int main() {
  long a, b, k;
  std::cin >> a;
  std::cin >> b;
  std::cin >> k;

  long takahashi = a;
  long aoki = b;

  if (a < k) {
    takahashi = 0;
    if (a + b < k) {
      aoki = 0;
    } else {
      aoki = b - k + a;
    }
  } else {
    takahashi = a - k;
    aoki = b;
  }
  std::cout << takahashi << " " << aoki << std::endl;
}


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

int main()
{
    ll x;
    cin >> x;
    ll ans = (x / 500) * 1000 + ((x % 500) / 5) * 5;
    cout << ans << endl;
    return 0;
}


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

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 100100;
const long long Q = 10001;
const long long mod = 1e9 + 7;;
const long long block = sqrt(N);

using namespace std;

int n;
int t;

void solve()
{
        cin >> n >> t;
        int ans = 1e9;
        for(int i = 1; i <= n; i++){
                int x, y;
                cin >> x >> y;
                if(y <= t){
                        ans = min(ans, x);
                }
        }
        if(ans == 1e9){
                cout << "TLE" << "\n";
        }
        else{
                cout << ans << "\n";
        }
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("substr3.in");
        //fout("substr3.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}


Measured memory_bytes: 256
from bisect import*
class BTreeNode:
    def __init__(self):self.key,self.child=[],[]
class BTree:
    def __init__(self):self.root=BTreeNode()
    def search_higher(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect(ptr.key,key)
            if i!=len(ptr.key):ret=ptr.key[i]
            ptr=ptr.child[i]
        i=bisect(ptr.key,key)
        if i!=len(ptr.key):ret=ptr.key[i]
        return ret
    def search_lower(self,key):
        ptr=self.root
        ret=None
        while ptr.child:
            i=bisect_left(ptr.key,key)
            if i:ret=ptr.key[i-1]
            ptr=ptr.child[i]
        i=bisect_left(ptr.key,key)
        if i:ret=ptr.key[i-1]
        return ret
    def insert(self,key):
        def insert_rec(ptr,key):
            b_size=512
            if not ptr.child:
                insort(ptr.key,key)
                if len(ptr.key)==b_size*2-1:
                    ret=BTreeNode()
                    ret.key=ptr.key[:b_size]
                    ptr.key=ptr.key[b_size:]
                    return ret
            else:
                i=bisect(ptr.key,key)
                tmp=insert_rec(ptr.child[i],key)
                if tmp:
                    ptr.key.insert(i,tmp.key.pop())
                    ptr.child.insert(i,tmp)
                    if len(ptr.child)==b_size*2:
                        ret=BTreeNode()
                        ret.child=ptr.child[:b_size]
                        ptr.child=ptr.child[b_size:]
                        ret.key=ptr.key[:b_size]
                        ptr.key=ptr.key[b_size:]
                        return ret
                return None
        tmp=insert_rec(self.root,key)
        if tmp:
            root=BTreeNode()
            root.key=[tmp.key.pop()]
            root.child=[tmp,self.root]
            self.root=root
def main():
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    t=BTree()
    t.insert(0)
    t.insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(t.search_higher(v)-v)*(v-t.search_lower(v))*i
        t.insert(v)
    print(c)
main()

Measured memory_bytes: 101564
#include <iostream>

using namespace std;

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

int main()
{
	int a, b;
	
	while ( (cin >> a) && (cin >> b) ) {
		int g = gcd(a, b);
		int l = (a/g) * b;
		cout << g << " " << l << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3044
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define MOD 1000000007;//1e9+7

void solve() {
    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    for (int i = 0; i < N-2; i++){
        if (S.substr(i, 3) == "ABC")ans++;
    }

    cout << ans;

    return;
}

int main() {
    solve();
    return 0;
}

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

typedef long long lint;
typedef long double ldouble;
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())

const int IINF = 1e9 + 10;
const lint LLINF = 1e18;
const lint MOD = 1e9 + 7;
const lint inv = MOD - 2;

int main(){
    int n;
    cin >> n;
    vector< vector<int> > f(n);
    rep(i, n){
        f[i].resize(10);
        rep(j, 10){
            cin >> f[i][j];
        }
    }
    vector< vector<int> > p(n);
    rep(i, n){
        p[i].resize(11);
        rep(j, 11){
            cin >> p[i][j];
        }
    }
    int ans = -IINF;
    for(int i = 1 ; i < (1 << 10) ; i++){
        vector<int> v(n, 0);
        int tmp = 0;
        for(int j = 0 ; j < 10 ; j++){
            if(i >> j & 1){
                rep(k, n){
                    if(f[k][j]){
                        v[k]++;
                    }
                }
            }
        }
        rep(k, n){
            tmp += p[k][v[k]];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256