akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <deque>
//#include <bitset>
//#include <math.h>
using namespace std ;
//using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//void yorn(bool a){if(a) cout << "Yes" << endl ; else cout << "No" << endl ;}
//void YorN(bool a){if(a) cout << "YES" << endl ; else cout << "NO" << endl ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	int INF = 1000000000 ;
	int n ; cin >> n ;
	int mn = INF ;
	int sum = 0 ;
	for(int i=0;i<n;i++){
		int a ; cin >> a ;
		sum += a ;
		if(a%10!=0) mn = min(mn,a) ;
	}
	if(sum%10==0){
		cout << (mn==INF?0:sum-mn) << endl ;
	}else{
		cout << sum << endl ;
	}
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#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##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i, N) cin >> a[i];

    vv<ll> dp = vvec(N + 1, N + 1, 0LL);
    rep(i, N + 1) rep(j, N + 1) dp[i][j] = i % 2 ? LINF : -LINF;
    rep(j, N + 1) dp[N][j] = 0;

    for (int i = N - 1; i >= 0; --i) rep(j, i + 1) {
        if (i % 2) {
            dp[i][j] = min(dp[i + 1][j] - a[i - j], dp[i + 1][j + 1] - a[N - 1 - j]);
        }
        else {
            dp[i][j] = max(dp[i + 1][j] + a[i - j], dp[i + 1][j + 1] + a[N - 1 - j]);
        }
    }

    write(dp[0][0]);
}

Measured memory_bytes: 70784
//hogehgoe

//#include<gchost.h>
#include<iostream>
#include<vector>
#include<stack>
#include<map>
#include<string>
#include<queue>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;

int main()
{
	int N;
	while(cin>>N && N!=0){
		vector<vector<int> > V(N);
		for(int i=0;i<N;i++){
			int M;
			cin>>M;
			for(int j=0;j<M;j++){
				int t; cin>>t;
				V[i].push_back(t);
			}
		}

		vector<int> target;
		int K; cin>>K;
		for(int i=0;i<K;i++){
			int t;cin>>t;
			target.push_back(t);
		}

		int ans=-1,num=0;

		for(int i=0;i<N;i++){
			bool ok=false;
			for(int k=0;k<K;k++){
				ok=false;
				for(int idx=0;idx<V[i].size();idx++){
					if(V[i][idx]==target[k]){ok=true;break;}
				}
				if(!ok) break;
			}
			if(ok){ans=i;num++;}
		}
		if(num!=1) cout<<-1<<endl;
		else cout<<ans+1<<endl;
	}
	return 0;
}

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

class Union_Find {
  vector<int> par; vector<int> rank; vector<int> num;
public:
  Union_Find(int n) {
    par = vector<int>(n); rank = vector<int>(n,0); num = vector<int>(n,1);
    rep(i,n) par[i] = i;
  }
  int find(int x) {
    if(par[x] == x) return x;
    else  return par[x] = find(par[x]);
  }
  int number(int x) {
    return num[find(x)];
  }
  void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (rank[x] < rank[y]) swap(x, y);
    if (rank[x] == rank[y]) rank[x]++;
    par[y] = x;
    num[x] += num[y];
  } 
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main(){
  int n;
  cin >> n;
  int x[n], y[n];
  map<int,vector<int>> m;
  vector<int> v(MAX,0);
  rep(i,n) {
    cin >> x[i] >> y[i];
    m[y[i]].push_back(x[i]);
    v[x[i]]++;
  }
  Union_Find uf(MAX);
  for(auto x : m) {
    rep(i,x.second.size()-1) uf.unite(x.second[i],x.second[i+1]);
  }
  vector<set<int>> s(MAX);
  rep(i,n) s[uf.find(x[i])].insert(y[i]);
  ll ans = 0;
  rep(i,MAX) ans += s[uf.find(i)].size() - v[i];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15104
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int dp[50][500][500];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N,Ma,Mb;cin>>N>>Ma>>Mb;
  int a[N],b[N],c[N];
  FOR(i,0,N) cin >> a[i] >> b[i] >> c[i];
  FOR(i,0,N+1) FOR(j,0,500) FOR(k,0,500) dp[i][j][k] = 1e9;
  dp[0][0][0] = 0;
  FOR(i,0,N) {
    FOR(j,0,401) {
      FOR(k,0,401) {
        if(dp[i][j][k] == 1e9) continue;
        // iを混ぜる
        dp[i+1][j+a[i]][k+b[i]] = min(dp[i+1][j+a[i]][k+b[i]], dp[i][j][k] + c[i]);
        // 混ぜない
        dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
      }
    }
  }
  int ans = 1e9;
  FOR(i,1,500) FOR(j,1,500) if(i*Mb==j*Ma) ans = min(ans, dp[N][i][j]);
  cout << (ans == 1e9 ? -1 : ans) << endl;
  return 0;
}

Measured memory_bytes: 41216
#include <bits/stdc++.h>
#include <chrono>
#include <math.h>
using namespace std;
using ll = long long;
using namespace std::chrono; 
#define fo(i,z,n) for(int i = z;i<n;i++)
#define Fo(i,z,n) for(ll i = z;i<n;i++)
#define INT_BITS 32
#define mod 1000000007
 
// auto start = high_resolution_clock::now(); 
// auto stop = high_resolution_clock::now(); 
// auto duration = duration_cast<microseconds>(stop - start); 
 
// cout << duration.count() << endl; 
 bool sortbysecdesc(const pair<ll,ll> &a, 
                   const pair<ll,ll> &b) 
{ 
       return a.second>b.second; 
}

int main()
{
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
// int t;
// cin >> t;
// while(t--){

// }
int n,k;
cin >> n >> k;
int arr[n];
fo(i,0,n)cin >> arr[i];
ll dp[n];
fo(i,0,n)dp[i] = mod;
dp[0] = 0;
dp[1] = abs(arr[1] - arr[0]);
fo(i,2,n){
	int j = 1;
	while(j <= k && i-j >= 0){
		dp[i] = min(dp[i],dp[i-j] + abs(arr[i]- arr[i-j]));
		j++;
	}
	
}
cout << dp[n-1] << endl;
return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include<cmath>
#define pb push_back
#define ld long double
#define mp make_pair
#define vl vector<ll> 
#define vd vector<double>
#define vld vector<long double>
#define ll long long int
#define pl pair<ll, ll>
#define all(a) a.begin(), a.end()
#define forr(i, n) for(ll i=0; i<n; i++) 
#define forr1(i, n) for(ll i=1; i<=n; i++)
using namespace std;
const ld PI =3.1415926535897923846;
const ll MOD = 1e9+7;
vl a;
void recursive(ll i)
{
    if(i>3234566669)
    {
        return;
    }
    a.pb(i);
    if(i<9)
    {
        recursive(i+1);
        recursive(i*10+(i-1));
        recursive(i*10+i);
        recursive(i*10+i+1);
        return;
    }
    else if(i%10==9)
    {
        recursive(i*10+9);
        recursive(i*10+8);
        return;
    }
    else if(i%10==0)
    {
        recursive(i*10+1);
        recursive(i*10);
        return;
    }
    else
    {
        ll dig=i%10;
        recursive(i*10+dig-1);
        recursive(i*10+dig);
        recursive(i*10+dig+1);
        return;
    }
}
void solve()
{
    ll k;
    cin>>k;
    recursive(1);
    sort(all(a));
    /*forr(i, a.size())
    {
        cout<<a[i]<<" ";
    }*/
    cout<<a[k-1];
}
int main()
{
    ll test=1;
    //cin>>test;
    while(test--)
        solve();
}


Measured memory_bytes: 4304
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin >> N;
  int A[N],B[N],C[N];
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  for(int i = 0; i < N; i++){
    cin >> B[i];
  }
  for(int i = 0; i < N; i++){
    cin >> C[i];
  }
  sort(A,A+N);
  sort(C,C+N);

  long long Ans = 0;
  for(int i = 0; i < N; i++){
    Ans += (lower_bound(A,A+N,B[i])-A)*(C+N-upper_bound(C,C+N,B[i]));
  }

  printf("%lld\n",Ans);
  return 0;


}


Measured memory_bytes: 1408
n = int(raw_input())
d = map(int, raw_input().split())
dict = {}
for i in range(n):
    if dict.has_key(d[i]):
        dict[d[i]] += 1
    else:
        dict[d[i]] = 1
dict = sorted(dict.items())
ans = []
for i in range(len(dict)-1, -1, -1):
    if dict[i][1] > 3:
        if len(ans) == 0:
            ans = [dict[i][0], dict[i][0]]
            break
        else:
            ans.append(dict[i][0])
            break
    elif dict[i][1] > 1:
        if len(ans) > 0:
            ans.append(dict[i][0])
            break
        else:
            ans.append(dict[i][0])
if len(ans) > 1:
    print ans[0]*ans[1]
else:
    print 0

Measured memory_bytes: 23136
import java.util.*;
 
public class Main {
		public static void main(String[] args) {
			 
			Scanner sc = new Scanner(System.in);
	 
			long N = sc.nextInt();
			long M = sc.nextInt();
			char[] S = sc.next().toCharArray();
			char[] T = sc.next().toCharArray();
			long g = gcd(N,M);
			long L = (N * M) / g;
			boolean flag = true;
	 
			for(long i = 0;i<g;i++) {
				if(S[(int)(N/g * i)] != T[(int)(M/g *i)]) {
					flag = false;
				}
			}
	 
			if(flag) {
				System.out.println(L);
			}else {
				System.out.println("-1");
			}
		    sc.close();
		}
	 
	 
	    private static long gcd(long m, long n) {
	        if(m < n) return gcd(n, m);
	        if(n == 0) return m;
	        return gcd(n, m % n);
	    }
}

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

int main(){
  int n,mx=0;
  map<string,int>S;
  string s;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>s;
    if(S.count(s)){
      S[s]++;
    }else{
      S[s]=0;
    }
  }
  for(auto m:S){
    mx=max(mx,m.second);
  }
  for(auto m:S){
    if(m.second==mx)cout<<m.first<<endl;
  }
}

Measured memory_bytes: 25216
S = input()
N = len(S)
mod = 2019

cnt = [0 for _ in range(2019)]
S = S[::-1]
wk = 0
cnt[0] = 1

for i in range(0,N):
  wk = (wk + int(S[i]) * pow(10,i,mod)) % mod
  #print(i,wk)
  cnt[wk] += 1
  
ans = 0
for i in range(2019):
  m = cnt[i]
  ans += m * (m-1) // 2
  
print(ans)

Measured memory_bytes: 68372
#include<cstdio>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}
int main(){
int n,i,j;
ll d[10],v[10],t[10];
while(scanf("%d",&n) && n){
t[0]=1;
for(i=0;i<n;i++){
scanf("%lld%lld",&d[i],&v[i]);
if(i){
ll T=t[i]=t[i-1]*d[i-1]*v[i];
for(j=0;j<i;j++){
t[j] *= d[i]*v[i-1];
T=gcd(T,t[j]);}
for(j=0;j<=i;j++)t[j]/=T;}}
for(i=0;i<n;i++)printf("%lld\n",t[i]);}}

Measured memory_bytes: 0
n = int(input())
a = [int(input()) for i in range(n)]

index = 0
count = 1
tf = False

while True:
  if a[index]==2:
    tf = True
    break
  else:
    index=a[index]-1
    if count == n:
      break
    else:
      count += 1
if tf:
    print(count)
else:
  print(-1)


Measured memory_bytes: 7084
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL -1
using namespace std;
const int64_t MOD = 1e9 + 7;

int main() {
	int a, b, c;
	cin >> a >> b >> c;

	bool bl = false;
	if ((b - a) == (c - b)) {
		bl = true;
	}

	cout << (bl ? "YES" : "NO") << endl;
}

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

int main(){
	string s; cin>>s;
	int k=s.size();
	int ans=0;
	rep(i,k) ans+=s[i]-'0';
	int n=stoi(s);
	if(n%ans==0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define endl    '\n'
using namespace std;

typedef long long ll;

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

    int t, n;

    for (int i = 0; i < 4; ++i) {
        cin >> t >> n;

        if (t == 1) n *= 6000;
        if (t == 2) n *= 4000;
        if (t == 3) n *= 3000;
        if (t == 4) n *= 2000;

        cout << n << endl;
    }

    return 0;
}




Measured memory_bytes: 3200
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

int solve(string s){
  int sum=0;
  if(isdigit(s[0])){
    istringstream iss(s);
    iss >> sum;
    return sum/2+1;
  }
  vector<int> data;
  for(int i=0, j=0, k=0; i<s.size(); ++i){
    if(isdigit(s[i])) continue;
    if(s[i]=='[') ++k;
    if(s[i]==']') --k;
    if(!k){
      data.push_back(solve(s.substr(j+1,i-j-1)));
      j=i+1;
    }
  }
  sort(data.begin(), data.end());
  for(int i=0; i<=data.size()/2; ++i) sum+=data[i];
  return sum;
}

int main(){
  int n;
  string s;
  cin >> n;
  for(int i=0; i<n; ++i){
    cin >> s;
    cout << solve(s.substr(1, s.size()-2)) << endl;
  }
  return 0;
}

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

#define MAX 150
#define MAXL 1000

int C[MAXL + 1][MAXL + 1];

int lec(string X, string Y)
{
	int XL = X.length();
	int YL = Y.length();
	X = ' ' + X;
	Y = ' ' + Y;
	for (int i = 0; i <=XL; i++)
		C[i][0] = 0;
	for (int i = 0; i <=YL; i++)
		C[0][i] = 0;
	for (int i = 1; i <=XL; i++)
	{
		for (int j = 1; j <=YL; j++)
		{
			if (X[i] == Y[j])
			{
				C[i][j] = C[i - 1][j - 1] + 1;
			}
			else if (C[i - 1][j] > C[i][j - 1])
			{
				C[i][j] = C[i - 1][j];
			}
			else{
				C[i][j] = C[i][j - 1];
			}
		}
	}
	return C[XL][YL];
}

int main()
{
	int q;
	string x, y;
	cin >> q;
	for (int i = 0; i<q; i++)
	{
		cin >> x >> y;
		cout << lec(x, y) << endl;
	}
	return 0;
}







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

string s;

int main() {
    cin>>s;
    string t=s; reverse(t.begin(),t.end());
    int cnt=0;
    for (int i=0; i<s.size()/2; i++) {
        if (s[i]!=t[i]) cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long a,h,s,i,n;

int main()
{
    cin>>h>>n;
    for(i=1;i<=n;i++){
        cin>>a;
        s+=a;
    }
    if(s>=h)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}


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

using namespace std;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define sz size
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORN(i,a,b) for(int i=a;i<=b;i++)
#define FORRN(i,a,b) for (int i=(a);i>=(b);i--)
#define FORR(i,a,b) for (int i=(a);i>(b);i--)
typedef unsigned long long ull;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); //Fast I/O
    cin.tie(0);
    cout.tie(0);
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);

    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll>> A;

    FOR(i,0,n){
        ll a,b;
        cin >> a >> b;
        A.pb(mp(a,b));
    }

    sort(A.begin(),A.end());

    ll res=0;

    FOR(i,0,n){
        ll mn=min(m,A[i].ss);
        m-=mn;
        res+=mn*A[i].ff;
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 2420
import java.util.Scanner;
public class Main {
        public static void main(String[] args){
        final Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] heap=new int[n+1];
        for(int i=1;i<=n;i++) heap[i]=sc.nextInt();

        for(int i=1;i<=n;i++) {
                System.out.print("node "+i+": key = "+heap[i]+", ");
                if(parent(i)>=1) System.out.print("parent key = " +heap[parent(i)]+", ");
                if(left(i)<=n) System.out.print("left key = "+heap[left(i)]+", ");
                if(right(i)<=n) System.out.print("right key = "+ heap[right(i)]+", ");
                System.out.println("");
        }

        }

        private static int parent(int x){
                return x/2;
        }

        private static int left(int x){
                return 2*x;
        }

        private static int right(int x){
                return 2*x+1;
        }

}

Measured memory_bytes: 27352
<?php

    $data = explode(" ", trim(fgets(STDIN)));
    $x = $data[0];
    $y = $data[1];
    $z = $data[2];
    
    $ans = 0;
    while(true){
        $s = $x%2 + $y%2 + $z%2;
        if($s>0){
            echo $ans;
            break;
        }
        if($x == $y && $y == $z){
            echo -1;
            break;
        }
        $ans++;
        $a = $y/2 + $z/2;
        $b = $z/2 + $x/2;
        $c = $x/2 + $y/2;
        $x = $a;
        $y = $b;
        $z = $c;
    }
    
?>

Measured memory_bytes: 4604
//Created by Young Charlie
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long

int main() {
	int n, k, q; cin>>n>>k>>q;
	vector<int> scores(n, k - q);
	while(q--){
		int x; cin>>x;
		scores[--x]++;
	}
	for(int x: scores){
		cout<<(x > 0 ? "Yes\n" : "No\n");		
	}
}


Measured memory_bytes: 1024
#include <stdio.h>

int array_pri[5637] = { 0 };

void chack_prime(int num)
{
	int i, no;
	int prime = 0;
	
	for(no = 2; no<num; no++){
		for(i=2; i<no; i++){
			if(no % i == 0)
				break;
		}
		if(no%5 != 1)
			continue;
		else if(no == i){
			prime++;
			array_pri[prime-1] = no;
		}
	}
}

int main(void)
{
	int n;
	int i;
	
	scanf("%d", &n);
	
	chack_prime(55555);
	
	for(i=0; i<n-1; i++)
		printf("%d ", array_pri[i]);
	printf("%d", array_pri[n-1]);
	
	return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <string.h>

int LCS(char *, char *);

int main() {
	int n, l;
	int i, j;
	char buf[1024], X[1024], Y[1024];
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf(" %s", X);
		scanf(" %s", Y);
		l = LCS(X, Y);
		printf("%d\n", l);
	}

	return 0;
}

int LCS(char *X, char *Y) {
	int m, n;
	int i, j;
	int c[1024][1024] = {0};
	m = strlen(X);
	n = strlen(Y);

	for (i = 0; i <= m; i++) {
		c[i][0] = 0;
	}
	for (j = 0; j <= n; j++) {
		c[0][j] = 0;
	}

	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			if (X[i - 1] == Y[j - 1]) {
				c[i][j] = c[i - 1][j - 1] + 1;
			} else if (c[i - 1][j] >= c[i][j - 1]) {
				c[i][j] = c[i - 1][j];
			} else {
				c[i][j] = c[i][j - 1];
			}
		}
	}

	return c[m][n];
}


Measured memory_bytes: 5956
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int x, k, d;

signed main() {
	cin >> x >> k >> d;
	if (x < 0) x = -x;
	
	if (k <= x / d) {
		cout << x - k * d << endl;
		return 0;
	}
	
	int x2 = x - (x / d) * d;
	int k2 = k - x / d;
	if (k2 % 2 == 0) {
		cout << x2 << endl;
	}
	else {
		cout << abs(x2 - d) << endl;
	}
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
#define pb push_back
#define mp  make_pair
#define loop(a,n) for(long long i=a;i<n;i++)
#define vil vector<long long int>
#define vi vector<int>
#define sz(v) v.size()
#define setbits(x)          __builtin_popcountll(x)
#define ff first
#define ss second
using namespace std;

int nCrevenoroddfinder(int n,int r)
{
    int a=r;
    int b=n-r;
    for(int i=0;i<30;i++)
    {
        int x=1<<i;
        if((x&a)&&(x&b))
        {
            return 0;//even
        }
    }
    return 1;//odd
}

ll gcd(ll a, ll b) {
  if (a == 0)return b;
  return gcd(b % a, a);
}
bool isperfect(ll n) {
  ll y = sqrt(n);
  if (n % y == 0 && y * y == n)return true;
  return false;
}
bool comp(pair<int,int> a, pair<int,int> b) {
    if(a.first == b.first) return a.second>b.second;
  return a.first < b.first;
}
 ll powi(ll a, ll b) {
  ll ans = 1;
  while (b > 0) {
    if (b & 1)ans = (ans * a);
    b = b >> 1;
    a = (a * a);
  }
  return ans;
}
bool isprime(ll n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)return false;
  }
  return true;
}
bool prime[10000000];
void seive() {

  prime[1] = true;
  for (int i = 2; i * i < 10000000; i++) {

    if (prime[i])continue;
    for (int j = i * i; j < 10000000; j += i) {
      prime[j] = true;
    }

  }
}

int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll n,m;cin>>n>>m;
  ll x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  ll dp[n+1][m+1];
  
  for(int i=0;i<n+1;i++){
      for(int j=0;j<=m;j++) dp[i][j]=INF;
  }dp[x1][y1]=0;
  pair<ll,ll> dir[4]={{1,0},{0,1},{-1,0},{0,-1}};
  map<pair<ll,ll>,bool> mp;
  deque<pair<ll,ll>> q;
  q.push_front({x1,y1});
  mp[{x1,y1}]=true;
  ll mini=0;ll f=0;
  //cout<<x1<<x2;
  while(!q.empty()){
      pair<ll,ll> p=q.front();
      q.pop_front();
      if(p.ff==x2&&p.ss==y2){
          f=1;
          break;
      }

      for(int i=0;i<4;i++){
          ll x=p.ff+dir[i].ff;
          ll y=p.ss+dir[i].ss;
          if(x<1||y<1||x>n||y>m) continue;
          
          if(s[x-1][y-1]=='.'&&dp[x][y]>dp[p.ff][p.ss]){
              q.push_front({x,y});
              mp[{x,y}]=true;
              dp[x][y]=dp[p.ff][p.ss];
          }
      }
              ll x=p.ff,y=p.ss;
              ll lx=min(1ll,x-2);
              ll rx=min(n,x+2);
              ll ly=min(1ll,y-2);
              ll ry=min(m,y+2);
              for(int i=x-2;i<=x+2;i++){
                    for(int j=y-2;j<=y+2;j++){
                                        if(i<1||j<1||i>n||j>m) continue;
                            if(s[i-1][j-1]=='.'&&dp[i][j]>dp[p.ff][p.ss]+1){
                                 q.push_back({i,j});
                                 mp[{i,j}]=true;
                                 mini++;
                                 dp[i][j]=dp[p.ff][p.ss]+1;
                            }
                    }
              }
  }
  if(f==0) mini=-1;
  else mini=dp[x2][y2];
  cout<<mini;
}



  


Measured memory_bytes: 38456
function main(input) {
  var N = input[0]-0;
  var map = {};
  for(var i=1;i<=N;i++){
    var str = i.toString();
    var start = str[0];
    var end = str[str.length-1];
    if(end=="0") continue;
    var key = start + "_" + end;
    map[key] = (map[key]||0)+1;
  }
  var ans = 0;
  Object.keys(map).forEach(key=>{
    var start = key.split("_")[0];
    var end = key.split("_")[1];
    ans += map[key]*(map[end+"_"+start]?map[end+"_"+start]:0);
  });
  console.log(ans);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


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

#define FOR(i,a) for(int i=0;i<a;i++)
#define inf 612695281

int hoge =0;
int chain[10002][2];
int n;


int solve(int where,int h){
	int copy=chain[where][0];
	chain[where][0]--;
	int re=0;
	int b=where;
	int a=where;
	//cout<<a<<b;
	if(h==0 and b==0){chain[where][0]=copy;/*cout<<"W"<<endl;*/return re;}
	if(h==1 and a==hoge-1){chain[where][0]=copy;/*cout<<"E"<<endl;*/return re;}
	if(h==0 and chain[b-1][0]<3){chain[where][0]=copy;/*cout<<"T"<<endl;*/return re;}
	if(h==1 and chain[a+1][0]<3){chain[where][0]=copy;/*cout<<"U"<<endl;*/return re;}
	
	if(0==0){
		//cout<<"     "<<b<<"    ";
		//cout<<chain[b-1][1]<<chain[b+1][1];
		if(chain[b][0]!=0 or chain[b-1][1]!=chain[b+1][1]){
			if(h==0){re+=chain[b-1][0]+1;b=b-2;/*cout<<"R";*/}
			else{re+=chain[a+1][0]+1;a=a+2;/*cout<<"K";*/}
		}
		else if(h==0){re+=chain[b-1][0]+1+chain[b+1][0];b=b-2;a=a+2;/*cout<<"L";*/}
		else{re+=chain[b-1][0]+1+chain[b+1][0];b=b-2;a=a+2;/*cout<<"P";*/}
	}
	while(1){
		if(b>=0 and a<=hoge-1){
			if(chain[a][1]==chain[b][1]){
				if(chain[b][0]+chain[a][0]>=4){
					re+=chain[b][0]+chain[a][0];
					b--;a++;
					continue;
				}
			}
		}
		break;
	}
	/*cout<<" "<<re;*/
	chain[where][0]=copy;
	return re;
}

int main(){
	while(1){
	cin>>n;
	if(n==0){break;}
	FOR(i,10002){chain[i][0]=chain[i][1]=0;}
	hoge=0;
	int last=0;
	int howlong=0;
	FOR(i,n){
		int u;
		cin>>u;
		if(u==last or last==0){howlong++;last=u;}
		else{
			chain[hoge][1]=last;
			last=u;
			chain[hoge][0]=howlong;
			howlong=1;
			hoge++;
		}
	}
	chain[hoge][1]=last;chain[hoge][0]=howlong;hoge++;
	//FOR(i,hoge){cout<<chain[i][0]<<chain[i][1]<<endl;}
	int ans=-inf;
	FOR(i,hoge){
		ans=max(ans,solve(i,0));//cout<<endl;
		ans=max(ans,solve(i,1));//cout<<endl;
	}
	cout<<n-ans<<endl;
}
return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define ll long long
#define REV(v) reverse(v.begin(), v.end());
#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, start, stop) for (int i = start; i < stop; i++)
#define FORR(i, start, stop) for (int i = start; i > stop; i--)
#define SORT(v, n) sort(v, v + n);
#define SORTR(v, n) sort(v, v + n,greater<int>());
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.begin(), v.end(),greater<ll>());
#define REMOVE(v,n) remove(vector<ll> v,v+v.size(),ll n)
#define ERASE(v,n) v.erase(v.begin()+n);
#define ull unsigned long long
#define pb(a) push_back(a)
#define INF 999999999
#define V(v,i,j) vector(v.begin() + i, v.begin() + j)
#define INSERT(va,vb) va.insert(va.end(), vb.begin(), vb.end())
using namespace std;
typedef vector<int> vint;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
const int MOD = 1000000007;
void chmin(int &a, int b) { if (a > b) a = b; }

//vector< vector<int> > v (size1, vector<int>(size2) );

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin>>N;
    vector<ll> p(N);
    FOR(i,0,N) cin>>p[i];

    ll ans=0;

    FOR(i,0,N-1){
        if(i+1==p[i]){
            swap(p[i],p[i+1]);
            ans++;
        }
    }
    if(p[N-1]==N){
        swap(p[N-1],p[N-2]);
        ans++;
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
set<int>ss;
int main()
{
    int s,n=2;
    scanf("%d",&s);
    a[1]=s;
    ss.insert(s);
    while(1){
        if(a[n-1]&1){
            a[n]=3*a[n-1]+1;
        }
        else{
            a[n]=a[n-1]/2;
        }
        if(ss.count(a[n])){
            printf("%d\n",n);
            return 0;
        }
        ss.insert(a[n]);
        n++;
    }

}

Measured memory_bytes: 256
Sd=input().strip()
T=input().strip()
S=""
for i in range(len(Sd)-len(T),-1,-1):
    sub=Sd[i:i+len(T)]
    for t,s in zip(T,sub):
        if s!="?" and s!=t:
            break
    else:
        S=Sd[:i]+T+Sd[i+len(T):]
        break
if S != "":
    print(S.replace("?", "a"))
else:
    print("UNRESTORABLE")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DEBUG 0
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define dump(o) if(DEBUG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DEBUG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
using pii = pair<int, int>; using vi = vector<int>;
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

signed main() {
	vector<int> area_px = { 2,2,2,0,1,-1, -2,-2,-2,0,1,-1 };
	vector<int> area_py = { 0,1,-1,2,2,2, 0,1,-1,-2,-2,-2 };
	for (int px, py; cin >> px >> py && !(px == 0 && py == 0);) {
		int n; cin >> n;
		vi x(n), y(n);
		rep(i, 0, n)cin >> x[i] >> y[i];
		queue<pii> cur, next;
		cur.emplace(px, py);
		rep(i, 0, n) {
			while (!cur.empty()) {
				pii p = cur.front(); cur.pop();
				rep(j, 0, area_px.size()) {
					int xx = p.first + area_px[j];
					int yy = p.second + area_py[j];
					if (x[i] - 1 <= xx && xx <= x[i] + 1 && y[i] - 1 <= yy && yy <= y[i] + 1) {
						next.emplace(xx, yy);
					}
				}
			}
			swap(cur, next);
		}
		dump(cur.size());
		if (cur.size())cout << "OK" << endl;
		else cout << "NA" << endl;
	}
	return 0;
}

Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e9;
#define sz              200005
#define Fast            ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

vector < ll > arr,brr;

int main(){
    Fast;
    int a,b,c, i,j,k, n,m,t, cs=1;

    cin>>n>>m>>k;
    for(i=0; i<n; i++){
        cin>>a;
        arr.push_back(a);
        if(i)arr[i]+=arr[i-1];
    }
    for(i=0; i<m; i++){
        cin>>a;
        brr.push_back(a);
        if(i)brr[i]+=brr[i-1];
    }
    int tot;
    a=upper_bound(arr.begin(),arr.end(),k)-arr.begin();
    b=upper_bound(brr.begin(),brr.end(),k)-brr.begin();
    tot=max(a,b);

    for(i=0; i<n; i++){
        if(arr[i]>k){
            b=upper_bound(brr.begin(),brr.end(),k-arr[i])-brr.begin();
            tot=max(tot,b);
            break;
        }
        else{
            a=i;
            b=upper_bound(brr.begin(),brr.end(),k-arr[i])-brr.begin();
            tot=max(tot,a+b+1);
        }
    }
    cout<<tot<<endl;


    return 0;
}



Measured memory_bytes: 7924
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,t,ans=0;
	cin>>a>>b>>t;
	if(t+0.5<a){
		cout<<0;
		return 0;
	}
	
	ans=floor((t+0.5)/a)*b;
	cout<<ans;
	return 0;
}
/*
3 2 9
*/

Measured memory_bytes: 256
N, A, B, C = map(int, input().split())
l = [int(input()) for i in range(N)]
INF = 10**9

def dfs(cur, a, b, c):
    if cur == N:
        return abs(a-A) + abs(b-B) + abs(c-C)-30 if min(a, b, c) > 0 else INF
    ret0 = dfs(cur+1, a, b, c)
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10
    ret2 = dfs(cur+1, a, b+l[cur], c) + 10
    ret3 = dfs(cur+1, a, b, c+l[cur]) + 10
    return min(ret0, ret1, ret2, ret3)

print(dfs(0, 0, 0, 0))

Measured memory_bytes: 43996
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define MP make_pair
#define pb push_back

using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef long long LL;

static const int INF = INT_MAX;
static const LL L_INF = LLONG_MAX;
static const int MOD = (1000000000 + 7);

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

    int S;
    cin >> S;
    int h, m, s;
    h = S / 3600;
    S %= 3600;
    m = S / 60;
    S %= 60;
    s = S;
    cout << h << ':' << m << ":" << s << endl;

    return 0;
}


Measured memory_bytes: 3200
S = input()
l = []
for i in S:
    l.append(i)

c = 0
cnt = []
for j in range(len(l)):
    if l[j] == 'A' or l[j] == 'T' or l[j] == 'C' or l[j] == 'G':
        c+=1
        cnt.append(c)
    else:
        cnt.append(c)
        c = 0

#print(cnt)
print(max(cnt))

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

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

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,x,i,l,d=0,ans=1;
	cin >> n >> x;
	for(i=0; i<n; ++i){
		cin >> l;
		d += l;
		if(d<=x){
			++ans;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int fac(int n){
    int sum = 1;
    for(int i=1; i<n+1; i++){
        sum *= i;
    }
    return sum;

}

int paw(int a, int b){
    int c=1;
    for(int i=0; i<3; i++){
        c *= a;
    }
    return c;
}

int main(){
    int N;
    cin >> N;
    int s = paw(N,3);
    // int ans = fac(N)/fac(N-3);
    cout << s << endl;
    return 0;
}


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

#define ll long long
#define ull unsigned long long
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(a,b) for(int a=0;a<(b);++a)
#define REP1(i,n) for(int i=1;i<=(n);++i)
#define debug(x) cerr<<#x<<": "<<x<<'\n'
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define INF (1<<29)
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

template<class T=int>
T in(){T x;cin>>x;return (x);}
template<class T>
void print(T& x){cout<<x<<'\n';}

const int MOD =(int)1e9+7;
const int MAX =510000;

ll fac[MAX],finv[MAX],inv[MAX];
void COMint(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<MAX;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}
ll COM(int n,int k){
    if(n<k) return 0;
    if(n<0||k<0)return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

ll gcd(ll a,ll b){
    if(b==0)return a;
    if(a>b){
        swap(a,b);
    }
    return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    ll g;g=gcd(a,b);
    return a*b/g;
}
bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string S=in<string>();
    int r;r=0;

    int l;l=0;
    REP(i,S.size()){
        if(S[i]=='R'){
            if(l>0){
                REP(j,r-1){
                    cout<<0<<" ";
                }
                cout<<r/2+r%2+l/2<<" "<<r/2+l/2+l%2<<" ";
                REP(j,l-1){
                    cout<<0<<" ";
                }
                r=0;
                l=0;
            }
            r++;
        }else{
            l++;
        }
    }
    REP(j,r-1){
        cout<<0<<" ";
    }
    cout<<r/2+r%2+l/2<<" "<<r/2+l/2+l%2;
    REP(j,l-1){
        cout<<" "<<0;
    }
    cout<<endl;
    //cout<<fixed;
    return 0;
}


Measured memory_bytes: 720
a, b, c, x = 4.times.map { gets.to_i }
cnt = 0
(0..a).each do |i|
    (0..b).each do |j|
        (0..c).each do |k|
            cnt += 1 if i * 500 + j * 100 + k * 50 == x
        end
    end
end

puts cnt

Measured memory_bytes: 14252
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????§?????????
FX????????§????????°?????????????????¨????????????????????¨??§????????????????????????????????¨?????§????????????
????????°????????????100???????????? 1000???????????????????????????????????? 1?????? 108???????????£??????????£??????¨???
(108??? ?????? 100???) ???? 1000?????? == 8000??????????????????????????¨?????§????????????

???????????¨????????????????????? t ?????????????????? Rt (t=0,1,2,,,n???1)???
??\?????¨??????????????????????????§??????????????? Rj???Ri (????????????j>i ??¨??????) ????????§??????
?±??????????????????????
"""
import math

# ?????????
cnt = -1000000000

n = int(input().strip())
min = int(input().strip())

for i in range(1,n):
    a =int(input().strip())
    x = a - min
    if cnt < x:
        cnt = x
    if min > a:
        min = a
print(cnt)

Measured memory_bytes: 7768
#include<iostream>

int main(){

	int n, k;
	while (std::cin >> n >> k){

		if (n == 0 && k == 0)break;

		int data[100001] = { 0 };
		for (int i = 1; i <= n; i++){
			std::cin >> data[i];
		}
		for (int i = 1; i <= n; i++){
			data[i] += data[i - 1];
		}

		int max = 0;
		for (int i = k; i <= n; i++){
			int sum = data[i] - data[i - k];
			if (sum > max)max = sum;
		}

		std::cout << max << std::endl;
	}
	return 0;
}

Measured memory_bytes: 1556
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,dp[310][310],w[310][310];
char ch[400][400];
int solve(int k){
	memset(w,0x00,sizeof w);
	for (int i=n;i;i--)
		for (int j=n;j;j--)
			w[i][j]=w[i+1][j+1]+(ch[i][k]==ch[j][k+1]);
	memset(dp,0x3f,sizeof dp);
	dp[1][1]=0;
	for (int i=1;i<=n+1;i++)
		for (int j=1;j<=n+1;j++){
			if (i!=1) dp[i][j]=dp[i-1][j]+w[i-1][j];
			if (j!=1) dp[i][j]=min(dp[i][j],dp[i][j-1]+w[i][j-1]);
		}
	return dp[n+1][n+1];
}
int main(){
	scanf("%d%d",&n,&m); int ans=0;
	for (int i=1;i<=n;i++) scanf("%s",ch[n-i+1]+1);
	for (int i=1;i<m;i++) ans+=solve(i);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
int main(){
  int K,S;
  cin >> K >> S;
  
  int count = 0;
  for(int a=0;a<K+1;a++){
    for(int b=0;b<K+1;b++){
        if(0<=S-(a+b) && S-(a+b)<=K){
          count++;
        }
    }
  }
  
  cout << count << endl;
  return 0;
}



Measured memory_bytes: 256
n, k = map(int, input().split())
mod = 998244353
lr = []
s = set()
for i in range(k):
  l,r = map(int, input().split())
  for j in range(l,r+1):
    s.add(j)
  lr.append([l,r])

dp = [0 for i in range(n+1)]
dp[1] = 1
tot = [0 for i in range(k)]

for i in range(1,n+1):
  for j in range(k):
    l,r = lr[j][0],lr[j][1]
    if i-l < 1:
      continue
    tot[j] += dp[i-l]
    if i-r > 1:
      tot[j] -= dp[i-r-1]
    dp[i] += tot[j]
    dp[i] %= mod
print (dp[n])

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

using namespace std ;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll ;
typedef vector<int> vint;
typedef vector<double> vdbl ;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int>> vvint;
typedef vector<pair<int,int>> vpii ;
typedef vector<pair<ll,ll>> vpll ;
typedef priority_queue<int, vector<int>, greater<int>> spqint ; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll ; //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int>> bpqint ; //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll ; //大きい順に取り出し


#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++) 
#define FOR(i, a, b) for(int (i) = a; (i) < (int)b; i++)
#define IREP(i,v) for(auto i=v.begin(); i !=v.end(); i++)
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(),(v).end()
#define SZ(x)  (ll)x.size()
#define SP(x)  setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[8] = {1, 0 -1, 0, -1, 1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}
//-----------------------------------------


const int dz[3] = {-1,0,1} ;
vll vec ;

void dfs(int x,string s){
  if(SZ(s)==11){
    return ;
  }
  vec.PB(stol(s)) ;
  REP(i,3){
    if(x+dz[i]>=0 && x+dz[i]<=9){
      dfs(x+dz[i],s+TS(x+dz[i])) ;
    }
  }
  return ;
}
//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  FOR(i,1,10){
    dfs(i,TS(i)) ;
  }
  sort(ALL(vec)) ;
  int n ;
  cin >> n ;
  cout << vec[n-1] <<endl ;
  return 0 ;
}



Measured memory_bytes: 2420
n,m,c=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
ct=0
for i in range(n):
    a=[int(x) for x in input().split()]
    su=0
    for j in range(len(a)):
        su+=a[j]*b[j]
    #print(su)
    if(su+c>0):
        ct+=1
print(ct)


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

using namespace std;

typedef long long ll;
const int Nmax = 1e5 + 5;

int x, y, z, a, n, i;

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
    {
        cin >> a;
        if(a&1) ++x;
            else if(a%4==2) ++y;
                else ++z;
    }

    if((!y && x<=z+1) || x<=z) cout << "Yes\n";
        else cout << "No\n";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
#define pb push_back

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;
const double PI = acos(-1.0);


long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a * g / b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}



const int MAX_N = 100010;


signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n; cin >> n;
	VE a(n), b(n); rep(i, n)cin >> a[i] >> b[i];
	vector<P>pa;
	rep(i, n) {
		pa.push_back(make_pair(b[i], a[i]));
	}
	sort(ALL(pa));
	int now = 0;
	rep(i, n) {
		now += pa[i].second;
		if (now > pa[i].first) {
			cout << "No" << endl; return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

int main () {
	int m = ri();
	int d = ri();
	int cnt = 0;
	for (int i = 1; i <= m; i++) {
		for (int j = 2; j <= d; j++) {
			if (j % 10 >= 2 && j / 10 >= 2 && (j % 10) * (j / 10) == i) cnt++;
		}
	}
	std::cout << cnt << std::endl;
	return 0;
}


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

#define debug(x) cout <<"DEBUG"<<" "<<#x<<":"<<x<<'\n'

//↓0-indexか1-indexでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   //0-index昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++) //1-index昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-index降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-index降順
//rep2 -> 第二引数 m から n 回繰り返し ex) m=5 n=3 なら i=5,i=6,i=7 まで
#define rep2(i,m,n) for(int i = ((int)(m)); i < ((int)(n))+((int)(m)); i++)
#define SIZE(x) ((int)((x).size()))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii; //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;
template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

/* 円周率は M_PI を使おうね */
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;

/*FUNCs=================================================*/

int MOD = 1000000007;

//modにおけるaの逆元a^-1を計算
long long modinv(long long a, long long mod){
    long long m = mod, u=1, v=0;
    while(m) {
        long long t = a/m;
        a -= t * m; swap(a,m);
        u -= t * v; swap(u,v);
    }
    u %= mod;
    if(u < 0) u += mod;
    return u;
}
//modにおける割り算(a/b)は...a%=mod -> a*modinv(b,mod)%modでできる
//逆元はmodとaが互いに素であるときのみ存在
/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(15);
    
    int x, y; cin >> x >> y;
    int a, b;
    if((2*y-x)%3!=0) {
        cout << 0 << '\n';
        return 0;
    } 
    if((2*x-y)%3!=0) {
        cout << 0 << '\n';
        return 0;
    }
    a = (2*x-y)/3;
    b = (2*y-x)/3;
    //debug(a);
    //debug(b);
    if(a<0||b<0) {
        cout << 0 << '\n';
        return 0;
    }
    ll answer = 1;

    for(int i = a+b; i >= b+1; --i) {
        answer *= i%MOD;
        answer %= MOD;
    }
    //debug(answer);
    for(int i = 1; i <= a; i++) {
        answer %= MOD;
        answer = answer*modinv(i, MOD)%MOD;
        answer %= MOD;
    }

    cout << answer << '\n';
}

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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)


int main(void){
  int n,m;
  cin>>m>>n;
  cout<<(m-1)*(n-1)<<endl;




return 0;

}


Measured memory_bytes: 256
// AOJ ITP1_11_D Dice IV
// 2018.5.2 bal4u

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

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()
{
	int n = 0, c = gc();
	do n = 10*n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

int rot[24][7] = {
	{ 0,1,2,3,4,5,6 },{ 0,1,3,5,2,4,6 },{ 0,1,4,2,5,3,6 },{ 0,1,5,4,3,2,6 },
	{ 0,2,6,3,4,1,5 },{ 0,2,3,1,6,4,5 },{ 0,2,1,4,3,6,5 },{ 0,2,4,6,1,3,5 },
	{ 0,3,1,2,5,6,4 },{ 0,3,2,6,1,5,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
	{ 0,4,1,5,2,6,3 },{ 0,4,2,1,6,5,3 },{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },
	{ 0,5,1,3,4,6,2 },{ 0,5,3,6,1,4,2 },{ 0,5,4,1,6,3,2 },{ 0,5,6,4,3,1,2 },
	{ 0,6,2,4,3,5,1 },{ 0,6,3,2,5,4,1 },{ 0,6,5,3,4,2,1 },{ 0,6,4,5,2,3,1 } };

int  a[102][7];
char f[102];

int identical(int *a, int *b)
{
	int i, j;
	memset(f, 0, sizeof(f));
	for (i = 1; i <= 6; i++) f[a[i]]++;
	for (i = 1; i <= 6; i++) f[b[i]]--;
	for (i = 1; i <= 6; i++) if (f[b[i]]) return 0;

	for (j = 0; j < 24; j++) {
		if (b[1] == a[rot[j][1]]) {
			for (i = 2; ; i++) {
				if (i > 6) return 1;
				if (b[i] != a[rot[j][i]]) break;
			}
		}
	}
	return 0;
}

int main()
{
	int n, i, j, f;

	n = in();
	for (i = 0; i < n; i++) {
		for (j = 1; j <= 6; j++) a[i][j] = in();
	}
	f = 1;
	for (i = 0; i < n; i++) for (j = i+1; j < n; j++) {
		if (identical(a[i], a[j])) { f = 0; goto done; }
	}
done:
	puts(f? "Yes": "No");
	return 0;
}



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

vector<string> s = {"SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT"};

int main(){
	string S;
	cin >> S;
	
	rep(i,7){
		if(S == s[i]){
			cout << 7-i << endl;
		}
	}
	
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	while(n!=0){
		if(n%10==9){
			cout<<"Yes";
			return 0;
		}
	    n/=10;
	}
	cout<<"No";
	return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pint;
typedef map<int,int> mint;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+10;

mint mp;
bool f;




int main() {
	int N,M;
	cin>>N>>M;
	int a[M+1],b[M+1];
	Rep(i,M) cin>>a[i]>>b[i];
	Rep(i,M){
		if(b[i]==N){
			mp[a[i]]++;
		}
	}
	f=false;
	Rep(i,M){
		if(a[i]==1 && mp[b[i]]>=1){
			f=true;
			break;
		}
	}
	if(f){
		cout<<"POSSIBLE"<<endl;
	}
	else cout<<"IMPOSSIBLE"<<endl;
	
	return 0;
}

Measured memory_bytes: 11136