akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);

  int x;
  cin >> x;
  bool flag = true;

  while(flag){
    flag = false;
    FOR(j,2,x){
      if(x % j == 0){
        flag = true;
        break;
      }
    }
    x++;
  }

  cout << x - 1 << endl;

  return 0;
}

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

namespace AthleteProgramming2
{
    class Program
    {
        static void Main()
        {
            int verticalLine = int.Parse(Console.ReadLine());

            int[] array = new int[verticalLine];
            for (int i = 0; i < verticalLine; i++)
            {
                array[i] = i + 1;
            }

            int horizontalLine = int.Parse(Console.ReadLine());
            int[] verticalArray = new int[2];
            for (int i = 0; i < horizontalLine; i++)
            {
                verticalArray = Console.ReadLine().Split(',').Select(int.Parse).ToArray();
                Swap(ref array[verticalArray[0]-1], ref array[verticalArray[1]-1]);
            }
            for (int i = 0; i < array.Length; i++)
            {
                Console.WriteLine(array[i]);
            }
        }

        static void Swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
    }
}

Measured memory_bytes: 9516
#include <iostream>

using namespace std;

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


Measured memory_bytes: 3080
#include <stdio.h>
int main(void)
{
    int N,X;
    int m[1100];
    int min=1100;
    scanf("%d%d", &N, &X);
    for(int i=0;i<N;i++){
        scanf("%d", &m[i]);
        if(min>m[i]) min=m[i];
        X-=m[i];
    }
    printf("%d\n",N+X/min);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>

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

    for (int i = 0; i * 4 <= n; i++) {
        int amari = n - i * 4;
        if (amari % 7 == 0) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }

    std::cout << "No" << std::endl;

    return 0;
}


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

int main() {
    int n;
    while (cin >> n, n) {
        vector<char> name(n);
        vector<int> cnt_w(n), cnt_l(n);
        for (int i = 0; i < n; i++) {
            cin >> name[i];
            for (int j = 0; j < n - 1; j++) {
                int r; cin >> r;
                if (r == 0) cnt_w[i]++;
                if (r == 1) cnt_l[i]++;
            }
        }
        vector<vector<int>> res(n);
        for (int i = 0; i < n; i++) res[cnt_w[i]].emplace_back(i);
        for (int w = 0; w < n; w++) {
            sort(res[w].begin(), res[w].end(), [&](int i, int j) {
                if (cnt_l[i] == cnt_l[j]) return i < j;
                else return cnt_l[i] < cnt_l[j];
            });
        }
        for (int w = n - 1; w >= 0; w--){
            for (int idx: res[w]) cout << (char)name[idx] << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3092
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 1000000007


def nck(n, k, mod):
    bunbo = bunshi = 1
    for i in range(k):
        bunshi = (bunshi * (n-i)) % mod
        bunbo = (bunbo * (i+1)) % mod
    return (bunshi * pow(bunbo, mod-2, mod)) % mod


def patterns(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    elif (n < 3):
        return n
    ret = [0]*(n+1)
    ret[1] = 1
    ret[2] = 2
    for i in range(3, n+1):
        ret[i] = ret[i-2] + ret[i-1]
    # print('ret', ret[n])
    return ret[n]


N, M = list(map(int, input().split()))
a = [0]*M
for i in range(M):
    a[i] = int(input())
a.append(N+1)
start = 0
ans = 1
for lack in a:
    steps = (lack - 1) - start
    # print('start', start)
    # print('lack', lack)
    # print('input', steps)
    ans = (ans * patterns(steps)) % mod
    # ans = ans % mod
    start = lack + 1
print(ans % mod)


Measured memory_bytes: 468940
#include <stdio.h>

int main(void){

   int num1,num2;
   int count;
   
   while(1){
      num1 = -1;
      scanf("%d %d", &num1, &num2);
      
      if(num1 < 0)break;

      num1 += num2;
   
      while(num1!=0){
         num1 /= 10;
         ++count;
      }
   
      printf("%d\n",count);
      num1 = 0;
      num2 = 0;
      count = 0;
   }
   return 0;
}

Measured memory_bytes: 600
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, K = map(int, input().split())

    d = [True]*N
    for K in range(K):
        dl = input()
        A = list(map(int, input().split()))
        for a in A:
            d[a-1] = False
    print(sum(d))




if __name__ == '__main__':
    main()

Measured memory_bytes: 67528
import java.util.*;
public class Main {

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

		int N=scan.nextInt();
		int[] H=new int[N];
		
		for (int i=0;i<N;i++) {
			H[i]=scan.nextInt();
		}
		int max=0;
		int count=0;
		int last=H[0];
		
		for(int i=1;i<H.length;i++) {
			if (last>=H[i]) {
				count+=1;
				if (count>max) {
					max=count;
					
				}
				
			}else {
				count=0;
			}
		last=H[i];
		}
		System.out.print(max);
}

}

Measured memory_bytes: 48440
#include <iostream>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;
    auto c = stoi(a+b);
    for (int i = 0; i <= 1000; ++i) {
        if (i * i == c) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
import itertools
import sys
from typing import Callable, List, NoReturn


def main() -> NoReturn:
    readline: Callable[[], str] = sys.stdin.readline
    n, k = map(int, readline().rstrip().split())  # type: int,...
    p: List[int] = [int(_) for _ in readline().rstrip().split()]
    p.sort()
    print(sum(p[:k]))


if __name__ == '__main__':
    main()


Measured memory_bytes: 10100
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.split(/ |\n/),
    cid = 0;

function next() {
    return +cin[cid++];
} // number一個取得
function nextstr() {
    return cin[cid++];
} // 文字列一個取得
function nextbig() {
    return BigInt(cin[cid++]);
} // BigInteger一個取得
// 長さnの配列として取得。aは文字列フラグ
function nexts(n, a) {
    return a ? cin.slice(cid, cid += n) : cin.slice(cid, cid += n).map(a => +a);
}
// 長さnのBigInt配列として取得。
function nextsbig(n) {
    return cin.slice(cid, cid += n).map(a => BigInt(a));
}
// w個ずつを組にして長さhの配列。aは文字列フラグ。
function nextm(h, w, a) {
    var r = [],
        i = 0;
    if (a)
        for (; i < h; i++) r.push(cin.slice(cid, cid += w));
    else
        for (; i < h; i++) r.push(cin.slice(cid, cid += w).map(a => +a));
    return r;
}
// 多次元配列。v,a1,a2,a3 なら、3次元。[[値vで長さa3の配列]をa2個並べた配列]をa1個並べた配列。
function xArray(v) {
    var a = arguments,
        l = a.length,
        r = "Array(a[" + --l + "]).fill().map(x=>{return " + v + ";})";
    while (--l) r = "Array(a[" + l + "]).fill().map(x=>" + r + ")";
    return eval(r);
}


console.log(main().toString());

function main() {
    let n = next();
    let a = next();
    return a >= 500 || n % 500 <= a ? 'Yes' : 'No'
}

Measured memory_bytes: 7372
using System;

namespace AtCoder{
    public static class AtCoder{
        public static void Main(){
            var input = Console.ReadLine().Split(' ');
            for(int i = 0; i < 5; i++){
                if(input[i] == "0"){
                    Console.WriteLine(i+1);
                    return;
                }
            }
            return;
        }
    }
}

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

using namespace std;

const int maxn = 1000;
const int mod = 1000000007;

long long int dp[maxn][maxn];

int main(){
	int h, w;
	cin >> h >> w;
	string grid[h];
	for (int i = 0; i < h; i++){
		cin >> grid[i];
	}
	for (int i = 0; i < w; i++){
		if (grid[0][i] == '#'){
			break;
		}
		dp[0][i] = 1;
	}
	for (int i = 0; i < h; i++){
		if (grid[i][0] == '#'){
			break;
		}
		dp[i][0] = 1;
	}
	for (int i = 1; i < h; i++){
		for (int j = 1; j < w; j++){
			if (grid[i][j] == '.'){
				dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
			}
		}
	}
	cout << dp[h-1][w-1] << endl;
	return 0;
}


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

using namespace std;

#define FOR(i,l,r) for( int i = l-(l>r); i != r-(l>r); i += 1-2*(l>r) )
#define st string
#define pb push_back
#define vi vector<int>

int main() {
    int n,k,c; cin>>n>>k>>c;
    st s; cin>>s;
    int nxt[n];
    memset(nxt,n,sizeof(nxt));
    int last = n;
    FOR(i,n,0) {
        nxt[i] = last;
        if( s[i] == 'o' ) last = i;
    }
    int prev[n];
    memset(prev,-1,sizeof(prev));
    int pre = -1;
    FOR(i,0,n) {
        prev[i] = pre;
        if( s[i] == 'o' ) pre = i;
    }
    int g = 0;
    if( s[g] != 'o' ) g = nxt[g];
    if( g == n ) return 0;
    int ct = 1;
    int left[k];
    int le,ri;
    le = ri = 0;
    ri = k-1;
    int right[k];
    FOR(i,0,k) left[i] = right[i] = -1;
    left[le++] = g;
    while( ct < k ) {
        g += c;
        if( g < n ) g = nxt[g];
        else break;
        if( g < n ) {
            left[le++] = g;
            ct++;
        } else break;
    }
    if( ct != k ) return 0;
    g = n-1;
    if( s[g] != 'o' ) g = prev[g];
    if( g == -1 ) return 0;
    ct = 1;
    right[ri--] = g;
    while( ct < k ) {
        g -= c;
        if( g >= 0 ) g = prev[g];
        else break;
        if( g >= 0 ) {
            right[ri--] = g;
            ct++;
        } else break;
    }
    if( ct != k ) return 0;
    vi ans;
    FOR(i,0,k) if( left[i] == right[i] ) ans.pb(left[i]+1);
    for( auto e : ans ) cout<<e<<" "; cout<<"\n";
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef double long dl;
typedef pair < int , int > pii;
typedef pair < pii, pii > p2i;
const int maxn = (int) 2e5 + 1;
const int mod = (int) 1e9 + 7;
const ll inf = (ll)1e18;

#define fi first
#define se second
#define acel ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define next continue

int n;
ll s, a[maxn];
vector < ll > q;
ll last, ans = inf;
ll get(int x){
    return abs((s - a[x]) - (a[x] - last));
}

void solve1(int l1, int r1, int l2, int r2){
    s = a[r1];
    ll h = a[r1];
    while(r1 - l1 > 1){
        int mid = (r1 + l1) / 2;
        if(get(mid) >= get(mid + 1)){
            l1 = mid;
        }
        else {
            r1 = mid;
        }
    }
    last = a[l2 - 1];
    s = a[r2];
    while(r2 - l2 > 1){
        int mid = (r2 + l2) / 2;
        if(get(mid) >= get(mid + 1)){
            l2 = mid;
        }
        else {
            r2 = mid;
        }
    }
    q.push_back(a[l1]);
    q.push_back(h - a[l1]);
    q.push_back(a[l2] - last);
    q.push_back(s - a[l2]);
    sort(q.begin(), q.end());
    ans = min(ans, q[3] - q[0]);
    q.clear();
    q.push_back(a[l1]);
    q.push_back(h - a[l1]);
    q.push_back(a[r2] - last);
    q.push_back(s - a[r2]);
    sort(q.begin(), q.end());
    ans = min(ans, q[3] - q[0]);
    q.clear();
    q.push_back(a[r1]);
    q.push_back(h - a[r1]);
    q.push_back(a[l2] - last);
    q.push_back(s - a[l2]);
    sort(q.begin(), q.end());
    ans = min(ans, q[3] - q[0]);
    q.clear();
    q.push_back(a[r1]);
    q.push_back(h - a[r1]);
    q.push_back(a[r2] - last);
    q.push_back(s - a[r2]);
    sort(q.begin(), q.end());
    ans = min(ans, q[3] - q[0]);
    q.clear();

}


int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for(int i = 2; i < n - 1; i++){
        last = 0;
        solve1(1, i, i + 1, n);
    }
    cout << ans;
}













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

typedef long long ll;

int main(){
  ll q,h,s,d,n,ans=0;
  cin>>q>>h>>s>>d>>n;
  ll one=min({4*q,2*h,s});
  ll two=min(2*one,d);
  
  ans=two*(n/2);
  if(n%2==1)ans+=one;
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
k = int(input())
s = input()
s = len(s)

mod = 10 ** 9 + 7
n = k + s


def _fac_inv(_n, _mod):
    _fac = [1] * (_n + 1)
    _inv = [1] * (_n + 1)
    for i in range(_n):
        _fac[i + 1] = _fac[i] * (i + 1) % _mod
    _inv[_n] = pow(_fac[_n], _mod - 2, _mod)
    for i in range(_n, 0, -1):
        _inv[i - 1] = _inv[i] * i % _mod

    return _fac, _inv


fac, inv = _fac_inv(n, mod)

n25 = [1]
n26 = [1]
for _ in range(n-s):
    n25.append((n25[-1] * 25) % mod)
    n26.append((n26[-1] * 26) % mod)

ans = 0

for i in range(s, n + 1):
    ans = (ans + fac[i-1] * inv[s-1] * inv[i-s] * n25[i-s] * n26[n-i]) % mod

print(ans)


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

struct Edge {
  int to, cost;
};

const int MAX_N = 100002;
const int MOD = 10007;
int N;
Edge E[MAX_N][2];
bool vis[MAX_N];

int getMaxCostNum(int p) {
  int num = 0;
  int maxCost = 0;
  int pp = -1;
  while(1) {
    int d = (E[p][0].to == pp);
    bool flag = false;
    for(int i = 0; i < 2; ++i) {
      Edge &e = E[p][(i+d)%2];
      if(vis[e.to]) continue;

      vis[e.to] = true;
      pp = p;
      p = e.to;
      if(e.cost == maxCost) {
	++num;
      } else if(e.cost > maxCost) {
	num = 1;
	maxCost = e.cost;
      }
      flag = true;
      break;
    }
    if(!flag) return num;
  }
}

int solve() {
  int res = 1;
  fill(vis, vis+MAX_N, false);
  for(int i = 0; i < N; ++i) {
    if(vis[i]) continue;
    int tmp = getMaxCostNum(i);
    res = (res*tmp)%MOD;
  }
  return res;
}

int main() {
  while(cin >> N && N) {
    for(int i = 0; i < N; ++i) {
      for(int j = 0; j < 2; ++j) {
	cin >> E[i][j].to >> E[i][j].cost;
      }
    }
    cout << solve() << endl;
  }
  return 0;
}

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

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, a, b) for (int i = (int)(a); i >= (int)b; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, r, l) for (int i = (r); i >= (l); i--)
#define ms(x, y) memset(x, y, sizeof(x))
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

i64 n;
 
int main() {
	ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin);
#endif
	
	cin >> n;
	if (n & 1) {
		cout << 0 << '\n';
		return 0;
	}
	i64 sum = 0;
	while (n /= 5) {
		sum += n / 2;
	}
	cout << sum << '\n';
		
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main()
{
	int i, j;
	char a[11], b[11], c[11];

	scanf("%s%s%s", a, b, c);

	i = 0;
	j = 0;

	while (a[i] != '\0')
		i++;
	while (b[j] != '\0')
		j++;

	if (a[i - 1] == b[0] && b[j - 1] == c[0])
		printf("YES\n");
	else
		printf("NO\n");

	return 0;
}

Measured memory_bytes: 128
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dist[200010] = {};
vector<ll> tree[200010];

void dfs(ll cur, ll par){
    dist[cur] = 1;
    for(auto &e: tree[cur]){
        if(e == par) continue;
        dfs(e, cur);
        dist[cur] += dist[e];
    }
}

ll ans = 0;
ll N;

ll power(ll x, ll n){
    if(n == 0) return 1LL;
    ll res = power(x * x % MOD, n/2);
    if(n % 2 == 1) res = res * x % MOD;
    return res;
}

void dfs2(ll cur, ll par){
    if(tree[cur].size() > 1){
        ll res = power(2, N-1);
        for(auto &e: tree[cur]){
            res -= power(2, dist[e]) - 1;
            res = (res + MOD) % MOD;
        }
        res = (res - 1 + MOD) % MOD;
        ans += res;
        ans %= MOD;
    }
    for(auto &e: tree[cur]){
        if(e == par) continue;
        ll tmp = dist[e];
        dist[cur] = dist[cur] - dist[e];
        dist[e] = N;
        dfs2(e, cur);
        dist[e] = tmp;
        dist[cur] = N;
    }

}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    ll A[200010], B[200010];

    rep(i,0,N-1){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
        tree[A[i]].push_back(B[i]);
        tree[B[i]].push_back(A[i]);
    }
    dfs(0, -1);
    dfs2(0, -1);
    ll v = power(2, N);
    ans *= power(v, MOD-2);
    ans %= MOD;
    print(ans);



    

}

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
typedef double ld;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (int)3e5 + 9;
int cnt[N];
int d[N];
int pf[N];
int suf[N];
int f[N];

int main(){
  fastIO;
  int n;
  cin >> n;
  int x;
  for(int i = 1; i <= n; i ++ ){
    cin >> x;
    cnt[x] ++ ;
  }
  for(int i = 1; i <= n; i ++ ) d[cnt[i]] ++ ;
  for(int i = 1; i <= n; i ++ ){
    pf[i] = (pf[i - 1] + i * d[i]);
  }
  for(int i = n; i >= 1; i -- ){
    suf[i] = (suf[i + 1] + d[i]);
  }
  for(int i = 1; i <= n; i ++ ){
    f[i] = (pf[i]/i) + suf[i+1];
  }
  int p = n;
  for(int i = 1; i <= n; i ++ ){
    while(p > 0 && f[p] < i){
      p -- ;
    }
    cout << p << "\n";
  }
  return 0;
}

Measured memory_bytes: 6144
#include<bits/stdc++.h>
using namespace std;
#define int long long

template <class T>
struct DelaySegmentTree{
  using F = function<T(T,T)>;
  F f;
  T inf;
  int n;
  vector<int> node,delay;
  vector<bool> delayflag;

  DelaySegmentTree(vector<T> v,T inf,F f):inf(inf),f(f){
    n = 1; while(n < v.size()) n *= 2;
    node.resize(2*n-1,inf);
    delay.resize(2*n-1,inf);
    delayflag.resize(2*n-1,false);
    for(int i = 0; i < v.size(); i++) node[i+n-1] = v[i];
    for(int i = n-2; i >= 0; i--) node[i] = f(node[2*i+1],node[2*i+2]);
  }

  void eval(int k,int l,int r){
    if(delayflag[k]){
      node[k] = delay[k];
      if(r-l > 1){
        delay[2*k+1] = delay[2*k+2] = delay[k];
        delayflag[2*k+1] = delayflag[2*k+2] = true;
      }
      delayflag[k] = false;
    }
  }

  void update(int a,int b,int x){ update(a,b,x,0,0,n); }
  void update(int a,int b,int x,int k,int l,int r){
    eval(k,l,r);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      delay[k] = x;
      delayflag[k] = true;
      eval(k,l,r);
    }
    else {
      update(a,b,x,2*k+1,l,(l+r)/2);
      update(a,b,x,2*k+2,(l+r)/2,r);
      node[k] = f(node[2*k+1],node[2*k+2]);
    }
  }

  T getval(int a,int b){ return getval(a,b,0,0,n); }
  T getval(int a,int b,int k,int l,int r){
    //区間[a, b)の値を返す
    eval(k,l,r);
    if(b <= l || r <= a) return inf;
    if(a <= l && r <= b) return node[k];
    T vl = getval(a, b, 2*k+1, l, (l+r)/2);
    T vr = getval(a, b, 2*k+2, (l+r)/2, r);
    return f(vl, vr);
  }
};

signed main(){

  int n; cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
    a[i] *= -1;
  }

  auto f = [&](int x,int y){
    if(x < y) return x;
    else return y;
  };
  DelaySegmentTree<int> seg(a,0,f);

  for(int i = 0; i < n; i++){
    cout << -f(seg.getval(0,i),seg.getval(i+1,n)) << endl;
  }

  return 0;
}


Measured memory_bytes: 11648
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        String s = sc.next();

        List<Integer> nums = new ArrayList<>();

        char prev = s.charAt(0);
        if (prev == '0') {
            nums.add(0);
        }

        int count = 0;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == prev) {
                count++;
            } else {
                nums.add(count);
                prev = s.charAt(i);
                count = 1;
            }
        }
        if (count != 0) {
            nums.add(count);
        }
        if (prev == '0') {
            nums.add(0);
        }

        int c = 0;
        int[] sum = new int[nums.size() + 1];
        int i = 1;
        for (Integer num : nums) {
            sum[i] = sum[i - 1] + num;
            i++;
        }

        int result = 0;
        for (int l = 0; l < sum.length; l += 2) {
            int r = l + 2 * k + 1;
            if (r >= sum.length) r = sum.length - 1;
            result = Math.max(result, sum[r] - sum[l]);
        }

        System.out.println(result);
    }
}


Measured memory_bytes: 26204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please

int like2017(int X) {
	if (X <= 2) return 0;
	int saidai = sqrt(X);
	for (int i = 2; i <= saidai; i++) {
		if (X % i == 0) return 0;
	}
	int Y = (X + 1) / 2;
	saidai = sqrt(Y);
	for (int i = 2; i <= saidai; i++) {
		if (Y % i == 0) return 0;
	}
	please return 1;
}


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

	int A[100001] = {};

	rep1(i, 100000) {
		A[i] = A[i - 1] + like2017(i);
	}

	int Q;
	cin >> Q;

	rep(i, Q) {
		int L, R;
		cin >> L >> R;
		co(A[R] - A[L - 1]);
	}

	Would you please return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <set>
using namespace std;
int main()
{
    int n,k,d,a;
    cin >> n >> k;
    set<int> st;
    for(int i=0;i<k;i++)
    {
        cin >> d;
        for(int j=0;j<d;j++)
        {
            cin >> a;
            st.insert(a);
        }
    }
    cout << n-st.size() << endl;
    return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i,a,n)	for(int i=a;i<n;i++)
bool a[100001];
int n[100002];
int main(){
	int q;
	cin>>q;
	for(int i=2;i<=100000;i++)if(!a[i])for(int j=i+i;j<=100000;j+=i){
		a[j]=true;
	}
	for(int i=3;i<=100000;i+=2)if(a[i]==false&&a[(i+1)/2]==false)n[i]++;
	for(int i=3;i<=100000;i++)n[i]+=n[i-1];
	for(int i=0;i<q;i++){
		int a,b;
		cin>>a>>b;
		cout<<n[b]-n[a-1]<<endl;
	}
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#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 REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

ll pow_mod(ll n, ll p, ll mod) {
    if (p == 0) {
        return 1;
    } else if (p % 2 == 1) {
        return pow_mod(n, p - 1, mod) * n % mod;
    } else {
        ll s = pow_mod(n, p / 2, mod);
        return s * s % mod;
    }
}

void solve() {
    int n;
    cin >> n;
    vi b(n);
    int a;
    REP(i, n) {
        cin >> a;
        b[a]++;
    }
    if (n % 2 == 0) {
        for (int i = 1; i < n; i += 2) if (b[i] != 2) {
            cout << 0 << endl;
            return;
        }
    } else {
        if (b[0] != 1) {
            cout << 0 << endl;
            return;
        }
        for (int i = 2; i < n; i += 2) if (b[i] != 2) {
            cout << 0 << endl;
            return;
        }
    }
    cout << pow_mod(2, n / 2, MOD) << endl;
}


Measured memory_bytes: 3728
/*
g++ -std=c++11 -Wall -O2 -o main.exe main.cpp
./main.exe
*/

#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <climits>
//intの最大値: INT_MAX
//longの最大値: LONG_MAX
//long longの最大値: LLONG_MAX
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <complex>
#include <numeric>
//最大公約数: gcd()
//最小公倍数: lcm()

#define ll long long int

using namespace std;

template <typename T>
string itos(T val){ //数値を文字列(string)に変換
	stringstream ss;

	ss << val;
	return ss.str();
}

int stoi(string s){ //文字列(string)を数値に変換
	stringstream ss;
	int val = 0;

	ss << s;
	ss >> val;
	return val;
}

template <typename T>
void sortasc(vector<T> &v){ //vectorを昇順にソート
    sort(v.begin(), v.end(), std::less<T>());
    return;
}

template <typename T>
void sortdesc(vector<T> &v){ //vectorを降順にソート
    sort(v.begin(), v.end(), std::greater<T>());
    return;
}

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

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

	cout << (n + 1 - i) << endl;
	return 0;
}


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

int main() {
	int a, b, c; cin >> a >> b >> c;
	if ((a > c && c > b) || (b > c && c > a) )
	{
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
	
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  char S[6] = {'\0'};
  
  do{
    scanf("%s",S);
  }while(S[6]!=0&&S[5]==0);
  
  if(S[2]==S[3] && S[4]==S[5])
    printf("Yes");
  else
    printf("No");
  
  return 0;
}  

Measured memory_bytes: 1708
package main

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

func getNextLine(scanner *bufio.Reader) string {
	var buffer string
	for {
		line, isPrefix, _ := scanner.ReadLine()
		buffer += string(line)
		if isPrefix == false {
			break
		}
	}
	return buffer
}

func getIntList(scanner *bufio.Reader) []int {
	list := strings.Split(getNextLine(scanner), " ")
	l := len(list)
	result := make([]int, l)
	for i := 0; i < l; i++ {
		result[i], _ = strconv.Atoi(list[i])
	}
	return result
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := bufio.NewReader(fp)

	var n, k int

	fmt.Sscan(getNextLine(scanner), &n, &k)

	fmt.Println(n - k + 1)
}


Measured memory_bytes: 640
local MOD = 1000000007
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, string.sub(k, i, i)) end local r = io.read local u = table.unpack return function() return r(u(a)) end end})
local N, K = read.nnl()
local A = {}
for i=1,N do
    A[i] = read.n()
end

local T = {}
local L = {}
for i=1,N do
    local p = A[i]
    L[i] = 0
    for j=1,i-1 do
        local add = A[j] < p and 1 or 0
        L[i] = L[i] + add
    end
    T[i] = 0
    for j=i+1,N do
        local add = A[j] < p and 1 or 0
        T[i] = T[i] + add
    end
end

local SUM1 = (K * (K + 1) // 2) % MOD
local SUM2 = (K * (K - 1) // 2) % MOD

local ans = 0
for i=1,N do
    ans = ans + (SUM1 * T[i] % MOD)
    ans = ans % MOD
    ans = ans + (SUM2 * L[i] % MOD)
    ans = ans % MOD
end
print(ans)

Measured memory_bytes: 760
import java.util.Scanner;

public class Main {
	
	static int mod = 1000000007;
	static long fac[];
	static long finv[];
	static long inv[];
	static int n , k;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		 n = Integer.parseInt(sc.next());
		 k = Integer.parseInt(sc.next());
		 
		 long []num = new long [n+2];
		 long []low = new long [n+2];
		 num[0] = 0;
		 low[0] = 0;
		 for(int i = n ; i >= 0 ; i--) {
			num[n-i+1] += i + num[n-i]; 
			low[n-i+1] += (n-i) + low[n-i];
			
		 }
		 
		
		long ans = 0;
		for(int i = k ; i <= n+1 ; i++) {
			ans = (ans + (num[i]-low[i]+1)) % mod;
		}
		
		System.out.println(ans);
		
	
	}	
}


Measured memory_bytes: 30400
// https://atcoder.jp/contests/abc077/tasks/arc084_a

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

template<typename T>
T Input()
{
    T v;
    cin >> v;
    return v;
}

template<typename T>
vector<T> InputVector(int n)
{
    vector<T> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    return v;
}

template<typename T>
void InputArray(T* begin, int n)
{
    for(int i = 0; i < n; ++i)
    {
        cin >> begin[i];
    }
}

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)


int main(int argc, const char* argv[])
{
    auto n = Input<int>();
    auto a = InputVector<int>(n);
    auto b = InputVector<int>(n);
    auto c = InputVector<int>(n);

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());

    int64_t total = 0;

    for(auto bi = b.begin(); bi != b.end(); ++bi)
    {
        auto pa = lower_bound(a.begin(), a.end(), *bi);
        auto pc = upper_bound(c.begin(), c.end(), *bi);
        total += static_cast<int64_t>(pa - a.begin()) * static_cast<int64_t>(c.end() - pc);
    }

    cout << total << endl;
    return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define pb push_back
#define MOD 1000000007
#define INF 1000000000000
#define EPS 0.00000000001
typedef long long ll;


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    //---------------------------------------------

    ll n,k,q;
    cin>>n>>k>>q;
    vector<ll> a(n);
    int x;
    rep(i,q){
        cin>>x;
        x--;
        a[x]++;
    }

    rep(i,n){
        if(k-(q-a[i])>0){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }


}

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

#define eb emplace_back
#define ld long double
#define ll long long

using namespace std;

const int nm = 200002;
const ll inf = 1e9;

struct rec {
	ll min, min2, add;
	int pos;
};

int m, n;
rec tree[4 * nm];
int a[nm], b[nm];

void push(int id, int c1, int c2, int l, int m, int r) {
	if (tree[id].add > 0) {
		tree[c1] = {tree[id].add, tree[id].add, tree[id].add, l};
		tree[c2] = {tree[id].add + m - l + 1, tree[id].add + m - l + 1, tree[id].add + m - l + 1, m + 1};
		tree[id].add = 0;
	}
}

rec combine(rec &a, rec &b) {
	rec res;
	res.min = min(a.min, b.min);
	if (a.min2 - a.pos <= b.min2 - b.pos) {
		res.min2 = a.min2;
		res.pos = a.pos;
	} else {
		res.min2 = b.min2;
		res.pos = b.pos;
	}
	return res;
}

void update(int u, int v, ll x, int l, int r, int id) {
	if (l >= u && r <= v) {
		tree[id] = {x + l - u, x + l - u, x + l - u, l};
		return;
	}
	int m = (l + r) >> 1, c1 = id << 1, c2 = c1 ^ 1;
	push(id, c1, c2, l, m, r);
	if (u <= m) {
		update(u, v, x, l, m, c1);
	}
	if (v > m) {
		update(u, v, x, m + 1, r, c2);
	}
	tree[id] = combine(tree[c1], tree[c2]);
}

void build(int l, int r, int id) {
	if (l == r) {
		tree[id] = {0, 0, 0, l};
		return;
	}
	int m = (l + r) >> 1, c1 = id << 1, c2 = c1 ^ 1;
	build(l, m, c1);
	build(m + 1, r, c2);
	tree[id] = {0, 0, 0, r};
}

rec get_minpos(int u, int l, int r, int id) {
	if (l > u) {
		return {inf, inf, 0, 0};
	}
	if (r <= u) {
		return tree[id];
	}
	int m = (l + r) >> 1, c1 = id << 1, c2 = c1 ^ 1;
	push(id, c1, c2, l, m, r);
	rec x1 = get_minpos(u, l, m, c1);
	rec x2 = get_minpos(u, m + 1, r, c2);
	rec res = combine(x1, x2);
	return res;
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> m >> n;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= m; ++i) {
		if (a[i] > 1) {
			rec tmp = get_minpos(a[i] - 1, 1, n, 1);
			update(a[i], b[i], tmp.min2 + a[i] - tmp.pos, 1, n, 1);
		} else {
			update(a[i], b[i], inf, 1, n, 1);
		}
		if (tree[1].min < inf) {
			cout << i + tree[1].min << "\n";
		} else {
			cout << "-1\n";
		}
	}
#ifdef LOCAL
	cout << (double) clock() / CLOCKS_PER_SEC << "\n";
#endif
}


Measured memory_bytes: 21572
import java.util.Scanner;
public class Main {
 
	public static void main(String[] args) {
		  Scanner sc = new Scanner(System.in);
	         
          String X = sc.next();
      int a = X.charAt(2);
      int b = X.charAt(3);
      int c = X.charAt(4);
      int d = X.charAt(5);
      if(a==b&&c==d){
        System.out.println("Yes");
      }else{
        System.out.println("No");
      }
    }
}

Measured memory_bytes: 25300
#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int main(){
	
	int a,b;
	
	
	while(1){
		cin>>a>>b;
		if(a==0&&b==0)break;
		char P[150][150]={};
	for(int i=0;i<a;i++)
		{
			string q;cin>>q;
			for(int I=0;I<b;I++)
			P[i][I+1]=q[I];
		}
	int X=1;
	int M[120][120]={};
	for(int i=0;i<a;i++)
		for(int j=1;j<=b;j++)
		{
			if(P[i][j]!=P[i][j-1])X++;
			M[i][j]=X;
			//if(P[i][j]==P[i][j-1]&&j>0)M[i][j]==M[i][j-1];
		}
		/*
		for(int i=0;i<a;i++){cout<<endl;
		for(int j=1;j<=b;j++)
		{ cout<<M[i][j];}
		}
	*/

		for(int i=0;i<a;i++)
		for(int j=1;j<=b;j++)
			if(P[i+1][j]==P[i][j]){
				int Y=M[i+1][j];
				//M[i][j]=M[i-1][j];
				for(int I=0;I<a;I++)
					for(int J=0;J<=b;J++)
						if(M[I][J]==Y)M[I][J]=M[i][j];
			}
		
	
		bool F[10004]={};
		int ans=0;
		for(int i=0;i<a;i++)
		for(int j=1;j<=b;j++){
			F[M[i][j]]=true;
		}
		for(int i=1;i<10002;i++)
			if(F[i]==true)ans++;/*
		for(int i=0;i<a;i++){cout<<endl;
		for(int j=1;j<=b;j++)
		{ cout<<M[i][j];}
		}
	
	
	*/
	
		
	cout<<ans<<endl;
	}
	return 0;
}
				

Measured memory_bytes: 1300
#include <stdio.h>

int f(int x){
    x==9 ? (x=1):(x=9);
    return x;
}

int main(void){
    // Your code here!
    int a,b,c,d;
    scanf("%d\n",&a);
    b=a/100;
    d=a%10;
    c=(a-b*100-d)/10;
    printf("%d\n",f(b)*100+f(c)*10+f(d));
}


Measured memory_bytes: 128
// Created by Nandu Vinodan
#include <bits/stdc++.h>

#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define vi vector<int>
#define pii pair<int, int>
#define INF INT_MAX
#define _INF INT_MIN
#define TC 0

using namespace std;
using ll = long long;

double sq(double x) {
	return x*x;
}

double dist (pii a, pii b) {
	int x1 = a.first, y1 = a.second;
	int x2 = b.first, y2 = b.second;
	return sqrt(sq(x1-x2) + sq(y1-y2));
}
void testcase() {
    int n; cin >> n;

    vector<pair<int, int> > pts;
    vector<int> v;
    rep (i, 1, n) v.push_back(i);

    rep (i, 0, n-1) {
    	int x, y; cin >> x >> y;
    	pts.push_back({x, y});
    }

    double tot = 0;
    double ct = 0;
    do {
    	double sum = 0;
    	rep (i, 0, n-2) {
    		sum = sum + dist(pts[v[i]-1], pts[v[i+1]-1]);
    	}	
    	ct++;
    	tot += sum;
    }while(next_permutation(v.begin(), v.end()));

    printf("%.7f", tot/ct);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if (TC)
        cin>>t;
    while(t--) {
        testcase();
    }
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def solve():
    N = II()
    d_list = LI()

    from itertools import combinations

    sm = 0
    for comb in combinations(d_list, 2):
        sm += comb[0] * comb[1]

    print(sm)


solve()

Measured memory_bytes: 3064
#include <cstdio>

int N, A, B, C, X;
int Y[100];

void updateX() {
  X = (A*X+B)%C;
}

int main() {
  while (true) {
    scanf("%d %d %d %d %d", &N, &A, &B, &C, &X);
    if (N == 0 && A == 0 && B == 0 && C == 0 && X == 0) break;
    for (int i=0;i<N;i++) scanf("%d", &Y[i]);
    int cnt = N-1;
    for (int i=0;i<N;i++) {
      while (X != Y[i] && cnt < 10000) {
        updateX();
        cnt++;
      }
      if (X != Y[i]) {
        cnt = -1;
        break;
      }
      updateX();
    }
    printf("%d\n", cnt);
  }
  return 0;
}

Measured memory_bytes: 2572
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)-1
using ll = long long;
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int k; cin >> k;
  queue<ll> q;
  rep(i,9) q.push(i+1);
  rep(i,k){
    ll x = q.front(); q.pop();
    if(x % 10 != 0) q.push(10*x+x%10-1);
    q.push(10*x+x%10);
    if(x % 10 != 9) q.push(10*x+x%10+1);
    if(i == k-1){
      cout << x;
      return 0;
    }
  }
  cout << "\n";
  return 0;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  if(b%a==0){
    cout << a+b << endl;
  }
  else{
    cout << b-a << endl;
  }
}


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

template <typename T>
T _min(
  const T & lhs
  , const T & rhs
)
{
  return ((lhs < rhs) ? lhs : rhs);
}

int main()
{
  int N, A, B;
  cin >> N >> A >> B;
  cout << _min(N*A, B);
  return 0;
}


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

int main(){
  int rate[9];
  for(int i = 0; i < 9; i++){
    rate[i] = 0;
  }
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    int a;
    cin >> a;
    if(a/400 < 9){
       rate[a/400]++;
    }
    else{
      rate[8]++;
    }
  }
  int min_num = 0;
  for(int i = 0; i < 8; i++){
    if(rate[i] != 0){
      min_num++;
    }
  }
  int max_num = min_num + rate[8];
  if(min_num == 0){
    min_num = 1;
  }
  cout << min_num <<' ' << max_num;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#include <set> 
 
using namespace std;
 
#define int long long
#define val(x) cout << #x << " equals to " << x << endl
 
const int N = 2e6 + 7;
const int INF = 1e18;

int n, m, k, q, a[N];

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

    #ifdef LOCAL
        freopen("C:/Users/emrey/Code/in.txt", "r", stdin);
    #endif

    int T; cin >> T;

    int aa, ab, ac, ad;
    aa = ab = ac = ad = 0;
    while(T--) {
        string s;
        cin >> s;
        if (s == "AC") aa++;
        if (s == "WA") ab++;
        if (s == "TLE") ac++;
        if (s == "RE") ad++;
    }
    cout << "AC x " << aa << endl;
    cout << "WA x " << ab << endl;
    cout << "TLE x " << ac << endl;
    cout << "RE x " << ad << endl;
       
}

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

void pattern(string str, int i, set<string>& st) {
  string s1, s2;
  int j = 0;
  while (j < i) s1.push_back(str[j++]); 
  while (j < str.size()) s2.push_back(str[j++]);
  
  string rs1 = s1, rs2 = s2;
  reverse(rs1.begin(), rs1.end());
  reverse(rs2.begin(), rs2.end());

  st.insert(s1 + s2);
  st.insert(rs1 + s2);
  st.insert(s1 + rs2);
  st.insert(rs1 + rs2);
  st.insert(s2 + s1);
  st.insert(s2 + rs1);
  st.insert(rs2 + s1);
  st.insert(rs2 + rs1);
}

int solve(string str) {
  set<string> st;
  for (int i = 1; i < str.size(); ++i)
    pattern(str, i, st);
  
  return st.size();
}

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    cout << solve(s) << endl;
  }
  return 0;
}


Measured memory_bytes: 3212
#include<bits/stdc++.h>
#define LL long long int
using namespace std;
int flg[10000002];
int main(void)
{		
	int i,j,k,n;
	for(i=2;i<=10000000;i++) flg[i]=1;
	for(i=2;i*i<=10000000;i++){
		if(flg[i]==1){
			for(j=2;j*i<10000000;j++) flg[i*j]=0;
		}
	}
	cin>>n;
	while(n!=0) {
		for(i=n;i>=13;i--) {
			if(flg[i]==1&&flg[i-2]==1&&flg[i-6]==1&&flg[i-8]==1) {
				cout<<i<<endl;
				break;
			}
		}
		cin>>n;
	}
	return 0;
}

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

int main(){
  int firstNum,secondNum;
  char _operator_;

  cin>>firstNum >> _operator_ >>secondNum;
  
  if(_operator_ == '+')
   cout<< firstNum + secondNum;
  else
   cout<< firstNum - secondNum;

  // system("pause");
  return 0;
}

Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int((n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
                arr.append(i ** cnt)

    if temp != 1:
        arr.append(temp)

    if arr == []:
        arr.append(n)

    return arr

ans = 0
X = int(input())
Y = factorization(X)
Y.sort()
Z = X
for i in range(len(Y)):
  if X % Y[i] == 0:
    ans += 1
    X /= Y[i]
    
if Z == 1:
  print(0)
else:
  print(ans)

Measured memory_bytes: 9448
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;
//vector<vector<int>> vec(縦,vector<int>(横));
/*deque<型> 配列の先頭にも用がある時はvectorの代わりに。
入力はstringでもらってからpush_back()*/

int main(){
  ll H;
  ll W;
  ll ans;
  cin>>H;
  cin>>W;
  
  ans=((H*W)+1)/2;
  if(H==1&&W>2){
    cout<<1<<endl;
    return 0;
  }
  else if(H>2&&W==1){
    cout<<1<<endl;
    return 0;
  }
  cout<<ans<<endl; 
}

  
  

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a += b;
	if(a>MOD){
		a -= MOD;
	}
}

string s;
int n,q;
char t[225816],d[225816];

bool judge_l(int p){
	int i;
	for(i=0; i<q; ++i){
		if(t[i]==s[p]){
			p += ((d[i]=='L')?(-1):1);
		}
		if(p<0){
			return false;
		}else if(p>=n){
			return true;
		}
	}
	return true;
}

bool judge_r(int p){
	int i;
	for(i=0; i<q; ++i){
		if(t[i]==s[p]){
			p += ((d[i]=='L')?(-1):1);
		}
		if(p>=n){
			return true;
		}else if(p<0){
			return false;
		}
	}
	return false;	
}

int main(void){
	int i,l,r,ok,ng,mid;
	cin >> n >> q;
	cin >> s;
	for(i=0; i<q; ++i){
		cin >> t[i] >> d[i];
	}
	if(judge_l(0)){
		l = 0;
	}else{
		ok = n;
		ng = 0;
		while(ok-ng>1){
			mid = (ok+ng)/2;
			if(judge_l(mid)){
				ok = mid;
			}else{
				ng = mid;
			}
		}
		l = ok;
	}
	if(judge_r(0)){
		r = 0;
	}else{
		ok = n;
		ng = 0;
		while(ok-ng>1){
			mid = (ok+ng)/2;
			if(judge_r(mid)){
				ok = mid;
			}else{
				ng = mid;
			}
		}
		r = ok;	
	}
	cout << (r-l) << endl;
	return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> VI;
typedef vector<VI> VVI;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = numeric_limits<int>::max() / 2;
const int NEG_INF = numeric_limits<int>::min() / 2;

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

    int m, t, p, r;
    while (true)
    {
        cin >> m >> t >> p >> r; //???????????°???????????°?????¬???????????°
        if (t == 0)
            break;
        int seikai[t + 1] = {0}, penalty[t + 1] = {0}, gotou[t + 1][p + 1] = {0};
        for (int i = 0; i < r; i++)
        {
            int j, tID, pID, time;
            cin >> time >> tID >> pID >> j;
            if (j == 0)
            {
                seikai[tID]++;
                penalty[tID] += gotou[tID][pID] * 20 + time;
            }
            else
            {
                gotou[tID][pID]++;
            }
        }
        bool checked[t + 1] = {false};
        int preseikai = -1, prepena = -1;
        for (int i = t; i >= 1; i--)
        {
            int team, seikaimax = -1, pena = INF;
            for (int j = t; j >= 1; j--)
            {
                if (!checked[j])
                {
                    if (seikaimax < seikai[j])
                    {
                        seikaimax = seikai[j];
                        team = j;
                        pena = penalty[j];
                    }
                    else if (seikaimax == seikai[j])
                    {
                        if (pena > penalty[j])
                        {
                            team = j;
                            pena = penalty[j];
                        }
                    }
                }
            }
            checked[team] = true;
            if (prepena == -1)
                cout << team;
            else if (prepena == pena && preseikai == seikaimax)
                cout << "=" << team;
            else
                cout << "," << team;
            preseikai = seikaimax, prepena = pena;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3152
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;;

public class Main{
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int P=sc.nextInt(),Q=sc.nextInt(),R=sc.nextInt();
		
		int min=P+Q;
		
		if(P+R<min) {
			min=P+R;
		}
		if(Q+R<min) {
			min=Q+R;
		}
		
		System.out.println(min);
		
		
		
	}

	
}
		


Measured memory_bytes: 23636