akhauriyash/Code-Regression huggingface dataset:
/*
START BY THE NAME OF ALMIGHTY ALLAH
THIS WONT BE ACCEPTED
STOP_GIVING_UP

██╗███████╗████████╗██╗ █████╗ ██╗  ██╗
██║██╔════╝╚══██╔══╝██║██╔══██╗██║ ██╔╝
██║███████╗   ██║   ██║███████║█████╔╝
██║╚════██║   ██║   ██║██╔══██║██╔═██╗
██║███████║   ██║   ██║██║  ██║██║  ██╗
╚═╝╚══════╝   ╚═╝   ╚═╝╚═╝  ╚═╝╚═╝  ╚═╝

*/
#include<bits/stdc++.h>
#define l(i,a,n)for(int i=a;i<n;i++)
#define pb push_back
#define in insert
#define mp make_pair
#define lw(v) sort(v.begin(),v.end());
#define hi(v) sort(v.begin(),v.end(),greater<long long>());
#define all(v) v.begin(),v.end()
#define filein freopen ("input.txt", "r", stdin)
#define fileout freopen ("output.txt", "w", stdout)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long t,r=1,r1=0,r2=0,k=0,a,b,c=1,m,d=0,n,e,f,x=0,g,p=0,q=0,y=0,z=0;
    vector<long long>v;
    vector<long long>u;
    set<char>s;
    std::vector<int>::iterator it;
    string  s1,s2,s3,s4;
   cin>>n>>s1>>s2;
   l(i,0,n)
   {
       s3=s3+s1[i]+s2[i];
   }
cout<<s3<<endl;

}


Measured memory_bytes: 3564
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
x = int(input())
#a, b = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

c = 100
ans = 0
while (True):
    ans += 1
    c = math.floor(c*1.01)
    if c >= x:
        print(ans)
        break


Measured memory_bytes: 9560
char S[12];
char out[2<<20];
int outsz,Slen;
main()
{
	int N,K;
	scanf("%d%d ",&N,&K);
	gets(S);
	Slen=strlen(S);
	for(int i=0;i<K;i++)
	{
		strcpy(out+outsz,S);
		outsz+=Slen;
		out[outsz++]='\n';
	}
	for(int i=K;i<N;i++)
	{
		out[outsz++]='7';
		out[outsz++]='\n';
	}
	write(1,out,outsz);
}

Measured memory_bytes: 2304
#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>

#define forin(i,f,t) for(ll i = f; i < t; ++i)

using namespace std;
using ll = long long;
using ld = long double;

ll N;
string S;

void input() {
    cin >> N;
    cin >> S;
}

ll solve() {
    vector<ll> cw(N), cb(N);
    cb[0] = S[0] == '#';
    for (ll i = 1; i < N; i++) {
        cb[i] = cb[i-1] + (S[i] == '#' ? 1 : 0);
    }
    cw[N-1] = S[N-1] == '.';
    for (ll i = N-2; i >= 0; i--) {
        cw[i] = cw[i+1] + (S[i] == '.' ? 1 : 0);
    }
    ll ans = min(cw[0], cb[N-1]);
    for (ll i = 1; i < N; i++) {
        ans = min(ans, cb[i-1] + cw[i]);
    }
    return ans;
}

int main() {
    input();
    cout << solve() << endl;
    
    return 0;
}



Measured memory_bytes: 3708
N, A, B = map(int, input().split())

ans_list = []
for i in range(N + 1):
    n = i
    local_sum = 0
    for j in reversed(range(len(str(i)))):
        local_sum += n // (10 ** j)
        n -= n // (10 ** j) * (10 ** j)
    if A <= local_sum and local_sum <= B:
        ans_list.append(i)
print(sum(ans_list))

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

int main() {
    string S;
    cin >> S;
    int N = stoi(S);
    int bunbo = 0;
    for (int i=0; i<int(S.size()); i++) {
        bunbo += S.at(i) - '0';
    }
    if (N%bunbo==0) cout << "Yes\n";
    else cout << "No\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll unsigned long long
#define rep(i,l,r) for(int (i)=(l);(i)<(r);(i)++)
#define drep(i,l,r) for(int (i)=(l);(i)>=(r);(i)--)
using namespace std;
int main(){
    ll n;
    string s,t,ans;
    cin>>s>>t;
    ans=t;
    ans+=s;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
//↓見なくていいよ！ここから--------------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
var obj;
var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  myerr("-----start-----");
  var start = new Date();
  Main();
  var end = new Date() - start;
  myerr("----- end -----");
  myerr("time : " + (end) + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  var returnObj = {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(!this.hasNext()){throw "ArrayIndexOutOfBoundsException これ以上ないよ";}else{var returnInput = this.list[this.index];this.index++;return returnInput;}}
  };
  return returnObj;
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//[no]要素の扱い。数値型
//不明値、異常時:引数そのまま返す 1:数値へ変換
//2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字で分割  7:1文字で分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//↑見なくていいよ！ここまで--------------------------------------------------
function Main(){
	var N = nextInt();
	var minList = new Array(N);
	var maxList = new Array(N);
	for(var i = 0; i < N; i++){
		var tmp = nextIntArray();
		minList[i] = tmp[0];
		maxList[i] = tmp[1];
	}
	minList.sort(function(a,b){
		return a - b;
	});
	maxList.sort(function(a,b){
		return a - b;
	});
	var output = 0;
	var MIN;
	var MAX;
	if(N % 2 == 1){
		MIN = minList[(N - 1) / 2];
		MAX = maxList[(N - 1) / 2];
		output = MAX - MIN + 1;
	}else{
		MIN = (minList[N / 2 - 1] + minList[N / 2]) / 2;
		MAX = (maxList[N / 2 - 1] + maxList[N / 2]) / 2;
		output = (MAX - MIN) * 2 + 1;
	}
	
	myout(output);
}

Measured memory_bytes: 90904
N,M,S,T = map(int,input().split())
yX = [[] for _ in range(N)]
sX = [[] for _ in range(N)]
for i in range(M):
    u,v,a,b = map(int,input().split())
    yX[u-1].append((v-1,a))
    yX[v-1].append((u-1,a))
    sX[u-1].append((v-1,b))
    sX[v-1].append((u-1,b))

# 0-indexed
S,T = S-1,T-1

# ---------- ---------- ---------- ---------- ---------- ----------
# dijkstra's algorithm
# ---------- ---------- ---------- ---------- ---------- ----------
import heapq
INF = float("inf")
def dijkstra(start, dM, cost):
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        for xto, xc in dM[v]:
            if c + xc >= cost[xto]:
                continue
            cost[xto] = c + xc
            heapq.heappush(hq, (cost[xto],xto))

# 頂点数
dN = N
# 開始頂点
start = S
# 隣接リスト (v,cost)
dM = yX
# コスト
cost1 = [INF]*dN
cost1[start] = 0
# 実行
dijkstra(start, dM, cost1)


# 開始頂点
start = T
# 隣接リスト (v,cost)
dM = sX
# コスト
cost2 = [INF]*dN
cost2[start] = 0
# 実行
dijkstra(start, dM, cost2)

Ans = [INF]
for i in reversed(range(N)):
    Ans.append(min(Ans[-1], cost1[i]+cost2[i]))

for ans in reversed(Ans[1:]):
    print(10**15 - ans)


Measured memory_bytes: 87988
import java.util.Scanner;

//atcoderはScannerクラスのsc.next()で行ける
public class Main{
    public static void main (String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int x = sc.nextInt();
        if (500*k >= x){
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 35648
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

constexpr auto M = 1000000007;

int64_t p(int64_t m) {
  constexpr auto B = 3;
  if (m == 0) {
    return 1;
  }
  int64_t ret = p(m / 2) * p(m / 2) % M;
  if (m % 2 == 1) ret = ret * B % M;
  return ret;
}

main() {
  string s;
  cin >> s;

  int64_t ans = 0;
  int64_t coeff = 1;
  for (auto i : irange(0uL, s.size())) {
    if (s[i] == '1') {
      ans += coeff * p(s.size() - i - 1);
      ans %= M;
      coeff *= 2;
      coeff %= M;
    }
  }
  ans += coeff;
  ans %= M;
  cout << ans << endl;
}

Measured memory_bytes: 512
import java.util.*;
public class Main{
  public static void main(String[] args) {

    Scanner ob = new Scanner(System.in);
    String S = ob.next();
    String result = "";

    if(S.equals("ABC")){
      result += "ARC";
    }
    else{
      result += "ABC";
    }
    System.out.println(result);
  }
}


Measured memory_bytes: 26888
import java.util.Scanner;



public class Main {


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());
		int sum = 0;

		int xa = Math.min(a,k);
		k -= xa;
		int xb = Math.min(b, k);
		k -= xb;
		int xc = k;
		sum = xa - xc;
		System.out.println(sum);


	}
}


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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long x;
    cin >> x;
    long long a = 0;
    long long b = 0; 
    while (pow(a,5) - pow(a-1,5) <= x) {
        b = -a;
        while (b < a) {
            if (pow(a,5) - pow(b,5) == x) {
                cout << a << " " << b;
                return 0;
            }
            b++;
        }
        a++;
    }
}


Measured memory_bytes: 4008
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from heapq import heappush, heappop
from collections import defaultdict

x,y,z,k = li()
a = list(li())
b = list(li())
c = list(li())

a.sort()
b.sort()
c.sort()

acur = x-1
bcur = y-1
ccur = z-1

deli = []
que = [(-a[-1]-b[-1]-c[-1], x-1, y-1, z-1)]
searched = defaultdict(bool)

while len(deli) < k:
    good, acur, bcur, ccur = heappop(que)
    deli.append(-good)
    
    if acur > 0 and not searched[(acur-1, bcur, ccur)]:
        heappush(que, (-a[acur-1]-b[bcur]-c[ccur], acur-1, bcur, ccur))
        searched[(acur-1, bcur, ccur)] = True
    
    if bcur > 0 and not searched[(acur, bcur-1, ccur)]:
        heappush(que, (-a[acur]-b[bcur-1]-c[ccur], acur, bcur-1, ccur))
        searched[(acur, bcur-1, ccur)] = True
    
    if ccur > 0 and not searched[(acur, bcur, ccur-1)]:
        heappush(que, (-a[acur]-b[bcur]-c[ccur-1], acur, bcur, ccur-1))
        searched[(acur, bcur, ccur-1)] = True
        
for di in deli:
    print(di)

Measured memory_bytes: 5628
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>

using namespace std;

const int MAXN=2e5;
const int INF=1e9;
struct node
{
	int x,y,l,r;
	friend bool operator <(const node a,const node b)
	{
		return a.x>b.x;
	}
};
priority_queue <node> ans;
int f[4*MAXN][2]; 
int a[MAXN],id[MAXN]; 
void build(int root,int left,int right)
{
	if (left==right)
	{
		if (left&1)
		{
			f[root][1]=a[left],f[root][0]=INF; 
		}
		else
		{
			f[root][0]=a[left],f[root][1]=INF;
		}
		return ;
	}
	int mid=(left+right)>>1;
	build(2*root,left,mid);
	build(2*root+1,mid+1,right);
	f[root][1]=min(f[2*root][1],f[2*root+1][1]);
	f[root][0]=min(f[2*root][0],f[2*root+1][0]); 
}	
int query(int root,int left,int right,int qleft,int qright,bool p)
{
	if (left>=qleft && right<=qright)
	{
		if (p)
		{
			return f[root][1];
		}
		else
		{
			return f[root][0];
		}
	}
	int mid=(left+right)>>1;
	if (qright<=mid)
	{
		return query(2*root,left,mid,qleft,qright,p);
	}
	else if (qleft>mid)
	{
		return query(2*root+1,mid+1,right,qleft,qright,p);
	}
	else
	{
		int ans1,ans2;
		ans1=query(2*root,left,mid,qleft,mid,p);
		ans2=query(2*root+1,mid+1,right,mid+1,qright,p);
		return min(ans1,ans2);
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		id[a[i]]=i;
	}
	build(1,1,n);
	int x=query(1,1,n,1,n,1);
	int y=query(1,1,n,id[x]+1,n,0);
	node q;
	q.l=1,q.r=n,q.x=x,q.y=y;
	ans.push(q);
	for (int i=2;i<=n/2;i++)
	{
		q=ans.top();
		ans.pop();
		int nx=id[q.x];
		int ny=id[q.y];
		node now;
		if (q.l<nx)
		{
			bool p=q.l&1;
			int x=query(1,1,n,q.l,nx-1,p);
			int y=query(1,1,n,id[x]+1,nx-1,p^1);
			now.l=q.l;
			now.r=nx-1;
			now.x=x;
			now.y=y;
			ans.push(now);
		}
		if (nx+1<ny)
		{
			bool p=(nx+1)&1;
			int x=query(1,1,n,nx+1,ny-1,p);
			int y=query(1,1,n,id[x]+1,ny-1,p^1);
			now.l=nx+1;
			now.r=ny-1;
			now.x=x;
			now.y=y;
			ans.push(now);
		}
		if (ny<q.r)
		{
			bool p=(ny+1)&1;
			int x=query(1,1,n,ny+1,q.r,p);
			int y=query(1,1,n,id[x]+1,q.r,p^1);
			now.l=ny+1;
			now.r=q.r;
			now.x=x;
			now.y=y;
			ans.push(now);
		}
		printf("%d %d ",q.x,q.y);
	}
	while (!ans.empty())
	{
		node now=ans.top();
		ans.pop();
		printf("%d %d ",now.x,now.y);
	}
    return 0;
}


Measured memory_bytes: 8436
n, m = map(int, input().split())
c = []
for i in range(m):#h:高さ
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
p = []
q = []
for i in range(n):
    p.append(0)
    q.append(0)
j = 0
count = 0
for i in range(m):
    if i == 0:
        p[j] = c[i][0]
        q[j] = c[i][1] - 1
    elif i != 0:
        if c[i][0] != c[i - 1][0]:
            j += 1
            p[j] = c[i][0]
            q[j] = c[i][1] - 1
            if q[j - 1] < p[j]:
                count += 1
            else:
                if p[j] < p[j - 1]:
                    p[j] = p[j - 1]
                if q[j] > q[j - 1]:
                    q[j] = q[j - 1]
count += 1
print(count)

Measured memory_bytes: 30296
import bisect

N, M, K = map(int, input().split())

A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_sum = A.copy()
B_sum = B.copy()

for i in range(1, N):
    A_sum[i] = A_sum[i - 1] + A[i]

A_sum = [0] + A_sum

for i in range(1, M):
    B_sum[i] = B_sum[i - 1] + B[i]


max_ = 0
for i, n in enumerate(A_sum):
    if n > K:
        continue

    target = K - n
    v = bisect.bisect_left(B_sum, target)

    if v != M and B_sum[v] == target:
        v += 1

    max_ = max(max_, i + v)

print(max_)


Measured memory_bytes: 48920
#include <stdio.h>

int main ()
{
  int S, h, m1, m, s1;
  scanf("%d", &S);
  h=S/3600;
  m1=S%3600;
  m=m1/60;
  s1=m1%60;
  printf("%d:%d:%d\n", h,m,s1);
  return 0;
}



Measured memory_bytes: 2100
#include <iostream>

using namespace std;

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

	int N = S.length();

	int win_count = 0;
	for (int i = 0; i < N; i++) {
		if (S.at(i) == 'o') {
			win_count++;
		}
	}

	if (15 - N + win_count >= 8) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
	

}






Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    S = list(input())
    
    tmp = {}
    for i in S:
        if i in tmp:
            print("no")
            sys.exit()
        else:
            tmp[i] = 1
            
    print("yes")
        
if __name__ == "__main__":
	main()


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

//One case remains WA
int main(){
	ll a; cin>>a;
	double b; cin>>b;
	int c=b*100+0.5;
	ll ans=(a*c)/100;
	cout << ans << endl;
}

Measured memory_bytes: 3724
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
		int d=Math.abs(a+b-c);
		int e=Math.abs(b-a-c);
		if(c>=b&&c<=b+a||c+a>=b&&c+a<=b+a) {
			System.out.println(0);
		}
		else {
			System.out.println(d<=e?d:e);
		}
		}
	}


Measured memory_bytes: 21460
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    char c[3][3];
    rep(i,3) rep(j,3) cin >> c[i][j];
    rep(i,3) cout << c[i][i];
    cout << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#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() {
  int a, b;
  string s;
  while (1) {
    cin >> a >> s >> b;
    if (s == "?")
      break;
    else if (s == "+")
      cout << a + b << endl;
    else if (s == "-")
      cout << a - b << endl;
    else if (s == "*")
      cout << a * b << endl;
    else
      cout << a / b << endl;
  }
  return 0;
}


Measured memory_bytes: 3136
import java.util.Scanner;

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

        sc.close();

        String a = s.substring(0, 1);
        String c = s.substring(2, s.length() - 1);
        String rep = s.replaceAll("A", "");
        rep = rep.replaceAll("C", "");

        boolean flg = true;

        if (!a.equals("A")) {
            flg = false;
        }

        int count = 0;
        for (int i = 0; i < c.length(); i++) {
            if (c.charAt(i) == 'C') {
                count++;
            }
        }
        if (count != 1) {
            flg = false;
        }

        String low = rep.toLowerCase();
        if (!rep.equals(low)) {
            flg = false;
        }

        if (flg) {
            System.out.println("AC");
        } else {
            System.out.println("WA");
        }
    }
}

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

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back

using namespace std;

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

int main() {

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

	//ifstream cin("input.txt");

	int n;
	ll a, b, c, d;
	
	cin >> n;
	cin >> a >> b >> c >> d;
	--n;

	for (ll k = 0; k <= n; ++k) {
		ll m = n - k;
		ll lf = a + k * c, rg = a + k * d;
		lf -= m * d;
		rg -= m * c;
		if (b >= lf && b <= rg) {
			cout << "YES\n";
			return 0;
		}
	}

	cout << "NO\n";

}

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

int main(void) {
    int n,x;
    while(1) {
        cin>>n>>x;
        int ans=0;
        if(n==0 && x==0) return 0;
        for(int i=1;i<=n-2;i++) {
            for(int j=i+1;j<=n-1;j++) {
                for(int k=j+1;k<=n;k++) {
                    if(x==i+j+k) ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 3108
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
int main()
{
	string s;
	int k;
	cin>>s>>k;
	vector<string> v;
	for(int i=0;i<s.size();i++) 
	for(int j=1;j<=5;j++)
	v.push_back(s.substr(i,j));
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	cout<<v[k-1]<<endl;
return 0;
 } 

Measured memory_bytes: 1788
n=int(input())
a=list(map(int,input().split()))
k=[0]*max(a)
for i in range(n):
	k[a[i]-1]+=1
ans=0
b=0
for i in range(max(a)):
	if k[i]%2!=0:
		ans+=1
	elif k[i]!=0:
		b+=1
if b%2==0:
	ans+=b
else:
	ans+=b-1
print(ans)

Measured memory_bytes: 14008
use std::io::*;
use std::str::FromStr;

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

struct Solver {
    s: Vec<char>,
    skip: Vec<Vec<usize>>,
    memo: Vec<usize>,
}

impl Solver {
    fn new() -> Solver {
        let s = read::<String>().chars().collect::<Vec<char>>();
        let n = s.len();
        let mut skip = vec![vec![n + 10; 26]; n + 1];
        for i in (0..n).rev() {
            let c = (s[i] as u8 - 'a' as u8) as usize;
            skip[i] = skip[i + 1].clone();
            skip[i][c] = i;
        }
        Solver {
            s: s,
            skip: skip,
            memo: vec![n + 10; n + 10],
        }
    }
    fn calc(&mut self, pos: usize) -> usize {
        let n = self.s.len();
        if pos >= n + 10 {
            return 0;
        }
        if self.memo[pos] < n + 10 {
            return self.memo[pos];
        }
        let mut ret = n;
        for c in 0..26 {
            let npos = 1 + self.skip[pos][c];
            let nret = 1 + self.calc(npos);
            // println!("{} {} {}", c, npos, nret);
            ret = std::cmp::min(ret, nret);
        }
        self.memo[pos] = ret;
        ret
    }
    fn solve(&mut self) {
        let n = self.s.len();
        let len = self.calc(0);
        let mut ans = vec![];
        let mut pos = 0;
        while pos < n {
            for c in 0..26 {
                let npos = 1 + self.skip[pos][c];
                let nlen = self.calc(npos);
                if 1 + nlen + ans.len() == len {
                    ans.push(c);
                    pos = npos;
                    break;
                }
            }
        }
        for &c in ans.iter() {
            let v = (c as u8 + 'a' as u8) as char;
            print!("{}", v);
        }
        println!("");
    }
}

fn main() {
    let mut solver = Solver::new();
    solver.solve();
}


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

  int money;
  cin >> money;

  int i = money/500;
  int j = (money - 500*i)/5;
  
  int happy = 1000*i + 5*j;
  
  cout << happy << endl;
}

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

int main() {
  int a;
  cin >> a;
  cout << a + pow(a, 2) + pow(a, 3) << endl;
}

Measured memory_bytes: 4292
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = 1LL << 60;

int main() {
	int N, K;
	cin >> N >> K;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int h;
		cin >> h;
		if (h >= K) ans++;
	}
	cout << ans << endl;
}

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

using namespace std;

struct Node{
  int p[100]={0}, d=-1, c[100], c_n;
};

Node nodes[101];

void search(int x){
    for(int i=0;i<nodes[x].c_n;++i){
        if(nodes[nodes[x].c[i]].d > nodes[x].d + 1 || nodes[nodes[x].c[i]].d == -1){
            nodes[nodes[x].c[i]].d = nodes[x].d + 1;
        }
    }
    
    for(int i=0;i<nodes[x].c_n;++i){
        if(nodes[nodes[x].c[i]].d == nodes[x].d + 1){
            search(nodes[x].c[i]);
        }
    }
    return;
}

int main(){
    int n, num, child;
    cin >> n;
    
    
    
    for(int i=1;i<=n;++i){
        cin >> num;
        
        if(num == 1){
            nodes[num].d=0;
        }
        
        cin >> nodes[num].c_n;
        for(int j=0;j<nodes[num].c_n;++j){
            cin >> nodes[num].c[j];
        }
    }
    
    search(1);
    
    for(int i=1;i<=n;++i){
        cout << i << " " << nodes[i].d << endl;
    }
    
    
    return 0;
}


Measured memory_bytes: 3168
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int A = sc.nextInt();
   Integer[] not = {1,2,3,5,6,9,10,13,17};
   if(Arrays.asList(not).contains(A)) System.out.println("No");
   else System.out.println("Yes");
 }
}

Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;

namespace ABC099
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> list = new List<string>();
            while (true)
            {
                string line = Console.ReadLine();
                if (line == null) break;
                list.Add(line);
            }

            int ans = int.Parse(list[0]);

            var a = list[0].First();
            if (list[0].First().Equals(list[0].Last())&& list[0].First().ToString().Equals(list[0].Substring(1,1)))
            {
                Console.WriteLine(list[0]);
            }
            else if (ans < 111)
            {
                Console.WriteLine("111");
            }
            else if (ans < 222)
            {
                Console.WriteLine("222");
            }
            else if (ans < 333)
            {
                Console.WriteLine("333");
            }
            else if (ans < 444)
            {
                Console.WriteLine("444");
            }
            else if (ans < 555)
            {
                Console.WriteLine("555");
            }
            else if (ans < 666)
            {
                Console.WriteLine("666");
            }
            else if (ans < 777)
            {
                Console.WriteLine("777");
            }
            else if (ans < 888)
            {
                Console.WriteLine("888");
            }
            else if (ans < 999)
            {
                Console.WriteLine("999");
            }
        }
    }
}


Measured memory_bytes: 13268
import sys
sys.setrecursionlimit(10**4)

inf = float('inf')

# 計算量O(VE) V:頂点数, E:辺の数
# True - >正常に更新, False -> startからendまでの経路において負閉路有り
def bellmanford(start, end):
    global dist
    dist = [inf] * N
    dist[start] = 0
    # 頂点数Nなら更新は高々N-1回で済む
    for _ in range(N-1):
        for v ,nv, w in edges:
            if dist[nv] > dist[v] + w:
                dist[nv] = dist[v] + w
    # 負閉路の検出部分
    # N回目で更新があった場合、負閉路を含む
    for v, nv, w in edges:
        if dist[nv] > dist[v] + w:
            return False
    return True

def dfs(v, ad):
    visited[v] = True
    for nv in ad[v]:
        if not visited[nv]:
            dfs(nv, ad)

N, M, P = map(int,input().split())
to = [[] for _ in range(N)]
fr = [[] for _ in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    C -= P
    C *= -1
    to[A].append(B)
    fr[B].append(A)
    edges.append((A, B, C))

visited = [False] * N

dfs(0, to)
tmp = visited[:]
visited = [False] * N
dfs(N-1, fr)
visited = [a and b for a, b in zip(tmp, visited)]
edges = [(v, nv, w) for v, nv, w in edges if visited[v] and visited[nv]]

flag = bellmanford(0, N-1)
ans = max(-dist[N-1], 0) if flag else -1
print(ans)

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

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

    long long k, a, b, ans = 0;
    cin >> k >> a >> b;
    if(b - a >= 2){
        int cnt = a - 1;
        if(k < cnt){
            ans = k + 1;
        }else{
            k -= cnt;
            ans += a;
            ans += (k / 2) * (b - a);
            ans += k % 2;
        }
    }else{
        ans = k + 1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
void main() {
	auto K = ri;
	dchar[] genarr(dchar c) {
		if(c == '0') return ['0', '1'];
		if(c == '9') return ['8', '9'];
		else return [c-1, c, c+1];
	}
	dstring[] arr = ["1", "2", "3", "4", "5", "6", "7", "8", "9"];

	bool comp(dstring a, dstring b) {
		if(a.length < b.length) return true;
		else if(a.length > b.length) return false;
		else return a < b;
	}
	
	while(arr.length < 100001) {
		dstring[] tmparr;
		foreach(d; arr) {
			auto T = genarr(d.back);
			foreach(t; T) {
				tmparr ~= (d ~ t);
			}
		}
		arr ~= tmparr;
		arr = arr.sort!(comp)().uniq.array;
	}
	arr[K-1].writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 39224
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()   //reverse
#define strall(v) (v).cbegin(),(v).cend() //const_itterator
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
const int INF = 1e8;

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int cnt = 0;
  while(1){
    if(cnt % 2 == 0) c-=b;
    else a-=d;
    cnt++;
    if(a <= 0 || c <= 0) break;
  }
  if(a > c) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3596
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    int n; cin >> n;
    int a[100001]; INITA(a, 0, 100000, 0);
    bool visited[100001]; INITA(visited, 0, 100000, false);
    REP(i, n) {
        cin >> a[i+1];
    }
    int current = 1;
    int res = 0;
    while (true) {
        int next = a[current];
        if (!visited[next]) {
            current = next;
            visited[next] = true;
            res++;
        } else {
            break;
        }
        if (next == 2) {
            cout << res << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,i,j,b = 1,ans = -100000000000,now;cin >> n;
  long long f[n][10],p[n][11];
  for(i=0;i<n;i++){
    for(j=0;j<10;j++) cin >> f[i][j];
  }
  for(i=0;i<n;i++){
    for(j=0;j<11;j++) cin >> p[i][j];
  }
  while(b<1024){
    long long s[n] = {};
    for(i=0;i<10;i++){
      if(b&(1<<i)){
        for(j=0;j<n;j++) s[j] += f[j][i];
      }
    }
    now = 0;
    for(i=0;i<n;i++) now += p[i][s[i]];
    ans = max(ans,now);
    b++;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
N, A, B, C = map(int, input().split())
state = {'A':A, 'B':B, 'C':C}
ans = []
if A+B+C >= 3 or A+B+C == 1:
    for _ in range(N):
        s = input()
        if state[s[0]] == 0 and state[s[1]] == 0:
            print('No')
            exit()
        elif state[s[0]] >= state[s[1]]:
            ans.append(s[1])
            state[s[0]] -= 1
            state[s[1]] += 1
        else:
            ans.append(s[0])
            state[s[0]] += 1
            state[s[1]] -= 1
elif A+B+C == 2:
    sn = 0
    for i in range(N):
        if sn != 0:
            s = sn
            sn = 0
        else:   
            s = input()
        if state[s[0]] == 0 and state[s[1]] == 0:
            print('No')
            exit()
        elif state[s[0]] == state[s[1]]:
            if i == N-1:
                ans.append(s[1])
                state[s[0]] -= 1
                state[s[1]] += 1
            else:
                sn = input()
                if s[0] in sn:
                    ans.append(s[0])
                    state[s[0]] += 1
                    state[s[1]] -= 1
                else:
                    ans.append(s[1])
                    state[s[0]] -= 1
                    state[s[1]] += 1
        elif state[s[0]] > state[s[1]]:
            ans.append(s[1])
            state[s[0]] -= 1
            state[s[1]] += 1
        else:
            ans.append(s[0])
            state[s[0]] += 1
            state[s[1]] -= 1
else:
    print('No')
    exit()

print('Yes')
for i in range(N):
    print(ans[i])         


Measured memory_bytes: 9960
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n = int(input())
MOD = 10 ** 9 + 7

factorial = [0] * (n+1)
factorial[0] = 1
for i in range(1, n+1):
    factorial[i] = (factorial[i-1] * i)

n = factorial[n]
prime_factors = []
i = 2
while i ** 2 <= n:
    ext = 0
    while n % i == 0:
        ext += 1
        n //= i
    if ext:
        prime_factors.append((i, ext))
    i += 1
if n != 1:
    prime_factors.append((n, 1))

ans = 1
for pf, num in prime_factors:
    ans = (ans * (num + 1)) % MOD
print(ans)


Measured memory_bytes: 67800
from itertools import *
from collections import *
from math import *
def qrime():
  p = [2, 3, 5, 7]
  yield from p
  q = [i for i in range(1, 210, 2) if 0 not in (i%3, i%5, i%7)]
  yield from q[1:]
  for i in count(210, 210):
    for j in q:
      yield i + j

def factor(n):
  limit = int(sqrt(n))
  p = Counter()
  for q in qrime():
    if n == 1 or q > limit:
      break
    while n % q ==0:
      p[q] += 1
      n //= q
      limit = int(sqrt(n))
  if n != 1:
    p[n] += 1
  return p

def divisor(n):
  f = factor(n)
  p, m = zip(*f.items())
  for c in product(*map(lambda x:range(x+1), m)):
    if sum(c) == 0:
      continue
    C = 1
    for a, b in zip(p, c):
      C *= pow(a, b)
    yield C

ans = 0
N = int(input())
for d in divisor(N):
  n = N
  while n % d == 0:
    n //= d
  if n % d == 1:
    ans += 1

f = factor(N-1)
ans2 = 1
for c in f.values():
  ans2 *= c+1

print(ans + ans2 - 1)

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

int N;
int A[100002];
// B[i]: A[i]とA[i-1]の距離
int B[100002];
// C[i]: A[i]を消すことでどれだけ距離が減るか
int C[100002] = {0};

int main() {
  long long sum = 0;

  scanf("%d", &N);
  A[0] = 0;
  for(int i = 1; i < N + 1; ++i) {
    scanf("%d", &A[i]);
    B[i] = abs(A[i] - A[i-1]);
    sum += B[i];
  }
  A[N+1] = 0;
  B[N+1] = abs(A[N+1] - A[N]);
  sum += B[N+1];

  for (int i = 1; i < N + 1; ++i) {
    printf("%lld\n", sum - (B[i] + B[i+1]) + abs(A[i+1] - A[i-1]));
  }
  return 0;
}

Measured memory_bytes: 2048
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s=sc.next();
		char ca[]=s.toCharArray();
		int a=Character.getNumericValue(ca[0]);
		int b=Character.getNumericValue(ca[1]);
		int c=Character.getNumericValue(ca[2]);
		int d=Character.getNumericValue(ca[3]);
		if (a + b + c + d == 7) {
			System.out.println(a + "+" + b + "+" + c + "+" + d + "=7");
		} else if (a + b + c - d == 7) {
			System.out.println(a + "+" + b + "+" + c + "-" + d + "=7");
		} else if (a + b - c + d == 7) {
			System.out.println(a + "+" + b + "-" + c + "+" + d + "=7");
		} else if (a + b - c - d == 7) {
			System.out.println(a + "+" + b + "-" + c + "-" + d + "=7");
		} else if (a - b + c + d == 7) {
			System.out.println(a + "-" + b + "+" + c + "+" + d + "=7");
		} else if (a - b + c - d == 7) {
			System.out.println(a + "-" + b + "+" + c + "-" + d + "=7");
		} else if (a - b - c + d == 7) {
			System.out.println(a + "-" + b + "-" + c + "+" + d + "=7");
		} else if (a - b - c - d == 7) {
			System.out.println(a + "-" + b + "-" + c + "-" + d + "=7");
		}

	}

}

Measured memory_bytes: 22736
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std ;
template< class T > inl T read() {
	T x = 0 ; int f = 1 ; char k = getchar() ;
	for( ; k > '9' || k < '0'; k = getchar() ) if( k == '-' ) f = -1 ;
	for( ; k >= '0' && k <= '9'; k = getchar() ) x = x * 10 + k - '0' ;
	return x * f ;
}
template< class T > inl T read( T &x ) { return x = read<T>() ; }
int _num, _buf[20];
template< class T > il print( T x ) {
   	if( x == 0 ) return putchar( '0' ) ,void() ;
	if( x < 0 ) putchar( '-' ), x = -x ;
	while( x ) _buf[++_num] = x % 10, x /= 10 ;
	while( _num ) putchar( _buf[_num--] + '0' ) ;
}
ll mul( ll a, ll b, ll mod ) { long double c = 1. ; return ( a * b - (ll)( c * a * b / mod ) * mod ) % mod ; }
it qpow( int x, int m, int mod ) {
	int res = 1, bas = x ;
	while(m) {
		if( m & 1 ) res = ( 1ll * res * bas ) % mod ;
		bas = ( 1ll * bas * bas ) % mod, m >>= 1 ;
	}
	return res ;
}
int n, ans;
it phi( int n ) {
	int res = n ;
	for( ri i = 2; i * i <= n; ++i ) {
		if( n % i )
		 	continue ;
		while( n % i == 0 )
			n /= i ;
		res = res / i * ( i - 1 ) ;
	}
	if( n > 1 )
		res = res / n * ( n - 1 ) ;
	return res ;
}
int main() {
//	freopen( ".in", "r", stdin ) ;
//	freopen( ".out", "w", stdout ) ;
	n = read<int>() ;
	n = n / __gcd( n, 7 ) * 9 ;
	int m = phi( n ) ;
	ans = INF ;
	for( ri i = 1; i * i <= m; ++i ) {
		if( m % i )
			continue ;
		if( qpow( 10, i, n ) == 1 )
			ans = std::min( ans, i ) ;
		if( qpow( 10, m / i, n ) == 1 )
			ans = std::min( ans, m / i ) ;
	}
	if( ans == INF )
		puts( "-1" ) ;
	else
		print( ans ), puts( "" ) ;
	cerr << 1. * clock() / CLOCKS_PER_SEC << "\n" ;
	return 0;
}

Measured memory_bytes: 3776
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a == 0 && b == 0){
			return;
		}
		while (true) {
			boolean f = true;
			for (int i = a; i <= b; i++) {
				if (i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) {
					f = false;
					System.out.println(i);
				}
			}
			if(f)System.out.println("NA");
			a = sc.nextInt();
			b = sc.nextInt();
			if (a == 0 && b == 0) {
				break;
			} else {
				System.out.println();
			}
		}
	}
}

Measured memory_bytes: 12000
let main = (standardInput) => {
    let asa = standardInput.split(' ');
    let a = Number.parseInt(asa[0]);
    let b = Number.parseInt(asa[1]);
    let c = Number.parseInt(asa[2]);
　　let kawaiihito=0;
　　let kawaiihito2=0;

if(a>b){
   kawaiihito=a;
   kawaiihito2=b;
   a=kawaiihito2; 
   b=kawaiihito;
}
if(b>c){
   kawaiihito=b;
   kawaiihito2=c;
   b=kawaiihito2;
   c=kawaiihito;
}
if(a>b){
    kawaiihito=a;
    kawaiihito2=b;
    a=kawaiihito2;
    b=kawaiihito;
}
console.log(a+' '+b+' '+c);
}
main(require('fs').readFileSync('/dev/stdin', 'UTF-8'));


Measured memory_bytes: 15140
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iomanip>


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define shandom_ruffle random_shuffle

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001; //check the limits, dummy


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << std::setprecision(9);
    cout << std::fixed;

    ll n;cin >>n;
    vl six;
    vl nine;
    ll temp = 6;
    while(temp <= n){
      six.pb(temp);
      temp*=6;
    }
    temp=9;
    while(temp <= n){
      nine.pb(temp);
      temp*=9;
    }
    ll a[n+2];
    a[1] = 1;
    FOR(i,2,n+1){
        ll ans = INF;
        if(find(six.begin(),six.end(),i) != six.end())
        {
          a[i] = 1; continue;
        }
        if(find(nine.begin(),nine.end(),i) != nine.end())
        {
          a[i] = 1; continue;
        }
        F0R(j,sz(six)){
          if(i > six[j])
            if(ans > a[i-six[j]] + 1) ans = a[i-six[j]] + 1;
        }
        F0R(j,sz(nine)){
          if(i > nine[j])
            if(ans > a[i-nine[j]] + 1) ans = a[i-nine[j]] + 1;
        }
        if(ans > a[i-1] +1) ans = a[i-1]+1;
        a[i] = ans;
    }
    cout << a[n] << endl;
    return 0;
}

// read the question correctly (ll vs int)
// template by super1 derived from bqi343


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

typedef long long int  ll;

const ll mod = 1e9+7;
const int N = 1e4+7, D = 111;

ll dp[N][D];

ll solve(string& s, int d)
{
  ll res = 0, curmod = 0;
  for(int i=0;i<(int)s.size();++i)
  {
    for(int j=0;j<s[i]-'0';++j)
    {
      res = (res  + dp[s.size() - i - 1][(0 + d - (curmod + j) % d) % d]) % mod;
    }
    curmod += s[i]-'0';
    curmod %= d;
  }
  if(curmod == 0) ++res;
  return res;
}

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  
  
  string k; int d;
  cin >> k >> d;
  
  int n = k.size();
  dp[0][0] = 1;
  for(int i=0;i<n;++i)
  {
    for(int j=0;j<d;++j)
      for(int l=0;l<10;++l)
        dp[i+1][(j+l)%d] = (dp[i+1][(j+l)%d] + dp[i][j]) % mod;
  }
  
  
  cout << (solve(k, d) + mod - 1) % mod << endl;
  
  return 0;
}


Measured memory_bytes: 8960
/*author* Priyanshu Shrivastav (from IIT Palakkad) *
 * *_ __ ___  _ ______ ___  _ ____   ___  ___| |_  *
 * | '_ ` _ \| '__/ __/ _ \| '_ \ \ / / |/ __| __| *
 * | | | | | | | | (_| (_) | | | \ V /| | (__| |_  *
 * |_| |_| |_|_|(_)___\___/|_| |_|\_/ |_|\___|\__| *
When I wrote this, only God and I understood what I was doing
 ** * * * * * * * Now, only God knows * * * * * * */
#include         <bits/stdc++.h>
using namespace std;
#ifndef CONVICTION
#pragma GCC      optimize ("Ofast")
#pragma GCC      optimize ("unroll-loops")
#pragma GCC      target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif

#define IOS      ios_base::sync_with_stdio(false); cin.tie (nullptr)
#define PREC     cout.precision (10); cout << fixed
#define bg(x)    " [ " << #x << " : " << (x) << " ] "
#define x        first
#define y        second
using ll = long long;
using ff = long double;
using pii = pair<int,int>;

#define debug(args...) { \
   /* WARNING : do NOT compile this debug func calls with following flags: // \
    * // -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -D_FORTIFY_SOURCE=2*/ \
   string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
   stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); \
}
void err(istream_iterator<string> it) { it->empty();
   cerr << " (Line : " << __LINE__ << ")" << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
   cerr << fixed << setprecision(15) << " [ " <<  *it << " : " << a  << " ] "<< ' ';
   err(++it, args...);
}

const int N = (int)1e4 + 10, S = 104;
const int MOD = (int)1e9 + 7;

int dp[N][S][2];
int n, d;
string s;

inline int add (int a, int b) {
   return (a + b)%MOD;
}

// dp[pos][sum][false] := till pos, digits used are upto max limits(i.e. forming highest number)
//  // // // has to come from false
// dp[pos][sum][true] := till pos, digits used are such they are less than the limits
// // // // can come from both false and true

void solve() {
   n = (int)s.size();
   s = ' ' + s;

   for (int dg = 0; dg < s[1] - '0'; ++dg)
      dp[1][dg % d][true] += 1;

   dp[1][(s[1] - '0')%d][false] += 1;

   // or equivalent base case : dp[0][0][0] = 1 // and start dp from pos = 1

   for (int pos = 2; pos <= n; ++pos) {
      for (int rem = 0; rem < d; ++rem) {
         for (bool les : {false, true}) {
            int mx_digit = 9;
            if (!les)
            {
               mx_digit = s[pos] - '0';
            }
            for (int dg = 0; dg <= mx_digit; ++dg) {
               bool is_les = (les || (dg < s[pos] - '0'));
               dp[pos][(rem + dg) % d][is_les] =
                  add(dp[pos][(rem + dg) % d][is_les], dp[pos - 1][rem][les]);
            }
         }
      }
   }
   cout << (dp[n][0][0] + dp[n][0][1] - 1 + MOD) % MOD << '\n';
}

signed main() {
   IOS; PREC;
   cin >> s >> d;
   solve();

   return EXIT_SUCCESS;
}


Measured memory_bytes: 8448
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <deque>

using namespace std;

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

	int n;
	int l[11];

	int maxv = 0;
	int sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l[i];
		sum += l[i];
		if (l[i] > maxv)  maxv = l[i];
	}

	if (maxv < sum - maxv) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

Measured memory_bytes: 256
/* ＵＴＦ－８ */
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

long gcd(long a, long b)
{
	while (b != 0) {
		a %= b;
		std::swap(a, b);
	}
	return a;
}

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	long A, B;
	std::cin >> A >> B;
	
	std::cout << (A / gcd(A, B) * B) << "\n";
}


Measured memory_bytes: 256