akhauriyash/Code-Regression huggingface dataset:
from collections import deque


n, k = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n-1)]
MOD = 10**9 + 7
tree = [[] for i in range(n)]
for i in range(n-1):
    tree[info[i][0] - 1].append(info[i][1] - 1)
    tree[info[i][1] - 1].append(info[i][0] - 1)

visited = [-1] * n
q = deque([0])
visited[0] = k

while q:
    pos = q.pop()
    cnt = k - 1
    for i in tree[pos]:
        if visited[i] != -1:
            cnt -= 1
    for i in tree[pos]:
        if visited[i] == -1:
            if cnt == 0:
                print(0)
                exit()
            visited[i] = cnt
            cnt -= 1
            q.append(i)
ans = 1
for i in range(n):
    ans *= visited[i]
    ans %= MOD
print(ans)

Measured memory_bytes: 78936
/*
 _ _ _   _    _   _    _   _ _ _   _    _   _ __ _   __       __
|  _ _| | |  | | | |  | | |  _  | | |  | | |  __  | |   \   /   |
| |_ _  | |__| | | |  | | | |_| | | |__| | | |__| | | |\ \_/ /| |
|_ _  | |  __  | | |  | | |  _ <  |  __  | |  __  | | | \   / | |
 _ _| | | |  | | | |__| | | |_| | | |  | | | |  | | | |  \_/  | |  _   _   _
|_ _ _| |_|  |_| |_ __ _| |_ _ _| |_|  |_| |_|  |_| |_|       |_| |_| |_| |_|

*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << " = " << a << " ";
#define endl "\n"
const int  MOD=1000000007;
const int N=1000100;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve(){
    long n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);

    long minn=a[0],maxx=a[n-1];
    ll ans=LLONG_MAX;
    for(int i=minn;i<=maxx;i++){
        ll tp=0;
        for(int j=0;j<n;j++){
            tp+=abs(i-a[j])*abs(i-a[j]);
        }
        ans=min(ans,tp);
    }
    cout<<ans<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long int t = 1;
    // cin>>t;
    for (long int tt = 1; tt <= t; tt++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,n;
	int max;
	cin>>m>>n;
	max=m*n;
	if(m+n>max)
		max=m+n;
	if(m-n>max)
		max=m-n;
	cout<<max;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define ALL(v) v.begin(),v.end()

int main(int argc, char const *argv[])
{
    double a, b, x;
    cin >> a >> b >> x;
    double mid = 0;
    double left = 0, right = 90.0;

    // 二分探索
    if (a * a * b / 2 > x)
    {
        while (abs(right - left) > 0.000001)
        {
            mid = (right + left) / 2.0;
            double temp = b * b * a / 2.0 / tan(M_PI * mid / 180.0);

            if (x > temp)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
    }
    else
    {
        double max = a * a * b;
        while (abs(right - left) > 0.000001)
        {
            mid = (right + left) / 2.0;
            double temp = a * a * a / 2.0 * tan(M_PI * mid / 180.0); // 傾けたときの水がない空間の体積

            if (x > max - temp)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
        }
    }

    cout << SP(10) << mid << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int MOD = 1000000007;
const ll INF = 1LL << 60;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n), sum_a(n + 1);
    vector<ll> b(m), sum_b(m + 1);
    sum_a[0] = 0;
    sum_b[0] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum_a[i + 1] = sum_a[i] + a[i];
    }
    for (int i = 0; i < m; i++)
    {
        cin >> b[i];
        sum_b[i + 1] = sum_b[i] + b[i];
    }
    int cnt = 0;
    for (int i = 0; i < n + 1; i++)
    {
        ll num = sum_a[i];
        ll target = k - num;
        if (target < 0)
        {
            break;
        }
        vector<ll>::iterator uit = upper_bound(sum_b.begin(), sum_b.end(), target);
        int index = std::distance(sum_b.begin(), uit - 1);
        if (index != -1)
        {
            cnt = max(cnt, i + index);
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 9532
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<(int)(r); i++)
#define rep_eq(i,l,r) for(int i=l; i<=(int)(r); i++)
#define all(vec) vec.begin(),vec.end()
#define allr(vec) vec.rbegin(),vec.rend()
using namespace std;

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

using ll=int64_t;

using vb=vector<bool>;
using vc=vector<char>;
using vs=vector<string>;
using vi=vector<int>;
using vll=vector<ll>;
using vvi=vector<vi>;

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

  int N; cin >>N;

  set<int> sd;
  rep(i,0,N) {
    int d; cin >>d;
    sd.insert(d);
  }

  cout <<sd.size() <<'\n';
  return 0;
}


Measured memory_bytes: 3608
/*input
5 1
1
2
3
4
5



*/
#include <bits/stdc++.h>
using namespace std;

// ALL DEFFINES HERE
#define ll long long int
#define ii pair<int, int>
#define mp make_pair
#define N 100005
#define rep(i, n) for(int i=0; i < n; i++)
#define Rep(i, k, n) for(int i=k; i < n; i++)
#define pb push_back
#define vi vector<int>
#define vii vector< vector<int> >
#define vl vector<ll>
#define F first
#define S second
#define all(v) v.begin(), v.end()

// ALL declarations here const ints etc
const  ll mod = 1e9+7; 

// IMPORTANT FUNCTION DECLARATIONS , 
//SORRY FOR THE BAD PRESENTATION
ll gcd(ll a, ll b)
{
	if ( b==0)
		return a;
	return gcd(b, a%b);
}
ll absl(ll a )
{
	return  a>= 0 ?a:-a;
}
ll maxl(ll a, ll b)
{
	return a >= b? a:b;
}
ll minl(ll a, ll b)
{
	return a <= b? a:b;
}
ll exp(ll a, ll n)
{
	if ( n==0)
		return 1;
	if ( n==1 )
		return a;
	if ( n & 1)
		return (a%mod * exp((a*a)%mod, n/2)%mod)%mod;
	else
		return exp((a*a)%mod, n/2)%mod;
}
// --->>> main starts here
// m*h >= l + k
double mi( double a , double b)
{
	return a < b? a : b;
}
double mx( double a , double b)
{
	return a >= b ? a : b;
}

ll dp[100004][3];


void solve()
{
	int n , d;
	cin >> n >> d;
	int arr[n+1][d+1];
	for ( int i =0 ; i < n; i++)
		for  (int j =0; j < d ; j++)
			cin >> arr[i][j];
		int cnt =0;
	for ( int i =0; i < n; i++)
	{
		
		for ( int j =i+1 ; j < n; j++)
		{
			double dist =0.0;
			for ( int k =0; k < d; k++)
			{
				dist+= pow(arr[j][k] -arr[i][k] , 2);
			}
			if ( sqrt(dist) - floor(sqrt(dist)) == 0)
				cnt++;

		}
	}
	
	cout << cnt;

}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  // auto beginProgram = chrono::steady_clock::now();

  // int t; cin >> t;
  // while (t--) 
  {
    solve();
  }
  // auto endProgram = chrono::steady_clock::now();
  // std::chrono::duration<double> diff = endProgram - beginProgram;
  // cout << "\nTime: " <<diff.count()*1000 << " ms\n";
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string { sc.Scan(); return sc.Text() }
func scanInt() int { a,_ := strconv.Atoi(scanString()); return a }
func scanInt64() int64 { a,_ := strconv.ParseInt(scanString(),10,64); return a }
func scanFloat64() float64 { a,_ := strconv.ParseFloat(scanString(),64); return a }

func scanInts(n int) []int {
	res := make([]int, n); for i := 0; i < n; i++ { res[i] = scanInt() }; return res
}

func abs(a int) int { if a<0 { return -a }; return a }
func min(a,b int) int { if a<b { return a }; return b }
func max(a,b int) int { if a>b { return a }; return b }

//•*¨*•.¸¸♪Main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1000000)

	r1 := scanInt()
	c1 := scanInt()
	r2 := scanInt()
	c2 := scanInt()

	facInit(r2+c2+2)

	g := 0
	for i := 0; i < r2+1; i++ {
		g = (g+comb(c2+i+1, c2))%mod
		// fmt.Println(comb(c2+i+1, c2))
	}
	for i := 0; i < r2+1; i++ {
		g = (g-comb(c1-1+i+1, c1-1))%mod
		// fmt.Println(comb(c1-1+i+1, c1-1))
	}
	for i := 0; i < c2+1; i++ {
		g = (g-comb(r1-1+i+1, r1-1))%mod
		// fmt.Println(comb(r1-1+i+1, r1-1))
	}
	for i := 0; i < r1; i++ {
		g = (g+comb(c1-1+i+1, c1-1))%mod
		// fmt.Println(comb(c1-1+i+1, c1-1))
	}

	fmt.Println(g)

}

const mod = 1000000007

var fac, ifac []int

func facInit(n int) {
	fac = make([]int,n+1)
	ifac = make([]int,n+1)

	mpow := func (x,n int) int {
		a := 1
		for n!=0 {
			if n&1 == 1 { a = a*x%mod }
			x = x*x%mod; n >>= 1
		}
		return a
	}

	fac[0] = 1; ifac[0] = 1

	for i := 0; i < n; i++ {
		fac[i+1] = fac[i]*(i+1)%mod
		ifac[i+1] = ifac[i]*mpow(i+1,mod-2)%mod
	}
}

func comb(a,b int) int { return (fac[a]*ifac[b]%mod)*ifac[a-b]%mod }
func perm(a,b int) int { return fac[a]*ifac[a-b]%mod }

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

int main()
{
    int r, g, b, n, ans = 0;
    cin >> r >> g >> b >> n;
    for (int i = 0; i <= n / r; i++)
    {
        for (int j = 0; j <= (n - i * r) / g; j++)
        {
            if ((n - i * r - j * g) % b == 0)
            {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include <map>
#include <fstream>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <assert.h>
#include <complex>
using namespace std;
#define LONG_INF 10000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define MOD 998244353LL
#define seg_size 65536*4
#define REP(i,n) for(long long i = 0;i < n;++i)
int main() {
	while (true) {
		int n, m, t, p;
		cin >> n >> m >> t >> p;
		if (n == 0) {
			return 0;
		}
		int grid[200][200] = {};
		for (int i = 0; i < n; ++i) {
			for (int q = 0; q < m; ++q) {
				grid[i][q]++;
			}
		}
		REP(tere, t) {
			int a, b;
			cin >> a >> b;
			if (a == 1) {
				for (int i = 0;i < m;i++) {
					for (int q = 0; q < b; ++q) {
						grid[(2 * b - q - 1)][i] += grid[q][i];
						grid[q][i] = 0;
					}
				}
				for (int i = 0; i < n; ++i) {
					for (int q = 0; q < m; ++q) {
						grid[i][q] = grid[i + b][q];
						grid[i + b][q] = 0;
					}
				}
			}
			else {
				for (int i = 0; i < n; ++i) {
					for (int q = 0; q < b; ++q) {
						grid[i][(2*b - q - 1)] += grid[i][q];
						grid[i][q] = 0;
					}
				}
				for (int i = 0; i < n; ++i) {
					for (int q = 0; q < m; ++q) {
						grid[i][q] = grid[i][q + b];
						grid[i][q + b] = 0;
					}
				}
			}
		}
		REP(i, p) {
			int a, b;
			cin >> a >> b;
			cout << grid[a][b] << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3248
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	ll H,W;
	cin >> H >> W;

	ll ans = INF*INF;
	ll a=0,b=0,c=0;

	for(int h = 0; h <= H; h++){
		if(W%2==0) a = h*W/2,b = h*W/2;
		else a = h*(W-1)/2,b = h*(W+1)/2;
		c = W*(H-h);

		ll s_max = max(max(a,b),c);
		ll s_min = min(min(a,b),c);
		if(s_max - s_min < ans) ans = s_max - s_min;

		a = h*W;
		if((H-h)%2==0) b = (H-h)/2 * W,c = b;
		else b = (H-h-1)/2 * W,c = (H-h+1)/2 * W;

		s_max = max(max(a,b),c);
		s_min = min(min(a,b),c);
		if(s_max - s_min < ans) ans = s_max - s_min;
	}

	for(int w = 0; w <= W; w++){
		if(H%2==0) a = H/2*w, b = a;
		else a = (H-1)/2*w, b = (H+1)/2*w;
		c = H*(W-w);

		ll s_max = max(max(a,b),c);
		ll s_min = min(min(a,b),c);
		if(s_max - s_min < ans) ans = s_max - s_min;

		a = w*H;
		if((W-w)%2==0) b = H*(W-w)/2 , c = b;
		else b = H*(W-w-1)/2, c = H*(W-w+1)/2;
		s_max = max(max(a,b),c);
		s_min = min(min(a,b),c);
		if(s_max - s_min < ans) ans = s_max - s_min;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAXN	500005
#define INF	1000000005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int a[MAXN], pre[MAXN], suf[MAXN];
int main() {
	int n, d;
	read(n), read(d);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	pre[0] = d;
	for (int i = 1; i <= n; i++)
		pre[i] = min(pre[i - 1], abs(pre[i - 1] - a[i]));
	suf[n] = 1;
	for (int i = n - 1; i >= 1; i--)
		if (suf[i + 1] * 2 <= a[i + 1]) suf[i] = suf[i + 1];
		else suf[i] = min(suf[i + 1] + a[i + 1], INF);
	int q; read(q);
	for (int i = 1; i <= q; i++) {
		int x; read(x);
		if (pre[x - 1] >= suf[x]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Measured memory_bytes: 7808
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// input scanner
var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// util
func max(l []int) int {
	ans := l[0]
	for _, n := range l {
		if n > ans {
			ans = n
		}
	}
	return ans
}

func min(l []int) int {
	ans := l[0]
	for _, n := range l {
		if n < ans {
			ans = n
		}
	}
	return ans
}

// main
func main() {
	sc.Split(bufio.ScanWords)
	c := next()
	r := []rune(c)
	fmt.Println(string((r[0] + 1)))
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>

using namespace std;

void insertionSort(int *, int, int);
void shellSort(int *, int);

int cnt = 0;
int m = 13;

void print_array(int *x, int n, bool f)
{
	if(f)
	{
		for (int k = n - 1; k >= 0; k--)
		{
			if (k == 0)
			{
				printf("%d\n", x[k]);
			}
			else
			{
				printf("%d ", x[k]);
			}
		}
	}
	else
	{
		for (int i = 0; i < n; ++i)
		{
			printf("%d\n", x[i]);
		}
	}
}


int main(int argc, char const *argv[])
{
	int inputSize = 0;
	cin >> inputSize;
	int input[inputSize];

	for (int i = 0; i < inputSize; ++i)
	{
		cin >> input[i];
	}

	shellSort(input, inputSize);
	printf("%d\n", cnt);
	print_array(input, inputSize, false);

	return 0;
}


void insertionSort(int *array, int arraySize, int g)
{
	for (int i = g; i < arraySize; ++i)
	{
		int key = array[i];
		int j = i - g;
		while(j >= 0 && array[j] > key)
		{
			array[j + g] = array[j];
			j -= g;
			cnt++;
		}
		array[j + g] = key;
	}
}


/* g 離れた数に対して挿入ソートを行う */
void shellSort(int *array, int arraySize)
{
	int G[13] = {1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161};

	while(G[m-1] > arraySize) m--;

	printf("%d\n", m);
	print_array(G, m, true);

	for (int i = m - 1; i >= 0; i--)
	{
		insertionSort(array, arraySize, G[i]);
	}
}

Measured memory_bytes: 5048
#include <bits/stdc++.h>
using namespace std;
#define forn for(i=0;i<n;i++)
#define car cin>>h[i]
typedef long long ll;
const ll maxn=100002;
ll dp[maxn];
int main()
{
    ll n,k;
    cin>>n>>k;
    ll h[n+1];
    ll i;
    for(ll i=1;i<=n;i++) cin>>h[i];
    dp[1]=0;
    dp[2]=abs(h[2]-h[1]);
    for(ll i=3;i<=n;i++)
    {
         ll cost = LLONG_MAX;
           for( ll j=1;j<=k;j++)
           {
               if(i-j<=0) continue;
                cost = min(cost, dp[i-j]+abs(h[i-j]-h[i]));
           }
           dp[i]=cost;
    }
    cout<<dp[n]<<"\n";
    return 0;
    
    
     
     
}


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

using namespace std;

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

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int num[3], cnt[3];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n, a[125252];
	cin>>n;
	REP(i, 3){
		num[i]=-1;
	}
	REP(i, n){
		cin>>a[i];
		bool ok=false;
		REP(j, 3){
			if(num[j]==-1){
				num[j]=a[i];
				++cnt[j];
				ok=true;
				break;
			}
			else if(num[j]==a[i]){
				++cnt[j];
				ok=true;
				break;
			}
		}
		if(!ok){
			cout<<"No"<<'\n';
			return 0;
		}
	}
	if(num[1]==-1){
		cout<<(num[0]==0 ? "Yes" : "No")<<'\n';
		return 0;
	}
	if(num[2]==-1){
		if(n%3!=0){
			cout<<"No"<<'\n';
			return 0;
		}
		if(!(cnt[0]*2==cnt[1]) && !(cnt[0]==cnt[1]*2)){
			cout<<"No"<<'\n';
			return 0;
		}
		int idx=0;
		if(cnt[0]*2==cnt[1]){
			idx=1;
		}
		bool can=false;
		if(0==num[(idx+1)&1]){
			can=true;
		}
		cout<<(can ? "Yes" : "No")<<'\n';
	}
	else{
		if(n%3!=0){
			cout<<"No"<<'\n';
			return 0;
		}
		REP(i, 2){
			if(cnt[i]!=cnt[i+1]){
				cout<<"No"<<'\n';
				return 0;
			}
		}
		bool can=false;
		if((num[0]^num[1])==num[2]){
			can=true;
		}
		cout<<(can ? "Yes" : "No")<<'\n';
	}
	return 0;
}


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

// 地点cにいるゴーレムが左(もしくは右)に抜けるか否かをシュミレート
int isOK(int c, string &s, vector<char> &t, vector<char> &d) {
    for(int i = 0; i < t.size(); i++) {
        if(s[c] == t[i]) {
            c += (d[i] == 'L' ? -1 : 1);
        }
        if (c < 0) return 1;
        if (c >= s.size()) return 3;
    }
    return 2;
}

int main() {
    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    vector<char> t(Q), d(Q);
    for(int i = 0; i < Q; i++) {
        cin >> t[i] >> d[i];
    }    

    // ゴーレムはとなりのゴーレムを飛び越えることがないので、相対的位置関係が変わらない
    // ある地点で左に抜けるゴーレムがいたとき、そのひだりのゴーレムは全て抜ける
    // そのため、二分法でその座標を求めることができる

    // 左に抜けるケース
    int ok = -1, ng = N;
    while(abs(ng - ok) > 1) {
        int c = (ng + ok) / 2;

        if(isOK(c, s, t, d) == 1) ok = c;
        else ng = c;
    }
    int ok_l = ok;

    // 右に抜けるケース
    ok = N, ng = -1;
    while(abs(ng - ok) > 1) {
        int c = (ng + ok) / 2;

        if(isOK(c, s, t, d) == 3) ok = c;
        else ng = c;
    }
    int ok_r = ok;

    cout << (ok_r - ok_l - 1) << endl;

    return 0;
}

Measured memory_bytes: 900
#D

def main():
  K = int(input())

  import copy

  ss = ["1","2","3","4","5","6","7","8","9"]
  ss2 = []
  ss3 = ss

  nx = {"0": ["0", "1"],
      "1": ["0", "1", "2"],
      "2": ["1", "2", "3"],
      "3": ["2", "3", "4"],
      "4": ["3", "4", "5"],
      "5": ["4", "5", "6"],
      "6": ["5", "6", "7"],
      "7": ["6", "7", "8"],
      "8": ["7", "8", "9"],
      "9": ["8", "9"],
  }

  i=0
  while i<K:
    for s in ss:
      nxi = nx[s[-1]]
      ss2 += [s+n for n in nxi]
      i+=len(nxi)
    ss = copy.deepcopy(ss2)
    ss3 += ss
    ss2 = []

  print(int(ss3[K-1]))
main()

Measured memory_bytes: 20020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll m,n,k;
ll ksm(int x,int k)
{
	if(k==1) return x;
	ll ans=ksm(x,k/2);
	ans=(ans*ans)%mod;
	if(k%2) ans=ans*x%mod;
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	ll i,j;
	ll cnt=0,cnt2=0,s=0,ans=0;;
	cnt=n*n;
	cnt%=mod;
	for(i=1;i<=m;i++) 
	s=(s+i*(m-i))%mod;
	cnt=(cnt*s)%mod;
	
	cnt2=m*m;
	cnt2%=mod;
	s=0;
	for(i=1;i<=n;i++)
	s=(s+i*(n-i))%mod;
	cnt2=(s*cnt2)%mod;
	
	ans=(cnt+cnt2)%mod;
	ll p=n*m-2;
	for(i=p;i>p-k+2;i--)
	ans=(ans*(i%mod))%mod;
	
	ll q=1;
	for(i=1;i<=k-2;i++) q=(q*(i%mod))%mod;
	
	q=ksm(q,mod-2);
	ans=ans*q%mod;
	cout<<ans;
	return 0;
 } 

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

int main() {
  int a,b,c;cin>>a>>b>>c;
  if (a != b && b != c && c != a) cout << 3 << endl;
  else if (a == b && b == c && c == a) cout << 1 << endl;
  else cout << 2 << endl;
}

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



int main() {

  vector<int> N(32,0);
  N={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

  int K;
  cin >> K;

  cout << N.at(K-1) << endl;

}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int N,r=0;
	vector<int> V(20);

	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>V[i];
	}

	for(int i=0;i<N;i++)
	{
		int c;
		cin>>c;
		r+=max(0,V[i]-c);
	}

	cout<<r;
	return 0;
}


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


void solve(long long A, long long B, long long K){
    ll cnt = 0;
    for(ll i=100; i>= 1; i--){
        if(A%i==0 && B%i==0){
            cnt++;
        }
        if(cnt == K) {
            cout << i << endl;
            break;
        }
    }
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long K;
    scanf("%lld",&K);
    solve(A, B, K);
    return 0;
}


Measured memory_bytes: 256
//Yash Kodesia, IIITM.
#include<bits/stdc++.h>
using namespace std;
#define   debug3(x,y,z)   cout<<x<<" "<<y<<" "<z<<"\n";
#define   present(c,x)    ((c).find(x) != (c).end())
#define   debug2(x,y)     cout<<x<<" "<<y<<"\n";
#define   rep2(i,k,n)     for(int i=k;i<=n;i++)
#define   repd(i,k,n)     for(int i=n;i>=k;i--)
#define   rep1(i,k,n)     for(int i=k;i<n;i++)
#define   linp2(x,y)      ll x,y; cin>>x>>y;
#define   linp1(n)        ll  n; cin>>n;
#define   debug(x)        cout<<x<<"\n";

#define   all(x)          x.begin(),x.end()
#define   vpll            vector<pll >
#define   sz(a)           a.size()
#define   vll             vector<ll>
#define   MOD             1000000007
#define   pll             pair<ll,ll>
#define   ppb             pop_back
#define   INF             1e18+7

#define   ff              first
#define   ss              second
#define   pf              pop_front
#define   pb              push_back
#define   ld              long double
#define   eb              emplace_back
#define   vb              vector<bool>
#define   ll              long long int
#define   vs              vector<string > 

const ll MAX2 = 105;
const ll MAX3 = 1005;
const ll MAX4 = 10005;
const ll MAX5 = 100005;
const ll MAX6 = 1000005;
const ll MAX7 = 10000005;


// Start
 
 
void solve(){
  linp1(n);
  ld t,a;
  cin>>t>>a;
  vector<ld > arr(n);
  rep1(i,0,n)
  	cin>>arr[i],
  	arr[i]=(ld)(t-0.006*arr[i]);
 ld mi=(ld)MAX7;
 ll idx;
 rep1(i,0,n){
 	if((ld)abs(arr[i]-a)<mi){
 		mi=(ld)abs(arr[i]-(ld)a);
 		idx=i;
 	}
 }
 	//mi=min(mi,abs(arr[i]-a));
 cout<<idx+1;	 	

}
int main(){
  int t;
  t=1;
  //freopen ("input.txt","r",stdin);
  //freopen ("output.txt","w",stdout);
  cin.sync_with_stdio(0), cin.tie(0);
  //cin>>t;
  while(t--){
          solve();
          cout<<"\n";
     }
return 0;
}
 

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


void solve(long long N, std::vector<long long> H){
  long long mymax = H[0];
  long long count = 1;
  for(long long i = 1; i < N; i++){
    if(mymax <= H[i]) {
      mymax = H[i];
      count++;
    }
  }

  cout << count << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  std::vector<long long> H(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&H[i]);
  }
    solve(N, std::move(H));
    return 0;
}


Measured memory_bytes: 3676
#include<vector>
#include<map>
#include<algorithm>
#include<set>
#include<iostream>
#include<string>
#include<set>
#include<queue>
#include<random>
#include<unordered_set>

using namespace std;

/*

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

tree<pair<long long, long long>, null_type, less<pair<long long, long long>>, rb_tree_tag, tree_order_statistics_node_update> st;

*/
/*

st.find_by_order();
st.order_of_key();

*/

#pragma GCC optimize("Ofast")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")

#define pb push_back
#define ld long double

mt19937 rnd(51);

const int N = 1e6 + 10;
pair<int,int> mp[N][26];

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<string> v(n);
    int now = 2;
    for (int i = 0; i < n; i++){
        cin >> v[i];
    }
    for (int i = 0; i < n; i++){
        string s = v[i];
        vector<int> have(26);
        for (int i = 0; i < s.size(); i++){
            have[s[i] - 'a']++;
        }
        int st = 1;
        for (int k = 0; k < 26; k++){
            if (have[k] != 0){
                mp[st][k].second++;
            }
        }
        for (int j = s.size() - 1; j > 0; j--){
            have[s[j] - 'a']--;
            if (mp[st][s[j] - 'a'].first == 0){
                mp[st][s[j] - 'a'].first = now++;
            }
            st = mp[st][s[j] - 'a'].first;
            for (int k = 0; k < 26; k++){
                if (have[k] != 0){
                    mp[st][k].second++;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
        int st = 1;
        for (int j = v[i].size() - 1; j > 0; j--){
            st = mp[st][v[i][j] - 'a'].first;
        }
        ans += mp[st][v[i][0] - 'a'].second - 1;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 207300
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

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

long long modpow(long long a, int p) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    int halfP = p / 2;
    long long half = modpow(a, halfP);
    return half * half % MOD;
  } else {
    return a * modpow(a, p - 1) % MOD;
  }
}
long long calcComb(int a, int b) {
  if (b > a - b) return calcComb(a, a - b);

  long long ansMul = 1;
  long long ansDiv = 1;
  for (int i = 0; i < b; i++) {
    ansMul *= (a - i);
    ansDiv *= (i + 1);
    ansMul %= MOD;
    ansDiv %= MOD;
  }
  // ansDivの逆元
  long long ans = ansMul * modpow(ansDiv, MOD - 2) % MOD;
  return ans;
}

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

  lint n, k;
  cin >> n >> k;

  lint sum = 0;
  FOR(i, 1, k + 1) {
    lint ans = 0;
    lint p = n - k + 1;
    lint q = i;

    ans = calcComb(p, q) % MOD;
    ans = (ans * calcComb(k - 1, i - 1)) % MOD;

    if (i - 1 > n - k) {
      ans = 0;
    }

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct data{
	int x,y;
	data(){}
	data(int x,int y):x(x),y(y){}
}q[1001000];
int dist[810][810],k,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},w,h,l,r;
char s[810][810];
int get(int x){
	if(x%k==0)return x/k;
	else return x/k+1;
}
int main(){
	scanf("%d%d%d",&w,&h,&k);
	for(int i=1;i<=w;++i)
		scanf("%s",s[i]+1);
	for(int i=1;i<=w;++i)
		for(int j=1;j<=h;++j)
			if(s[i][j]=='S')q[r++]=data(i,j),dist[i][j]=1;
	while(l<r){
		data d=q[l++];
		if(dist[d.x][d.y]==k+1)continue;
		for(int i=0;i<4;++i){
			int nx=d.x+dx[i],ny=d.y+dy[i];
			if(nx<1||ny<1||nx>w||ny>h)continue;
			if(dist[nx][ny]||s[nx][ny]!='.')continue;
			dist[nx][ny]=dist[d.x][d.y]+1;
			q[r++]=data(nx,ny);
		}
	}
	int ans=1<<30;
	for(int i=1;i<=w;++i)
		for(int j=1;j<=h;++j)if(dist[i][j])
			ans=min(ans,get(min(min(i-1,j-1),min(w-i,h-j)))+1);
	printf("%d",ans);
}

Measured memory_bytes: 8448
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> void max_self(T & a, const T & b) { if(a < b) a = b; }
template<class T> void min_self(T & a, const T & b) { if(a > b) a = b; }
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

string in;
int divisor, N;

int main(){
  FAST_IO
  cin >> in;
  N = stoi(in);
  divisor = 0;
  for(char c : in) divisor += (c - '0');
  
  if(N % divisor) cout << "No\n";
  else cout << "Yes\n";

  return 0;
}


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

using namespace std;

#define Rep(i,a,b)  for (int i=(a);i<(b);i++)
#define rep(i,n)    for (int i=0;i<(n);i++)
#define all(x)      (x).begin(), (x).end()

#define ll long long

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

	string ans = "";
	while (n != 0) {
		if (n % 2) {
			n--;
			ans = "1" + ans;
		} else {
			ans = "0" + ans;
		}
		n /= -2;
	}
	if (ans == "")
		ans = "0";
	cout << ans << endl;

}



Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from operator import itemgetter
 
N,M = map(int,readline().split())
A = list(map(int,readline().split()))
m = map(int,read().split())
BC = list(zip(m,m))
 
BC.sort(key = itemgetter(1),reverse=True)
 
BC.append((N,-1))
 
change = []
for b,c in BC:
    change += [c] * b
    if len(change) > N:
        break
 
A += change
A.sort()
answer = sum(A[-N:])
print(answer)

Measured memory_bytes: 31520
#include<stdio.h>
#include<iostream>
using namespace std;

int main(){

	
	
	int x,y,z;
	while(1){int a[1001]={},b[1001]={},c[1001]={},d[1001]={};
	int N;int n[401]={};
	cin>>x>>y>>z;if(x==0&&y==0&&z==0)break;
	cin>>N;
	for(int i=0;i<401;i++)
		n[i]=2;
	for(int i=0;i<N;i++)
	{	cin>>a[i]>>b[i]>>c[i]>>d[i];

	if(d[i]==1){n[a[i]]=1;n[b[i]]=1;n[c[i]]=1;}
	}


	for(int i=0;i<N;i++){
		if(d[i]==0){
			if(n[a[i]]==1&&n[b[i]]==1)n[c[i]]=0;
			else if(n[a[i]]==1&&n[c[i]]==1)n[b[i]]=0;
			else if(n[c[i]]==1&&n[b[i]]==1)n[a[i]]=0;
		}
	}
	
	for(int i=1;i<=x+y+z;i++)
		cout<<n[i]<<endl;
	}
return 0;
}
	

Measured memory_bytes: 1176
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

namespace A_ABC148
{
    class MainClass
    {

        static int[] s,n;

        public static void Main(string[] args)
        {
            s = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);
            n = Array.ConvertAll(ReadLine().Split().ToArray(), int.Parse);
            int a = 6;
            WriteLine(a-s[0]-n[0]);
            

        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define UP 2000005
#define mod 1000000007
ll pw[UP] = {0, 1};
ll inv[UP] = {1, 1};
ll modinv(ll a, ll p) {
    if (p == 1) return 0;
    ll pp = p, y = 0, x = 1;
    while (a > 1) {
        ll q = a / p, t = p;
        p = a % p, a = t, t = y, y = x - q * y, x = t;
    }
    if (x < 0) x += pp;
    return x;
}
void init() {
	for (int i = 2; i < UP; i++) {
		pw[i] = pw[i-1] * i % mod;
		inv[i] = modinv(pw[i], mod);
		//cout <<  i << " " << pw[i] << " " << inv[i] << "\n";
	}
}
ll C(int a, int b) {
	return pw[a] * inv[a-b] % mod * inv[b] % mod;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int r1, c1, r2, c2;
	cin >> r1 >> c1 >> r2 >> c2;
	init();
	ll ans = 0;
	for (int x = r1; x <= r2; x++) {
		ans = (ans + C(c2 + x + 1, x + 1)) % mod;
		ans = (ans + mod - C(c1 + x, x + 1)) % mod;
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 31488
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() (int, []int) {
	n := readInt()
	return n, readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	n := readInt()
	xa := 0
	bx := 0
	ba := 0
	var ans int
	for i := 0; i < n; i++ {
		s := []byte(readString())
		if s[0] == 'B' && s[len(s)-1] == 'A' {
			ba++
		} else if s[0] == 'B' {
			bx++
		} else if s[len(s)-1] == 'A' {
			xa++
		}
		ans += bytes.Count(s, []byte("AB"))
	}
	if 0 < ba {
		if 1 < ba {
			ans += ba - 1
		}
		if 0 < xa {
			ans++
			xa--
		}
		if 0 < bx {
			ans++
			bx--
		}
	}
	ans += min(xa, bx)
	println(ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// -----------------------------------------------------------------------------


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
const ll mod = 1000000007;
ll dp[2][105][5];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    dp[0][0][0] = 1;
    ll K;
    cin >> S >> K;
    S = "#" + S;
    for(int i = 1; i < S.size(); i++) {
        for(int before = 0; before <= K; before++) {
            for(int digit = 0; digit <= 9; digit++) {
                int after = before;
                if(digit != 0) after++;
                if(char('0' + digit) < S[i]) {
                    dp[1][i][after] += dp[0][i-1][before];
                    dp[1][i][after] += dp[1][i-1][before];
                }
                if(char('0' + digit) == S[i]) {
                    dp[0][i][after] += dp[0][i-1][before];
                    dp[1][i][after] += dp[1][i-1][before];
                }
                if(char('0' + digit) > S[i]) {
                    dp[1][i][after] += dp[1][i-1][before];
                }
            }
        }
    }
    ll ans = 0;
        ans += dp[0][S.size()-1][K];
        ans += dp[1][S.size()-1][K];
    cout << ans;
    return 0;
}

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

public class Main {
	private static final long MOD = 1_000_000_000 + 7;

	// 反復二乗法を用いる
	public static long myPow(long a) {
		long ans = 1L;
		long x = a;
		long b = 1_000_000_000 + 5L;

		for(int i = 0; i < 64; i++) {
			if((b & (1L << i)) != 0L) {
				ans = (ans * x) % MOD;
			}
			x = (x * x) % MOD;
		}

		return ans;
	}

	public static long nck(int n, int k, long[] fact, long[] inverse) {
		if(n < k || n < 0 || k < 0) {
			return 0;
		}
		//	return (((fact[n] * myPow(fact[n - k])) % MOD) * myPow(fact[k])) % MOD;
		return (((fact[n] * inverse[n - k]) % MOD) * inverse[k]) % MOD;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] a = new int[n + 1];
		int[] count = new int[n + 1];

		int tar = 0;
		int l = 0; int r = 0;

		for(int i = 0; i < n + 1; i++) {
			a[i] = sc.nextInt();
			count[a[i]]++;
			if(count[a[i]] == 2) {
				tar = a[i];
				r = i + 1;
			}
		}

		for(int i = 0; i < n + 1; i++) {
			if(a[i] == tar) {
				l = i + 1;
				break;
			}
		}

		// n+1までの階乗の計算
		long[] fact = new long[n + 2];
		fact[0] = 1L;
		long[] inverse = new long[n + 2];
		inverse[0] = 1L;
		for(int i = 1; i <= n + 1; i++) {
			fact[i] = (fact[i - 1] * i) % MOD;
			inverse[i] = myPow(fact[i]) % MOD;
		}

		for(int k = 1; k <= n + 1; k++) {
			//	long comb1 = (fact[n + 1] * ((myPow(fact[n + 1 - k]) * myPow(fact[k])) % MOD)) % MOD;
			long comb1 = nck(n + 1, k, fact, inverse) % MOD;
			//	long comb2 = 0;
			//	if(l + n - r >= k - 1) {
			//		comb2 = (fact[l + n - r] * ((myPow(fact[l + n - r - k + 1]) * myPow(fact[k - 1])) % MOD)) % MOD;
			//	}
			long comb2 = nck(l + n - r, k - 1, fact, inverse) % MOD;
			System.out.println((comb1 - comb2 + MOD) % MOD);
		}
	}
}



Measured memory_bytes: 56380
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private void solve(Scanner sc) {
        int N = sc.nextInt();
        int C = sc.nextInt();
        int K = sc.nextInt();
        int[] T = new int[N];
        for (int i = 0; i < N; ++i) {
            T[i] = sc.nextInt();
        }
        Arrays.sort(T);

        int min = 0;
        int start = K;
        int busCnt = 0;
        int pCnt = 0;
        for (int i = 0; i < N; ++i) {
            if (i == 0) {
                min = T[i];
                start = T[i] + K;
                ++pCnt;
                ++busCnt;
            } else {
                if (T[i] > start) {
                    min = T[i];
                    start = T[i] + K;
                    pCnt = 1;
                    ++busCnt;
                } else if (pCnt >= C) {
                    min = T[i];
                    start = T[i] + K;
                    pCnt = 1;
                    ++busCnt;
                } else {
                    min = T[i];
                    ++pCnt;
                }
            }
        }
        _out.println(busCnt);
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

Measured memory_bytes: 50444
#include <stdio.h>

int main(void)
{  
    int i, flag=0;
    char str[3];

    scanf("%s", str);

    for(i=1; i<3 ;i++) {
        if(str[i-1] != str[i]) {
            flag = 1;
        }
    }

    if(flag == 1) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 1652
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
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; }

lli n;

int main(void){
    cin >> n;
    vector<pair<lli, lli>> d(n);
    lli y = 0;
    rep(i, n){
        lli a, b;
        cin >> a >> b;
        d[i] = {a, b};
        y+=b;
    }
    sort(d.begin(), d.end(), [](const pair<lli, lli> &x, const pair<lli, lli> &y){
        if(x.first+x.second > y.first+y.second) return true;
        else return false;
    });
    lli x = 0;
    rep(i, n){
        if(i%2==0) x+=d[i].first+d[i].second;
    }
    cout << x-y << endl;
    return 0;
}


Measured memory_bytes: 4856
using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.IO.Compression;
using System.Linq;
using System.Text;

namespace Atcoder
{
    class Program
    {
        private const long COMDIV = 1000000007;
        static void Main(string[] args)
        {
            var K = int.Parse(Console.ReadLine());
            int ret = 0;
            for (int i = 1; i <= K; i++)
            {
                for (int j = 1; j <= K; j++)
                {
                    for (int k = 1; k <= K; k++)
                    {
                        ret += Gcd(Gcd(i, j), k);
                    }
                }
            }

            Console.WriteLine(ret);
        }

        public static int Gcd(int a, int b)
        {
            if (a < b)
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
    }
}

Measured memory_bytes: 27480
#include <stdio.h>

int main()
{
    int a, b, n, ans;
    while(scanf("%d %d", &a, &b) != EOF)
    {
        ans = 0;
        n = a + b;
        while (n) {
            n/=10;
            ans++;
        }
        
        printf("%d\n", ans);
    }

    return 0;
}



Measured memory_bytes: 2036
#include <iostream>
#include <cmath>
using namespace std;
int main(){
  double w,h;
  while(cin >> h >> w,w+h){
    int dline = w*w+h*h,Maxline = 1000000;
    int answ,ansh;
    for(int i = 1 ;i <= 149; i++ ){
      for(int j = i+1 ; j <= 150 ; j++ ){
	if(dline < i*i + j*j && i*i + j*j < Maxline ){
	  Maxline = i*i + j*j;
	  ansh = i;
	  answ = j;
	}else if(h < i && dline == i*i + j*j ){
	  Maxline = i*i + j*j;
	  ansh = i;
	  answ = j;
	  goto N;
	}
      }
    }
  N:;
    cout << ansh << " " << answ << endl;
  }
  return 0;
}

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

void direction(char d, int dice[])
{
    int temp;
    switch(d)
    {
        case 'E': temp    = dice[1];
                  dice[1] = dice[4];
                  dice[4] = dice[6];
                  dice[6] = dice[3];
                  dice[3] = temp;
                  break;
        case 'S': temp    = dice[1];
                  dice[1] = dice[5];
                  dice[5] = dice[6];
                  dice[6] = dice[2];
                  dice[2] = temp;
                  break;
        case 'W': temp    = dice[1];
                  dice[1] = dice[3];
                  dice[3] = dice[6];
                  dice[6] = dice[4];
                  dice[4] = temp;
                  break;
        case 'N': temp    = dice[1];
                  dice[1] = dice[2];
                  dice[2] = dice[6];
                  dice[6] = dice[5];
                  dice[5] = temp;
                  break;
        case 'R': temp    = dice[2];
                  dice[2] = dice[3];
                  dice[3] = dice[5];
                  dice[5] = dice[4];
                  dice[4] = temp;
                  break;
    }
    return;
}

int main ()
{
    int dice[7], q;
    for (int i = 1;i <= 6;i++) cin >> dice[i];
    cin >> q;
    
    while(q--)
    {
        int top, front;
        cin >> top >> front;
        if (top == dice[3]) direction('W', dice);
        if (top == dice[4]) direction('E', dice);
        while(top != dice[1])   direction('N', dice);
        while(front != dice[2]) direction('R', dice);
        cout << dice[3] << endl;
    }
    return 0;
}


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  int ans = 0;
  rep(i,n) {
    if (h[i] >= k) ans++;
  }
  cout << ans << endl;
  return 0;
}

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

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'C') {
      for (int j = i + 1; j < s.size(); j++) {
        if (s[j] == 'F') {
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256