akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
import sys

def solve(H: int, W: int, K: int, m: "List[int][int]"):
    tmp=0
    for i in range(H):
        for j in range(W):
            if m[i][j] == 0:
                if tmp != 0:
                    m[i][j]=tmp
            else:
                tmp = m[i][j]
        tmp = 0

    for i in range(H):
        for j in range(W)[::-1]:
            if m[i][j] == 0:
                if tmp != 0:
                    m[i][j]=tmp
            else:
                tmp = m[i][j]
        tmp = 0

    for i in range(W):
        for j in range(H):
            if m[j][i] == 0:
                if tmp != 0:
                    m[j][i]=tmp
            else:
                tmp = m[j][i]
        tmp = 0

    for i in range(W):
        for j in range(H)[::-1]:
            if m[j][i] == 0:
                if tmp != 0:
                    m[j][i]=tmp
            else:
                tmp = m[j][i]
        tmp = 0

    for i in range(H):
        for j in range(W):
            print(m[i][j],end=' ')
        print()

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    m = [[0 for i in range(W)] for j in range(H)]  # type: "List[int][int]"
    id = 1
    for i in range(H):
        s=next(tokens)
        for j in range(W):
            if s[j] == ".":
                m[i][j] = 0
            else:
                m[i][j] = id
                id+=1
    solve(H, W, K, m)

if __name__ == '__main__':
    main()


Measured memory_bytes: 7504
#include <bits/stdc++.h>
using namespace std;
int n, a[1000008];
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	reverse(a + 1, a + n + 1);
	long long ans = a[1];
	int i = 2;
	for (int c = 2; c <= n - 1; ++c)
	{
		ans += a[(c + 2) / 2];
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 4576
N = int(input())
src = list(map(int,input().split()))

fixed = [0] * 8
free = 0
for a in src:
    if a < 3200:
        fixed[a//400] = 1
    else:
        free += 1

mn = max(1, sum(fixed))
mx= sum(fixed) + free
print(mn,mx)

Measured memory_bytes: 3060
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

#pragma warning(disable : 4996)

using namespace std;

int N, M, K, A, B, L;

vector<vector<pair<int, int> > > G;

vector<int> P, D;

int main()
{
	scanf("%d", &N);
	scanf("%d", &M);
	scanf("%d", &K);

	G = vector<vector<pair<int, int> > >(N);

	for (int i = 0; i < M; i++)
	{
		scanf("%d", &A);
		scanf("%d", &B);
		scanf("%d", &L);

		G[A - 1].push_back(make_pair(B - 1, L));
		G[B - 1].push_back(make_pair(A - 1, L));
	}

	P = vector<int>(K);

	for (int i = 0; i < K; i++)
	{
		scanf("%d", &P[i]); P[i]--; // 0 - indexed
	}

	D = vector<int>(N, 999999999);

	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;

	for (int i = 0; i < K; i++)
	{
		que.push(make_pair(0, P[i])); D[P[i]] = 0;
	}

	while (!que.empty())
	{
		pair<int, int> state = que.top(); que.pop();

		int dist = state.first;
		int node = state.second;

		for (int j = 0; j < G[node].size(); j++)
		{
			int node2 = G[node][j].first;
			int leng2 = G[node][j].second;

			if (D[node2] > D[node] + leng2)
			{
				D[node2] = D[node] + leng2;

				que.push(make_pair(D[node2], node2));
			}
		}
	}

	int ret = 0;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < G[i].size(); j++)
		{
			ret = max(ret, D[i] + D[G[i][j].first] + G[i][j].second);
		}
	}

	printf("%d\n", (ret + 1) / 2);

	return 0;
}

Measured memory_bytes: 5972
#include<stdio.h>

int main(){
  int h,w,i;
  char str[1000][1000];

  scanf("%d",&h);
  scanf("%d",&w);

  for(i=0;i<h;i++){
    scanf("%s",str[i]);
  }
  printf("\n");
  for(i=0;i<h;i++){
    printf("%s\n",str[i]);
    printf("%s\n",str[i]);
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;
const int INF = 1000000000;
const ll LINF = 1000000000000000000; //1e18
const double EPS = 1e-10;

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

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

int main(void)
{
    int N;
    cin >> N;

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

    ll ans = T[0];
    for (int i = 1; i < N; i++)
    {
        ans = lcm(ans, T[i]);
    }
    cout << ans << endl;
    return (0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

int h,w,x;
char s[1000][1000];
bool visited [1000][1000];
pair<int,int> start,goal;
queue<pair<int,pair<int,int>>> q;
vector<pair<int,int>> ino;

int main(){
  int a,b,c;cin>>a>>b>>c;
  if(a-b==b-c){
    cout << "YES";
  }else{
    cout << "NO";
  }
}


Measured memory_bytes: 256
class Combination:
    def __init__(self, mod, max_num):
        self.mod = mod
        self.fac = [0] * max_num
        self.finv = [0] * max_num
        self.inv = [0] * max_num

        self.fac[0], self.fac[1] = 1, 1
        self.finv[0], self.finv[1] = 1, 1
        self.inv[1] = 1

        for i in range(2, max_num):
            self.fac[i] = self.fac[i-1] * i % mod
            self.inv[i] = mod - self.inv[mod % i] * (mod // i) % mod
            self.finv[i] = self.finv[i - 1] * self.inv[i] % mod

    def calc(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return self.fac[n] * (
            self.finv[k] * self.finv[n - k] % self.mod) % self.mod


def modinv(val, mod):
    b, u, v = mod, 1, 0
    while b:
        t = val // b
        val = val - t * b
        val, b = b, val
        u = u - t * v
        u, v = v, u
    u = u % mod
    return u


def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort()
MOD = 1000000007

com = Combination(MOD, 510000)

ret = 0

for i in range(len(a_list)):
    if i >= k - 1:
        ret = ret + (a_list[i] * com.calc(i, k - 1))
        ret = ret % MOD


a_list.reverse()

rev = 0

for i in range(len(a_list)):
    if i >= k - 1:
        rev = rev + (a_list[i] * com.calc(i, k - 1))
        rev = rev % MOD

ret = ret - rev
if ret < 0:
    ret = ret + MOD

print(ret)


Measured memory_bytes: 71208
#include <stdio.h>
int main(){
	int i;
	int sum;
	int dec;
	scanf("%d",&sum);
	while(sum!=0){
		for(i=0;i<9;i++){
			scanf("%d",&dec);
			sum=sum-dec;
		}
		printf("%d\n",sum);
		scanf("%d",&sum);
	}
	return 0;
}

Measured memory_bytes: 600
import sys
readline = sys.stdin.buffer.readline

a,b,c,d = map(int,readline().split())

class Square():
    def __init__(self,a,b,c,d):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
    
    def require(self,ab_or_cd=0):
        if ab_or_cd==0:
            return self.a * self.b
        else:
            return self.c * self.d
    
    def compare(self):
        print(self.require(0) if self.require(0) >= self.require(1) \
            else self.require(1))

x = Square(a,b,c,d)
x.compare()




Measured memory_bytes: 38256
n,m =map(int,input().split())
A = list(map(int, input().split())) 

souwa = sum(A)
hyou = souwa/(4*m)
ninki = 0

for number in A:
  if number >= hyou:
    ninki = ninki + 1

if m <= ninki:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <math.h>

typedef long long ll;

int main() {
    std::string S,T;
    int A,B;
    std::string U;

    std::cin >> S >> T;
    std::cin >> A >> B;
    std::cin >> U;

    if(S == U){
        A -= 1;
    }
    else if(T == U){
        B -= 1;
    }

    std::cout << A << " " << B << std::endl;

    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)
func main() {
	var A, B, C string
	fmt.Scan(&A)
	fmt.Scan(&B)
	fmt.Scan(&C)
	if A[len(A)-1] == B[0] && B[len(B)-1] == C[0] {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
/*  -*- coding: utf-8 -*-
 *
 * c.cc: C: Vacant Seat
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 99999;

/* typedef */

enum { V = -1, M = 0, F = 1 };

/* global variables */

/* subroutines */

int query(int k) {
  printf("%d\n", k); fflush(stdout);

  char s[16];
  scanf("%s", s);
  if (s[0] == 'M') return M;
  if (s[0] == 'F') return F;
  return V;
}

/* main */

int main() {
  int n;
  scanf("%d", &n);
  int nh = n / 2, pnh = (nh & 1);

  int g0 = query(0);
  if (g0 == V) return 0;

  int g1 = query(nh);
  if (g1 == V) return 0;

  int k0, k1;
  if ((pnh == 0 && g0 != g1) || (pnh == 1 && g0 == g1))
    k0 = 0, k1 = nh;
  else
    k0 = nh, k1 = n, swap(g0, g1);

  while (k0 + 1 < k1) {
    int k = (k0 + k1) / 2;
    int g = query(k);
    if (g == V) return 0;
    int pk = (k - k0) & 1;

    if ((pk == 0 && g0 != g) || (pk == 1 && g0 == g)) k1 = k, g1 = g;
    else k0 = k, g0 = g;
  }
  return 0;
}


Measured memory_bytes: 852
import heapq
def Dijkstra(edge,start):
    d = [float('inf')]*(n*(A+1))
    d[start] = 0
    pq = [(0,start)]
    heapq.heapify(pq)
    while pq:
        dist,p = heapq.heappop(pq)
        for to,cost in edge[p].items():
            if d[to] <= dist + cost:continue
            d[to] = dist + cost
            heapq.heappush(pq, (d[to], to))
    return d

n,m,s = map(int,input().split())
edge = [{} for _ in range(n)]
A = 2500
for i in range(m):
    u,v,a,b = map(int,input().split())
    # A += a
    u -= 1
    v -= 1
    edge[u][v] = (a,b)
    edge[v][u] = (a,b)


A *= 2
C = [0]*n
D = [0]*n
for i in range(n):
    C[i],D[i] = map(int,input().split())

path = [{} for _ in range(n*(A+1))]
for i in range(n):
    for j in range(A+1):
        for to,(a,b) in edge[i].items():
            if j - a >= 0:
                path[i*(A+1)+j][to*(A+1)+j-a] = b
        path[i*(A+1)+j][i*(A+1)+min(j+C[i],A)] = D[i]

ans = Dijkstra(path,min(s,A))
for i in range(1,n):
    print(min(ans[i*(A+1):i*(A+1)+A+1]))


Measured memory_bytes: 192124
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N;
  double sum_den = 0;

  cin >> N;
  for(int i = 0; i < N; i++) {
    int po;
    cin >> po;
    sum_den += 1.0 / po;
  }

  cout << (1 / sum_den);
}

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

public class Jugyo
{
    public int from { get; set; }
    public int to { get; set; }
    public int teach { get; set; }
    public int stud { get; set; }
}
public class FromTo
{
    public int from { get; set; }
    public int to { get; set; }
}

public class hello
{
    public static void Main()
    {
        var jugyos = new List<Jugyo>();
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n1 = int.Parse(line[0]);
        var f = new FromTo();
        for (int i = 0; i < n1; i++)
        {
            GetFromTo(f, line[i+1]);
            jugyos.Add(new Jugyo { from = f.from, to = f.to });
        }
        var n2 = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n2; i++)
        {
            string[] line2 = Console.ReadLine().Trim().Split(' ');
            var n3 = int.Parse(line2[0]);
            for (int j = 0; j < n3; j++)
            {
                GetFromTo(f, line2[j + 1]);
                foreach (var x in jugyos)
                    if (f.from <= x.from && f.to >= x.to) x.teach++;
            }
        }
        var n4 = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < n4; i++)
        {
            string[] line3 = Console.ReadLine().Trim().Split(' ');
            var n5 = int.Parse(line3[0]);
            for (int j = 0; j < n5; j++)
            {
                GetFromTo(f, line3[j + 1]);
                foreach (var x in jugyos)
                    if (f.from <= x.from && f.to >= x.to) x.stud++;
            }
        }
        var ans = 0;
        foreach (var x in jugyos)
            ans += Math.Min(x.teach, x.stud);
        Console.WriteLine(ans);
    }
    public static void GetFromTo (FromTo f ,string s)
    {
        string[]  s2 = s.Split(':', '-');
        f.from = int.Parse(s2[0]) * 60 + int.Parse(s2[1]);
        f.to = int.Parse(s2[2]) * 60 + int.Parse(s2[3]);
    }
}

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

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

	int A, B;
	cin >> A >> B;
	if (A + B >= 10) {
		cout << "error";
	}
	else {
		cout << A + B;
	}
}


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

int main()
{
    uint64_t A, B, K;
    cin >> A >> B >> K;
    if(A >= K){
        cout << A-K << " " << B << endl;
    } else if(A + B >= K){
        cout << 0 << " " << A + B - K << endl;
    } else {
        cout << 0 << " " << 0 << endl;
    }
	return 0;
}


Measured memory_bytes: 256
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def dijkstra(src):
    from heapq import heappush, heappop

    que = [(0, src)]
    dist = {}
    dist[src] = 0
    while que:
        cost, u = heappop(que)
        if 0 not in dist or dist[0] > cost+abs(u)*d:
            dist[0] =  cost+abs(u)*d
        if u >= 5:
            x = u % 5
            v = (u-x) // 5
            if v not in dist or cost+c+d*x < dist[v]:
                dist[v] = cost+c+d*x
                heappush(que, (cost+c+d*x, v))
            if u % 5 != 0:
                x = 5 - u % 5
                v = (u+x) // 5
                if v not in dist or cost+c+d*x < dist[v]:
                    dist[v] = cost+c+d*x
                    heappush(que, (cost+c+d*x, v))
        if u >= 3:
            x = u % 3
            v = (u-x) // 3
            if v not in dist or cost+b+d*x < dist[v]:
                dist[v] = cost+b+d*x
                heappush(que, (cost+b+d*x, v))
            if u % 3 != 0:
                x = 3 - u % 3
                v = (u+x) // 3
                if v not in dist or cost+b+d*x < dist[v]:
                    dist[v] = cost+b+d*x
                    heappush(que, (cost+b+d*x, v))
        if u >= 2:
            x = u % 2
            v = (u-x) // 2
            if v not in dist or cost+a+d*x < dist[v]:
                dist[v] = cost+a+d*x
                heappush(que, (cost+a+d*x, v))
            if u % 2 != 0:
                x = 2 - u % 2
                v = (u+x) // 2
                if v not in dist or cost+a+d*x < dist[v]:
                    dist[v] = cost+a+d*x
                    heappush(que, (cost+a+d*x, v))
    return dist

for _ in range(INT()):
    N, a, b, c, d = MAP()

    res = dijkstra(N)
    ans = res[0]
    print(ans)


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

#define st first
#define nd second
#define int long long

typedef pair<int,int> pii;
const int N = 1e2+5 , M = 1e5+5;
int mx , n , w , dp[N][M]; 
pii A[N];

int32_t main(){

  cin >> n >> w;

  for(int i = 1 ; i <= n ; i++) cin >> A[i].st >> A[i].nd;

  for(int i = 1 ; i <= n ; i++){
    for(int j = 0 ; j < M; j++){
      if(j-A[i].st >= 0) dp[i][j] = max(dp[i][j],dp[i-1][j-A[i].st]+A[i].nd);
      dp[i][j] = max(dp[i][j],dp[i-1][j]);
    }
  }

  for(int i = 0 ; i <= w ; i++) mx = max(dp[n][i],mx);

  cout << mx << "\n";

}

Measured memory_bytes: 79360
#include <iostream>

using namespace std;

int n, k, q, cnt[100005];

int main()
{
    cin >> n >> k >> q;
    for (int i = 1; i <= q; i++)
    {
        int now;
        cin >> now;
        cnt[now]++;
    }
    for (int i = 1; i <= n; i++)
    {
        if (cnt[i] > q - k) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 1152
// https://atcoder.jp/contests/abc090/tasks/abc090_a
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<string> v(3);
    REP(i, 3) cin >> v[i];
    REP(i, 3) cout << v[i][i];
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
int main(){
	int x, y;
	scanf("%d %d", &x, &y);
	for (int i = 0; i <= x; i++){
		if (2 * i + 4 * (x - i) == y){
			printf("Yes\n");
			return 0;
		}
	}
	printf("No\n");
}

Measured memory_bytes: 1660
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <string.h>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <sstream>

#define ll long long
#define ld long double
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;


int main() {
   int N, K; cin >> N >> K;
   int res = 0;
   for (int i = N; i <= K; i++) {
       string s = to_string(i);
       if(s[0] == s[4] && s[1] == s[3]) res++;
   }
   cout << res << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;




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

	vector<ll>data(101010);
	rep(i, 0, n) {
		ll a,b;
		cin >> a >> b;
		data[a] += b;
	}


	rep(i, 0, data.size()) {
		if (data[i] != 0) {
			if (k <= data[i]){
				cout << i << endl;
				exit(0);
			}
			else {
				k -= data[i];
			}
		}
	}





	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//const ll INF = 1LL << 60;
//const int INF = 1001001001;

int main(void){
    string s,t;
    cin >> s >> t;
    int ans=0;
    REP(i,3)if(s[i]==t[i])ans++;
    cout << ans;

    return 0;
}

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


#include<bits/stdc++.h>
using namespace std;
int visited[100005];

void dfs(int s, vector<int> vec[], vector<int> &dp)
{
	visited[s]=1;
	for(auto it = vec[s].begin();it!=vec[s].end();it++)
	{
		if(!visited[*it])
			dfs(*it, vec, dp);
			
		dp[s] = max(dp[s], 1+dp[*it]);
		
	}
}

int main()
{
	int n,m;
	cin>>n>>m;
	vector<int> vec[n+1];
	int x,y, ans=0;
	for(int i=0;i<m;i++)
	{
		
		cin>>x>>y;
		vec[x].push_back(y);
	}
	vector<int> dp(n+1);
	
	memset(visited, 0, sizeof(visited));
	
	for(int i=1;i<=n;i++)
	{
		if(!visited[i])
		dfs(i,vec, dp);
	}
	for(int i=1;i<=n;i++)
	{
		ans = max(ans,dp[i]);
	}
	cout<<ans;
	
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

int T[100100];
int A[100100];
int main(){
    int N;
    cin >> N;
    REP(i,N){
        int t,a;
        cin >> t >> a;
        T[i] = t;
        A[i] = a;
    }

    ll AA=1, TT=1;
    for(int i = 0; i < N; i++){
        ll t = T[i]; 
        ll a = A[i];
        ll tmpt = TT/t + !(TT%t == 0);
        ll tmpa = AA/a + !(AA%a == 0);
        if(tmpt != 0 || tmpa != 0){
            a *= max(tmpt, tmpa);
            t *= max(tmpt, tmpa);
        }
        AA = a;
        TT = t;
        //printf("TT:%lld, AA:%lld\n", TT, AA);
    }

    ll ans = AA + TT;
    //cout << ans << endl;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
using namespace std;
 
int main(){
  string str;
  cin >> str;
  vector<int> v(str.length(), 1);
  r(i,str.length()){
    if(str[i] == 'R'){
      if(str[i+1] == 'R'){
        v.at(i+2)+= v.at(i);
        v.at(i) = 0;
      }
    }
  }
  for(int i = str.length()-1; i >=0; i--){
    if(str[i]=='L'){
    if(str[i-1] == 'L'){
      v.at(i-2)+=v.at(i);
      v.at(i)=0;
    }
    }
  }
  r(i,str.length()){
    if(i) cout << " ";
    cout << v.at(i);
  }
  cout << endl;
}


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

int main() {
	int a, b, c; cin>>a>>b>>c;
	string ans = (c >= a && c <= b) ? "Yes" : "No";
	cout << ans << endl;
	return 0;
}


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

using namespace std;

int main(){
  int N;
  cin >> N;
  if(N % 2 == 1){
    cout << "No" << endl;
    return 0;
  }
  
  string s;
  cin >> s;
  
  for(int i = 0; i < N / 2; i++){
    if(s[i] != s[N / 2 + i]){
      cout << "No" << endl;
      return 0;
    }
  }
  
  cout << "Yes" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int f[100001]={0},a[101];
int main()
{
	int i,j,n,k;
	scanf("%d %d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<=k;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(a[j]<=i)
			{
				if(f[i-a[j]]==0)
				{
					f[i]=1;
					break;
				}
				else
					f[i]=0;
			}	
		}
	}
	if(f[k]==1)
		printf("First");
	else
		printf("Second");
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int v[100],c[100];
int main()
{
  int n,ans=0;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>v[i];
  for(int i=1;i<=n;i++) cin>>c[i];
  for(int i=1;i<=n;i++) if(v[i]-c[i]>0) ans+=(v[i]-c[i]);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let mut s = read::<String>().as_bytes().to_vec();

    s.dedup();
    let ans = if s.len() != 4 { "Bad" } else { "Good" };

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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


 int main(){
  string S;
  string sub;
  cin >> S;


  int i=0;
  int n;
  n = S.size();
 
  while (i <= n){
   sub = S.substr(i,1);
   cout << sub;
   i= i+2;
  }

 return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <algorithm>

template <class T>
T gcd(T n, T m) {
    while (m != 0) {
        n %= m;
        std::swap(n, m);
    }
    return n;
}

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

    uint ans = 1;
    for (int i = 0; i < n; ++i) {
        uint a;
        std::cin >> a;
        ans *= a / gcd(ans, a);
    }
    std::cout << ans << std::endl;
}



Measured memory_bytes: 3116
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
  string S;
  cin >> S;
  bool hflag = false, iflag = false;
  string ans = "Yes";
  for (int i = 0; i < S.length(); i++) {
    if (S[i] == 'h') {
      if ((i < S.length() - 1) && S[i + 1] == 'i') {
        i++;
        continue;
      } else {
        ans = "No";
        break;
      }
    } else {
      ans = "No";
      break;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> v(n);
    for (auto &&i : v) scanf("%lld", &i), i /= 2;
    ll val = 1, p = 1LL << 31;
    for (int i = 0; i < n; ++i) {
        if(val > m){
            puts("0");
            return 0;
        }
        val = val/__gcd(val, v[i])*v[i];
        p = __gcd(p, v[i]);
    }
    if(val > m){
        puts("0");
        return 0;
    }
    for (int i = 0; i < n; ++i) {
        if(v[i]/p%2 == 0){
            puts("0");
            return 0;
        }
    }
    cout << (m/val+1)/2 << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    ll n;
    cin>>n;
    string ans;
    while(n>0){
        --n;
        ans+='a'+n%26;
        n/=26;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}


Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include<numeric>
using namespace std;
using P = pair<int, int>;
#define rep(i,n) for(int i=0; i<(n);i++)
typedef long long ll;


int main(){
    int n, m; cin >> n >> m;
    vector<int> h(n+1);
    vector<int> ma(n+1, 0);
    for(int i=1; i <= n; i++){
        cin >> h[i];
    }
    rep(i, m){
        int a,b;
        cin >> a >> b;
        ma[a] = max(ma[a], h[b]);
        ma[b] = max(ma[b], h[a]);
    }
    int ans=0;
    for(int i=1; i <= n; i++){
        ans += h[i] > ma[i];
    }
    cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3640
n=int(input())
li=list(map(int,list(str(n))))
if(n<10):
    print(n)
else:
    ma=sum(li)
    for i in range(0,len(li)-1):
        if(li[-(i+1)]!=9):
            li[-(i+1)]=9
            li[-(i+2)]-=1
        ma=max([ma,sum(li)])
    print(ma)


Measured memory_bytes: 3060
#gcdは3.4.3だとfractionsにある
from fractions import gcd

from math import factorial as f

from math import ceil,floor,sqrt

from sys import exit

from copy import deepcopy
import numpy as np

import bisect
import re


ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))



def main():
    n = ii()
    s = input()

    ans = 1
    for i in range(1,n):
        if not s[i] == s[i-1]:
            ans+=1
    
    print(ans)


main()


Measured memory_bytes: 22784
#include "stdio.h"

#define MANA_MAX 9999

int FindBetter(int d[10][10], int w[10][10])
{
	int i, j, k;

	//i to jの最短を更新
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
			for(k=0;k<10;k++) //がj to kの距離に更新されたら
			{
				if(i!=j&&j!=k&&i!=k)
				{
					if(d[i][j]+d[j][k]<d[i][k])
					{
						d[i][k] = d[i][j]+d[j][k];
						return 1;
					}
				}
			}
		}
	}
	return 0;
}


int main(void){
	int i, j;
	int D[10][10];
	int WW, HH;
	int ans = 0;

#if 1
	int W[10][10];
	int BAMEN[200][200];

	scanf("%d", &HH);
	scanf("%d", &WW);

	for(i=0;i<10;i++)
	{
/*
		for(j=0;j<10;j++)
		{
			scanf("%d", &W[i][j]);
		}
*/
		scanf("%d%d%d%d%d%d%d%d%d%d", &W[i][0], &W[i][1], &W[i][2], &W[i][3], &W[i][4], &W[i][5], &W[i][6], &W[i][7], &W[i][8], &W[i][9]);
	}

	for(i=0;i<HH;i++)
	{
		for(j=0;j<WW;j++)
		{
			scanf("%d", &BAMEN[i][j]);
		}
	}


#else
#if 0
	HH = 3;
	WW = 5;

	int W[10][10] ={{0, 4, 3, 6, 2, 7, 2, 5, 3, 3}, 
			 		{4, 0, 5, 3, 7, 5, 3, 7, 2, 7},
					{5, 7, 0, 7, 2, 9, 3, 2, 9, 1},
					{3, 6, 2, 0, 2, 4, 6, 4, 2, 3},
					{3, 5, 7, 4, 0, 6, 9, 7, 6, 7},
					{9, 8, 5, 2, 2, 0, 4, 7, 6, 5},
					{5, 4, 6, 3, 2, 3, 0, 5, 4, 3},
					{3, 6, 2, 3, 4, 2, 4, 0, 8, 9},
					{4, 6, 5, 4, 3, 5, 3, 2, 0, 8},
					{2, 1, 3, 4, 5, 7, 8, 6, 4, 0}};

	int BAMEN[200][200] = {{3, 5, 2, 6, 1},{2, 5, 3, 2, 1},{6, 9, 2, 5, 6}};
#else
	HH = 2;
	WW = 4;

	int W[10][10] ={{0, 9, 9, 9, 9, 9, 9, 9, 9, 9}, 
			 		{9, 0, 9, 9, 9, 9, 9, 9, 9, 9},
					{9, 9, 0, 9, 9, 9, 9, 9, 9, 9},
					{9, 9, 9, 0, 9, 9, 9, 9, 9, 9},
					{9, 9, 9, 9, 0, 9, 9, 9, 9, 2},
					{9, 9, 9, 9, 9, 0, 9, 9, 9, 9},
					{9, 9, 9, 9, 9, 9, 0, 9, 9, 9},
					{9, 9, 9, 9, 9, 9, 9, 0, 9, 9},
					{9, 9, 9, 9, 2, 9, 9, 9, 0, 9},
					{9, 2, 9, 9, 9, 9, 9, 9, 9, 0}};

	int BAMEN[200][200] = {{-1, -1, -1, -1},{8, 1, 1, 8}};

#endif
#endif
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
			D[i][j] = W[i][j];
		}
	}

	while(FindBetter(D, W)==1)
	{

	}

	for(i=0;i<HH;i++)
	{
		for(j=0;j<WW;j++)
		{
			if(BAMEN[i][j]!=-1)
			{
				ans += D[BAMEN[i][j]][1];
			}
		}
	}

	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

signed main(){

	lli n;
	cin>>n;
	vector<lli> a(n);
	REP(i,0,n)cin>>a[i];

	vector<lli> now;
	for(auto x : a){
		auto ub = upper_bound(now.begin(),now.end(),x,greater<lli>());
		if(ub != now.end()){
			*ub = x;
		}
		else{
			now.push_back(x);
		}
	}
	cout<<now.size()<<endl;

	return 0;
}

Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) cin >> grid[i];
    vector<vector<ll>> dp(H+1, vector<ll>(W+1, 0));
    dp[1][1] = 1;
    ll mod = 1e9+7;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (i == 1 && j == 1) continue;
            if (grid[i-1][j-1] == '#') continue;
            dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
        }
    }
    cout << dp[H][W] << endl;
    
    return 0;
}

Measured memory_bytes: 12968
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine().trim();
		int s = Integer.parseInt(line);
		int h = s / 3600;
		s -= 3600 * h;
		int m = s / 60;
		s -= 60 * m;
		System.out.println(h + ":" + m + ":" + s);
		br.close();
	}
	
}

Measured memory_bytes: 24416
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int a, b;
    cin >> a >> b;
    if ( a % 3 == 0 || b % 3 == 0 || ( a + b ) % 3 == 0 ) cout << "Possible" << endl;
    else                                                  cout  <<"Impossible" << endl; 
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
int n,last[maxn],dp[maxn];
char s[maxn];
int main()
{	
	scanf("%d%s",&n,s+1);
	int lp=0;
	for (int i=1;i<=n;i++)
	{
		last[i]=lp;
		if (s[i]=='0') lp=i;
	}
	for (int i=1;i<=n;i++)
	{
		dp[i]=dp[i-1];
		if (s[i]=='0' || !last[i] || s[last[i]-1]=='0') continue;
		int pos=last[i];
		int lpos=last[pos];
		if (pos>=2) dp[i]=max(dp[i],dp[pos-2]+i-pos);//10111111...
		if (pos==i-1)//0111111...01
		{
			if (lpos>=0) dp[i]=max(dp[i],dp[lpos]+i-lpos-2);//dp[lpos]+number of 1 on the left
		if (lpos+1<pos) dp[i]=max(dp[i],dp[lpos+1]+i-lpos-3);
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}


Measured memory_bytes: 4608
#include <algorithm>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
// const int INF = (1 << 30) - 1;
// const ll LL_INF = (1LL << 62) - 1;
// const ll MOD = 1e9 + 7;

string S;
// vector<int> A;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> S;
  // A.resize(N);
  // for (int i = 0; i < N; i++) {
  //   int tmp;
  //   cin >> tmp;
  //   A[i] = tmp;
  // }

  if (S == "AAA" || S == "BBB") {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;

template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}

template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==v.size()?"":" ");
    return os;
}

struct UnionFind{
    vector<int> par;
    vector<int> siz;
    vector<ll> a;
    int c;//親の個数(グループ数)
    void init(int n){
        c=n;
        for(int i=0;i<n;i++){
            par.push_back(i);
            siz.push_back(1);
        }
        a.assign(n,0);
    }
    UnionFind(int n){
        init(n);
    }
    int root(int x){
        //根を返す
        return(par[x]==x?x:(par[x]=root(par[x])));
    }
    bool sameParent(int x,int y){
        return(root(x)==root(y));
    }
    void unite(int x, int y){
        x=root(x);y=root(y);
        if(x==y)    return;
        if(siz[x]<siz[y]) swap(x,y);
        siz[x] += siz[y];par[y]=x;c--;
        a[x]+=a[y];
    }
    int size(int x){
        return siz[root(x)];
    }
};

struct edge{
    int from,to,id;ll cost;
    edge(int from,int to,ll cost,int id=-1):from(from),to(to),cost(cost),id(id){}
    edge(){}
};

signed main(){
    int n,m;cin>>n>>m;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];
    vector<edge>es;
    vector<vector<edge>> g(n);
    rep(i,m){
        int u,v;ll c;cin>>u>>v>>c;u--,v--;
        es.push_back(edge(u,v,c,i));
        g[u].push_back(edge(u,v,c,i));
        g[v].push_back(edge(v,u,c,i));
    }
    sort(ALL(es),[](edge lhs,edge rhs){
        return lhs.cost<rhs.cost;
    });
    UnionFind uf(n);
    rep(i,n)uf.a[i]=a[i];
    vector<ll>check(m,-1);
    for(auto e:es){
        uf.unite(e.from,e.to);
        if(uf.a[uf.root(e.from)]>=e.cost){
            check[e.id]=e.cost;
        }
    }

    // dfsでcheckしたところのコスト以下のところをcheckつける
    function<void(int,ll)> dfs=[&](int now,ll lim){
        // lim以下を辿れる
        for(auto e:g[now]){
            if(e.cost<=lim){
                if(chmax(check[e.id],lim)){
                    dfs(e.to,lim);
                }
            }
        }
    };

    reverse(ALL(es));
    for(auto e:es){
        if(check[e.id]<0) continue;
        dfs(e.from,e.cost);
        dfs(e.to,e.cost);
    }

    int ans=m;
    rep(i,m)if(check[i]>=0) ans--;
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  long double  a,b,h,m;
  cin >> a >> b >> h >> m;
  
  long double x,y,shita;
  
  x = 30.0*h+0.5*m;
  y = 6.0*m;
  shita = abs(x-y);
  if(shita>180.0)
    shita = 360.0-shita;
  
  long double rad;
  long double pi     = 2.0 * asin(1.0);
  long double radian = pi / 180.0; 
  rad = radian*shita;
  
  long double c;
  
  c = a*a + b*b -2*a*b*cos(rad);
  long double ans;
  ans = sqrt(c);
  
  cout << fixed <<  setprecision(15) << ans << endl;
  
  
  
  return 0;
}

Measured memory_bytes: 4168
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main
{
	public static void main(String[] Arguments) throws IOException 
	{
		BufferedReader BR = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ST;
		int N = Integer.parseInt(BR.readLine()), A; HashMap<Integer, Integer> Counts = new HashMap<>();
		ST = new StringTokenizer(BR.readLine());
		for (int i = 1; i < N; i++)
		{
			A = Integer.parseInt(ST.nextToken());
			if (Counts.containsKey(A)) Counts.put(A, Counts.get(A) + 1);
			else Counts.put(A, 1);
		}
		for (int i = 1; i <= N; i++) System.out.println((Counts.containsKey(i)) ? Counts.get(i) : "0");
	}
}


Measured memory_bytes: 69580
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define E "\n"

using namespace std;
const long long MOD = (long long)1e9 + 7;

int n, m, u, v;
vector<pair<int, int> > dat[100009];
pair<int, int> edge[100009];
bool vis[100009];

bool fun(int cur)
{
    bool self_state = true;
    vector<int> my_e;
    for (int i = 0; i < (int)dat[cur].size(); i++) {
        if (!vis[dat[cur][i].se]) {
            vis[dat[cur][i].se] = true;
            self_state = !self_state;
            if (edge[dat[cur][i].se].se != dat[cur][i].fi)
                swap(edge[dat[cur][i].se].fi, edge[dat[cur][i].se].se);
            my_e.pb(dat[cur][i].se);
        }
    }
    for (int i = 0; i < (int)my_e.size(); i++) {
        int tmp = edge[my_e[i]].se;
        bool ret = fun(tmp);
        if (!ret) {
            self_state = !self_state;
            swap(edge[my_e[i]].fi, edge[my_e[i]].se);
        }
    }
    return self_state;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        u--; v--;
        edge[i].fi = u; edge[i].se = v;
        dat[u].pb(make_pair(v, i));
        dat[v].pb(make_pair(u, i));
    }
    if (fun(0)){
        for (int i = 0; i < m; i++) {
            cout << edge[i].fi + 1 << " " << edge[i].se + 1 << E;
        }
    }
    else {
        cout << -1 << E;
    }
    //system("pause");
    return 0;
}


Measured memory_bytes: 18688
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define endl        "\n"

const int mod = 1e9+7;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

int last(int num) {
    string s = to_string(num);
    int n = s.size();
    int ans = s[n - 1] - '0';
    return ans;
}

void solve() { 
    int k; cin >> k;
    queue<int> q;
    vector<int> v;
    for(int i=1; i<10; i++) {
        q.push(i);
        v.push_back(i);
    }
    if(k < 10) {
        cout << v[k-1] << endl;
        return;
    }
    int cnt = 9;
    while(cnt < k) {
        int sz = q.size();
        while(sz--) {
            int cur = q.front(); q.pop();
            int ld = last(cur);
            if(ld == 0) {
                q.push(cur*10);
                q.push(cur*10 + 1);
                v.push_back(cur*10);
                v.push_back(cur*10 + 1);
            } else if(ld == 9) {
                q.push(cur*10 + 8);
                q.push(cur*10 + 9);
                v.push_back(cur*10 + 8);
                v.push_back(cur*10 + 9);
            } else {
                q.push(cur*10 + ld-1);
                q.push(cur*10 + ld);
                q.push(cur*10 + ld+1);
                v.push_back(cur*10 + ld-1);
                v.push_back(cur*10 + ld);
                v.push_back(cur*10 + ld+1);
            }
        }
        cnt += q.size();
    }
    cout << v[k-1] << endl;
   // for(int x : v) cout << x << " ";
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3060
#include<iostream>

using namespace std;

int main()
{
    int a,b,c,d=0,i;
    cin >> a >> b >> c;
    for(i = a;i <= b; i++)
    {
        if(c % i == 0)
        {
            d += 1;
        }
    }
    cout << d << endl;
    return 0;
}


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

#define REP(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long

using namespace std; 

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

    int x[n];
    int y[n];
    int z[n];
    REP(i, n){
        cin >> x[i] >> y[i];
        z[i] = x[i] + y[i];
    }
    
    int xmax = x[0];
    int nmax = z[0];
    int nmin = z[0];
 
    FOR(i,1, n){
        if(x[i] > xmax) xmax = x[i];
        if(z[i] > nmax) nmax = z[i];
        if(z[i] < nmin) nmin = z[i];
    }
    
    int ans = nmax - nmin;

    nmax = y[0] + xmax-x[0];
    nmin = y[0] + xmax-x[0];
    FOR(i, 1, n){
        z[i] = y[i] + xmax-x[i];
        if(nmax < z[i]) nmax = z[i];        
        if(nmin > z[i]) nmin = z[i];
    }
    if (ans < nmax - nmin) ans = nmax-nmin;
    cout << ans;

    
}

Measured memory_bytes: 5904
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define ufor(i,l,r) for (int i=l;i<=r;i++)
#define MAXN 20000500

int main()
{
	char s[100000];
	scanf("%s",s);
	bool flag=(s[2]==s[3] && s[4] == s[5]);
	printf((flag)? "Yes":"No");
		
	return 0;
}


Measured memory_bytes: 3836
#include <stdio.h>

int main(void)
{
	int n, max, min;
	long long sum;
	int i, d;

	max = -1000000;
	sum = 0;
	min = 1000000;

	scanf("%d", &n);

	for(i=0;i<n;i++){
		scanf("%d", &d);
		sum += d;
		if(d>max)
			max = d;
		if(d < min)
			min = d;
	}

	printf("%d %d %ld\n", min, max, sum);
	return 0;
}

Measured memory_bytes: 600
#include <iostream>
using namespace std;
int A, B;
int C[4005][4005], Pref[4005][4005], Pref2[4005][4005];
const int MOD = 1000000007;
void precalcC()
{
    C[0][0] = 1, Pref[0][0] = 1;
    for(int i = 1; i <= 4000; i++)
        C[i][0] = 1, Pref[i][0] = 1;
    for(int i = 0; i <= 4000; i++)
        for(int j = 1; j <= 4000; j++)
        {
            if(j <= i)
            {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]);
                if(C[i][j] >= MOD)
                    C[i][j] -= MOD;
            }

            Pref[i][j] = Pref[i][j - 1] + C[i][j];
            if(Pref[i][j] >= MOD)
                Pref[i][j] -= MOD;

        }
    for(int j = 0; j <= 4000; j++)
        for(int i = 0; i <= 4000; i++)
        {
            if(i > 0)
            Pref2[j][i] = Pref2[j][i - 1];
            else
                Pref2[j][i] = 0;
            Pref2[j][i] += Pref[j][i];
            if(Pref2[j][i] >= MOD)
                Pref2[j][i] -= MOD;
        }
}
void Add(int& x, int y)
{
    x += y;
    if(x >= MOD)
        x -= MOD;
}
void Solve()
{
    int ans = 0;
    for(int p = 0; p <= A; p++)
    {

        for(int q = 0; q < B; q++)
        {
            if(p + q > A)
                continue;

                int r = C[B - 1][q];
            int aux = 1;
            if(q > 0)
                aux = Pref2[q - 1][p];
            r = (1LL * r * (aux)) % MOD;
            Add(ans, r);


        }
    }
    cout << ans << '\n';
}
int main()
{
    cin >> A >> B;
    precalcC();
    Solve();
    return 0;
}


Measured memory_bytes: 188160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n;
ll M=1000000007;
int main(void){
    int a,b;
    cin>>a>>b;
    if(a+b==15){
        cout<<"+"<<endl;
    }else if(a*b==15){
        cout<<"*"<<endl;
    }else{
        cout<<"x"<<endl;
    }
    
}


Measured memory_bytes: 3612
#include <stdio.h>

int A[305][305];
int need[305][305];

typedef long long ll;

int main(){

	int N;

	scanf("%d",&N);

	int i,j,k;

	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
		scanf(" %d",&A[i][j]);
		}
	}

	for(k=0;k<N;k++){
		for(i=0;i<N;i++){
			for(j=0;j<N;j++){
				if(A[i][j]>A[i][k]+A[k][j]){
				printf("-1\n");
				return 0;
				}
				if(A[i][j]==A[i][k]+A[k][j]&&A[i][k]>0&&A[k][j]>0){
				need[i][j]=1;
				}
			}
		}
	}
	ll ans=0ll;
	for(i=0;i<N;i++){
			for(j=i;j<N;j++){
				if(need[i][j]==0){
				ans+=(ll)A[i][j];
				}
			}
	}
	printf("%lld\n",ans);

	return 0;
}

Measured memory_bytes: 896
//In the name of GOD
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt" , "r+" , stdin) ; freopen("output.txt" , "w+" , stdout);
#define pb push_back
#define Mp make_pair
#define pll pair<ll, ll>
#define F first
#define S second

ll n, a[maxn], ps[maxn], sp[maxn], x, ans;
multiset<ll> s;

int main(){
	fast_io;
	
	cin >> n;
	for(ll i = 0; i < 3 * n; i++){
		cin >> a[i];
	}
	for(ll i = 0; i < n; i++){
		s.insert(a[i]);
		ps[n - 1] += a[i];
	}
	for(ll i = n; i < 3 * n; i++){
		ps[i] = ps[i - 1];
		if(a[i] > *s.begin()){
			ps[i] += a[i] - *s.begin();
			s.erase(s.begin());
			s.insert(a[i]);
		}
	}
	reverse(a, a + 3 * n);
	for(ll i = 0; i < 3 * n; i++){
		a[i] *= -1;
	}
	s.clear();
	for(ll i = 0; i < n; i++){
		s.insert(a[i]);
		sp[n - 1] += a[i];
	}
	for(ll i = n; i < 3 * n; i++){
		sp[i] = sp[i - 1];
		if(a[i] > *s.begin()){
			sp[i] += a[i] - *s.begin();
			s.erase(s.begin());
			s.insert(a[i]);
		}
	}
	ans = -inf;
	for(ll i = n - 1; 3 * n - i - 2 >= n - 1; i++){
		ans = max(ans, ps[3 * n - i - 2] + sp[i]);
	}
	cout << ans;
	
	return 0;
}


Measured memory_bytes: 14464
#include<iostream>
#include<cmath>

int main(){
	//入力機構
	int X,maxbp=1;
	std::cin>>X;
	//処理機構
	//単純に2~sqrt(X)について最大の畳数を求める
	if(X==1){
		//1^nについては、nを求められないので個別に処理
		maxbp=1;
	} else{
		//2以上について探していく
		int rx=(int)(std::sqrt((double)X));
		if(rx*rx==X){
			//Xがrx^2である場合はすぐわかる
			maxbp=X;
		} else{
			//Xがrx^2出ない場合は、地道に求める
			for(int b=2;b<=rx;b++){
				int bp=b*b;//bpにはb^2,b^3.....が格納されていく
				while(bp<=X){
					if(maxbp<bp){
						maxbp=bp;//より大きい値を見つけたら更新
					}
					bp*=b;
				}
				if(maxbp==X){
					//maxbpがXに達したら直ちに終了させる
					break;
				}
			}
		}

		}
	//出力機構
	std::cout<<maxbp<<std::endl;

	return 0;
}

Measured memory_bytes: 256