akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <assert.h>
#include <numeric>
#include <math.h>
#include <climits>
#include <stack>
#include <iomanip>
#include <sstream>

using namespace std;

template <typename T>
inline bool sign(T A) {
    return (A>0)-(A<0);
}
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SREP(i,s,n) for(int i=s; (n-i)*sign(n-s)>0; i+=sign(n-s))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef unsigned long long ull;

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

bool _less(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

template <template<class,class,class...> class C, typename K, typename V, typename... Args>
V map_get(const C<K,V,Args...>& m, K const& key, const V & defval)
{
    typename C<K,V,Args...>::const_iterator it = m.find( key );
    if (it == m.end())
        return defval;
    return it->second;
}

#define MOD (1'000'000'000+7)

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

    double cM = (-1 + sqrt(1 + 8 * N)) / 2;

    if (floor(cM) != cM) {
        cout << "No" << endl;
        return 0;
    }

    int M = cM;

    vector < vector<int>> c(M + 1, vector<int>(M));
    int b = 1;
    REP(i, M) {
        REP(j, M-i) {
            c[i][i + j] = b+j;
            c[i + j + 1][i] = b + j;
        }
        b += M - i;
    }
    cout << "Yes" << endl;
    cout << M + 1 << endl;
    REP(i, M+1)
    {
        cout << M << " ";
        REP(j, M){
            cout << c[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}


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

int main()
{
	long double a,v,b,w,t;
	cin>>a>>v>>b>>w>>t;


		if(v<=w)
		{
			cout<<"NO"<<endl;
			return 0;
		}
		else
		{
			long double itr=abs((b-a)/(v-w));
			if(t>=itr)
			{
				cout<<"YES"<<endl;
				return 0;
			}
			else
			{
				cout<<"NO"<<endl;
				return 0;
			}
		}
	

	return 0;
}


Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int main() {
    int n; cin >> n;
    string s; cin >> s;
    int left = 0;
    rep(i, n) {
        if(s[i]=='(') left++;
        else if(left>0) left--;
    }
    int right = 0;
    for(int i=n-1;i>=0;i--) {
        if(s[i]==')') right++;
        else if(right>0) right--;
    }
    rep(i, left) s = s + ')';
    rep(i, right) s = '(' + s;
    cout << s;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define plll pair<ll,pll>
#define ppll pair<pll, pll>
#define pii pair<int, int> 
#define pb push_back
#define mod 1000000007

ll power(ll a,ll b){
    ll res=1ll;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res%mod;
}
ll ncr(ll n,ll k){
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro)%mod;
}

void swap(ll *a,ll *b) {
    ll temp=*a;
    *a=*b;
    *b=temp;
}
vector<ll> prime;
void seive(){
    vector<bool > isprime(1000001,true);
    for(int i=2;i*i<=1000000;i++){
        if(isprime[i]){
            for(int j=i*i;j<=1000000;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
vector<ll> parent;
ll find(ll p) {
    if(parent[p]==p) return parent[p];
    return parent[p]=find(parent[p]); 
}
void unun(ll a,ll b) {
    ll r1=find(a);
    ll r2=find(b);
    if(r1!=r2) parent[r2]=r1;
}
vector<ll> visited;
vector<vector<ll>> adj;
int cycle,nodes,last;
vector<ll> xr,cs;
void dfs(ll src) {
    visited[src]=1;
    nodes++;
    last=src;
    xr.pb(src);
    for(auto itr: adj[src]) {
        if(!visited[itr]) {
            dfs(itr);
        }
    }
}
void dfs1(ll src) {
    visited[src]=1;
    cycle++;
    cs.pb(src);
    for(auto itr:adj[src]) {
        if(!visited[itr]) {
            dfs1(itr);
        }
    }
}
void solve() {
    ll n,k;
    cycle=0;
    cin>>n>>k;
    nodes=0;
    visited = vector<ll>(n);
    adj = vector<vector<ll>>(n);
    vector<ll> arr(n);
    for(int i=0;i<n;i++) {
        cin>>arr[i];
        arr[i]--;
    }
    for(int i=0;i<n;i++) {
        adj[i].pb(arr[i]);
    }
    dfs(0);
    for(int i=0;i<n;i++) visited[i]=0;
    dfs1(adj[last][0]);
    if(k<nodes) {
        cout<<xr[k]+1;
        return ;
    }
    k-=(nodes-cycle);
    k%=cycle;
    
    // cout<<k<<endl;
    cout<<cs[k]+1;
}   


int main(void){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t=1;
    // cin>>t;
    while(t--) {
        solve();
        cout<<endl;
    }
    return 0; 

}


Measured memory_bytes: 30520
#include<iostream>
using namespace std;
main() {
	string s,u="++++++++++",c=">+++++[<++++++>-]>+++++[<++++++++>-]>+++++[<"+u+">-]>++++++[<"+u+">-]>+++++++[<"+u+">-]>++++++++[<"+u+">-]>+++++++++[<"+u+">-]>"+u+"[<"+u+">-]>+++++++++++[<"+u+">-]>++++++++++++[<"+u+">-]<<<<<<<<<<";
	int p=0,t[10]={},i,j,a,b,d;
	for(cin>>s,i=0;i<s.length();++i){
		a=(s[i]/10)-3,b=a-p,p=a,d=s[i]-(a+3)*10;
		for(j=b>0?b:-b;j--;)c+=(b>=0?">":"<");
		for(j=d;j--;)c+="+";
		c+=".";
		for(j=d;j--;)c+="-";
	}
	cout<<c<<endl;
}

Measured memory_bytes: 1252
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <iostream>
#define ll long long
using namespace std;
int dp[10000+7];
int t[10]= {0,2,5,5,4,5,6,3,7,6},a[10],b[100];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    //freopen("in.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,i,j,k;
    cin>>n>>m;
    for(i=0; i<m; i++)
        cin>>a[i];
    sort(a,a+m,cmp);
dp[0]=1;
//memset(dp,-1,sizeof(dp));
    for(i=0;i<m;i++)
    {
        for(j=t[a[i]];j<=n;j++)
        {
            if(j&&j>=t[a[i]])dp[j]=max(dp[j],dp[j-t[a[i]]]+1);
        }
    }
   // for(i=0;i<=n;i++)cout<<dp[i]<<endl;
    while(n>0)
    {//cout<<n<<endl;
        for(i=0;i<m;i++)
        {//cout<<a[i]<<" ";
           // cout<<n<<" "<<dp[n]<<"  "<<dp[n-t[a[i]]]<<endl;
            if(n>=t[a[i]]&&dp[n]-dp[n-t[a[i]]]==1)
            {
                cout<<a[i];
                n=n-t[a[i]];
                break;
            }
        }
 //  cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef pair<int,int> P;
typedef complex<double> CP;
typedef long long ll;

int n;
P res;

int main(){
	cin>>n;
	int a,v;
	res.F=1; res.S=0;
	rep(i,n){
		cin>>a>>v;
		if(res.S<v||(res.S==v&&a<res.F)){
			res.F=a; res.S=v;
		}
	}
	cout<<res.F<<" "<<res.S<<endl;
	return 0;
}

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

int main(){
    string S;
    cin >> S;
    int A[26]={0};

    for(int i=0;i<S.size();i++){
        int j= S.at(i)-'a';
        A[j]++;
    }
 
    for(int i=0;i<26;i++){
        if(A[i]==0){
            cout << (char)(i+'a') << endl;
            break;
        }
        if(i==25){
            cout << "None" << endl;
            break;
        }

    }
}

Measured memory_bytes: 512
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    x1,y1,x2,y2=map(int, input().split())
    a=x2-x1
    b=y2-y1
    x3=x2-b
    y3=y2+a
    x4=x3-a
    y4=y3-b
    print(x3,y3,x4,y4)
resolve()

Measured memory_bytes: 3064
#include <stdio.h>

#define Mod 1000000007

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

typedef struct List {
	struct List *next;
	int v, size, id;
	long long count;
} list;

list *adj[200001] = {}, e[400001];
long long fact[200001], fact_inv[200001];

long long recursion(int k)
{
	if (e[k^1].count > 0) return e[k^1].count;
	else e[k^1].count = 1;
	
	int u = e[k].v, w = e[k^1].v, tmp;
	list *p;
	for (p = adj[u]; p != NULL; p = p->next) {
		if (p->v == w) continue;
		recursion(p->id);
		e[k^1].size += e[(p->id)^1].size;
	}
	for (p = adj[u], tmp = e[k^1].size; p != NULL; p = p->next) {
		if (p->v == w) continue;
		e[k^1].count = e[k^1].count * e[(p->id)^1].count % Mod * fact[tmp] % Mod * fact_inv[e[(p->id)^1].size] % Mod * fact_inv[tmp - e[(p->id)^1].size] % Mod;
		tmp -= e[(p->id)^1].size;
	}
	e[k^1].size++;
	return e[k^1].count;
}

int main()
{
	int i, N, u, w;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d", &u, &w);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].count = 0;
		e[i*2+1].count = 0;
		e[i*2].size = 0;
		e[i*2+1].size = 0;
		e[i*2].id = i * 2;
		e[i*2+1].id = i * 2 + 1;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int flag[200001] = {}, q[200001], head, tail;
	long long ans[200001], tmp;
	list *p;
	for (i = 1, fact[0] = 1; i <= N; i++) fact[i] = fact[i-1] * i % Mod;
	for (i = N - 1, fact_inv[N] = div_mod(1, fact[N], Mod); i >= 0; i--) fact_inv[i] = fact_inv[i+1] * (i + 1) % Mod;
	for (head = 0, tail = 1, q[0] = 1, flag[1] = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u], ans[u] = 1, tmp = N - 1; p != NULL; p = p->next) {
			ans[u] = ans[u] * recursion(p->id) % Mod * fact[tmp] % Mod * fact_inv[e[(p->id)^1].size] % Mod * fact_inv[tmp - e[(p->id)^1].size] % Mod;
			tmp -= e[(p->id)^1].size;
			if (flag[p->v] == 0) {
				flag[p->v] = 1;
				q[tail++] = p->v;
			}
		}
		for (p = adj[u]; p != NULL; p = p->next) {
			if (p->count == 0) {
				p->count = div_mod(ans[u], e[(p->id)^1].count * fact[N-1] % Mod * fact_inv[e[(p->id)^1].size] % Mod * fact_inv[N-1-e[(p->id)^1].size] % Mod, Mod);
				p->size = N - e[(p->id)^1].size;
			}
		}
	}
	for (i = 1; i <= N; i++) printf("%lld\n", ans[i]);
	fflush(stdout);
	return 0;
}

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

int N;
int buka[200010];
int main(){
    cin >> N;
    int tmp;
        
    for(int i = 0; i < N; ++i){
        buka[i] = 0;
    }
    for(int i = 0; i < N-1; ++i){
        cin >> tmp;
        buka[tmp]++;
    }
    
    for(int i = 0; i < N; ++i){
        cout << buka[i+1] << endl;
    }
    return 0;
}

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

int main(){
	static int arr[200003]; int N , K;
	cin >> N >> K; for(int i = 1 ; i <= N ; ++i) cin >> arr[i];
	set < int > num; int ans = 1;
	for(int i = 1 ; i <= K ; ++i) num.insert(arr[i]);
	for(int i = K + 1 ; i <= N ; ++i){
		ans += *num.begin() != arr[i - K] || *--num.end() > arr[i];
		num.erase(arr[i - K]); num.insert(arr[i]);
	}
	bool flg = 0; int pre = -1 , cnt = 0;
	for(int i = 1 ; i <= N ; ++i){
		if(pre < arr[i]) ++cnt;
		else cnt = 1;
		pre = arr[i];
		if(cnt == K){flg = 1; --ans;}
	}
	cout << ans + flg; return 0;
}


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ld long double
#define mem(x,y) memset(x,y,sizeof x)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update> ordered_set;

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

void solve()
{
	int k;
	cin>>k;
	while(k--) cout<<"ACL";
	cout<<'\n';
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


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

vector<ll> po(4,1);

vector<int> Sort(vector<int> v){
    vector<int> res=v,u(4);
    for (int i=1;i<4;++i){
        for (int j=0;j<4;++j){
            u[j]=v[(i+j)%4];
        }
        if (u<res) res=u;
    }
    return res;
}

ll hashed(vector<int> v){
    ll res=0; v=Sort(v);
    for (int i=0;i<4;++i){
        res+=v[i]*po[i];
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<vector<int>> C(N,vector<int>(4));
    for (int i=0;i<N;++i){
        for (int j=0;j<4;++j){
            cin >> C[i][j];
        }
    }
    for (int i=0;i<3;++i) po[i+1]=po[i]*1000;
    map<ll,ll> cnt;
    vector<ll> each(N);
    vector<int> v(4);
    for (int i=0;i<N;++i){
        each[i]=hashed(C[i]);
        ++cnt[each[i]];
    }
    ll ans=0;
    for (int i=0;i<N;++i){
        for (int j=0;j<N;++j){
            if (i==j) continue;
            --cnt[each[i]]; --cnt[each[j]];
            for (int p=0;p<4;++p){
                map<ll,int> used;
                ll sum=1,rot;
                for (int q=0;q<4;++q){
                    v[0]=C[i][q];
                    v[1]=C[j][(p-q+4)%4];;
                    v[2]=C[j][(p-q+7)%4];
                    v[3]=C[i][(q+1)%4];
                    if (v[0]==v[1]&&v[1]==v[2]&&v[2]==v[3]&&v[3]==v[0]) rot=4;
                    else if (v[0]==v[2]&&v[1]==v[3]) rot=2;
                    else rot=1;
                    ll surface=hashed(v);
                    sum*=(cnt[surface]-used[surface])*rot;
                    ++used[surface];
                }
                ans+=sum;
            }
            ++cnt[each[i]]; ++cnt[each[j]];
        }
    }
    cout << ans/6 << '\n';
}

Measured memory_bytes: 80128
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
#include<typeinfo>
#include<complex>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)

int main() {

	int r, d, x;
	cin >> r >> d >> x;

	rep(i, 0, 10) {
		x = x * r - d;
		cout << x << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

void solve()
{
	priority_queue<int> pque;
	char order[10] = "";
	while (true)
	{
		cin >> order;
		//scanf_s(" %s", order);
		if (order[2] == 'd')
		{
			break;
		}
		else if (order[0] == 'i')
		{
			int num;
			scanf("%d", &num);
			pque.push(num);
		}
		else
		{
			printf("%d\n", pque.top());
			pque.pop();
		}
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 6756
h, w = map(int, input().split())
ma = []
ma.append(["."]*(w+2))
for i in range(h):
    k = ["."]
    k += input()
    k += "."
    ma.append(k)
ma.append(["."] * (w + 2))
end = 0
for i in range(h):
    if end == 1:
        break
    for j in range(w):
        if ma[i + 1][j + 1] == "#":
            if ma[i][j + 1] == "." and ma[i + 1][j] == "." and ma[i + 2][j + 1] == "." and ma[i + 1][j + 2] == ".":
                print("No")
                end = 1
                break
else:
    print("Yes")

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


main(){
   int i;
   string s;
   cin >> s;
   int len=s.length();

   int ans=0;
   for(i=0;i<len/2;i++){
      if(s[i]!=s[len-1-i]) ans++;
   }
   cout << ans << endl;
   
}

Measured memory_bytes: 256
import java.util.*;
import java.util.Arrays;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        Integer[] d = new Integer[K];

        for(int i = 0 ; i < K ; i++){
            d[i] = sc.nextInt();
        }

        boolean ok = true;

        while(ok){
            int N0 = N / 10000;
            int N1 = (N % 10000) /1000;
            int N2 = (N % 1000) / 100;
            int N3 = (N % 100) / 10;
            int N4 = N % 10;
            
            boolean NG0 = (N >= 10000 ? Arrays.asList(d).contains(N0) : false);
            boolean NG1 = (N >= 1000 ? Arrays.asList(d).contains(N1) : false);
            boolean NG2 = (N >= 100 ? Arrays.asList(d).contains(N2) : false);
            boolean NG3 = (N >= 10 ? Arrays.asList(d).contains(N3) : false);
            boolean NG4 = Arrays.asList(d).contains(N4);

            if (NG0 || NG1 || NG2 || NG3 || NG4) {
                N++;
            }
            else
                ok = false;
        }

        System.out.println(N);
    }
}

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


int main(void) {
  string s, t;
  cin >> s >> t;

  vector<int> sv(26);
  vector<int> tv(26);
  rep(i, s.size()) {
    sv[s[i] - 'a']++;
    tv[t[i] - 'a']++;
  }
  sort(sv.begin(), sv.end());
  sort(tv.begin(), tv.end());

  rep(i, sv.size()) {
    if (sv[i] != tv[i]) {
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3920
N = int(input())
if N == 0:
    print('0')
    exit()
check = 1
now = 0
ans = ''
count = 1
while True:
    check *= 2
    a = N%check
#    print(a,count,now)
    if now == N:
        break    
    else:
        if (a-now)%check != 0:
            ans = ans + '1'
            now += count
        else:
            ans = ans + '0'
        count *= -2

print(ans[::-1])



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

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

  for (int i = 9; i > 0; i--) {
    for (int j = 9; j > 0; j--) {
      if (i * j == N) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}


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

using namespace std;
using ll = long long;

int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            ans++;
        }
    }
    ans = min(ans + 2 * k, n - 1);
    cout << ans;
    return 0;
}


Measured memory_bytes: 512
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define rep(i, l, r) for (ll i = (l); i < (r); ++i)
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<ll>
#define pii pair<int, int>
#define int ll
#define pll pair<ll, ll> 
#define pdd pair<ld, ld> 
#define pb push_back
#define reset(x,v) memset(x,v,sizeof(x))
#define mod 998244353
using namespace std;

void dfs(vector<int> adj[], int sv, vector<bool> &vis){
	vis[sv] = true;
	for(int i = 0; i < adj[sv].size(); i++){
		if(!vis[adj[sv][i]]){
			dfs(adj, adj[sv][i], vis);
		}
	}
}
ll power(ll x, ll y){  
	if(x == 1 || y == 0)
		return 1;
    ll res = 1;   
    x = x % mod; 
    if (x == 0) 
		return 0;  
    while (y > 0){  
        if (y & 1)  
            res = (res * x) % mod;  
        y = y >> 1; 
        x = (x * x) % mod;  
    }  
    return res;  
}  


signed main(){
	FASTIO
	int k;
	cin >> k;
	queue<int> q;
	rep(i, 1, 10)
		q.push(i);
	while(!q.empty()){
		int f = q.front();
		q.pop();
		if(k == 1){
			cout << f;
			return 0;
		}
		k--;
		if(f%10 != 0)
			q.push(f*10 + f%10 -1);
		q.push(f*10 + f%10);
		if(f%10 != 9)
			q.push(f*10 + f%10 +1);
		
	}
    return 0;
}


Measured memory_bytes: 4684
#include<bits/stdc++.h>
#define ll long long int
#include <cmath>
using namespace std;
const unsigned int m = 10e3+5;

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   	int t;
   	//cin>>t;
   	t=1;
   	while(t--)
   	{
       ll a;
        long double b;
       cin>>a>>b;
       ll ans;
         ans=a*b;
       cout<<ans<<endl;
	}
	return 0;
}


Measured memory_bytes: 3712
// depends on: -

/*
usage:

tools::floor(5, 3) // => 1
tools::ceil(5, 3) // => 2
*/

namespace tools {
  template <typename T> constexpr T floor(T lhs, T rhs);
  template <typename T> constexpr T ceil(T lhs, T rhs);

  template <typename T> constexpr T floor(const T lhs, const T rhs) {
    return
      lhs >= 0 && rhs >= 0 ?
        lhs / rhs :
      lhs < 0 && rhs >= 0 ?
        -ceil<T>(-lhs, rhs) :
      lhs >= 0 && rhs < 0 ?
        -ceil<T>(lhs, -rhs) :
        floor<T>(-lhs, -rhs);
  }

  template <typename T> constexpr T ceil(const T lhs, const T rhs) {
    return
      lhs >= 0 && rhs >= 0 ?
        (lhs - 1 + rhs) / rhs :
      lhs < 0 && rhs >= 0 ?
        -floor<T>(-lhs, rhs) :
      lhs >= 0 && rhs < 0 ?
        -floor<T>(lhs, -rhs) :
        ceil<T>(-lhs, -rhs);
  }
}
#include <iostream>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <iterator>
#include <numeric>

bool can_beat(const std::int_fast64_t a, const std::int_fast64_t b, const std::vector<std::int_fast64_t>& h, const std::int_fast64_t k) {
  return std::accumulate(h.begin(), h.end(), static_cast<std::int_fast64_t>(0), [&a, &b, &k](const std::int_fast64_t sum, const std::int_fast64_t h_i) {
    return sum + (h_i <= b * k ? 0 : tools::ceil(h_i - b * k, a - b));
  }) <= k;
}

int main() {
  std::int_fast64_t n, a, b;
  std::cin >> n >> a >> b;
  std::vector<std::int_fast64_t> h(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, h.begin());

  std::int_fast64_t min_k_exclusive = 0;
  std::int_fast64_t max_k_inclusive = tools::ceil(*std::max_element(h.begin(), h.end()), b);
  while (max_k_inclusive - min_k_exclusive > 1) {
    const std::int_fast64_t avr_k = (min_k_exclusive + max_k_inclusive) / 2;
    if (can_beat(a, b, h, avr_k)) {
      max_k_inclusive = avr_k;
    } else {
      min_k_exclusive = avr_k;
    }
  }
  std::cout << max_k_inclusive << std::endl;
  return 0;
}

Measured memory_bytes: 1024
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using ll = long long;
using namespace std;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(int i = int(a); i < int(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
const long long INF = (1LL << 60);
const long long mod = 1e9 + 7;

int main() {
    int n, f;
    cin >> n;
    f = (n + 1) / 2;
    vector<double> p(n);
    rep(i, n) cin >> p[i];
    // dp:when you toss i coin(s), j coins are in back
    vector<vector<double>> dp(n + 10, vector<double>(n + 10, 0));
    dp[0][0] = 1;

    rep(i, 0, n) {
        rep(j, 0, min(f, n)) {
            dp[i + 1][j] += dp[i][j] * p[i];
            dp[i + 1][j + 1] += dp[i][j] * (1 - p[i]);
        }
    }
    double sum = 0;
    rep(i, f) sum += dp[n][i];
    printf("%.10lf\n", sum);
}

Measured memory_bytes: 71168
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
ll mod=1e9+7;
int main(){
	string s;
	cin >>s;
	ll ans=0;
	/*
	dp [10^at][mod 13]= count
	init; 0 ,[0][0]=1;
	transiston:
	[at][b+(s[at]*10^at)mod13]=[at-1][b] if s[at]==? -> all 
	*/

	V trans(1e5+5,1LL);
	reps(i,1e5+1){
		trans[i]*=trans[i-1]*10;
		trans[i]%=13;
	}
	VV dp(s.size()+2,V(14,0LL));
	for(int i=0;i<s.size();i++){
		for(int t=0;t<=9;t++){
			if(s[i]==t+'0' or s[i]=='?'){
				for(int j=0;j<13;j++){
					if(i==0){
						dp[i][( t * trans[s.size() - i-1]) % 13]=1LL;
					}else{
						dp[i][(j + t * trans[s.size() - i-1]) % 13] += dp[i-1][j];
						dp[i][(j + t * trans[s.size() - i - 1]) % 13]%=mod;
					}
				}	
			}
		}
	}

	/*rep(i,s.size()){
		rep(j,13){
			clog<<dp[i][j]<<" ";
		}
		clog<<endl;
	}
	*/
	cout<<dp[s.size()-1][5]<<endl;
}

Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define ms(a, n) memset(a, n, sizeof(a))
#define Size(Array) sizeof(Array)/sizeof(Array[0])
#define pb push_back
#define ed endl
#define en cout << endl
#define it(A) A.begin(), A.end()
#define mod (ll)(1e9 + 7)
#define f(i, a, b) for(ll i = a; i < b; i++)
#define cin(a, n) for(ll i = 0; i < n; i++) cin >> a[i]
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define MAX 200005


using namespace std;


void solve()
{
    ll p, x, n, i = 0;
    cin >> n;
    p = 100;

    while(p < n)
    {
        i++;
        p = p + p*(0.01);
    }

    cout << i << endl;

    return;
}

int main()
{
    FAST;

    ll t = 1;
    while(t--)
        solve();


    return 0;
}



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


def main():
    d, g = map(int, input().split())
    ps = [0 for _ in range(d)]
    cs = [0 for _ in range(d)]
    score_with_bonus = dict()
    ans = float('inf')

    for i in range(d):
        pi, ci = map(int, input().split())
        ps[i] = pi
        cs[i] = ci
        score_with_bonus[i] = (i + 1) * pi * 100 + ci

    # See:
    # https://img.atcoder.jp/abc104/editorial.pdf
    for bit in range(1 << d):
        total_score = 0
        problem_count = 0
        pmax = 0

        for j in range(d):
            if bit & (1 << j):
                total_score += score_with_bonus[j]
                problem_count += ps[j]
            else:
                pmax = max(pmax, j)

        for k in range(1, ps[pmax]):
            if total_score < g:
                total_score += (pmax + 1) * 100
                problem_count += 1

        if problem_count > 0 and total_score >= g:
            ans = min(ans, problem_count)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using ll = unsigned long long;
using pii = pair<int, int>;
#define endl '\n'

ll a, b, c, d;

vector<pii> v;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

gp_hash_table<long long, ll, custom_hash> mp;

ll calc(ll n) {
	if(n == 1) return d;
	if(n == 0) return 0;
	ll ret = 1e18;
	if(mp.find(n) != mp.end()) return mp[n];
	ret = min(ret, d * (n % 2) + calc(n / 2) + a);
	ret = min(ret, d * (n % 3) + calc(n / 3) + b);
	ret = min(ret, d * (n % 5) + calc(n / 5) + c);

	ll d1 = ((n+(2-n%2)))/2;
	ll d2 = ((n+(3-n%3)))/3;
	ll d3 = ((n+(5-n%5)))/5;

	if(d1 < n) ret = min(ret, d * (2 - n % 2) + calc(d1) + a);
	if(d2 < n) ret = min(ret, d * (3 - n % 3) + calc(d2) + b);
	if(d3 < n) ret = min(ret, d * (5 - n % 5) + calc(d3) + c);
	ret = min(ret, d * n);

	return mp[n] = ret;
}

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

	while(t--) {
		ll n;
		cin >> n >> a >> b >> c >> d;

		cout << calc(n) << endl;
		mp.clear();
	}
}


Measured memory_bytes: 6048
/*
    Created by Rahul Goel.
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/*******************************************************************************/
using namespace std;
using namespace __gnu_pbds;
template < typename T >
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*******************************************************************************/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
// const ll MOD = 998244353;
const int INF = 1e9;
const ll LINF = 1e18;
/*******************************************************************************/
ll mod_sum() { return 0LL; }
template < typename T, typename... Args >
T mod_sum(T a, Args... args) { return ((a + mod_sum(args...))%MOD + MOD)%MOD; }
/*******************************************************************************/
ll mod_prod() { return 1LL; }
template< typename T, typename... Args >
T mod_prod(T a, Args... args) { return (a * mod_prod(args...))%MOD; }
/*******************************************************************************/
#ifdef ONLINE_JUDGE
#define endl '\n'
#endif
#define fastio          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(c)          (c).begin(), (c).end()
#define present(c,x)    ((c).find(x) != (c).end())
#define cpresent(c,x)   (find(all(c),x) != (c).end())
#define uniq(c)         (c).resize(distance((c).begin(), unique(all(c))))
#define min_pq(t)       priority_queue < t, vector < t >, greater < t > >
#define max_pq(t)       priority_queue < t >
#define pb              push_back
#define ff              first
#define ss              second
/*******************************************************************************/
using pii = pair < ll, ll >;
using vi = vector < ll >;
using vb = vector < bool >;
using vvi = vector < vector < ll > >;
using vvb = vector < vector < bool > >;
using vpii = vector < pii >;
using vvpii = vector < vector < pii > >;
/*******************************************************************************/
//.-.. . -. -.- .- .. ... .-.. --- ...- .
/*
    Code begins after this.
*/

ll solve() {
    string str;
    cin >> str;
    ll sum = 0;
    for (char x : str) {
        sum = (sum + x - '0') % 9;
    }
    if (sum == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

signed main() {
    fastio;

    ll t = 1;
    while (t--) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <limits>
using namespace std;

int main(int argc, const char * argv[]) {
    char S[20] = {0};
    int min_diff = numeric_limits<int>::max();
    
    cin >> S;
    
    for (int i = 0; i < strlen(S) - 2; i++) {
        char num_str[4] = {0};
        for (int j = 0; j < 3; j++) {
            num_str[j] = S[i + j];
        }
        int num = atoi(num_str);
        int diff = abs(num - 753);
        if (min_diff > diff) {
            min_diff = diff;
        }
    }
    cout << min_diff << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr int INF = 1 << 30;
constexpr ll LINF = 1LL << 60;
constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll k, ans = 0;
    cin >> k;

    for(int i=1;i<=k;++i) for(int j=1;j<=k;++j) for(int l=1;l<=k;++l) ans += gcd(i, gcd(j, l));
    cout << ans << endl;
}


Measured memory_bytes: 3652
#include <stdio.h>
#define ll long long
#define rep(i,l,r)for(ll i=l;i<r;i++)

int p[300010];
int prime[300010],pcnt;

//間に合う？
int main(){
	for(int i=6,mmm=5;i<300005;i+=mmm^=7)if(!p[i]){
		prime[pcnt++]=i;
		for(int j=6,nnn=5;i*j<300005;j+=nnn^=7)p[i*j]=1;
	}
	ll n;
	while(scanf("%lld",&n),n!=1){
		printf("%lld:",n);
		rep(i,0,pcnt){
			if(prime[i]>n)break;
			if(n%prime[i]==0)printf(" %lld",prime[i]);
		}
		puts("");
	}
}


Measured memory_bytes: 3028
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll INFL = 1e18+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	int A, B;
	cin >> A >> B;
	if (A <= 8 && B <= 8) puts("Yay!");
	else puts(":(");
	return 0;
}


Measured memory_bytes: 256
def gcd(a, b):
  while b:
    a, b = b, a % b
 
  return a

n = int(input())
monster = sorted(list(map(int,input().split())))
ans = []
for i in range(n-1):
  g = gcd(monster[i], monster[i+1])
  ans.append(g)
print(min(ans))

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

int N, L[100], X;

int main(){
    cin >> N >> X;
    int ans = 1, coord = 0;
    for(int i = 0; i < N; i++){
        cin >> L[i];
        coord += L[i];
        if(coord <= X){
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
//package com.company;

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][]arr = new int[3][3];
        for(int i = 0; i<3; i++)for(int j = 0; j<3; j++)arr[i][j] = in.nextInt();
        for(int i = 0; i<=100; i++){
            int[]a = new int[3];
            int[]b = new int[3];
            boolean ok = true;
            for(int j = 0; j<3; j++) a[j] = arr[j][0] - i;
            for(int j = 0; j<3; j++) b[j] = arr[0][j] - a[0];
            for(int k = 0; k<3; k++){
                for(int j = 0; j<3; j++){
                    if(arr[k][j] != a[k] + b[j])ok = false;
                }
            }
            if(ok){
                System.out.println("Yes");return;
            }
            a = null;
            b = null;
        }
        System.out.println("No");
    }
}


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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()
#define rALL(a) (a).rbegin(), (a).rend()
#define SZ(x) ((int)(x).size())
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
//const int mod = 1000000007;
const int mod = 998244353;

template <class T>inline bool chmin(T &a, const T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline bool chmax(T &a, const T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
template <class T>inline void line_out(const vector<T> vec) {
  int n = SZ(vec);
  rep(i, n) {
    cout << vec[i];
    if(i < n-1) cout << " ";
  }
  cout << endl;
  return;
}

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

int main()
{
  int n; cin >> n;
  for(int i = 1;;++i) {
    if(i*(i+1)/2 >= n) {
      for(int j = 1; j <= i; ++j) {
        if(j == i*(i+1)/2-n) continue;
        cout << j << endl;
      }
      return 0;
    }
  }
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;


int main(){
    ll n; set<string>a; string x;
    cin>>n;
    while(n--)
    {
        cin>>x; a.insert(x);
    }
    cout<<a.size();
    return 0;
}


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

using namespace std;

int main(){
    int N,K,x,y;
    cin>>N>>K>>x>>y;
    if(N>K){
        cout<<(K*x+y*(N-K))<<endl;
    }
    else{
        cout<<N*x<<endl;
    }





    return 0;
}


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

using namespace std;

const int N = 1e5 + 10;

int n, b[N];

int main() {
  cin >> n;
  int ans = 0;
  for (int i = 1; i < n; i++) cin >> b[i];
  ans += b[1] + b[n - 1];
  for (int i = 2; i < n; i++) {
     ans += min(b[i - 1], b[i]); 
  } 
  cout << ans << endl;
  return 0;
}

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

using namespace std;
typedef long long I64;
const I64 NMAX = 200000;
const I64 MOD  = 1000000007;

int fact[NMAX+5];

int main() {
    I64 N,M;
    fact[0] = 1;
    fact[1] = 1;
    for( I64 i = 2;  i <= NMAX;  ++i ) fact[i] = fact[i-1] * i % MOD;


    cin >> N >> M;
    if( N > M ) swap(N,M);
    if( M-N > 1 || N-M > 1 ) {
        cout << "0\n";
        return 0;
    }
    if( M != N ) {
        cout << 1LL*fact[N]*fact[M] % MOD;
    }
    else cout << 2LL*fact[N] % MOD *fact[M] % MOD;
    return 0;
}


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

using namespace std;

int n;
vector<int> a(100001);
int s;

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

    for(int i = 1; i <= n; i++){
        cout << s - abs(a[i] - a[i-1]) - abs(a[i] - a[i+1]) + abs(a[i-1] - a[i+1]) << endl;
    }

    return 0;
}


Measured memory_bytes: 1664
def main(s, t, a, b, u):
    d = {s: a, t: b}

    d[u] -= 1

    print(d[s], d[t])


if __name__ == "__main__":
    s, t = input().split()
    a, b = map(int, input().split())
    u = input()

    main(s, t, a, b, u)


Measured memory_bytes: 3060
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
template <typename T> using posteriority_queue = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
template <typename T> void unique(vector<T> &a) { a.erase(unique(ALL(a)), a.end()); }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  int n, ma, mb; cin >> n >> ma >> mb;
  vector<int> a(n), b(n), c(n); REP(i, n) cin >> a[i] >> b[i] >> c[i];
  vector<vector<int> > mid(201, vector<int>(201, INF));
  mid[0][0] = 0;
  REP(i, 1 << ((n + 1) / 2)) {
    int A = 0, B = 0, C = 0;
    REP(j, (n + 1) / 2) {
      if (i >> j & 1) {
        A += a[j];
        B += b[j];
        C += c[j];
      }
    }
    chmin(mid[A][B], C);
  }
  int ans = INF;
  REP(i, 1 << (n / 2)) {
    int A = 0, B = 0, C = 0;
    REP(j, n / 2) {
      if (i >> j & 1) {
        A += a[n - 1 - j];
        B += b[n - 1 - j];
        C += c[n - 1 - j];
      }
    }
    for (int j = max({(A + ma - 1) / ma, (B + mb - 1) / mb, 1}); ; ++j) {
      if (ma * j - A > 200 || mb * j - B > 200) break;
      chmin(ans, mid[ma * j - A][mb * j - B] + C);
    }
  }
  cout << (ans == INF ? -1 : ans) << '\n';
  return 0;
}


Measured memory_bytes: 384
using System;
using System.Linq;

namespace ARC061
{
    class C
    {
        static void Main(string[] args)
        {
            //input
            string S = Console.ReadLine();
            int N = S.Length;

            long sum = 0;
            for (int i = 0; i < 1 << (N - 1); i++)
            {
                string s = S[0].ToString();
                for (int j = 1; j < N; j++)
                {
                    if ((i & (1 << (j - 1))) != 0)
                    {
                        s += "+";
                    }
                    s += S[j];
                }
                sum += s.Split('+').Select(long.Parse).Sum();
            }
            Console.WriteLine(sum);
        }
    }
}


Measured memory_bytes: 13268
#include <iostream>
#include <math.h>
using namespace std;

int tax(int price, int rate) {
    return price * (100 + rate) / 100;
}

int solve(int a, int b, int p) {
    int ma = 0;
    for (int i = 1; i < p; i++) {
        for (int j = i; j < p; j ++) {
            if (tax(i, b) + tax(j, b) == p) {
                ma = max(ma, tax(i, a) + tax(j, a));
            }
        }
    }
    return ma;
}

int main()
{
    int b, a, p;
    while (cin >> b >> a >> p && b > 0)
    {
        cout << solve(a, b, p) << endl;
    }

    return 0;
}


Measured memory_bytes: 2984
#include<bits/stdc++.h>
#include <math.h>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    int x,y,z;
	cin >> x>> y>> z;
      cout << min(x*y,z) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
   

    bool flag = true;
    ll n;
    cin >> n;
    for (ll i=0;i<n;i++){
        ll a;
        cin >> a;
        if(a%2 == 0){
            if(a%3 != 0 and a%5 != 0){
                flag = false;
            }
        }
    }
    if(flag){
        cout << "APPROVED" << endl;
    }else{
        cout << "DENIED" << endl;
    }
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
using LL = long long;
using ULL = unsigned long long;

void solve() {
	string s; cin >> s;
	unsigned ans = 0;
	if (s == "SUN") ans = 7;
	if (s == "MON") ans = 6;
	if (s == "TUE") ans = 5;
	if (s == "WED") ans = 4;
	if (s == "THU") ans = 3;
	if (s == "FRI") ans = 2;
	if (s == "SAT") ans = 1;

	cout << ans << endl;
}

int main() {

	solve();

	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	long := len(s)

	m := make([][]int, 26)
	for i, S := range s {
		x := S - rune("a"[0])
		// fmt.Println(x, i)
		m[x] = append(m[x], i+1)
	}
	// fmt.Println(m)
	var ans, before int
	for _, T := range t {
		val := m[T-rune("a"[0])]
		l := len(val)
		if l == 0 {
			fmt.Println(-1)
			return
		}
		z := sort.Search(l, func(z int) bool { return val[z] > before })
		// fmt.Println(z, val, before, long)
		if z == l {
			ans += long + val[0] - before
			before = val[0]
		} else {
			ans += val[z] - before
			before = val[z]
		}

		// for j := 0; j < l; j++ {
		// 	if val[j] > before {
		// 		ans += val[j] - before
		// 		before = val[j]
		// 		break
		// 	} else if j == l-1 {
		// 		ans += long + val[0] - before
		// 		before = val[0]
		// 	}
		// }
	}
	fmt.Println(ans)
}


Measured memory_bytes: 5248
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define repi(i,x) for(auto i=(x).begin(),i##_fin=(x).end();i!=i##_fin;i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef pair<int , int> Pi;
typedef vector<Pi> VPi;
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<30;
const double PI=acos(-1);
Vi pre(8, -1);
Vi cr(8,-1);
bool func(int at){
	bool can=true;
	bool finc=true;
	if(at==8){
		for(int i=0;i<8;i++){
			for(int j=0;j<i;j++){
				if(cr[i]==cr[j]+(i-j) or cr[i]==cr[j]-(i-j)or cr[i]==cr[j]){
					return false;
				}
			}
		}
		return true;
	}else{
		if(pre[at]!=-1){
			cr[at]=pre[at];
			if( func(at+1)==false){
				return false;
			}else{
				return true;
			}
		}
		for(int i=0;i<8;i++){
			can=true;
			for(int j=0;j<at;j++){
				if(cr[j]==i){
					can=false;
				}
			}
			if(can){
				cr[at]=i;
				if(func(at+1)==true){
					return true;
				}
			}
			if(i==7){
				cr[at]=-1;
				return false;
			}
		}
	}
	return false;
}

int main(){
	int k;
	int ans=0;
	cin >>k;
	
	int r,c;
	rep(i,k){
		cin>>r>>c;
		pre[r]=c;
	}
	func(0);
	for(int i=0;i<8;i++){
		for(int j=0;j<8;j++){
			if(cr[i]!=j){
				cout<<'.';
			}else{
				cout<<'Q';
			}
			if(j==7){
				cout<<endl;
			}else{
			}
		}
	}
}


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

int N, K;
deque<int> A[10];

int dp[11][2222];

int main() {
  cin >> N >> K;
  for(int i = 0; i < N; ++i) {
    int C, G;
    cin >> C >> G;
    A[G-1].push_back(C);
  }
  for(int i = 0; i < 10; ++i) {
    sort(A[i].begin(), A[i].end(), greater<int>());
    A[i].push_front(0);
    for(int j = 1; j < A[i].size(); ++j) {
      A[i][j] += A[i][j-1];
    }
  }
  for(int i = 0; i < 10; ++i) {
    for(int j = 0; j <= K; ++j) {
      int &now = dp[i][j];
      for(int k = 0; k < A[i].size() && j+k <= K; ++k) {
        int &next = dp[i+1][j+k];
        next = max(next, now + A[i][k] + k * (k - 1));
      }
    }
  }
  cout << dp[10][K] << endl;
  return 0;
}

Measured memory_bytes: 1328
unittest
{
	assert( [ "3 4 5" ].parse.expand.solve == 6 );
	assert( [ "5 12 13" ].parse.expand.solve == 30 );
	assert( [ "45 28 53" ].parse.expand.solve == 630 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto abcs = input.front.split.to!( long[] );
	return tuple( abcs );
}

auto solve( long[] abcs )
{
	return abcs[ 0 ] * abcs[ 1 ] / 2;
}


Measured memory_bytes: 256