akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;
using System.Collections.Generic;

namespace AtCoder.DP
{
    class EDPC_J
    {
        public static void Main()
        {
            var n = int.Parse(Console.ReadLine());
            var a = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();

            var m = new int[3];
            for (int i = 0; i < a.Length; i++)
                m[a[i] - 1]++;


            var dp = new double[m[2] + 1, m[1] + m[2] + 1, n + 1];

            for (int i = 0; i <= m[2]; i++)
            {
                for (int j = 0; j <= m[1] + m[2] - i; j++)
                {
                    for (int k = 0; k <= n - i - j; k++)
                    {
                        if (i + j + k == 0)
                        {
                            dp[i, j, k] = 0;
                            continue;
                        }

                        dp[i, j, k] = n;
                        if (i > 0)
                            dp[i, j, k] += dp[i - 1, j + 1, k] * i;
                        if (j > 0)
                            dp[i, j, k] += dp[i, j - 1, k + 1] * j;
                        if (k > 0)
                            dp[i, j, k] += dp[i, j, k - 1] * k;
                        dp[i, j, k] /= i + j + k;
                    }
                }
            }
            Console.WriteLine(dp[m[2], m[1], m[0]]);
        }
    }
}


Measured memory_bytes: 226144
//by xxj
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int inf=1e9+7;
const ll linf=1e18+7;
const ll hh=523;
const int mod=998244353;
int main(){
	int R;
	cin>>R;
	if (R<1200){
		cout<<"ABC"<<endl;
	}
	else if(R<2800){
		cout<<"ARC"<<endl;
	}
	else{
		cout<<"AGC"<<endl;
	}
	return 0;
}


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

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

  int S1 = S/100, S2 = S % 100;

  if(1 <= S1  && S1 <= 12){
    if(1 <= S2 && S2 <= 12){
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;
    }
  } else {
    if(1 <= S2 && S2 <= 12){
      cout << "YYMM" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
} 

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char a[105],flag;
int main()
{
	cin>>a;
	flag=0;
	for(int i=0;i<strlen(a);i++)
	{
		if(a[i]=='C') flag=1;
		if(a[i]=='F'&&flag==1)
		{
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
import collections
import copy
N = int(input())
D = [int(i) for i in input().split()]

C = collections.Counter(D)
if C.most_common()[0][1] >= 3:
    print(0)
    exit()

D1 = [0, 24]
m = []
for k, v in C.items():
    if v == 2:
        D1.append(k)
        D1.append(24-k)
    elif v == 1:
        m.append(k)

ans = 0
for i in range(2 ** len(m)):
    D0 = copy.deepcopy(D1)
    for j in range(len(m)):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            D0.append(24-m[j])
        else:
            D0.append(m[j])

    # print(D0)

    D0 = sorted(D0)
    c = 24
    for i in range(N+1):
        c = min(c, D0[i+1]-D0[i])
    ans = max(ans, c)

print(ans)


Measured memory_bytes: 43632
# coding: utf-8

import sys
import math
import collections
import itertools
from inspect import currentframe
INF = 10 ** 10
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def MI() : return map(int, input().split())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def chkprint(*args) : names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}; print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))


L = I()

ll = L/3

print(ll ** 3)

Measured memory_bytes: 43376
#include <bits/stdc++.h>
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define foreach(i,n) for(auto &&i:n)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REV(x) reverse(all(x))
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define LOWitr(x, n) lower_bound(all(x), n)
#define UPRitr(x, n) upper_bound(all(x), n)
#define cii(x) int x;cin >> x
#define cill(x) LL x;cin >> x
#define cis(x) string x;cin >> x
#define co(x) cout << x << endl
#define dump(x)  cout << #x << " = " << (x) << endl
#define truecheck assert
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef long long int64;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
template<class T,class U>bool chmax(T &a, const U &b) { if (a<b) { a=b; return true; } return false; }
template<class T,class U>bool chmin(T &a, const U &b) { if (b<a) { a=b; return true; } return false; }
const int INF = 1e9, MOD = 1e9 + 7;
const LL LLINF = 1e16;

int main() {
    fastcin();
    cout << fixed << setprecision(10);
    cill(a);
    cill(b);
    cill(k);
    LL aa = a <= k
            ?0
            :a - k;
    LL bb = a - k >= 0
            ?b
            :max(b - (k - a), (LL)0);
    cout << aa << " " << bb;
    return 0;
}

Measured memory_bytes: 256
N,H = map(int,input().split())
A = []
B = []
for _ in range(N):
    a,b = map(int,input().split())          
    A.append(a)    
    B.append(b)    
    
A_max = max(A)      
B.sort(reverse=True)
B_sum = [0]
for b in B:
    if b<=A_max:
        break
    B_sum.append(B_sum[-1]+b)

ans = 10**10
for i in range(len(B_sum)):
    ans_tmp = i
    if B_sum[i]<H:
        ans_tmp += (H-B_sum[i]+A_max-1)//A_max
    ans = min(ans,ans_tmp)
print(ans)


Measured memory_bytes: 68440
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AOJALDS11A
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var strlist = new List<string>();
            strlist.AddRange(Console.ReadLine().Split(' ').ToList());
            var numlist = strlist.ConvertAll(int.Parse);

            for (var i = 0; i < n; i++)
            {
                var v = numlist[i];
                var j = i - 1;
                while (j >= 0 && numlist[j] > v)
                {
                    numlist[j + 1] = numlist[j];
                    j--;
                }
                numlist[j + 1] = v;

                for (int k = 0; k < n; k++)
                {
                    Console.Write("{0}", numlist[k]);
                    if (k != n - 1)
                        Console.Write(" ");
                    else
                    {
                        Console.WriteLine();
                    }
                }
            }
            Console.ReadLine();
        }
    }
}



Measured memory_bytes: 18240
// Problem : D - Chat in a Circle
// Contest : AtCoder - AtCoder Beginner Contest 173
// URL : https://atcoder.jp/contests/abc173/tasks/abc173_d
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<long,long> pl;
typedef pair<ll,ll> pll;
typedef vector<long> vl;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef unordered_map<ll,ll> umll;

#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define REV(i,a,b) for(long long i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define tc ll tests;cin>>tests;while(tests--)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
#define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
#define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
#define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
#define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define newl cout<<"\n"
#define mod 1000000007
#define INF LLONG_MAX/2

int main()
{
    io;
    ll n,ans=0;
    cin>>n;
    cinv(a,n)
    sort(rall(a));
    ans=a[0];//largest
    FOR(i,3,n+1)
    {
    	if(i&1){ans+=a[i/2];}
    	else{ans+=a[i/2-1];}
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 4776
#-*-coding:utf-8-*-

def main():
    n, m, x, y = map(int, input().split())
    x_list = list(map(int, input().split()))
    y_list = list(map(int, input().split()))
    for z in range(x + 1, y+1):
        if all(x < z for x in x_list) and all(y >= z for y in y_list):
            print('No War')
            exit()
    print('War')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>

using namespace std;
//累乗(繰り返し2乗法)　aのb乗(mod)を求める。


int main()
{
	string str,str2;
	long long int n, m, a, b,c;
	const long long int mod = 1000000007;
	cin >>str>>str2 ;
	for (int i = 0; i < str2.length() ; i++) {
		cout << str[i] << str2[i];
	}
	if (str.length() > str2.length()) {
		cout << str[str.length() - 1];
	}
}


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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
//constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int X, Y;
  cin >> X >> Y;
  bool flag = false;
  REP(i, 500){
    REP(j, 500){
      if(i+j==X && i*2+j*4==Y){
        flag = true;
      }
    }
  }
  if(flag){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3556
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.UncheckedIOException;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args) {
		SC sc=new SC(System.in);
		while(true) {
			int target=sc.nextInt();
			int point=sc.nextInt();
			if(target*point==0) {
				System.exit(0);
			}
			int[] score=new int[target*(target+3)/2+1];
			score[0]=0;
			for(int i=0; i<target; i++) {
				score[i+1]=sc.nextInt();
			}
			int counter=target+1;
			for(int i=1; i<=target; i++) {
				for(int j=1; j<=target; j++) {
					if(i<=j) {
						score[counter]=score[i]+score[j];
						counter++;
					}
				}
			}
			Arrays.sort(score);
			int max=0;
			for(int i=0; i<=target*(target+3)/2; i++) {
				int tmp=lowerBound(score,point-score[i]);
				if(point-score[i]>=0) {
					if(tmp==-1) {
						max=Math.max(max, score[i]+score[target*(target+3)/2]);
					}
					else if(score[i]+score[tmp]==point){
						max=Math.max(max, score[i]+score[tmp]);
					}
					else if(tmp>0 && score[i]+score[tmp]>point) {
						max=Math.max(max, score[i]+score[tmp-1]);
					}
					else if(tmp==0) {
						max=Math.max(max, score[i]);
					}
				}
				else {
					//
				}
			}
			pl(max);
		}
	}
	static class SC {
		private BufferedReader reader = null;
		private StringTokenizer tokenizer = null;
		public SC(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public String next() {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static void pl(Object o) {
		System.out.println(o);
	}
	public static void pl() {
		System.out.println();
	}
	public static void p(Object o) {
		System.out.print(o);
	}
	public static final int lowerBound(final int[] arr, final int value) {
		int low = 0;
		int high = arr.length;
		int mid;
		while (low < high) {
			mid = (high+low)/2;
			if (arr[mid] < value) {
				low = mid + 1;
			} else {
				high = mid;
			}
		}
		if(low<arr.length) {
			return low;
		}
		else {
			return -1;
		}
	}
}


Measured memory_bytes: 54352
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, x, sum=0, count1=0, i;
    cin >> n >> x;
    int arr[n];


    for(i=0; i<n; i++)
    {
        cin >> arr[i];
        sum = sum + arr[i];

        if(sum <= x)
        {
            count1++;
        }
    }

    cout<< count1+1;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
	int N;
	int x[100000];
	int y[100000];
	int t[100000];
	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%d %d %d", &t[i], &x[i], &y[i]);
	}

	int x0=0,y0=0,t0=0;
	for(int i=0;i<N;i++){
		int d = (x[i] - x0) + (y[i] - y0);
		int dt = t[i] - t0;
		dt -= d;
		if(dt<0 || dt%2!=0){
			printf("No\n");
			return 0;
		}
		t0 = t[i];
		x0 = x[i];
		y0 = y[i];
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 1280
def main():
    k, a, b = map(int, raw_input().split())
    biscuit = 1
    mon = 0
    if b - a <= 2:
        print 1 + k
        return
    if biscuit < a:
        if k < a - biscuit:
            print 1 + k
            return
        k -= a - biscuit
        biscuit = a
    print biscuit + (b - a) * (k / 2) + k % 2


if __name__ == '__main__':
    main()


Measured memory_bytes: 28012
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int ans = 999;
        
        for(int i=0; i<str.length()-2; i++){
            String str2 = str.substring(i,i+3);
            int N = Integer.parseInt(str2);
            //System.out.println(N);
            if(ans > Math.abs(753-N)){
                ans = Math.abs(753-N);
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    int count = 0;
    for (int i = 1; i <= N; i++)
    {
        string s = to_string(i);
        if(s.size()%2 == 1) count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
# include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;

const ll mod=1000000007;

int main(){
  ll N,a;
  cin >> N;
  int res=0;
  int flag=1;
  for(ll i=1;i<=N;i++){
    cin >> a;
    if(flag==1 && a%2==1) res++;
    flag = -flag;
  }
  cout << res;
  return 0;
}

Measured memory_bytes: 3592
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
EPS = 10 ** -10

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

    def union(self, x, y):
        """ 併合 """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, M = MAP()
uf = UnionFind(N)
for i in range(M):
    a, b = MAP()
    a -= 1; b -= 1
    uf.union(a, b)

ans = 0
for i in range(N):
    ans = max(ans, uf.get_size(i))
print(ans)


Measured memory_bytes: 22056
def updiv(x,y):

    if x % y == 0:
        return x // y
    else:
        return x // y + 1

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

if abs(A-B) % 2 == 0:
    print (abs(A-B) // 2)

else:
    ans = updiv(A+B-2 , 2)

    ans = min (ans , updiv(2 * N - A - B , 2))

    print (ans)


Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main(){
	int n,k;
	vector<int> l;
	
	cin >> n >> k;
	l.resize(n);
	
	for(int i=0;i<n;i++){
		cin >> l[i];
	}
	
	sort(l.begin(), l.end());
	
	int length;
	for(int i=0;i<k;i++){
		length += l[n-i-1];
	}

	cout << length << endl;
	
	return 0;
}

Measured memory_bytes: 256
package main

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

var scan = bufio.NewScanner(os.Stdin)

func main() {
	scanWords()

	for {
		x := readNextInt()
		y := readNextInt()

		if x == 0 && y == 0 {
			break
		}

		if x > y {
			x, y = y, x
		}
		fmt.Printf("%d %d\n", x, y)
	}
}

func scanWords() {
	scan.Split(bufio.ScanWords)
}

func readNextInt() int {
	scan.Scan()

	input, err := strconv.Atoi(scan.Text())
	if err != nil {
		panic(err)
	}

	return input
}



Measured memory_bytes: 1148
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(int)(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) ((flag)?1:0)
#define YN(flag) cout<<(flag?"YES":"NO")<<endl;
#define Yn(flag) cout<<(flag?"Yes":"No")<<endl;
#define yn(flag) cout<<(flag?"yes":"no")<<endl;
#define Cout(v) cout<<(v)
#define COUT(v) cout<<(v)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

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

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

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

template<typename T>
istream &operator>>(istream &is, vector<T> &v){
  for(T &in:v) is>>in;
  return is;
}

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

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ===================
// Template End =========================

constexpr int MOD=1e9+7;
locale LOCATE=locale::classic();

int main(void){
  string s; cin>>s;
  pi ans=pi(-1,-1);
  for(int i=0; i<s.size()-2; ++i){
    if(s[i]==s[i+2]) ans=pi(i+1,i+3);
  }
  for(int i=0; i<s.size()-1; ++i){
    if(s[i]==s[i+1]) ans=pi(i+1,i+2);
  }
  COUT(ans);
}











Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}
// auto v = make_vec<int>(h, w);
// fill(v, 0);

signed main(){

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

  auto dp = make_vec<double>(n+1, n+1, n+1);
  fill(dp, -1);
  dp[0][0][0] = 0;
  function< double(int,int,int) > rec =
  [&](int a, int b, int c){
    if(dp[a][b][c] != -1) return dp[a][b][c];
    double E = 1.0 * n / (a + b + c);
    if(a > 0) E += rec(a-1, b, c) * a / (a + b + c);
    if(b > 0) E += rec(a+1, b-1, c) * b / (a + b + c);
    if(c > 0) E += rec(a, b+1, c-1) * c / (a + b + c);
    return dp[a][b][c] = E;
  };
  printf("%.9f\n",rec(cnt[1], cnt[2], cnt[3]));

  return 0;
}


Measured memory_bytes: 216960
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<numeric>
#include<list>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//最大公約数
template<class T> T gcd(T a, T b)
{
	while (true)
	{
		T r;
		if (a%b == 0) return b;
		else
		{
			r = a % b;
			a = b;
			b = r;
		}
	}
}
//最小公倍数
template<class T> T lcm(T a, T b)
{
	return a / gcd(a, b)*b;
}
//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//int型0~9を文字0~9に変換
char int_to_char(int c) {
	if (c == 0) return '0';
	if (c == 1) return '1';
	if (c == 2) return '2';
	if (c == 3) return '3';
	if (c == 4) return '4';
	if (c == 5) return '5';
	if (c == 6) return '6';
	if (c == 7) return '7';
	if (c == 8) return '8';
	if (c == 9) return '9';
	else return'x';
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn = 1, Kr = 1, Knr = 1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}
//int型10進数をord桁のstring型2進数に変換する
string binary(int x, int ord)
{
	int y;
	string ans = "";
	for (int i = 0; i < ord; i++)
	{
		y = x / (int)pow(2, ord - 1 - i);
		y %= 2;
		if (y == 0) ans += "0";
		else ans += "1";
	}

	return ans;
}
//ord桁のstring型2進数をint型10進数に変換する
int rep_binary(string x, int ord)
{
	int res = 0;
	for (int i = 0; i < ord; i++)
	{
		if (x[i] == '1') res += (int)pow(2, ord - 1 - i);
	}
	return res;
}
//xとyのビットごとの排他的論理和
template<class T> T XOR(T x, T y)
{
	T n = 0;
	while (max(x, y) > pow(2, n)) n++;
	T ans=0;
	for (int i = 0; i <= n; i++)
	{
		T x1 = (x % (T)pow(2, i + 1)) / (T)pow(2, i);
		T y1 = (y % (T)pow(2, i + 1)) / (T)pow(2, i);
		if (x1 != y1) ans += (T)pow(2, i);
	}
	return ans;
}

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



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

	int A[32] = { 1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51 };

	cout << A[K - 1] << endl;
	
		 
	return 0;
}

Measured memory_bytes: 256
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

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

  int Ns = S.length();
  int Nt = T.length();

  vector<vector<int> > dp(Ns + 1, vector<int>(Nt + 1, 0));

  for (int i = 1; i <= Ns; i++) {
    for (int j = 1; j <= Nt; j++) {
      if (S[i - 1] == T[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
      }
    }  // j
  }    // i

  string ans = "";
  int sp = Ns, tp = Nt;
  while (dp[sp][tp] > 0) {
    if (dp[sp][tp] == dp[sp - 1][tp]) {
      sp--;
    } else if (dp[sp][tp] == dp[sp][tp - 1]) {
      tp--;
    } else {
      ans = S[sp - 1] + ans;
      sp--;
      tp--;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 35584
operand = input().split()
stack = []
for op in operand:
    if op.isdigit():
        stack.append(op)
    else:
        val1 = stack.pop()
        val2 = stack.pop()
        stack.append(str(eval("("+val2+")" + op + "("+val1+")")))
print (stack[0])

Measured memory_bytes: 7492
n = int(input())
x = input()
mod_num1 = [0 for i in range(n+1)]
mod_num2 = [0 for i in range(n+1)]
mod_num3 = [0 for i in range(n+1)]
num2 = x.count('1')
if num2 == 0:
    for i in range(n):
        print(1)
    exit()
elif num2 == 1:
    index = x.index('1')
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            if index == n-1 or i == n-1:
                print(2)
            else:
                print(1)
    exit()
num1 = num2 - 1
num3 = num2 + 1
for i in range(n):
    if x[i] == '1':
        mod_num1[i] = pow(2, n-i-1 ,num1)
        mod_num2[i] = pow(2, n-i-1, num2)
        mod_num3[i] = pow(2, n-i-1, num3)
def popcount(num):
    res = 0
    while num != 0:
        res += 1
        num = num % "{:b}".format(num).count('1')
    return res
s_1 = sum(mod_num1)
s_2 = sum(mod_num2)
s_3 = sum(mod_num3)
for i in range(n):
    if x[i] == '1':
        print(popcount((s_1 - pow(2, n-i-1, num1)) % num1) + 1)
    else:
        print(popcount((s_3 + pow(2, n-i-1, num3)) % num3) + 1)




Measured memory_bytes: 97852
n = int(input())
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	k = (tvote-1)//t + 1
	tnow = t * k
	anow = a * k
	if avote > anow:
		k = (avote-1)//a + 1
		tnow = t * k
		anow = a * k
	tvote = tnow
	avote = anow
	
print(avote+tvote)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int OO = 0x3f3f3f3f3f3f3f3f;

int n, w, maxi;
int value[120], weight[120];
int dp[100040];

int32_t main()
{
	cin >> n >> w;
	for(int i = 0; i < n; i++)
		cin >> weight[i] >> value[i];
	// dp[i] = maximum total value of itens with total weight exactly
	for(int item = 0; item < n; item++)
		for(int cur_wei = w - weight[item]; cur_wei >= 0; cur_wei--)
			dp[cur_wei + weight[item]] = max(dp[cur_wei + weight[item]], dp[cur_wei] + value[item]);
	cout << *max_element(dp, dp + w + 1) << '\n';
	
	return 0;
}

Measured memory_bytes: 1024
class UnionFind
	def initialize
		@obj_to_node = {}
	end

	def add(obj)
		@obj_to_node[obj] ||= Node.new(obj)
	end

	def size(x = nil)
		x ? @obj_to_node[x].root.size : @obj_to_node.size
	end

	class Node
		def initialize(obj)
			@obj = obj
			@parent = self
			@size = 1
			@rank = 0
		end

		def root
			return self if @parent == self
			@parent = @parent.root
		end	

		attr_accessor :parent, :size, :rank
	end

	def union(x, y)
		u = (@obj_to_node[x] ||= Node.new(x)).root
		v = (@obj_to_node[y] ||= Node.new(y)).root
		return if u == v
		if u.rank > v.rank
			v.parent = u
			u.size += v.size
		elsif v.rank > u.rank
			u.parent = v
			v.size += u.size
		else
			u.parent = v
			v.rank += 1
			v.size += u.size
		end
	end

	def same?(x, y)
		return false unless u = @obj_to_node[x]
		return false unless v = @obj_to_node[y]
		u.root == v.root
	end
end

loop do
	n, m = gets.split.map(&:to_i) 
	break if n == 0
	uf = UnionFind.new
	edges = (1..m).map { gets.split.map(&:to_i) }.sort_by(&:last)
	k = 0
	edges.each do |i, j, c|
		next if uf.same?(i, j)
		uf.union(i, j)
		k += 1
		if k == n / 2
			puts c
			break
		end
	 end
end

Measured memory_bytes: 10208
#include<bits/stdc++.h>
//cervello|Phoenix
using namespace std;
#define ll long long int
#define eb emplace_back
#define mk make_pair
#define all(x) x.begin(),x.end()
#define mod 1000000007

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

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e3+5;
int a[N];

int main(){
    int n,k;ll sum=0;cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=0;i<k;i++)
        sum+=a[i];
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
int main(void){
	int n,m,i,j;
	int dp[100001],t[100001]={0};
	dp[0] = 1;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d",&j);
		t[j] = 1;
	}
	for(i=1;i<=n;i++){
		if(t[i] == 0){
			if(i>=2) dp[i] = dp[i-1] + dp[i-2];
			else if(i == 1) dp[i] = dp[i-1];
		}
		else dp[i] = 0;
		dp[i] %= 1000000007;
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 896
<?php
$s = trim(fgets(STDIN));

$h = (int)( $s / 3600);
$m = (int)(($s - $h * 3600) /60);
$l = $s - $h * 3600 - $m * 60; 
$out = $h . ":" . $m . ":" . $l;
echo $out;
?>

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


int main(void){
	int r,c;
	cin >> r >> c;
	int **a = new int*[r+1];
	for(int i = 0; i < r+1; i++ ){
		a[i] = new int[c+1];
	}
	for(int i = 0; i < r; i++ ){
		for(int j = 0; j < c; j++ ){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < r; i++ ){
		for(int j = 0; j < c; j++ ){
			a[i][c] += a[i][j];
		}
	}
	for(int j = 0; j < c; j++ ){
		for(int i = 0; i < r; i++ ){
			a[r][j] += a[i][j];
		}
	}
	for(int i = 0; i < r; i++ ){
		a[r][c] += a[i][c];
	}
	
	for(int i = 0; i < r+1; i++ ){
		for(int j = 0; j < c+1; j++ ){
			cout << a[i][j];
			if( j != c ) cout << " ";
			else cout << endl;
			
		}
	}
	
	
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = (l); i < (r); i++)
#define repb(i, r, l) for (int i = (r); i > (l); i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define rank qwertyuio
#define next dfghjk
#define prev fhsgfhjf
#define plus fsghsf
#define minus ytryr
  
using namespace std;
  
inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  
const int N = 100000;
const int inf = (int)1e9 + 1;
const ll big = (ll)1e18 + 1;
const int P = 239;
const int P1 = 31;
const int P2 = 57;
const int MOD = (int)1e9 + 7;
const int MOD1 = (int)1e9 + 9;
const int MOD2 = 998244353;
const ld eps = 1e-9;
const double pi = atan2(0, -1);
const int ABC = 26;
 
deque<int> next_good(deque<int> s) {
    int p = sz(s) - 1;
    while (p >= 0 && s[p] == 9) {
        s[p] = 0;
        p--;
    }
    if (p == -1) {
        s.push_front(1);
    } else {
        s[p]++;
    }
    while (true) {
        int b = -1;
        rep(i, 0, sz(s) - 1) {
            if (abs(s[i] - s[i + 1]) > 1) {
                b = i;
                break;
            }
        }
        if (b == -1) {
            break;
        }
        if (s[b + 1] > s[b]) {
            s[b]++;
        }
        int lll = max(s[b] - 1, 0);
        rep(i, b + 1, sz(s)) {
            s[i] = lll;
            lll = max(lll - 1, 0);
        }
    }
    return s;
}
 
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.precision(20);
    cout << fixed;

    int k;
    cin >> k;
    deque<int> ans = {0};
    rep(i, 0, k) {
        ans = next_good(ans);
    }
    for (int i : ans) {
        cout << i;
    }
    cout << "\n";
    return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cstdio>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int) n; i++)

int main() {
    string s; cin >> s;
    vector<int> cnt(26,0);
    rep(i,s.length()) {
        cnt[s[i]-'a']++;
    }
    rep(i,26) {
        if (cnt[i] % 2 != 0) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX_N 100000

typedef struct {
  char mark;
  int num;
  int idx;
} Card;

int n;
Card A[MAX_N];

void swap(Card *a, Card *b) {
  Card tmp = *a;
  *a = *b;
  *b = tmp;
}

int partition(int p, int r) {
  Card x = A[r];
  int i = p-1, j;
  for(j = p; j < r; j++) {
    if(A[j].num <= x.num) {
      i++;
      swap(&A[i], &A[j]);
    }
  }
  swap(&A[i+1], &A[r]);
  return i+1;
}

void quickSort(int p, int r) {
  if(p < r) {
    int q = partition(p, r);
    quickSort(p, q-1);
    quickSort(q+1, r);
  }
}

int main() {
  int i;

  scanf("%d", &n);
  for(i = 0; i < n; i++) {
    scanf(" %c %d", &A[i].mark, &A[i].num);
    A[i].idx = i;
  }
  quickSort(0, n-1);
  int flag = 1;
  for(i = 0; i < n-1; i++) {
    if(A[i].num == A[i+1].num && A[i].idx > A[i+1].idx) flag = 0;
  }
  puts((flag ? "Stable" : "Not stable"));
  for(i = 0; i < n; i++) {
    printf("%c %d\n", A[i].mark, A[i].num);
  }

  return 0;
}

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

 using namespace std;

 int main() {
   int i, j, k, N;
   vector<vector<int>> A(3, vector<int>(3));
   vector<vector<int>> BINGO(3, vector<int>(3));
   bool bingo;

   for (i = 0; i < 3; i++) {
     for (j = 0; j < 3; j++) {
       cin >> A.at(i).at(j);
     }
   }

   cin >> N;

   vector<int> b(N + 1);

   for (i = 1; i <= N; i++) cin >> b.at(i);

   for (i = 1; i <= N; i++) {
     for (j = 0; j < 3; j++) {
       for (k = 0; k < 3; k++) {
         if (b.at(i) == A.at(j).at(k)) BINGO.at(j).at(k) = 1;
       }
     }
   }

   bingo = false;

   for (i = 0; i < 3; i++) {
     if (BINGO.at(i).at(0) == 1 && BINGO.at(i).at(1) == 1 && BINGO.at(i).at(2) == 1) {
       bingo = true;
       break;
     }
   }

   for (i = 0; i < 3; i++) {
     if (BINGO.at(0).at(i) == 1 && BINGO.at(1).at(i) == 1 && BINGO.at(2).at(i) == 1) {
       bingo = true;
       break;
     }
   }

   if (BINGO.at(0).at(0) == 1 && BINGO.at(1).at(1) == 1 && BINGO.at(2).at(2) == 1) bingo = true;
   if (BINGO.at(0).at(2) == 1 && BINGO.at(1).at(1) == 1 && BINGO.at(2).at(0) == 1) bingo = true;

   if (bingo == true) cout << "Yes" << endl;
   else cout << "No" << endl;

 }


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

#define INF (1 << 30)
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define out(x) cout << x << endl;
#define all(x) (x).begin(),(x).end()
typedef long long ll;
using namespace std;

int main(){
    int a, b, x;
    cin >> a >> b >> x;
    if(a*a*b/2.0 >= x){
        double y, angle;
        y = (double)x/((double)b)/((double)a)*2.0;
        double cos = sqrt(y*y + b*b);
        double ac = acos(y/cos);
        printf("%f\n",ac/M_PI * 180.0);
    }else{
        double z, angle;
        x = a*a*b-x;
        z = (double)x/((double)a)/((double)a)*2.0;
        double cos = sqrt(z*z + a*a);
        double ac = acos(a/cos);
        printf("%f\n",ac/M_PI * 180.0);
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
 
using namespace std;
 
#define rep(i,n) for(int i=0; i<(n); i++)
#define repc(i,s,e) for(int i=(s); i<(e); i++)
#define pb(n) push_back((n))
#define mp(n,m) make_pair((n),(m))
#define all(r) r.begin(),r.end()
#define fi first
#define se second
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
 
const int INF = 10000000;
const int mod = 1e9 + 7;
const double EPS = 1e-9;
 

int main(){
	int n, k;
	while(cin >> n >> k){
		if(n == 0 && k == 0) break;
		vi v(n + 1, 0);
		vi u(k, 0);
		for(int i = 0; i < k; i++){
			cin>>u[i];
			v[u[i]]++;
		}
		vi s(n + 1, 0);
		s[0] = 0;
		for(int i = 1; i <= n; i++){
			if(v[i]) s[i] = s[i-1] + 1;
			//else s[i] = 0;
		}
		for(int i = n-1; i>0; i--){
			if(s[i+1]!= 0 && s[i] != 0) s[i] = s[i+1]; 
		}
		bool f = (v[0] == 1? true: false);
		int ans = 0;

		for(int i = 1; i <= n; i++){
			ans = max(ans, s[i]);
			if(f && i < n - 1 && s[i + 1] == 0) ans = max(ans, s[i] + s[i + 2] + 1);
		}

		cout<<ans<<endl;
	}
	
}

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

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
#define maxn 200005
using namespace std;
LL k;
LL i;
vector<LL>  v;
void dfs(LL be,LL en)
{
    for(int i=be;i<=en;i++)
    {
        LL last=v[i]%10;
        if(last>=1&&last<=8)
        {
            v.push_back(v[i]*10+last-1);
            v.push_back(v[i]*10+last);
            v.push_back(v[i]*10+last+1);
        }
        else if(last==0)
        {
            v.push_back(v[i]*10+last);
            v.push_back(v[i]*10+last+1);
        }
        else
        {
            v.push_back(v[i]*10+last-1);
            v.push_back(v[i]*10+last);
        }
         if(v.size()>=k)
        {
            cout<<v[k-1];
            return ;
        }
    }
    dfs(en+1,v.size()-1);
}
void slove()
{
    for(int i=1;i<=9;i++)
    {
       LL tmp=i;
       v.push_back(tmp);
       if(v.size()>=k)
        {
            cout<<v[k-1];
            return ;
        }
    }
    LL b=0,en=v.size()-1;
    dfs(b,en);
}

int main()
{
    cin>>k;
    i=0;
    v.clear();
    slove();
}



Measured memory_bytes: 1400
#include <bits/stdc++.h>
#include <variant>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x) begin(x),end(x)

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

using ld = long double;
using P = complex<ld>;

const ld pi = acos(-1.0);

vector<P> FFT(ld theta, const vector<P> &a) {
  const int n = a.size();
  vector<P> ret = a;
  for (int m = n; m >= 2; m >>= 1, theta *= 2) {
    REP(i,m/2) {
      for (int j = i; j < n; j += m) {
        int k = j + m / 2;
        P x = ret[j] - ret[k];
        ret[j] += ret[k];
        ret[k] = exp(i * theta * P(0, 1)) * x;
      }
    }
  }
  for (int i = 0, j = 1; j < n - 1; j++) {
    for (int k = n >> 1; k > (i ^= k); k >>= 1) {;}
    if (j < i) swap(ret[i], ret[j]);
  }
  return ret;
}

vector<ll> convolution(const vector<ll> &lhs, const vector<ll> &rhs) {
  int n = 1, a = lhs.size(), b = rhs.size();
  while (n < max(a, b) * 2) n <<= 1;
  vector<P> temp1(n), temp2(n);
  REP(i,n/2) {
    if (i < a) temp1[i] = P(lhs[i], 0);
    if (i < b) temp2[i] = P(rhs[i], 0);
  }
  temp1 = FFT(2.0 * pi / n, temp1);
  temp2 = FFT(2.0 * pi / n, temp2);
  REP(i,n) temp1[i] *= temp2[i];
  temp1 = FFT(-2.0 * pi / n, temp1);
  vector<ll> ret(n);
  REP(i,n) ret[i] = temp1[i].real() / n + 0.5;
  return ret;
}

ll powm(ll x, ll y, ll m) {
  if (y == 0) return 1;
  if (y % 2) return x * powm(x, y-1, m) % m;
  ll h = powm(x, y/2, m);
  return h * h % m;
}

constexpr ll MOD = 200003;

ll is_gen_200003(ll x) {
  vecll v = {2, 11, 9091};
  for (auto&&d: v) {
    if (powm(x, 200002 / d, MOD) == 1) return false;
  }
  return true;
}

ll get_gen_200003() {
  FOR(i,2,MOD-1) {
    if (is_gen_200003(i)) return i;
  }
  throw "ERROR";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin>>n;
  ll g = 2;//get_gen_200003();
  cerr<<g<<endl;
  map<int,int> mg;
  ll p = 1;
  REP(i,MOD-1) {
    mg.emplace(p, i);
    p *= g;
    p %= MOD;
  }
  vecll poly(MOD);
  ll self = 0;
  REP(i,n) {
    ll a;
    cin>>a;
    if(a == 0) continue;
    ++poly[mg[a]];
    self += a * a % MOD;
  }
  auto sq_poly = convolution(poly, poly);
  ll ans = 0;
  ll len = size(sq_poly);
  p = 1;
  REP(i,len) {
    ans += sq_poly[i] * p;
    p *= g;
    p %= MOD;
  }
  ans -= self;
  ans /= 2;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 63924
using System.Linq;
using System.Text;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;

namespace AtCoder
{
    class Program
    {

        const int BiggestMod = 998244353;

        public static void Main()
        {

            Console.ReadLine();

            var args = Console.ReadLine().Split(' ').Select(x => int.Parse(x) - 1);
            var memo = new int[100000];
            var ansbuf = 0L;
            var ans = new List<long>();

            for (int i = 0, l = memo.Length; i < l; i++)
                memo[i] = 0;

            foreach (var arg in args)
            {
                memo[arg]++;
                ansbuf += arg + 1;
            }

            var query = int.Parse(Console.ReadLine());

            for (int i = 0; i < query; i++)
            {

                var inner = Console.ReadLine().Split(' ').Select(x => int.Parse(x) - 1).ToArray();
                var buf = memo[inner[0]];

                memo[inner[0]] = 0;
                memo[inner[1]] += buf;

                ansbuf += ((inner[1] - inner[0]) * buf);
                ans.Add(ansbuf);
                
            }

            foreach (var answer in ans)
                Console.WriteLine(answer);

        }

    }

}

Measured memory_bytes: 46160
#include <cstdio>
using namespace std;

int main(){
	char str[25];
	
	for(int i = 0; i < 25; i++) str[i] = 0;
	
	scanf("%s", str);
	
	int p = 25;
	while(str[--p] == 0);
	while(p >= 0){
		printf("%c", str[p--]);
	}
	printf("\n");
	
	return 0;
}

Measured memory_bytes: 928
/*
貪欲
後ろから見る
DP
順位表をチェック
二分探索


*/
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include<tuple>
using namespace std;
#define INF 3e18+7
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<double,int> P;
//typedef pair<pair<int,int>,int> p;
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
struct edge{ll to,cost,val;};
template<class T,class U>bool chmin(T&a,const U&b){if(a<=b)return false;a=b;return true;}
template<class T,class U>bool chmax(T&a,const U&b){if(a>=b)return false;a=b;return true;}
//__builtin_popcount(S);
//C.erase(unique(C.begin(),C.end()),C.end());

bool dp[90][90][6500];

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

    int H,W,A[90][90],B[90][90];
    cin>>H>>W;
    for(int i=0;i<90;i++){
        for(int j=0;j<90;j++){
            for(int k=0;k<6500;k++){
                dp[i][j][k]=false;
            }
        }
    }

    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++) cin>>A[i][j];
    }
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++) cin>>B[i][j];
    }
    dp[1][1][abs(A[1][1]-B[1][1])]=true;
    //cout<<abs(A[2][1]-B[2][1])<<endl;
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            for(int k=0;k<=6400;k++){
                if(dp[i][j][k]==false) continue;;
                //cout<<i<<" "<<j<<" "<<k<<endl;
                if(i!=H){
                int x=abs(A[i+1][j]-B[i+1][j]);
                     dp[i+1][j][k+x]=true;
                     dp[i+1][j][abs(k-x)]=true;
                }
                if(j!=W){
                int x=abs(A[i][j+1]-B[i][j+1]);
                     dp[i][j+1][k+x]=true;
                     dp[i][j+1][abs(k-x)]=true;
                }
            }
        }
    }
    for(int i=0;i<=6400;i++){
        if(dp[H][W][i]){
            cout<<i<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 51712
#include <stdio.h>

int main(){
	
int l,r,d;
int a = 0;

scanf ("%d %d %d", &l,&r,&d);
for (int i = l; i <= r; i++){
	if (i % d == 0){
		a++;
	}
}
printf ("%d", a);
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    ll ans = ll(1e10) + 1;
    for(int i = 1; i <= 100; i++) {
        ll p = 0;
        rep(j,n) p += (x[j]-i)*(x[j]-i);
        ans = min(ans, p);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 500001

void maxHeapify(int);

int n;
int array[MAX];

int main(){
  int i;

  scanf("%d", &n);

  for( i=1; i<=n; i++){
    scanf("%d", &array[i]);
  }

  for( i=n/2; i>=1; i--){
    maxHeapify(i);
  }

  for( i=1; i<=n; i++){
    printf(" %d", array[i]);
  }
  printf("\n");

  return 0;
}

void maxHeapify( int num ){
  int left, right, large, tmp;

  left = num*2;
  right = num*2+1;

  if( left <= n && array[left] > array[num] ) large = left;
  else large = num;

  if( right <= n && array[right] > array[large] ) large = right;

  if( large != num ){
    tmp = array[num];
    array[num] = array[large];
    array[large] = tmp;
    maxHeapify(large);
  }

}

Measured memory_bytes: 2552