akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<iterator>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#define lli long long int
#define mp make_pair
#define ULTRA_INSTINCT ios_base::sync_with_stdio(false); cin.tie(0)
#define PI  3.141592653589793
#define fo(i,n) for(lli i=0;i<(n);i++)
#define FO(i,x,n) for(lli i=(x);i<(n);i++)
#define pb push_back
#define FI first
#define SE second
#define vi vector<lli>
#define pi pair<lli,lli>
#define vii vector<pi >
#define Endl endl
#define ITA 200005
#define ROH 100005
using namespace std;
lli mod = 1e9 +7,test; 
lli max(lli a,lli b){return a>b?a:b;}
lli min(lli a,lli b){return a>b?b:a;}

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

lli n;
vi a(3001);

vector<vi > dp(3001, vi(3001,-1 * mod));

lli f(lli i,lli j){
    if(i>j){ return 0;}
    if(i==j){
        return a[i];
    }
    if(dp[i][j] != -1*mod){
        return dp[i][j];
    }
    return dp[i][j] = max( a[i] + min(f(i+2 , j) , f(i+1 , j-1) ) , a[j] + min(f(i , j-2) , f(i+1 , j-1) ) );
}


void solve(){
    cin>>n;
    lli sum = 0;
    fo(i,n){
        cin>>a[i];
        sum += a[i];
    }
    lli f1 = f(0,n-1);
    lli f2 = sum - f1;
    cout<<  f1 - f2 <<endl;


}

int main(){
    ULTRA_INSTINCT;
    lli t =1;
    // cin>>t;
    fo(i,t){
        solve();
    }
    return 0;

}

Measured memory_bytes: 70912
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
s = list(ins())
t = sorted(s)
ans = 0
for i in range(n):
    if t[i] != "R":
        break 
    if s[i] != t[i]:
        ans += 1
print(ans)

Measured memory_bytes: 12616
x=list(input())
n=len(x)

stack=['T',x[0]]
for i in range(1,n):
  if x[i]=='S':
    stack.append('S')
  else:
    if stack[-1]=='S':
      stack.pop()
    else:
      stack.append('T')
print(len(stack)-1)
  

Measured memory_bytes: 6196
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
int main() {
  int N,A,B;
  cin >> N >> A >> B;
  
  int ans = 0;
  for (int i=0; i<=N; i++) {
    int sum = 0;
    int j= i;
    while(j>0) {
      sum += j%10;
      j /= 10;
    }
    if (sum >= A && sum <= B) {
      ans += i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>
#include<bitset>
#include<stack>
#include<fstream>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> lltpl;
typedef tuple<int, int, int> tpl;

int dy8[8] = { 2,2,-2,-2,1,1,-1,-1 };
int dx8[8] = { 1,-1,1,-1,2,-2,2,-2 };
int dx4[4] = { 1,0,0,-1 };
int dy4[4] = { 0,1,-1,0 };


/******************************************************************************************/

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}

// vector
template <typename T>
istream& operator>>(istream & is, vector<T> & vec) { for (T& x : vec) is >> x; return is; }
// pair
template <typename T, typename U>ostream& operator<<(ostream & os, pair<T, U> & pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; }
// vector
template <typename T>ostream& operator<<(ostream & os, const vector<T> & vec) { os << "{";	for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); }os << "}"; return os; }
// map
template <typename T, typename U>ostream& operator<<(ostream & os, map<T, U> & map_var) { os << "{";	repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; }os << "}"; return os; }
// set
template <typename T>ostream& operator<<(ostream & os, set<T> & set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; }os << "}"; return os; }



const int IINF = 1e9 + 7;
const ll LINF = 1e18 + 7;
constexpr ll MOD = 1e9 + 7;

//ここから書くこと


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	ll n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	ll right = 0;
	ll total = 0;


	for (int i = 0; i < n; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			if (a[i] > a[j]) {
				right++;
			}
		}


		for (int j = 0; j < n; j++)
		{
			if (a[i] > a[j]) {
				total++;
			}
		}

	}
	
	ll ans = 0;

	ans += right * k;
	ans %= MOD;
	ans += (((k * (k - 1) / 2) % MOD) * total) % MOD;
	ans %= MOD;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

    while(true){
      int w = sc.nextInt();
      int h = sc.nextInt();
      if(w == 0 && h == 0) break;

      int n = sc.nextInt();
      boolean[][] t = new boolean[h][w];

      for(int i = 0; i < n; i++){
        int x = sc.nextInt() - 1;
        int y = sc.nextInt() - 1;
        t[y][x] = true;
      }

      int[][] dp = new int[h][w];
      if(!t[0][0]){
        dp[0][0] = 1;
      }

      for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
          if(dp[i][j] == 0) continue;

          if(j + 1 < w && !t[i][j + 1]){
            dp[i][j + 1] += dp[i][j];
          }
          if(i + 1 < h && !t[i + 1][j]){
            dp[i + 1][j] += dp[i][j];
          }
        }
      }

      System.out.println(dp[h - 1][w - 1]);
    }
  }
}

Measured memory_bytes: 12000
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(m)]
C = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]
for i in range(n):
    print(" ".join(map(str, C[i])))

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

using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const int MOD = 1000000007;

int main() {
#ifdef MYLOCAL
    ifstream in("input.txt");
    cin.rdbuf(in.rdbuf());
#endif
    int a, b, c, d, e, k;
    cin >> a >> b >> c >> d >> e >> k;

    if(e-a > k){
        cout << ":(" << endl;
    }
    else{
        cout << "Yay!" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

func getDist(p1, p2 int, dist [][]float64) float64 {
	if p2 < p1 {
		p2, p1 = p1, p2
	}
	return dist[p1][p2]
}

func calcDist(perm []int, dist [][]float64) float64 {
	result := 0.0
	for i := 0; i < len(perm)-1; i++ {
		result += getDist(perm[i], perm[i+1], dist)
	}
	return result
}

func main() {
	scanner := makeScanner(8192)
	n := eGetInt(scanner)
	px := make([]int, n)
	py := make([]int, n)
	for i := 0; i < n; i++ {
		ints := eGetInts(scanner)
		px[i], py[i] = ints[0], ints[1]
	}
	dist := make([][]float64, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]float64, n)
	}
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			sx := px[i] - px[j]
			sy := py[i] - py[j]
			dist[i][j] = math.Sqrt(float64(sx*sx) + float64(sy*sy))
		}
	}

	p := make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = i
	}
	perm := permutations(p)

	result := 0.0
	for _, p := range perm {
		result += calcDist(p, dist)
	}
	fmt.Println(result / float64(len(perm)))
}

////////////////////////////////////////////////////////////////////////////////
// ライブラリ
////////////////////////////////////////////////////////////////////////////////
func makeScanner(maxByte int) *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]uint8, 0, 8192), maxByte)
	return scanner
}
func makeCharScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanRunes)
	return scanner
}
func makeWordScanner() *bufio.Scanner {
	scanner := makeScanner(8192)
	scanner.Split(bufio.ScanWords)
	return scanner
}
func eGetLine(r *bufio.Scanner) string {
	if r.Scan() {
		return r.Text()
	}
	err := r.Err()
	if err != nil {
		log.Fatal(err)
	}
	// EOF
	return ""
}
func eGetInt(r *bufio.Scanner) int {
	line := eGetLine(r)
	return eAtoi(line)
}
func eGetInt64(r *bufio.Scanner) int64 {
	line := eGetLine(r)
	return eAtoInt64(line)
}
func eGetFields(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Fields(line)
}
func eGetInts(r *bufio.Scanner) []int {
	fields := eGetFields(r)
	ints := make([]int, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoi(fields[i])
	}
	return ints
}
func eGetInt64s(r *bufio.Scanner) []int64 {
	fields := eGetFields(r)
	ints := make([]int64, len(fields))
	for i := 0; i < len(ints); i++ {
		ints[i] = eAtoInt64(fields[i])
	}
	return ints
}
func eGetChars(r *bufio.Scanner) []string {
	line := eGetLine(r)
	return strings.Split(line, "")
}
func eAtoi(s string) int {
	n, err := strconv.Atoi(s)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func eAtoInt64(s string) int64 {
	n, err := strconv.ParseInt(s, 10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return n
}
func permutations(arr []int) [][]int {
	var helper func([]int, int)
	res := [][]int{}

	helper = func(arr []int, n int) {
		if n == 1 {
			tmp := make([]int, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					arr[i], arr[n-1] = arr[n-1], arr[i]
				} else {
					arr[0], arr[n-1] = arr[n-1], arr[0]
				}
			}
		}
	}
	helper(arr, len(arr))
	return res
}


Measured memory_bytes: 8064
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<string>


using namespace std;

int main(void)
{
	vector<int> n(3);
	int i;
	for (i = 0; i < 3; i++)
	{
		cin >> n[i];
	}
	sort(n.begin(), n.end());

		if (n[0] + n[1] == n[2])
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	return 0;
}


Measured memory_bytes: 256
import Data.Maybe
import Data.List
import Debug.Trace
import qualified Data.ByteString.Char8 as B
import qualified Data.IntMap.Strict as M

solve :: [[Int]] -> String
solve ((w:h:n:_):b)
  | stack == [0] = "YES"
  | otherwise = "NO"
  where
    edge x y = x == 0 || x == w || y == 0 || y == h
    toLiner (i,(x,y))
      | y == 0 = x
      | x == w = w + y
      | y == h = w + h + w - x
      | otherwise = w + h + w + h - y
    b' = filter (\(x1:y1:x2:y2:_) -> edge x1 y1 && edge x2 y2) b
    ps = concatMap (\(i, x1:y1:x2:y2:_) -> [(i,(x1,y1)), (i,(x2,y2))]) $ zip [1..] b'
    t = M.fromList $ map (\(i,(x,y)) -> (toLiner (i,(x,y)), i)) ps
    stack = M.foldl' (\(z:zs) i -> if i /= z then i : z : zs else zs) [0] t

readInt = fst . fromJust . B.readInt
parse = map (map readInt . B.words)
main = B.getContents >>= putStrLn.solve.parse.B.lines


Measured memory_bytes: 42364
#pragma warning(disable:4996)

#include<iostream>
#include<algorithm>
//#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#define INF 0x3f3f3f3f
#define inf 0x7FFFFFFF
#define MOD 1000000007
#define pii pair<ll,ll>
#define eps 1e-8
#define equals(a,b) (fabs(a-b)<eps)
#define bug puts("bug")
#define re  register
#define fi first
#define se second
const int maxn = 1e7 + 5;
const double Inf = 10000.0;
const double PI = acos(-1.0);
typedef  long long ll;
using namespace std;

ll a[305];
ll m, s;

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%lld", a + i);
	m = a[2];
	for (int i = 3; i < n; i++) m ^= a[i];
	s = a[0] + a[1];
	ll rem = s - m;
	if ((rem % 2) || (rem < 0)) {
		puts("-1");
		return 0;
	}
	rem /= 2;
	ll b = rem;
	int f = 1;
	for (ll i = 50; i >= 0; i--) {
		ll p = 1ll << i;
		if ((m & p) && (rem & p)) f = 0;
		if ((m & p) && ((b + p) <= a[0])) b += p;
	}
	b = a[0] - b;
	if ((b >= a[0]) || (b < 0)) f = 0;
	if (f) printf("%lld", b);
	else puts("-1");
}

Measured memory_bytes: 3828
import java.util.Scanner

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)

    val a = Vector.fill(3)(sc.nextInt()).sorted

    val expected = a(2) * 3
    val now = a.sum

    val ans =
      if ((expected - now) % 2 == 0) (expected - now) / 2
      else (expected - now) / 2 + 2

    println(ans)
  }

  //region

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }

  def printExecTime(process: => Unit): Unit = {
    val start = System.currentTimeMillis
    process
    debug("処理時間： " + (System.currentTimeMillis - start) + " ミリ秒")
  }

  def bitSearch[T](n: Int, choice: Vector[T]): Vector[Vector[T]] = {
    @tailrec
    def bitSearchLogic(n: Int,
                       choice: Vector[T],
                       acc: Vector[Vector[T]]): Vector[Vector[T]] = {
      if (n == 0) acc
      else {
        val newAcc =
          acc.flatMap(vec => {
            choice.map(c => vec :+ c)
          })
        bitSearchLogic(n - 1, choice, newAcc)
      }
    }

    val firstAcc = choice.map(i => Vector(i))
    bitSearchLogic(n - 1, choice, firstAcc)
  }
  //endregion
}


Measured memory_bytes: 27448
//
// Created on 2019-02-03.
//
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }

#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

#define PB push_back
#define INF 1e9
#define MOD 1e9+7
#define EPS 1e-9

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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


    int n, t, sum, max_num;
    cin >> n;
    max_num = 0;
    sum = 0;

    REP(i,n){
        cin >> t;
        sum += t;
        max_num = max(t, max_num);
    }

    if (max_num < sum-max_num) cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
x1,y1,x2,y2 = map(int,input().split())

X = x2-x1
Y = y2-y1

x3 = x2-Y
y3 = y2+X
x4 = x3-X
y4 = y3-Y

print(x3,y3,x4,y4)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 2940
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF 1<<30
#define LINF 1LL<<60
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	ll h, n, w;
	bool f = false;
	for (int i = 1; i <= 3500; i++) {
		for (int j = 1; j <= 3500; j++) {
			ll x = N*i*j;
			ll y = 4 * i*j - N*i - N*j;
			if (y <= 0) continue;
			if (x % y == 0) {
				h = x / y; n = i; w = j;
				f = true;
				break;
			}
		}
		if (f)break;
	}
	cout << h << " " << n << " " << w << endl;
	return 0;
}

Measured memory_bytes: 256
from collections import deque

s = deque(input())
q = int(input())
qu = [[0] * 3] * q
count = 0

for i in range(q):
    qu[i] = input().split()

for i in range(q):
    if qu[i][0] == '1':
        count += 1
        continue

    else:
        if (count + int(qu[i][1])) % 2:
            s.appendleft(qu[i][2])
        else:
            s.append(qu[i][2])

if count % 2:
    s.reverse()

print(''.join(s))

Measured memory_bytes: 107836
#include <stdio.h>

int main(void){

	int r, c;
	int i, j;
	int n[100]={0};
	int z, w=0;

	scanf("%d %d", &r, &c); /* ?????°r??¨?????°c?????\??? */

	int x[r][c];

	for(i=0; i<r; i++){
		for(j=0; j<c; j++){
			scanf("%d", &x[i][j]);
		}		/* 2?????????????????§????????¨??????????¨????????????????????´?????????? */
	}

	for(i=0; i<r; i++){
		z = 0;
		for(j = 0; j < c; j++){
			printf("%d ", x[i][j]);
				z += x[i][j];
				n[j] += x[i][j];	/* (100+1)??(100+1)???2?¬???????????????\??????????¨???? */
		}
		printf("%d\n", z);			/* (r+1)??(c+1)?????°????????¨????????? */
	}
	for(j=0; j<c; j++){
		printf("%d ", n[j]);
			w += n[j];
	}
	printf("%d\n", w);				/* ???????????????????????¨??¨??????????¨????????????\ */

	return 0;
}

Measured memory_bytes: 636
#include <iostream>
#define REP(i, a, b) for (auto i = (a); i < (b); ++i)
using namespace std;

using ll = long long;
const ll mod = 1e9 + 7;

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

	int n; cin >> n; ll a[n];
	REP(i, 0, n) cin >> a[i];
	ll ans = 0, p = 1;
	REP(i, 0LL, 61) {
		ll zc = 0, oc = 0, s = 0;
		REP(j, 0LL, n) { 
			if (a[j] & 1LL) oc++; 
			else zc++;
			a[j] >>= 1LL;
		}
		s = (1LL << i) % mod;
		s = oc * s % mod;
		s = zc * s % mod;
		ans = (ans + s) % mod;
	}
	cout << ans;
}

Measured memory_bytes: 2560
r,c = gets.split.map {|s| s.to_i}
mat = Array.new(r+1).map {Array.new(c+1,0)}
for i in 1..r
  a = gets.split.map {|s| s.to_i}
  for j in 1..c
    mat[i-1][j-1] = a[j-1]
    mat[i-1][c] += a[j-1]
    mat[r][j-1] += a[j-1]
    mat[r][c] += a[j-1]
  end
end
for i in 0..r
  for j in 0..c
    print " " unless j == 0
    print mat[i][j]
  end
  print "\n"
end

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

using namespace std;
typedef long long ll;
ll t , k,n,x , y , a, b,c , d ,sum;
string s;
char ch;
int main()
{
    cin >> n;
    a=26;
    s="";
    while(n>0)
    {
        //n--;
        x=(n-1)%26;
        s+=(x+'a');
        n=(n-1)/26;
    }
    reverse(s.begin(),s.end());
    cout << s;
    return 0;
}


Measured memory_bytes: 3608
from heapq import heappush, heappop
import re
from collections import deque
import sys
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


def main():
    N,K = ints_raw()
    anses = [0]*K
    #anses [1] = (N-K+1)%DIV
    NR = N-K
    for i in range(1,K+1):
        divBK = ncr(K-1,i-1)
        convR = 0
        if NR >= i-1:
            convR = ncr(NR-i+1+i,i)
        anses[i-1]=(divBK*convR)%DIV
    return "\n".join(map(str,anses))


print(main())


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

#define M 1777216
#define L 14

char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ 
  return key % M ; 
}
int h2(int key){ 
  return 1 + key % (M-1); 
}

int find(char str[]){

  long long hv,h;
  int i;
    hv = getKey(str);

    //printf("DEBUG : H[hv] = %s\n",H[hv]);
    for(i=0;1;i++ ) {
      h = ( h1(hv) + i * h2(hv) ) % M;    

      if(strcmp(H[h],str) == 0) {
	return 1;
      } else if(strlen(H[h]) == 0) {
	return 0;
      }
    }
}

int insert(char str[]){

  long long hv,h;
  int i;  

  hv = getKey(str);

  for(i=0;1;i++ ) {
      h = ( h1(hv) + i * h2(hv) ) % M;    
      
      if (strcmp(H[h],str) == 0) {
	return 1;
      }else if(strlen(H[h]) == 0) {
	strcpy(H[h],str);
	return 0;
      }
      
  }  
  return 0;
}

int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);
	
	if ( com[0] == 'i' ){ //select insert
	    insert(str);
	} else {
	  if (find(str)){ //select find
		printf("yes\n");
	    } else {
		printf("no\n");
	    }
	}
    }

    return 0;
}

Measured memory_bytes: 24904
#include<bits/stdc++.h>
 
using namespace std;
using ll=long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
 
int main(){
  string s,t;
    cin>>s>>t;
    int flag=0;
    rep(i,s.length()){
        if(s[i]!=t[i])flag=1;
    }
    if(flag==0 && s.length()+1==t.length()){
        cout<<"Yes\n";
    }
    else cout<<"No\n";
}

Measured memory_bytes: 3564
var lines = [];
var N; var max = 0; var b = []; var flag = false;
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    N = Number(lines[0]);
    b = lines[1].split(" ").map(value => Number(value));
    var result = [];

    for (var i = 0; i < N; i++) {
        var target = -1;
        for (var j = 1; j <= b.length; j++) {
            if (b[j - 1] === j) { target = j; }
        }
        if (target !== -1) result.unshift(b.splice(target - 1, 1));
        else { console.log(-1); return (0) }
    }

    for (var i = 0; i < result.length; i++)
        console.log(result[i].toString());
});

Measured memory_bytes: 9932
#include <vector>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

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

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

  for(int i=0;i<n;i++) {
    if(x[i] >= y[n/2]) {
      cout << y[n/2-1] << endl;
    } else {
      cout << y[n/2] << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std ;
int main(){
  cout.setf(ios::fixed,ios::floatfield);
  double w,h,x,y;
  cin>>w>>h>>x>>y;
  double result = w*h/2;
  if(x==w/2 && y==h/2){
    cout<<result<<" 1"<<endl;
  }else{
    cout<<result<<" 0"<<endl;
  }
  return 0;
}

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

int gcd(int a, int b);

int main()
{
    int N, X;
    cin >> N >> X;
    vector<int> x;
    for(int i=0; i<N; i++)
    {
    	int y;
    	cin >> y;
    	x.push_back(y);
    }
    
    int ans = abs(x[0]-X);
    for(int i=1; i<N; i++)
    {
    	ans = gcd(ans, abs(x[i]-X));
    }

    cout << ans << endl;

	return 0;
}


int gcd(int a, int b)
{
    int m = min(a,b);
    int M = max(a,b);
	if(M%m==0) return m;
	else return gcd(m, M%m);
}

Measured memory_bytes: 892
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

rule = [int(i) for i in input().split()]

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            break
    else:
        count += 1
    state = [0 for i in range(M)]
print(count)

Measured memory_bytes: 42588
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 1e5 + 5;

vector<int> adj [MAX_N];
int color [MAX_N];

int n;
vector<int> path1n;
void find_path (int u, int p) {
  path1n.push_back(u);
  for (int nxt : adj[u]) {
    if (nxt != p) {
      find_path(nxt, u);
    }
  }
  if (path1n.back() != n) {
    path1n.pop_back();
  }
}

void flood (int u, int c) {
  color[u] = c;
  for (int nxt : adj[u]) {
    if (color[nxt] == 0) {
      flood(nxt, c);
    }
  }
}

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

  cin >> n;

  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;

    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  find_path(1, 1);

  for (int i = 0; i < (int) (path1n.size() + 1) / 2; i++) {
    color[path1n[i]] = 1;
  }

  for (int i = (int) (path1n.size() + 1) / 2; i < (int) path1n.size(); i++) {
    color[path1n[i]] = -1;
  }

  for (int u : path1n) {
    flood(u, color[u]);
  }

  int cnt1 = 0, cntn = 0;
  for (int i = 1; i <= n; i++) {
    if (color[i] == 1) cnt1++;
    if (color[i] == -1) cntn++;
  }

  if (cnt1 > cntn) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
}


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

int main() {
    int h, w, n;
    cin >> h >> w >> n;
    vector<vector<int>> c(h, vector<int>(w, 0));
    int row = 0, col = 0, d = 1;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;

        for (int j = 0; j < a; j++) {
            c.at(row).at(col) = i + 1;

            if (col == w - 1 && d == 1) {
                row++;
                d = -1;
            }
            else if (col == 0 && d == -1) {
                row++;
                d = 1;
            }
            else col += d;
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << c.at(i).at(j) << " ";
        }
        cout << endl;
    }
}

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

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())

#define INF 1000000000000 //10^12
#define MOD 1000000007 //10^9+7:合同式の法
 
int main(){
    ll n, x, t;
    cin >> n >> x >> t;

    ll total = n/x;
    if(n%x!=0){
        total++;
    }
    ll time = t*total;

    cout << time << endl;
    
    return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
    int x,a,b;
    scanf("%d",&x);
    scanf("%d",&a);
    scanf("%d",&b);
    x-=a;
    while(b<=x){
        x-=b;
    }
    printf("%d",x);

    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>

using namespace std;

int main() {
  int N;
  string S;
  cin >> N >> S;
  int ans = 1;
  char ch = S[0];
  for(int i = 1; i < N; ++i) {
    if(ch != S[i]) {
      ch = S[i];
      ++ans;
    }
  }
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
const double eps=1e-9;
typedef vector<int> vi;
typedef long long ll;
int n;
int key[105];
string station;
string train="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(void)
{
  while(cin >> n&& n)
    {
      for(int i=0;i<n;i++)
	{
	  cin >> key[i];
	}
      cin >> station;
      int ssize=int(station.size());
      for(int i=0;i<ssize;i++)
	{
	  int back=key[i%n];
	  for(int j=0;j<int(train.size());j++)
	    {
	      if(station[i]==train[j])
		{
		  station[i]=train[(j-back+52)%52];
		  break;
		}
	    }
	}
      cout << station << endl;
    }
  return 0;
}




Measured memory_bytes: 3188
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int K = Integer.parseInt(tokens[0]);
		int X = Integer.parseInt(tokens[1]);

		int min = Math.max(-1000000, X - K + 1);
		int max = Math.min(1000000, X + K - 1);
		StringBuilder strBuilder = new StringBuilder();
		strBuilder.append(Integer.toString(min));
		for (int i = min + 1; i <= max; ++i) {
			strBuilder.append(" " + i);
		}
		System.out.println(strBuilder.toString());
	}
}


Measured memory_bytes: 22740
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
/*---------------------DEBUGGING--------------------------------------------*/
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
/*-------------------------------------------------------------------------------------*/
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define pcc pair<char,char>
#define F first
#define S second
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 998244353//1000000007
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 10000000000000000
#define N 1000001
#define vi vector<int>
#define all(v) v.begin(),v.end()
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int a[5];
   for(int i=0;i<5;i++)
    cin>>a[i];
   for(int i=0;i<5;i++)
   {
       if(!a[i])
       {
           cout<<i+1<<endl;
           return 0;
       }
   }



}


Measured memory_bytes: 3652
import java.util.*;

public class Main {
	
	public static void main(String[] args) {

		// argumentの取得
		Scanner s = new Scanner(System.in);

      int a = s.nextInt();
      int b = s.nextInt();
      int c = s.nextInt();
      int d = s.nextInt();
      
                // String型
	        // String x = s.next();
      
		// 戻り値の返却
      if (a == c) {
        System.out.println(0);
      } else {
        System.out.println(1);
      }
		
	
	} 
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main()
{
 long long n,i,j,s=0,c=0,k;
 char a,b;
 cin>>a>>b;
 if(a=='H')
 {
   if(b=='H') cout<<"H";
   else cout<<"D";
 }
 else
 {
   if(b=='D') cout<<"H";
   else cout<<"D";
 }
return 0;
}


Measured memory_bytes: 3568
#include <array>
  #include <cstdlib>
  #include <cmath>
  #include <climits>
  #include <cfloat>
  #include <map>
  #include <utility>
  #include <set>
  #include <iostream>
  #include <memory>
  #include <string>
  #include <vector>
  #include <algorithm>
  #include <functional>
  #include <sstream>
  #include <deque>
  #include <complex>
  #include <stack>
  #include <queue>
  #include <cstdio>
  #include <cctype>
  #include <cstring>
  #include <ctime>
  #include <iterator>
  #include <bitset>
  #include <numeric>
  #include <list>
  #include <iomanip>
  using namespace std;


  typedef long long LL;
  typedef pair<int,int> pii;
  typedef pair<LL,LL> pll;

  typedef vector<int> vint;
  typedef vector<vector<int> > vvint;
  typedef vector<long long> vll, vLL;
  typedef vector<vector<long long> > vvll, vvLL;

  #define VV(T) vector<vector< T > >

  template <class T>
  void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
  }

  template <class F, class T>
  void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
  }


  #define REP(i,n) for(int i=0;i<int(n);++i)
  #define ALL(v) (v).begin(),(v).end()
  #define RALL(v) (v).rbegin(),(v).rend()
  #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
  #define PB push


  #define MOD 1000000007LL
  #define EPS 1e-10

  struct UnionFind
  {
    vector< int > data;

    UnionFind(int sz)
    {
      data.assign(sz, -1);
    }

    bool unite(int x, int y)
    {
      x = find(x), y = find(y);
      if(x == y) return(false);
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
      return(true);
    }

    int find(int k)
    {
      if(data[k] < 0) return(k);
      return(data[k] = find(data[k]));
    }

    int size(int k)
    {
      return(-data[find(k)]);
    }

    bool same(int x, int y)
    {
        return find(x) == find(y);
    }
  };

  int main()
  {
    LL A, B, C;
    cin >> A >> B >> C;
    cout << (B + min(C, A + B + 1)) << endl;
      return 0;
  }


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

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

int n;
const int maxn = 1e5 + 5;

int a[maxn * 3];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n * 3;i++){
        cin >> a[i];
    }
    sort(a + 1,a + 1 + n * 3);
    ll sum = 0;
    for(int i = n + 1;i <= n * 3;i += 2){
        sum += a[i];
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 1408
from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
alist = list(sorted(d.keys(), reverse = True))
result = 0
for a in alist:
  if a not in d:
    continue
  t = (1 << a.bit_length()) - a
  if t not in d:
    continue
  if a != t:
    if d[a] < d[t]:
      i = d[a]
    else:
      i = d[t]
  else:
    if d[a] == 1:
      continue
    i = d[a] // 2
  result += i  
  if d[a] == i:
    del d[a]
  else:
    d[a] -= i
  if d[t] == i:
    del d[t]
  else:
    d[t] -= i
print(result)


Measured memory_bytes: 44592
#include <stdio.h>

int main(void)
{
	int a, b;
	char op;
	scanf("%d %c %d", &a, &op, &b);
	if(op == '+')
		printf("%d\n", a + b);
	else if(op == '-')
		printf("%d\n", a - b);
        else return;
	return 0;
}


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

using namespace std;

#define rep(i,m,n) for(int i=m;i<n;i++)


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

 vector<double> v(n);
  rep(i,0,n) cin >> v[i];
  sort(v.begin(),v.end());
  

  rep(i,0,n-1) v[i+1]=(v[i]+v[i+1])/2;
 
   
  

   cout << v[n-1] << endl;
}

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

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;

//container util
//------------------------------------------
#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair

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

bool p[1299710];

void erato(){
    fill(p, p+1299710, true);
    p[0] = p[1] = false;
    rep(i, 1299710){
        if(!p[i]) continue;
        for(int j=i+i; j < 1299710; j+=i){
            p[j] = false;
        }
    }
}

int main(){
    long long n;
    erato();
    while(cin >> n, n){
        int ans = 0;
        for(long long i = n; !p[i]; i--) ans++;
        if(!p[n]) for(long long i = n+1; !p[i]; i++) ans++;
        if(ans != 0) cout << ans+1 << endl;
        else cout << 0 << endl;
    }
}

Measured memory_bytes: 2428
double*p,*q,s[99],v;short t[9];main(c){for(p=s+2;~scanf("%[^ \n]%c",t,&c);c-10||printf("%f\n",*--p))v=*--p,q=p-1,*q=*t-43?*t-45?*t-42?*t-47?(sscanf(t,"%lf",&v,p++),*p++=v,*q):*q/v:*q*v:*q-v:*q+v;}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    int N;
    string S;
    cin >> N >> S;
    int l = 0, r = N-1;
    int ans = 0;
    while (l < r) {
        if (S[l] == 'W' && S[r] == 'R') {
            ans++;
            l++, r--;
        }
        else if (S[l] == 'W') {
            r--;
        }
        else if (S[r] == 'R') {
            l++;
        }
        else {
            l++, r--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3728
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;
long long int d[200][200] = {},n;


void dijkstra() {
	
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}


int main() {
	complex<long double>cmpmp;
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	string str,str2,tmp;
	//cout << fixed << setprecision(10);
	long long int res = 0, y, id = 0, m = 0, a[2000], b[2000], c[2000], x, k, ng[2000] = {}, left = 0, dp[100][3] = {};
	cin >>n>> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i != j) { d[i][j] = 9999999999; }
		}
	}

	for (int i = 0; i < m; i++) {
		cin >> a[i]>>b[i]>>c[i];
		d[a[i]][b[i]] = c[i];
		d[b[i]][a[i]] = c[i];
	}

	dijkstra();



	for (int k = 0; k < m; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][j] == c[k] + d[i][a[k]]+d[b[k]][j]) { ng[k] = 1;
				}
			}
		}
	}
	id = m;
	for (int k = 0; k < m; k++) {
		if (ng[k] == 1) { id--; }
	}

	cout << id << endl;
} 


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

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

  int N;  
  cin >> N;
  set<string> S;
  string p;

  
  rep(i, N){
      cin >> p;
      S.insert(p);
      
    }

    cout << S.size() << "\n";
  }




Measured memory_bytes: 19208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
mt19937 rnd;

const int maxn = 5e6, maxk = 5e6 + 1;
int root[maxn], L[16 * maxn], R[16 * maxn], sum[16 * maxn];
int rt = 1, sz = 1;
int lpos[maxk];

int copy(int v, int &u)
{
    L[sz] = L[v];
    R[sz] = R[v];
    sum[sz] = sum[v];
    return u = sz++;
}

void make_root()
{
    copy(root[rt - 1], root[rt]);
    rt++;
}

void add(int pos, int x, int v = root[rt - 1], int l = 0, int r = maxn)
{
	sum[v] += x;
    if(r - l == 1)
        return;
    int m = (l + r) / 2;
    if(pos < m)
        add(pos, x, copy(L[v], L[v]), l, m);
    else
        add(pos, x, copy(R[v], R[v]), m, r);
}

int get(int a, int b, int v, int l = 0, int r = maxn)
{
    if(a <= l && r <= b)
        return sum[v];
    if(r <= a || b <= l)
        return 0;
    int m = (l + r) / 2;
    return get(a, b, L[v], l, m) + get(a, b, R[v], m, r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        make_root();
        add(lpos[t], -1);
        lpos[t] = i;
        add(lpos[t], 1);
    }
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << get(l, r + 1, root[r]) << "\n";
    }

#ifdef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}


Measured memory_bytes: 273764
#include<bits/stdc++.h>
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<int, null_type,
		less_equal<int>, 
		rb_tree_tag,tree_order_statistics_node_update> ordered_mset;
		
typedef tree<int, null_type,
		less<int>, 
		rb_tree_tag,tree_order_statistics_node_update> ordered_set;
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	
 
vector<string>v;
map<string,bool>color;
 
bool comp(string a,string b)
{
	if(a.size()!=b.size()) return a.size()<b.size();
	return a<b;
}
 
 
void dfs(string u)
{
	if(color[u]) return;
	
	color[u]=1;
	v.push_back(u);
	if(u.size()==11) return;
	int x=u.back()-'0';
	if(x==0)
	{
		string a=u+"0";
		string b=u+"1";
		
		dfs(a);
		dfs(b);
	}
	else if(x==9)
	{
		string a=u+(char)(u.back()-1);
		string b=u+(char)(u.back()+0);
		
		dfs(a);
		dfs(b);
	}
	else 
	{
		string a=u+(char)(u.back()-1);
		string b=u+(char(u.back()+0));
		string c=u+(char)(u.back()+1);
		
		dfs(a);
		dfs(b);
		dfs(c);
	}
}
 
void make()
{
	for(int i=1;i<10;i++)
	{
		string x=to_string(i);
		dfs(x);
	}
		
	sort(v.begin(),v.end(),comp);
}
 
void solve()
{
	make();
	
	int n;
	cin>>n;
	
	n--;
	
	cout<<v[n];
	
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	solve();
	
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	
	return 0;
}


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

int main() {
	long x,y,n,m,a,b,c,i,j,k,ans,cur;
	cin >> x >> y >> a >> b >> c;
	
	vector<long> p(a),q(b),r(c);
	for(i=0; i<a; i++){
		cin >> p[i];
	}
	for(i=0; i<b; i++){
		cin >> q[i];
	}
	for(i=0; i<c; i++){
		cin >> r[i];
	}
	sort(p.begin(),p.end());
	sort(q.begin(),q.end());
	sort(r.begin(),r.end());
	
	ans=0;
	for(i=0; i<x; i++){
		ans+=p[a-1-i];
	}
	for(i=0; i<y; i++){
		ans+=q[b-1-i];
	}
	long acur=a-x,bcur=b-y,ccur=c-1,res;
	for(ccur=c-1; ccur>=0; ccur--){
        if(acur<a && bcur<b){
		        res=min(p[acur],q[bcur]);
        
          if(r[ccur]<=res){
		    	break;
		  }else if(res==p[acur]){
				ans-=p[acur];
				acur++;
				ans+=r[ccur];
		  }else{
				ans-=q[bcur];
				bcur++;
				ans+=r[ccur];
		  }
        }else if(acur==a && bcur==b){
          break;
        }else if(acur==a){
          if(r[ccur]<=q[bcur]){
		    	break;
		  }else{
                ans-=q[bcur];
				bcur++;
				ans+=r[ccur];
		  }
        }else{
          if(r[ccur]<=p[acur]){
		    	break;
		  }else{
                ans-=p[acur];
				acur++;
				ans+=r[ccur];
		  }
        }
	}
	cout << ans << endl;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int N;
string s[15];
vector<string> S;
int mar[15][15];
int dp[(1<<15)][15];

int marge(int a,int b){
  for(int i=0;i<(int)S[a].size();i++){
    bool f = true;
    for(int j=0;j<(int)S[b].size()&&i+j<(int)S[a].size();j++){
      if( S[b][j] != S[a][i+j] ) f = false;
      if(!f) break;
    }
    if( f ){
      if( i + S[b].size() <= S[a].size() ) return 0;
      return (int)S[b].size()-(S[a].size()-i);
    }
  }
  return (int)S[b].size();
}
bool contain(int a,int b){
  if( s[a].size() < s[b].size() ) return false;
  for(int i=0;i<(int)s[a].size()-(int)s[b].size()+1;i++){
    if( s[a].substr(i,(int)s[b].size()) == s[b] ) return true;
  }
  return false;
}
#define INF (1<<29)
int main(){
  while( cin >> N && N ){
    for(int i=0;i<N;i++){
      cin >> s[i];
    }
    bool used[15]={};
    for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
	if( i!=j && contain(i,j) ) 
	  used[j] = true;
    
    S.clear();
    for(int i=0;i<N;i++) if( !used[i] ) S.push_back( s[i] );
    N = S.size();

    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
	mar[i][j] = marge(i,j);
      }
    }
    for(int i=0;i<N;i++) mar[N][i] = S[i].size();
    fill(dp[0],dp[(1<<N)],INF);
    dp[0][N] = 0;
    int res = INF;
    for(int i=0;i<(1<<N);i++){
      for(int j=0;j<=N;j++){
	if( i == (1<<N) -1  ) res = min( res, dp[i][j] );
	if( dp[i][j] == INF ) continue;
	for(int k=0;k<N;k++){
	  if( i & (1<<k) ) continue;
	  dp[i|(1<<k)][k] = min( dp[i|(1<<k)][k], dp[i][j] + mar[j][k] );
	}
      }
    }
    cout << res << endl;
  }  
}

Measured memory_bytes: 2180
#include<stdio.h>

int main(void){
  int num;
  scanf("%d", &num);
  int i = 0;
  int n = 0;
  int keta[4];
  keta[0] = num/1000;
  n = num%1000;
  keta[1] = n/100;
  n=n%100;
  keta[2] = n/10;
  n=n%10;
  keta[3] = n;
  int pair1 = 0;
  int pair2 = 0;
  pair1 = keta[0]*10+keta[1];
  pair2 = keta[2]*10+keta[3];
  int yymm = 0;
  int mmyy = 0;
  if(0<pair1&&pair1<13){
    mmyy = 1;
  }
  if(0<pair2&&pair2<13){
    yymm = 1;
  }
  if(mmyy==1&&yymm==1){
    printf("AMBIGUOUS");
  }else if(mmyy==1){
    printf("MMYY");
  }else if(yymm==1){
    printf("YYMM");
  }else{
    printf("NA");
  }
  return 0;
}

Measured memory_bytes: 128