akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdlib>
#include <vector>
#include <string>

class Dice {
    private:
        std::vector<int> number;
        std::vector<int> initialize();
        std::string order_list;
        std::string decide_order();
    public: 
        std::string set_order();
        void move(std::string orders); 
        void print(); 
        Dice() {
            number = initialize();
            order_list = decide_order();
        }
};

int main(void) {
    Dice dice;
    std::string orders = dice.set_order();
    dice.move(orders);
    dice.print();
    return EXIT_SUCCESS;
}

std::vector<int> Dice::initialize() {
    number.resize(6);
    int temp;
    for (int surface = 0; surface < 6; surface++) {
        std::cin >> number[surface];
    }
    return number;
}

std::string Dice::decide_order() {
    std::cin >> order_list;
    return order_list;
}

std::string Dice::set_order() {
    return order_list;
}

void Dice::move(std::string orders) {
    std::vector<int> new_dice(6 ,0);
    int deflt_data[] = {1, 2, 3, 4, 5, 6};
    std::vector<int> deflt(deflt_data, deflt_data + 6);
    int east_data[] = {4, 2, 1, 6, 5, 3};
    std::vector<int> east(east_data, east_data + 6);
    int west_data[] = {3, 2, 6, 1, 5, 4};
    std::vector<int> west(west_data, west_data + 6);
    int south_data[] = {5, 1, 3, 4, 6, 2};
    std::vector<int> south(south_data, south_data + 6);
    int north_data[] = {2, 6, 3, 4, 1, 5};
    std::vector<int> north(north_data, north_data + 6);

    std::string dir;
    for (int loop = 0; loop < orders.size(); loop++) {
        dir = orders[loop]; 
        if (dir == "E") {
            for (int loop = 0; loop < 6; loop++) {
                new_dice[deflt[loop] - 1] = number[east[loop] - 1];
            }
        } else if (dir == "W") {
            for (int loop = 0; loop < 6; loop++) {
                new_dice[deflt[loop] - 1] = number[west[loop] - 1];
            }
        } else if (dir == "S") {
            for (int loop = 0; loop < 6; loop++) {
                new_dice[deflt[loop] - 1] = number[south[loop] - 1];
            }
        } else if (dir == "N") {
            for (int loop = 0; loop < 6; loop++) {
                new_dice[deflt[loop] - 1] = number[north[loop] - 1];
            }
        }
        number = new_dice;
    }
    return;
}

void Dice::print() {
/*
    for (int surface = 0; surface < number.size(); surface++) {
        std::cout << number[surface] << " ";
    }
    std::cout << std::endl;
    */
    std::cout << number[0] << std::endl;
    return;
}

Measured memory_bytes: 3224
n = int(input())
d = []
cnt = 0

for i in range(n):
    d.append(list(map(int, input().split())))

for i in range(n):
    if d[i][0] == d[i][1]:
        cnt += 1
        if cnt == 3:
            print('Yes')
            exit()
    else:
        cnt = 0

print('No')

Measured memory_bytes: 62476
#define _USE_MATH_DEFINES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007; 
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

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





int main(){
    int N, T; std::cin >> N >> T;
    std::vector<std::pair<int, int>> AB(N);
    for(int i(0); i < N; ++i){
        std::cin >> AB[i].first >> AB[i].second;
    }
    std::sort(std::begin(AB), std::end(AB));
    int ans(0);
    //dp[i][j] := (1からi 1o)でj分以内に完食 おいしさの合計max
    std::vector<std::vector<int>> dp(N+1, std::vector<int>(T, 0));
    for(int i(1); i <= N; ++i){
        for(int j(0); j < T; ++j){
            dp[i][j] = dp[i-1][j];
            chmax(ans, dp[i][j] + AB[i-1].second);
            if(j >= AB[i-1].first){
                chmax(dp[i][j], dp[i-1][j-AB[i-1].first] + AB[i-1].second);
            }
        }
    }
    std::cout << ans << std::endl;
    return 0;
}


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

int main(){
  string s;
  cin >> s;
  
  vector<int> N;
  int num0 = '0';
  
  for(int i = 0 ; i < s.size(); i++){
    N.push_back(s.at(i) - num0);
  }
  
  int min = 1000000;
  for(int i = 0 ; i < N.size() - 2; i++){
    int diff = abs(100 * N.at(i) + 10 * N.at(i + 1) + N.at(i + 2) -753);
    if(min > diff) min = diff;
  }
  cout << min << endl;
  return 0;
  
}


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

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

int MOD=1e9+7;
ll INF=1e18;

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

int main(){
    int n; cin>>n;
    vector<int> d(n);
    for(int i=0; i<n; i++) cin>>d[i];

    sort(d.begin(), d.end());

    int ans=1;
    for(int i=0; i<n-1; i++){
        if(d[i]<d[i+1]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
double dp[301][301][301];
long long n;

double func(long long i,long long j,long long k){
    if(!(i||j||k)){
        dp[i][j][k]=0;
        return 0;
    }if(i<0||j<0||k<0){
        return 0;
    }if(dp[i][j][k]!=-1){
        return dp[i][j][k];
    }long long c=0;
    if(i>0)
        c++;
    if(j>0)
        c++;
    if(k>0)
        c++;
        
    dp[i][j][k]=double(n)/(i+j+k)+double(func(i-1,j,k)*i/(i+j+k)+func(i+1,j-1,k)*j/(i+j+k)+func(i,j+1,k-1)*k/(i+j+k));
    
    return dp[i][j][k];
    
}
int main() {
	
    ios_base::sync_with_stdio(false);
    cout.precision(100);
    cout<<fixed;
    cin>>n;
    long long a[n+1];
    for(long long i=0;i<=300;i++){
        for(long long j=0;j<=300;j++){
            for(long long k=0;k<=300;k++){
                dp[i][j][k]=-1;
            }
        }
        
    }
    
    long long x=0,y=0,z=0;
    for(long long i=1;i<n+1;i++){
        cin>>a[i];
        if(a[i]==1){
            x++;
        }else if(a[i]==2){
            y++;
        }else{
            z++;
        }
    }cout<<func(x,y,z);
}


Measured memory_bytes: 213376
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <cmath>
#include <random>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK make_pair
#define PB push_back
#define VI vector<int>
#define VII vector<int,int>
#define MSI map<string,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define W1 while(1);
const int MOD = 1000000007;
int main()
{
	int a, b, c;
	cin>> a >> b >> c;
	if (b - a == c - b)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
def read_input():
    s = input().strip()
    return s


def submit():
    s = read_input()

    result = []
    for c in s:
        if c == 'B':
            result = result[:-1]
        else:
            result.append(c)

    t = ''.join(result)
    print(t)


if __name__ == '__main__':
    submit()


Measured memory_bytes: 2940
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace PaizaTest
{
    class Program
    {
        static void Main(string[] args)
        {
            var st = Console.ReadLine().Split(' ');
            Console.WriteLine(st[1] + st[0]);
        }
        
    }
}



Measured memory_bytes: 11092
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include<set>
#include<queue>
#include <iomanip>

typedef long long ll;

#define rep(i,n) for(ll i=0;i<n;i++)
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; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[20][20];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}
ll dp[20500];
int main() {
	ll a, b, c, x;
	cin >> a >> b >> c >> x;
	ll res = 0;
	rep(i, a + 1) {
		rep(j, b + 1) {
			rep(k, c + 1) {
				if (500 * i + 100 * j + 50 * k == x) {
					res++;
				}
			}
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

int main() {
	long long int n;
	cin >> n;
	long long int ans1 = 1;
	long long int ans2 = 1;
	long long int ans4 = 1;
	for (int i = 0; i < n; i++) {
		ans1 = ans1 * 10;
		ans1 = ans1 % MOD;
		ans2 = ans2 * 8;
		ans2 = ans2 % MOD;
		ans4 = ans4 * 9;
		ans4 = ans4 % MOD;
	}
	long long int ans3 = ans1 - (ans4-ans2) -(ans4-ans2)-ans2;
	ans3 = ans3 % MOD;
	if (ans3 < 0) {
		cout << MOD + ans3;
	}
	else {
		cout << ans3;
	}
}


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

int main(){
  int n,m,p;
  double sum;
  double sumg;
  int gold;
  int x[101];

  while(1){
    sum=0;
    sumg=0;
    gold=0;
    cin >> n >> m >> p;
    if(n==0 && m==0 && p==0)break;
    for(int i=0;i<n;i++){
      cin >> x[i];
      sum+=100*x[i];
    }
    sumg=sum-sum*(p*0.01);
    gold=sumg/x[m-1];
    if(x[m-1]!=0){
      cout << gold <<endl;
    }else{
      cout << 0 << endl; 
    }
  }
}

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

int main(){
  int a,b;
  cin >> a>>b;
  int c=a+b;
  int d=a-b;
  int e=a*b;
  // if(c>d){
  //   if(c>e){cout<<c<<endl;}
  //   else{cout<<e<<endl;}
  // }else if(d>e){cout<<d<<endl;}
  // else{cout<<e<<endl;}
  cout<<max({c,d,e})<<endl;
  return 0;
}

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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ld long double
#define mem(x,y) memset(x,y,sizeof x)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update> ordered_set;

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
/*
 * Be careful of overflow
 * Array bounds
 * Assert a!=0 when performing x/a
 * Check base condition for recursion
 * Iterator -> O(1), Element -> O(log n) while using erase
 * 1LL<<x when x>32
 * Be sure of what you are going to code (exception dp)
 * Don't try fancy tricks during contest
 * You can always make a bad round to a good enough round
 */ 

void solve()
{
	int n;
	cin>>n;
	ll val,ans=0,sum=0;
	for(int i=0;i<n;i++)
	{
		cin>>val;
		ans+=sum*val%mod;
		ans%=mod;
		sum+=val;
		sum%=mod;
	}
	cout<<ans<<'\n';
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


Measured memory_bytes: 3652
import numpy as np


N = int(input())
X = []
L = []
for _ in range(N):
    Xi, Li = map(int, input().split())
    X.append(Xi)
    L.append(Li)

begins = []
ends = []
for i in range(N):
    begins.append(X[i] - L[i])
    ends.append(X[i] + L[i])

b = []
e = []
for i in np.argsort(ends):
    b.append(begins[i])
    e.append(ends[i])
begins = b
ends = e

now = -1e9
cnt = 0
for i in range(N):
    if now <= begins[i]:
        cnt += 1
        now = ends[i]

print(cnt)

Measured memory_bytes: 45816
#include <iostream>

using namespace std;

static const int INF = (1 << 20);

int main()
{
    int n, m;
    cin >> n >> m;
    int c[m + 1];
    for (int i = 1; i <= m; i++)
        cin >> c[i];

    int dp[n + 1]; // dp[i]:i円支払うときのコインの最小枚数
    for (int i = 1; i <= n; i++)
        dp[i] = INF;
    dp[0] = 0;

    for (int i = 1; i <= m; i++)
    {
        for(int j = c[i]; j <= n; j++)
            dp[j] = min(dp[j], dp[j - c[i]] + 1);
    }

    cout << dp[n] << endl;
}


Measured memory_bytes: 3292
#include<bits/stdc++.h>
using namespace std;
int main(){
  char c;cin>>c;
  if(c=='A') cout<<'T'<<'\n';
  if(c=='T') cout<<'A'<<'\n';
  if(c=='G') cout<<'C'<<'\n';
  if(c=='C') cout<<'G'<<'\n';
}

Measured memory_bytes: 256
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

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

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

        if x == y:
            return

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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)

def resolve():
    N, M = LI()
    ab = [LI_() for _ in range(M)]

    ans = 0
    for i in range(M):
        uf = UnionFind(N)
        for j in range(M):
            if j!=i:
                uf.unite(ab[j][0], ab[j][1])
        if not uf.same(ab[i][0], ab[i][1]):
            ans += 1

    print(ans)


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 3064
use std::io::*;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::HashSet;
use std::cmp;
use std::f64::consts;

fn main() {
    let n: i32 = read();
    let mut vec: Vec<i32> = Vec::new();
    vec.push(0);
    let mut input: Vec<i32> = (0..n).map(|_| read()).collect();
    for &i in input.iter() {
        vec.push(i);
    }
    vec.push(0);
    let mut ruisekiwa: Vec<i32> = Vec::new();

    let mut count = 0;
    let mut before = 0;
    for &e in vec.iter() {
        let diff = (before - e).abs();
        count += diff;
        ruisekiwa.push(count);

        before = e;
    }

    let mut max = ruisekiwa[ruisekiwa.len()-1];

    for i in 1..n as usize +1 {
        let mataide = (vec[i+1] - vec[i-1]).abs();
        let original = (vec[i] - vec[i-1]).abs() + (vec[i+1]-vec[i]).abs();
        let diff = original - mataide;
        println!("{}", max - diff);
    }
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// 最大公約数
fn gcd(a: i32, b: i32) -> i32 {
    match b {
        0 => a,
        _ => gcd(b, a % b)
    }
}

// 最小公倍数
fn lcm(a: i32, b: i32) -> i32 {
    a * b / gcd(a, b)
}

// 階乗
fn kaijou(n: i32)->i32 {
    if n == 1 {
        return n;
    }
    return n * kaijou(n-1);
}

Measured memory_bytes: 5244
"""

部屋にいる人数が0の部屋は、操作一回につき一つできうる。が、どこかの部屋には移動しなければならないので、空っぽの部屋がNはあり得ない。
ので、空っぽの部屋の最大数=max(N-1,K)となる

移動方法について考えると、

・空の部屋が0個
行って戻ってを偶数回繰り返す（Kが1の場合はできない）
・空の部屋が１個
適当な部屋に移動をK回繰り返す
・空の部屋が２個
適当な部屋に移動→２人部屋以外に、二人部屋以外の人が移動
・空の部屋がm個
m-1人が別々の部屋に移動→最後の一人が、残り回数が１になるまで移動して、最後に一人部屋に移動

なので、やっぱり 0 or 1 ~ max(N-1,K)の部屋が空っぽになりうる
なので、その範囲について、どのような並び順になるか考える。
空っぽになる部屋の数をrとすると、
・n部屋からr個選ぶ方法 nCr
・残りn-r部屋について、
　人がn人、部屋の数がn-r個->n人と仕切りn-r-1個の並べ方。ただし残りの部屋について0人部屋はないので、
　最初にn-r人を残りの各部屋に割り当てて残りr人。

　** なので、n-rの部屋に重複を許して同質の人間r人を振り分ける方法（重複組み合わせ）と考えられる **

　ooo~oo <-r人の人間
　ここにn-r-1個の仕切りを入れることで、n-rの部屋に残りの人間を振り分ける
　n-rHr = (n-r-1 + r)! / ((n-r)! * r!) = (n-1)! / ((n-r)! * r!) =  n-1Cn-r-1
　

"""


N,K = map(int, input().split())
K = min(N-1, K)
MOD = 10**9 + 7

MAXN = N+10
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD
 
def nHr(n,r):
    return nCr(n+r-1, r)

ans = 0
for r in range(K+1):
    ans += nCr(N,r) * nHr(N-r, r)
    ans %= MOD

print(ans)

Measured memory_bytes: 28340
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define eb emplace_back


#define rep(X,Y) for(int (X) = 0; (X) < (Y) ; ++(X))
#define all(X) (X).begin,(X).end
#define reps(i,j,k) for(inti=(j); i <= (k); ++(i))
#define sz size()
#define in(i,j,k) ((i) >= (j) && (i) <= (k))

using namespace std;
typedef pair<int,int> pii;

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

int main(){
  int n;
  while(cin>>n,n){
    vector<pii> pos;
    pos.eb(0,0);
    rep(i,n-1){
      int a,d;
      cin>>a>>d;
      pos.eb(pos[a].X+dx[d], pos[a].Y+dy[d]);
    }
    int x=0,X=0,y=0,Y=0;
    rep(i,n){
      x=min(x,pos[i].X); X=max(X,pos[i].X);
      y=min(y,pos[i].Y); Y=max(Y,pos[i].Y);
    }
    cout<<X-x+1<<" "<<Y-y+1<<endl;
  }
    return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void counting_sort(const vector<int> &a, vector<int> &b, int k) {
    vector<int> c(k+1);
    for(auto&& x : a) c[x]++;
    for(int i=1; i<=k; i++) c[i] += c[i-1];
    for(int i=a.size()-1; i>=0; i--) b[--c[a[i]]] = a[i];
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    vector<int> b(n);
    counting_sort(a, b, 10000);
    for(int i=0; i<n; i++) cout << b[i] << (i==n-1 ? "\n" : " ");
}


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

using CP = complex<long double>;
#define X real()
#define Y imag()
const long double PI = acos(-1.0L);
const long double EPS = 1e-10;
// conj(x) : complex conjugate,(0,1)->(0,-1)
// abs(x) : dist between(0,0) and x
// norm(x) : abs(x) * abs(x)
// arg(x) : argment

// dot(a,b) = |a||b|cos x
long double dot(CP a, CP b) { return (a * conj(b)).X; }
// cross(a,b) : area of parallelogram
long double cross(CP a, CP b) { return (a * conj(b)).Y; }
long double corner(CP a, CP b) {
  //[0,pi]
  return acos(dot(a, b) / (abs(a) * abs(b)));
}
CP projection(CP p, CP s, CP t) {
  CP base = t - s;
  long double r = dot(p - s, base) / norm(base);
  return s + base * r;
}
CP reflection(CP p, CP s, CP t) {
  CP tmp = (projection(p, s, t) - p);
  tmp *= 2;
  return p + tmp;
}

CP intersection(CP a, CP b, CP c, CP d) {
  return a + (b - a) * (cross(d - c, c - a) /
                        cross(d - c, b - a));
}

bool on_seg(CP a, CP b, CP p) {
  // if not use end point, dot(a - p, b - p) < 0
  return abs(cross(a - p, b - p)) <= 1e-10 &&
         dot(a - p, b - p) <= 0;
}

// crossing lines? (a,b) and (c,d)
bool iscross(CP a, CP b, CP c, CP d) {
  // parallel
  if(abs(cross(a - b, c - d)) <= 1e-10) {
    return on_seg(a, b, c) || on_seg(a, b, d) ||
           on_seg(c, d, a) || on_seg(c, d, b);
  }
  CP isp = intersection(a, b, c, d);
  return on_seg(a, b, isp) && on_seg(c, d, isp);
}

long double distLP(CP a, CP b, CP p) {
  return abs(cross(b - a, p - a) / abs(b - a));
}

// segmentver.
long double distSP(CP a, CP b, CP p) {
  if(dot(b - a, p - a) < 0) return abs(p - a);
  if(dot(a - b, p - b) < 0) return abs(p - b);
  return distLP(a, b, p);
}

// segment and segment
long double distSS(CP a, CP b, CP c, CP d) {
  long double res = 1e18;
  res = min(res, distSP(a, b, c));
  res = min(res, distSP(a, b, d));
  res = min(res, distSP(c, d, a));
  res = min(res, distSP(c, d, b));
  return res;
}

struct convex_hull {
  vector<CP> ch;
  int psize;
  convex_hull() {}
  convex_hull(vector<CP> &ps) { calculation(ps); }
  void calculation(vector<CP> &ps) {
    auto lmd = [&](const CP &l, const CP &r) {
      if(l.X != r.X) return l.X < r.X;
      return l.Y < r.Y;
    };
    psize = ps.size();
    sort(ps.begin(), ps.end(), lmd);
    int k = 0;
    ch.resize(psize * 2);
    for(int i = 0; i < psize; ++i) {
      while(k > 1 && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    for(int i = psize - 2, t = k; i >= 0; --i) {
      while(k > t && cross(ch[k - 1] - ch[k - 2],
                           ps[i] - ch[k - 1]) <= 0)
        --k;
      ch[k++] = ps[i];
    }
    ch.resize(k - 1);
    psize = ch.size();
  }
};

int main() {
  cout << fixed << setprecision(10);
  int a, b, c, d, q;
  cin >> a >> b >> c >> d >> q;
  CP s(a, b), t(c, d);
  while(q--) {
    cin >> a >> b;
    CP res = reflection(CP(a, b), s, t);
    cout << res.X << " " << res.Y << endl;
  }

  cout << endl;
  return 0;
}


Measured memory_bytes: 3372
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    H, W, h, w = map(int, input().split())
    if H % h == 0 and W % w == 0:
        print("No")
    elif H % h == 0:
        print("Yes")
        ans = [[0 for _ in range(W)] for _ in range(H)]
        for i in range(H):
            for j in range(0, W, w):
                ans[i][j] = 99999
                if j + w - 1 < W:
                    ans[i][j + w - 1] = -100000
        for a in ans:
            print(*a)
    else:
        print("Yes")
        ans = [[0 for _ in range(W)] for _ in range(H)]
        for i in range(W):
            for j in range(0, H, h):
                ans[j][i] = 99999
                if j + h - 1 < H:
                    ans[j + h - 1][i] = -100000
        for a in ans:
            print(*a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 7100
#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<pair<int, int>> d(n);
	for (int i = 0; i < n; i++)
		cin >> d[i].first >> d[i].second;
	bool b = false;
	for (int i = 0; i < n - 2; i++)
		if ((d[i].first == d[i].second) &&
			(d[i + 1].first == d[i + 1].second) &&
			(d[i + 2].first == d[i + 2].second))
		{
			b = true;
			break;
		}
	if (b)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define repm(i,a,b) for(ll i=(ll)(a);i>(ll)(b);i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(),(x).rend()
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vc vector<char>
#define vvc vector<vc>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;
using vb =vector<bool>;
using vvb=vector<vb>;
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; }
//snippets:tmp,cl,cvl,cs,co,coy,con,cov,setp

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll d;
    cin >> d;
    vll c(26);
    rep(i, 26) cin >> c[i];
    vvll s(d,vll(26));
    rep(i,d){
        rep(j,26) cin>>s[i][j];
    }
    ll v=0;
    vector<set<int>>set(26);
    rep(i,26) set[i].insert(0);
    rep(i,d){
        ll ma=0;
        ll key=0;;
        rep(j,26){
            if(ma<c[j]*(i+1-(*--set[j].end()))+s[i][j]){
                key=j;
                ma=c[j]*(i+1-(*--set[j].end()))+s[i][j];
            }
            v-=c[j]*(i+1-(*(--set[j].end())));
        }
        set[key].insert(i+1);
        cout<<key+1<<endl;
    }
}

Measured memory_bytes: 3756
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <list>
#include <numeric>
#include <map>
#include <cmath>
#include <string>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define Cout(s) cout<<s<<endl

bool sosuu(const int x)
{
	if (x == 2)return true;
	if (x < 2 || x % 2 == 0)return false;
	for (int i = 3; i * i <= x; i += 2)
		if (x % i == 0)return false;
	return true;
}

typedef long long ll;
using namespace std;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================

int a = 0, b = 0, c, d, n, k = 0,ans=0;
string s, t;


int main()
{
	int d, n, ans = 1;
	cin >> d >> n;
	rep(i, d)
		ans *= 100;
	if (n == 100)
	{
		cout << ans * n + ans << endl;
	}
	else
		cout << ans * n << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

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

    string s;
    ll K;
    cin >> s >> K;

    ll n = s.size();
    ll cnt = 0;
    Rep (i, n) {
        if (s[i] == 'a') continue;
        ll sub = 'z' - s[i] + 1;
        if (cnt + sub <= K) {
            s[i] = 'a';
            cnt += sub;
        }
    }

    if (cnt < K) {
        ll sub = (K - cnt) % 26;
        while (sub) {
            if (s[n-1] != 'z') s[n-1]++;
            else s[n-1] = 'a';
            sub--;
        }
    }

    cout << s << endl;

}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

const int M=100001;
int n,vis[2*M],A,B;
vi g[2*M];

void dfs(int v){
	vis[v]++;
	if(v<M) A++;
	else B++;
	for(auto u:g[v]) if(!vis[u]) dfs(u);
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x,y;
		cin>>x>>y;
		g[x].push_back(y+M);
		g[y+M].push_back(x);
	}
	ll res=-n;
	for(int i=0;i<M;i++) if(!vis[i]){
		A=0,B=0;
		dfs(i);
		res+=(ll)A*B;
	}
	cout<<res<<endl;
}

Measured memory_bytes: 10752
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef pair<int,int>P;
typedef long long ll;

int dp[300][20000];
int w[300];

int main(){
	int n,W;scanf("%d%d",&n,&W);
	rep(i,n)scanf("%d",&w[i]);
	sort(w,w+n,greater<>());
	dp[0][0]=1;
	rep(i,n)rep(j,W+1){
		(dp[i+1][j]+=dp[i][j])%=MOD;
		if(j+w[i]<=W){
			(dp[i+1][j+w[i]]+=dp[i][j])%=MOD;
		}
	}
	int ans=0;
	int sum=0;
	rep(i,n)sum+=w[i];
	if(sum<=W)ans++;
	rep(i,n){//使わない最小
		sum=0;
		for(int j=i+1;j<n;j++)sum+=w[j];
		for(int j=max(sum,W-w[i]+1);j<=W;j++){
			(ans+=dp[i][j-sum])%=MOD;
		}
	}
	cout<<ans<<endl;
}


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

int main() {
	int k;
	cin>>k;
	int a, b;
	cin>>a>>b;
	for(int i=a; i<=b; i++) {
		if(i%k == 0) {
			cout<<"OK\n";
			return 0;
		}
	}
	cout<<"NG\n";
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long double PI = 3.14159265358979323846;

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

    string s, t;
    getline(cin, s);
    getline(cin, t);
    bool ans = true;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
        if (s[i] != t[i]) {
            ans = false;
            break;
        }
    }
    if (ans) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}


Measured memory_bytes: 3644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main {
	public static void main(String[] args)throws IOException {
		FastReader sc = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
		int  wt = sc.nextInt();
		int sum = sc.nextInt();
		int weight[] = {2, 4};
		int value[] = {1, 1};
		boolean ans = knapsack(weight, value, wt, sum, 2);
      if(ans)
		System.out.println("Yes");
      else
        System.out.println("No");



	}
	public static boolean knapsack(int weight[], int value[], int wt, int sum, int n) {
		if (n == 0) {
			if (sum == 0 && wt == 0) {
				return true;
			}
			return false;
		} else if (sum == 0 && wt == 0) {
			return true;
		}

		else if (sum < 0 || wt < 0)
			return false;

		boolean ans = knapsack(weight, value, wt - 1, sum - weight[n - 1], n) || knapsack(weight, value, wt - 1, sum - weight[n - 1], n - 1) || knapsack(weight, value, wt, sum, n - 1);
		return ans;

	}
}





class FastReader {
	BufferedReader br;
	StringTokenizer st;

	public FastReader() {
		br = new BufferedReader(new
		                        InputStreamReader(System.in));
	}

	String next() {
		while (st == null || !st.hasMoreElements()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException  e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	String nextLine() {
		String str = "";
		try {
			str = br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}
}

Measured memory_bytes: 32892
#include<iostream>
#include<cstdio>
#define _USE_MATH_DEFINES
#include<cmath>
#include<vector>
#include<map>
using namespace std;


#define INF 1e+10
#define EPS 1e-10
#define EQ(a,b) (abs(a-b)<EPS)

//誤差を考慮して足し算
double add(double a,double b){
	if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0;
	return a+b;
}
struct P{//2次元ベクトル
	double x,y;
	P(){}
	P(double x,double y):x(x),y(y){}
	P operator + (P p){
		return P(add(x,p.x),add(y,p.y));
	}
	P operator - (P p){
		return P(add(x,-p.x),add(y,-p.y));
	}
	P operator * (double d){
		return P(x*d,y*d);
	}
	P operator / (double d){
		return P(x/d,y/d);
	}
	double dot(P p){//内積
		return add(x*p.x,y*p.y);
	}
	double det(P p){//外積
		return add(x*p.y,-y*p.x);
	}
	bool equal(P p){
		return (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y) < EPS*EPS;
	}
};
//typedef pair<P,P> Line;

//線分p1-p2上に点qがあるか判定
bool on_seg(P p1,P p2,P q){
	return (p1-q).det(p2-q)==0 && (p1-q).dot(p2-q)<=0;
}
//直線p1-p2と直線q1-q2の交点
P intersection(P p1,P p2,P q1,P q2){
	return p1+(p2-p1)*( (q2-q1).det(q1-p1)/(q2-q1).det(p2-p1) );
}


//線分p1-p2と線分q1-q2が交差するか
bool intersecting(P p1,P p2,P q1,P q2){
	if(on_seg(p1,p2,q1)||on_seg(p1,p2,q2)||on_seg(q1,q2,p1)||on_seg(q1,q2,p2))return true;
	if((p1-p2).det(q1-q2)==0 )return false;//平行
	P a=intersection(p1,p2,q1,q2);
	return on_seg(p1,p2,a) && on_seg(q1,q2,a);
}
//原点中心回転
P rotate(P p,double rad){
	double s=sin(rad),c=cos(rad);
	return P(c*p.x-s*p.y, s*p.x+c*p.y);
}
//originを中心回転
P rotate(P p,double rad,P origin){
	return origin + rotate(p - origin,rad);
}
//二点間の距離
double dist(P p,P q){
	p = p-q;
	return sqrt(p.x*p.x+p.y*p.y);
}
//単位ベクトルに変換
P to_unit(P p){
	double d = sqrt(p.x*p.x+p.y*p.y);
	return p/d;
}
//円同士の交点を計算
pair<P,P> circle_intersection(double x1,double y1,double r1,double x2,double y2,double r2){
	double rad = atan2(y2-y1,x2-x1);
	x2 -= x1;
	y2 -= y1;
	P tmp = rotate(P(x2,y2),-rad);
	x2 = tmp.x;
	y2 = tmp.y;
	double x = (r1*r1-r2*r2+x2*x2)/(2*x2);
	if(abs(r1) < abs(x))return make_pair(P(0,0),P(0,0));//交点なし
	double y = sqrt(r1*r1-x*x);
	return make_pair( P(x1,y1)+rotate(P(x,y),rad) ,  P(x1,y1)+rotate(P(x,-y),rad) );
}
//線分と点の距離
double dist_lp(P p1,P p2,P q){
	double dx,dy;
	dx = p1.x-p2.x;
	dy = p1.y-p2.y;
	double d = min(dist(p1,q) ,dist(p2,q));
	pair<P,P> normal= make_pair(q+to_unit(P(-dy,dx))*d ,q+to_unit(P(dy,-dx))*d);//法線ベクトル
	if(intersecting(p1,p2,normal.first,normal.second)){
		return dist(q, intersection(p1,p2,normal.first,normal.second));
	}
	return d;
}
//線分同士の距離
double dist_ll(P p1,P p2,P q1,P q2){
	if(intersecting(p1,p2,q1,q2))return 0;
	return min( min(dist_lp(p1,p2,q1),dist_lp(p1,p2,q2))
		,min(dist_lp(q1,q2,p1),dist_lp(q1,q2,p2)) );
}
//ラジアンに変換
double radian(double angle){
	return angle/180.0*M_PI;
}


int main(){
	P a,b,c,g;
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a.x>>a.y;
		cin>>b.x>>b.y;
		cin>>c.x>>c.y;
		g = intersection((a+b)/2,(a+b)/2+P(-(a.y-b.y),a.x-b.x),
			    (a+c)/2,(a+c)/2+P(-(a.y-c.y),a.x-c.x) );
		printf("%.3f %.3f %.3f\n",g.x,g.y,dist(g,a));
	}
	return 0;
}

Measured memory_bytes: 1252
package main

import "fmt"

func min(vs []int) int {
	min_v := vs[0]
	for _, v := range vs {
		if v < min_v {
			min_v = v
		}
	}
	return min_v
}

func max(vs []int) int {
	max_v := vs[0]
	for _, v := range vs {
		if v > max_v {
			max_v = v
		}
	}
	return max_v
}

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	for i := range as {
		fmt.Scan(&as[i])
	}
	fmt.Println(max(as) - min(as))
}


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

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            long N = cin.ReadLong;
            long minAns = N - 1;
            for(long i=1;i<= Floor(Sqrt(N)); i++)
            {
                if (N % i != 0) continue;
                long b = N / i;
                if ((i + b-2) < minAns)
                {
                    minAns = i + b - 2;
                }
            }
            Console.WriteLine(minAns);
        }
            

                
    }  
            


    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
        public double[] ReadDoubleArray(long N) { var ret = new double[N]; for (long i = 0; i < N; ++i) ret[i] = ReadDouble; return ret; }
    }
}


Measured memory_bytes: 13268
import math


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M = read_ints()
    students, checkpoints = [], []
    for _ in range(N):
        students.append(read_ints())
    for _ in range(M):
        checkpoints.append(read_ints())
    for s in students:
        min_dist = math.inf
        min_j = math.inf
        for j, c in enumerate(checkpoints, start=1):
            if abs(s[0]-c[0])+abs(s[1]-c[1]) < min_dist:
                min_dist = abs(s[0]-c[0])+abs(s[1]-c[1]) 
                min_j = j
        print(min_j)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 68968
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < n; i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    ll r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

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

int main() {
    int a, b; cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  flag=True
  f=format(i,'b')
  if len(f)<n:
    f='0'*(n-len(f))+f
  for j in range(m):
    tmp=arr[j][1:]
    cnt=0
    for k in range(len(tmp)):
      if f[tmp[k]-1]=='1':
        cnt+=1
    cnt=cnt%2
    if p[j]!=cnt:
      flag=False
  if flag==True:
    ans+=1
print(ans)

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

typedef long long ll;
const int mod=1e9 + 7;

void dfs(int s,int p,list<int>* adj,vector<ll>& w,vector<ll>& b){
	for(int c:adj[s]){
		if(c==p)
			continue;
		dfs(c,s,adj,w,b);

		w[s]*=(b[c]+w[c]);
		w[s]%=mod;

		b[s]*=w[c];
		b[s]%=mod;
	}
}

int main(){

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

	int n;cin>>n;
	list<int>* adj=new list<int>[n+1];
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	vector<ll> w(n+1,1);
	vector<ll> b(n+1,1);

	dfs(1,0,adj,w,b);
	int ans=(b[1]+w[1])%mod;
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 21536
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
typedef long long LL;

int main(){
  int K;
  cin >> K;
  queue<LL> q;
  rep(i,9) q.emplace(i+1);
  int num=1;
  while(1){
    LL N=q.front(); q.pop();
    if(num==K){
      cout << N << endl;
      return 0;
    }
    if(N%10!=0) q.emplace(N*10+N%10-1);
    q.emplace(N*10+N%10);
    if(N%10!=9) q.emplace(N*10+N%10+1);
    num++;
  }

  return 0;
}


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()

vector<i64> a, f;

int main(){
    i64 n, k;
    cin >> n >> k;
    a.resize(n); f.resize(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> f[i];
    sort(all(a), greater<i64>());
    sort(all(f));
    i64 ng = 1e18 + 100, ok = -1;
    while(abs(ok - ng) > 1){
        i64 mid = (ok + ng) / 2;
        i64 sum = 0;
        rep(i, n){
            i64 lim = mid / f[i];
            sum += max(0LL, a[i] - lim);
        }
        if(sum <= k) ng = mid;
        else ok = mid;
    }
    cout << ok + 1 << endl;
}

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

double kakuritu(int a,int k,int n){
    int cnt=0;
    double b = 1.0/n;
    if(a >= k) return b;
    else{
        while(a<k){
            a *= 2;
            cnt++;
        }
        return 1.0/n*pow(1.0/2,cnt);
    }
}

int main(){
    int n,k;
    cin >> n >> k;
    double ans=0;
    for(int i=1; i<=n; i++){
        ans += kakuritu(i,k,n);
    }
    cout <<fixed << setprecision(15)<< ans << endl;
}

Measured memory_bytes: 256
import java.io.*;
 class Main {
 public static void main(String[] args) throws IOException {
 BufferedReader br;
 br=new BufferedReader(new InputStreamReader(System.in));
int target=Integer.parseInt(br.readLine());
 int man = target / 1000;
 int sen = target / 100 % 10;
 int hyaku = target / 10 % 10;
 int iti = target % 10;
 int count = 0;
 if(man == 2) { count++;}
 if(sen == 2) {count++;}
 if(hyaku == 2) { count++;}
if(iti == 2) { count++;}
 System.out.println(count); }
}

Measured memory_bytes: 22484
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pl;

#define FST first
#define SND second

const int MAX_N = 100000;                  // 10^5
// const int MAX_N = 100000;                  // 10^5
// const int MAX_N = 1000000000;              // 10^9
// const ll  MAX_N = 1000000000000000000;     // 10^18
const int BASE  = 1000000000 + 7;          // 10^9 + 7
// const int INFI  = 1000000000 + 7;          // 10^9 + 7
// const ll INFL  = 1000000000000000000 + 7; // 10^18 + 7

int N, M;
ll A[MAX_N + 1];
ll FACT[MAX_N + 2], IFACT[MAX_N + 2];

ll mod_pow(ll a, ll n, ll base) {
  ll res = 1;
  while (n > 0) {
    if (n % 2 == 1) res = (res * a) % base;
    a = (a * a) % base;
    n >>= 1;
  }
  return res;
}

void build_mod_fact(int n, ll base) {
  FACT[0] = 1;
  for (int i = 1; i <= n; i++) FACT[i] = (FACT[i - 1] * i) % base;
  for (int i = 0; i <= n; i++) IFACT[i] = mod_pow(FACT[i], base - 2, base);

#ifdef DEBUG
  for (int i = 0; i <= n; i++)
    cout << i << " " << FACT[i] << " " << IFACT[i] << " " << (FACT[i] * IFACT[i]) % base << endl;
#endif
}

ll mod_comb(int n, int k, ll base) {
  if (k < 0 || k > n) return 0;
  ll ret = (IFACT[k] * IFACT[n - k]) % base;
  ret = (ret * FACT[n]) % base;
  return ret;
}

int calc_m() {
  ll pos[MAX_N];
  for (int i = 0; i < N; i++) pos[i] = -1;

  for (int i = 0; i < N + 1; i++) {
    if (pos[A[i]] >= 0) return pos[A[i]] + N - i;
    pos[A[i]] = i;
  }

  return -1;
}

void solve() {
  build_mod_fact(N + 1, BASE);

  M = calc_m();

  for (int k = 1; k <= N + 1; k++) {
    ll cn = mod_comb(N + 1, k, BASE);
    ll cm = mod_comb(M, k - 1, BASE);
    cout << (cn - cm + BASE) % BASE << endl;
  }
}

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

  solve();

  return 0;
}


Measured memory_bytes: 4352