akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define PB push_back
#define PPB pop_back
#define ALL(X) (X).begin(),(X).end()
typedef pair<int, int> pii;

static const int INF = 1LL << 61;
static const int MAX_N = 100005;

int n, t, A[MAX_N], D[MAX_N], pos[MAX_N], q, X[1005];
int stop[MAX_N];

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

    fill(stop, stop + MAX_N, INF);
    cin >> n >> t >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> A[i] >> D[i];
    }
    for (int i = 0; i < q; ++i) {
        cin >> X[i];
    }

    for (int i = 2; i <= n; ++i) {
        if (D[i - 1] < D[i] && (A[i] - A[i - 1]) < 2 * t) {
            int temp = (A[i - 1] + A[i]) / 2;
            stop[i - 1] = stop[i] = temp;
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (stop[i] != INF && D[i] == 2) {
            int pos = stop[i];

            for (i = i + 1; D[i] == 2; ++i) {
                if (pos < A[i] - t) {
                    stop[i] = A[i] - t;
                } else {
                    stop[i] = pos;
                }
            }
        }
    }
    for (int i = n; 0 < i; --i) {
        if (stop[i] != INF && D[i] == 1) {
            int pos = stop[i];

            for (i = i - 1; D[i] == 1; --i) {
                if (A[i] + t < pos) {
                    stop[i] = A[i] + t;
                } else {
                    stop[i] = pos;
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        int tmp = X[i];
        if (stop[tmp] != INF) {
            cout << stop[tmp] << endl;
        } else {
            if (D[tmp] == 1) {
                cout << A[tmp] + t << endl;
            } else {
                cout << A[tmp] - t << endl;
            }
        }
    }
}

Measured memory_bytes: 5516
#include<bits/stdc++.h>
using namespace std;
long long S;
int main(){
   scanf("%lld",&S);
   long long  x2,y2,x3,y3;
    if(S!=1e18)y3=x2=(long long)sqrt(S)+1;
    else y3=x2=(int)sqrt(S);
    
   y2=x2*y3-S;x3=1;
	printf("0 0 %lld %lld %lld %lld",x2,y2,x3,y3);
		return 0;
}
/*
999999999999999999
*/

Measured memory_bytes: 256
#include<stdio.h>

int main(void){

int n,sum=0;

scanf("%d",&n);

int d[n];

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

for(int i=0;i<n;i++){
  for(int j=i+1;j<n;j++){
    sum=sum+d[i]*d[j];
  }
}

printf("%d",sum);

return 0;
}


Measured memory_bytes: 1728
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <sstream>
#include <map>
#include<vector>

using namespace std;
typedef long long ll;

ll ans,mx,sum,mn=1e8,cnt; 


bool check(ll n){
	for(ll i=2; i*i<=n; i++){
		if(n%i==0) return false;
	}
	return true;
}

ll b[1000],idx,c[100001];
int main(){
	for(ll i=3; i<=100000; i+=2){
		ll flag=(i+1)/2;
		if(check(i)==true && check(flag)==true){
			b[idx++]=i;
		}
	}
	for(ll i=0; i<idx; i++){
		ll flag=b[i];
		c[flag]++;
	}
	for(ll i=3; i<100001; i++){
		if(c[i]==1) cnt++;
		c[i]=cnt;
	}
	ll q;
	cin>>q;
	for(ll i=0; i<q; i++){
		ll l,r;
		cin>>l>>r;
		cout<<c[r]-c[l-1]<<endl;
	}
}


Measured memory_bytes: 1408
n = gets.chomp.to_i
sums = []
(1..n-1).each do |a|
  sum = a.to_s.split("").map(&:to_i).inject(:+) + (n-a).to_s.split("").map(&:to_i).inject(:+)
  sums.push(sum)
end

puts sums.min


Measured memory_bytes: 2936
import java.io.*;
import java.util.*;
class Main{
    public static void main(String[] args) throws Exception {
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		int[] l = new int[n];
		int ans = 0;
		for(int i = 0;i < n;i++){
			l[i] = saori.saori_hayami();
		}
		Arrays.sort(l);
		for(int i = 0;i < n-2;i++) {
			for(int j = i+1;j < n - 1; j++) {
				int num = l[i] + l[j];
				for(int m = j+1;m < n ;m++) {
					if(l[m] < num) {
						ans++;
					}else {
						break;
					}
				}
			}
		}
		System.out.println(ans);
    }
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}

Measured memory_bytes: 23252
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextInt();
		long b = sc.nextInt();
		long c = sc.nextInt();
		long k = sc.nextLong();
		if (k % 2 == 0) {
			System.out.println(a - b);
		} else {
			System.out.println(b - a);
		}
	}
}


Measured memory_bytes: 21844
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    string s;
    cin >> s;
    bool ok = true;
    if (s[0] != 'A') ok = false;
    int x = -1;
    FOR(i,2,s.length()-2) if (s[i] == 'C') x = i;
    if (x == -1) ok = false;
    else{
        FOR(i,1,s.length()-1){
            if (i != x){
                if (s[i] < 'a' || s[i] > 'z') ok = false;
            }
        }
    }
    cout << (ok ? "AC" : "WA") << endl;
    return 0;
}

Measured memory_bytes: 256
N, a, b, C, D = gets.split.map(&:to_i)
S = gets.chomp

if C < D
  ans = 'Yes'
  ((a-1)..C-2).each do |i|
    if S[i..(i+1)] == '##'
      ans = 'No'
      break
    end
  end
  ((b-1)..D-2).each do |i|
    if S[i..(i+1)] == '##'
      ans = 'No'
      break
    end
  end
else
  ans = 'No'
  ([(b-2),0].max..D-2).each do |i|
    if S[i..(i+2)] == '...'
      ans = 'Yes'
    end
  end
  ((a-1)..C-2).each do |i|
    if S[i..(i+1)] == '##'
      ans = 'No'
      break
    end
  end
  ((b-1)..D-2).each do |i|
    if S[i..(i+1)] == '##'
      ans = 'No'
      break
    end
  end
end
puts ans


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

#define all(x) (x).begin(), (x).end()
#define pb push_back

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;

const int mod=1e9+7;

int main(){
	string s;
	int n,k;
	cin>>n>>k>>s;

	s[k-1]=tolower(s[k-1]);

	cout<<s<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N= 1e5 + 5;
const ll mod=1e9 + 7;

typedef long double ld;
ld dist(ll x1,ll y1,ll x2,ll y2){
    ld val = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
    val = sqrt(val);
    return val;
}
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    ll n;
    cin>>n;
    ll x[n],y[n];
    for(ll i=0;i<n;i++)cin>>x[i]>>y[i];
    vector<ll> arr;
    for(ll i=0;i<n;i++)arr.push_back(i);
    ld sum=0;
    do{
        for(ll i=1;i<n;i++){
            sum=  sum+ dist(x[arr[i]],y[arr[i]] , x[arr[i-1]] , y[arr[i-1]]);
        }
    }while(next_permutation(arr.begin(),arr.end()));

    ld div=1;
    for(ll i=1;i<=n;i++)div*=i;
    cout<<fixed<<setprecision(18)<<sum/div;
}



Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  int i, n, p[50], M=0;

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

  for (i = 1; i <= n; i++) {
    if (p[i] == i) {
      M++;
    }
  }

  if (M == n || M == n-2) {
    printf("YES\n");
  } else {
    printf("NO\n");
  }

  return 0;
}


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

int main() {

	string A, B, C;
	cin >> A >> B >> C;

	transform(A.begin(), A.end(), A.begin(), ::toupper);
	transform(B.begin(), B.end(), B.begin(), ::toupper);
	transform(C.begin(), C.end(), C.begin(), ::toupper);

	cout << A[0] << B[0] << C[0] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <bitset>
using namespace std;
//constant
const long long MOD = 1e9+7;
//const long long MOD = ;
const long long INF_LL = 1e18+3; const int INF_int = 1e9+3;
//Macro
#define ll long long
#define rep(i,n) for(int i = 0;i<n;i++)
#define lrep(i,n) for(long long i = 0;i<n;i++)
#define All(a) a.begin(),a.end()
//Debuging tools
#define Debug_Output_ALL(a) for(auto itr = a.begin();itr!=a.end();itr++) cout << *itr << " ";cout << endl;
///library
//DataStructure
template <typename T>
struct segment_tree{
    int n = 1;
    std::vector<T> data;
    T unit;
    using Monoid = std::function<T(T,T)>;
    Monoid monoid;
    segment_tree(int a,T unit_,Monoid monoid_){
        while(n<a) n*=2;
        for(int i = 0;i<2*n;i++) data.push_back(unit_);
        unit = unit_;
        monoid = monoid_;
    }
    //0-index
    void change(int i,T k){
        i+=(n-1);
        data[i] = k;
        while(i>0){
            i = (i-1)/2;
            data[i] = monoid(data[2*i+1],data[2*i+2]);
        } 
        return;
    }
    //0-index
    T query(int i,int j){
        return query_(i,j,0,0,n);
    }
    T query_(int i,int j,int k,int l,int r){
        if(i>=r || j<=l) return unit;
        if(i<=l && j>=r) return data[k];
        T teml = query_(i,j,2*k+1,l,(l+r)/2);
        T temr = query_(i,j,2*k+2,(l+r)/2,r);
        return monoid(teml,temr);        
    }
};
//Ad-HocFunc
int hoge(int a){
    int ret = 0;
    while(a>0){
        ret+=(a%2);
        a/=2;
    }
    return ret;
}
//MainFunc
int main(){
    int n;
    string s;
    cin >> n >> s;
    segment_tree<int> tree(n,0,[](int a,int b){return a|b;});
    rep(i,n) tree.change(i,1<<(s[i]-'a'));
    int a,b,c2,q;
    char c1;
    cin >> q;
    vector<int> ans;
    rep(i,q){
        cin >> a;
        if(a==1){
            cin >> b >> c1;
            tree.change(b-1,1<<(c1-'a'));
        }
        else{
            cin >> b >> c2;
            ans.push_back(hoge(tree.query(b-1,c2)));
        }
    }
    rep(i,ans.size()) cout << ans[i] << endl;

}


Measured memory_bytes: 7160
A, B, K = map(int, input().split())

C = max(A, B)
l = []
for n in range(1, C+1):
    if A % n == 0 and B % n == 0:
        l.append(n)
l.sort(reverse=True)

for i in range(len(l)):
    if i + 1 == K:
        print(l[i])

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

vector<int> ans;

void dfs(int num, int d){
    ans.push_back(num);
    if(num > 5000000000) return;

    if(d != 0) dfs(num * 10 + d - 1, d - 1);
    if(d != 9) dfs(num * 10 + d + 1, d + 1);
    dfs(num * 10 + d, d);
}


signed main() {
    int k;
    cin >> k;

    for(int i = 1; i <= 9; i++){
        dfs(i,i);
    }
    sort(ans.begin(),ans.end());
    cout << ans[k - 1] << endl;
}




Measured memory_bytes: 6512
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N-1][N-1]
print(r)

Measured memory_bytes: 46444
#include <iostream>
#include <cstdio>
#include <cassert>

using namespace std;


class Solution{

public:
    long long minbase(long long n, long long s){

        long long b;
        for(b = 2ll; b * b <= n; b ++)
            if(sum(n, b) == s) return b;
        assert(b * b > n);

        if(s == n) return n + 1ll;
        if(s == 1ll) return n;
//        if(s > (b - 1) + (b - 1)) return -1;

        long long res = LONG_LONG_MAX;
        for(long long k1 = 1; k1 < b; k1 ++){
            long long k2 = s - k1;
            if(k2 >= 0 && (n - k2 > 0) && (n - k2) % k1 == 0){
                long long tb = (n + k1 - s) / k1;
                if(k1 < tb && k2 < tb){
                    assert(sum(n, tb) == s);
                    res = min(res, tb);
                }
            }
        }
        return res == LONG_LONG_MAX ? -1 : res;
    }

private:
    long long sum(long long n, long long b){

        long long res = 0ll;
        while(n){
            res += n % b;
            n /= b;
        }
        return res;
    }
};


int main() {

//    cout << Solution().minbase(87654ll, 30ll) << endl;
//    // 10
//
//    cout << Solution().minbase(87654ll, 138ll) << endl;
//    // 100
//
//    cout << Solution().minbase(87654ll, 45678ll) << endl;
//    // -1
//
//    cout << Solution().minbase(31415926535ll, 1ll) << endl;
//    // 31415926535
//
//    cout << Solution().minbase(1ll, 31415926535ll) << endl;
//    // -1
//
//    cout << Solution().minbase(31415926535ll, 31415926535ll) << endl;
//    // -1

//    cout << Solution().minbase(100000000000ll, 1ll) << endl;
//    // 100000000000ll

//    cout << Solution().minbase(1ll, 1ll) << endl;
//    // 100000000000ll

    long long n, s;
    scanf("%lld%lld", &n, &s);
    printf("%lld\n", Solution().minbase(n, s));

    return 0;
}


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

vector<int> a;
int N;

int main(int argc, char** argv)
{
	scanf("%d", &N);
	int temp;
	for (int i = 0; i < N; i++) 
	{
		scanf("%d", &temp);
		a.push_back(temp);
	}

	stable_sort(a.begin(), a.end(), greater<int>());

	temp = 0;
	bool flag = true;

	for (int ele : a)
	{
		if (flag)
			temp += ele;
		else
			temp -= ele;

		flag = !flag;
	}

	printf("%d", temp);
	return 0;
}

Measured memory_bytes: 256
def era(n):
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(2*i, n + 1, i):
                table[j] = 1
    
    return prime_list

def f(n):
    cnt = 0
    for i in data:
        if i[1] >= n-1:
            cnt += 1
    return cnt
 
N = int(input())
s = era(N)
data = []
 
for i in s:
    k = i
    c = 0
    while N // k >= 1:
        c += N // k
        k = k*i
 
    data.append([i,c])
 

print(f(75)+f(15)*(f(5)-1)+f(25)*(f(3)-1)+f(5)*(f(5)-1)*(f(3)-2)//2)

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

#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())
#define endl "\n"

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
void initialize( void );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;
template <typename T, typename K> struct P {
	T a; K b;
};
typedef struct {
	vector <int> to;
	int cost;
} edge;

int main( void ){
	// initialize();
	string S; cin >> S;
	int N = S.size();
	int prev[ 2019 ] = {};
	ll ans = 0;

	prev[ ( int )( S[ 0 ] - '0' ) ] = 1;
	rep( i, 1, N ){
		int num = ( int )( S[ i ] - '0' );
		int now[ 2019 ] = {};
		rep( j, 0, 2019 ){
			if(prev[ j ] != 0){
				int temp = prev[ j ];
				now[ ( j * 10 + num ) % 2019 ] = temp;
			}
		}
		now[ num ]++;
		ans += now[ 0 ];
		rep( i, 0, 2019 ){
			prev[ i ] = now[ i ];
		}
	}
	cout << ans << endl;
}

template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}
void initialize( void ){
	cout << fixed << setprecision( 10 );
}


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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
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; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    int n; scanf("%d",&n);
    int k; scanf("%d",&k);
    int cnt=0;
    rep(i,0,n){
        int p; scanf("%d",&p);
        cnt+=(p>=k);
    }
    printf("%d\n",cnt);
    return 0;
}

Measured memory_bytes: 256
fun main(args:Array<String>){
    val l = readLine()!!.split(" ").map {it.toInt()}
    val sx = l[0]
    val sy = l[1]
    val tx = l[2]
    val ty = l[3]
    var x = sx
    var y = sy
    var first = String()
    var second = String()
    var result = String()
    for(i in 1..(tx+ty-sx-sy)){
        if((y-sy)*(tx-sx)>=(ty-sy)*(x+1-sx)){
            x++
            first = first.plus("R")
        }else{
            y++
            first = first.plus("U")
        }
    }
    for(i in 1..(tx+ty-sx-sy)-1){
        if((y-sy)*(tx-sx)<(ty-sy)*(x-1-sx)){
            x--
            second = second.plus("L")
        }else{
            y--
            second = second.plus("D")
        }
    }
    second = second.plus("L")

    result = first.plus(second).plus("LU").plus(first).plus("RDRD").plus(second).plus("LU")
    println(result)
}

Measured memory_bytes: 65512
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 500005;
const int mod = 998244353;

int main(){
	int n; cin >> n;
	while(n--){
		int x; cin >> x;
		if(x & 1){
			cout << "first" << endl;
			return 0;
		}
	}
	cout << "second" << endl;
}


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

string s1, s2;
int n, m;
int dp[3010][3010];

int rek(int x, int y) {
	if (x == n || y == m) return 0;
	
	int &ret = dp[x][y];
	if (ret != -1) return ret;
	
	if (s1[x] == s2[y]) {
		ret = rek(x+1, y+1) + 1;
	}
	else if (rek(x+1, y) > rek(x, y+1)) {
		ret = rek(x+1, y);
	}
	else {
		ret = rek(x, y+1);
	}
	
	
	return ret;
}

string s;
int h;

void dfs(int x, int y) {
	if (s1[x] == s2[y]) {
		s += s1[x];
		if (s.size() == h) {return;}
	}
	
	if (s1[x] == s2[y]) {
		dfs(x+1, y+1);
	}
	else if (dp[x+1][y] > dp[x][y+1]) {
		dfs(x+1, y);
	}
	else {
		dfs(x, y+1);
	}
}

int main () {
	
	cin >> s1 >> s2;
	n = s1.size();
	m = s2.size();
	memset(dp, -1, sizeof dp);
	h = rek(0, 0);
	if (h) dfs(0, 0);
	cout << s;
	
	return 0;
}

Measured memory_bytes: 36096
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
using namespace std;
typedef long long ll;

int main(){
  int n; cin >> n;
  bool occupied[8];
  fill(occupied,occupied+8,false);
  int free = 0;
  REP(i,n){
    int a; cin >> a;
    if(a<3200){
      occupied[a/400] = true;
    }else{
      free++;
    }
  }
  int fixed = 0;
  REP(i,8) if(occupied[i]) fixed++;
  cout << max(1,fixed) << " " << fixed+free << endl;
  return 0;
}


Measured memory_bytes: 764
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: String,
    }
    let m = &n.parse().unwrap();
    let mut n_ = 0;
    for c in n.to_string().chars() {
        n_ += c as i32 - 48;
    }

    println!("{}", if m % n_ == 0 { "Yes" } else { "No" });
}


Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Math;

class Node
{
    public List<int> children;
    public int Value;

    public Node()
    {
        children = new List<int>();
    }
}

class Graph
{
    public int n;
    public Node[] node;
    public bool[] isVisited;
    public int[] c;
    public int index = 0;

    public Graph(int n)
    {
        this.n = n;
        node = new Node[n];
        isVisited = new bool[n];
        for (int i = 0;i < n; i++)
            node[i] = new Node();
        c = new int[n];
    }

    public void SetEdge(int a,int b)
    {
        node[a - 1].children.Add(b - 1);
        node[b - 1].children.Add(a - 1);
    }

    public void DFS(int v)
    {
        isVisited[v] = true;
        foreach (var i in node[v].children)
        {
            if (!isVisited[i]) DFS(i);
        }
        node[v].Value = c[index];
        index++;
    }

    public void Solve()
    {
        Array.Sort(c);
        DFS(0);
        Console.WriteLine(c.Sum() - c[n - 1]);
        for (int i = 0;i < n; i++)
            Console.Write("{0} ",node[i].Value);
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Graph g = new Graph(n);
        for (int i = 0;i < n - 1; i++)
        {
            int[] ab = Console.ReadLine().Split().Select(int.Parse).ToArray();
            g.SetEdge(ab[0],ab[1]);
        }
        g.c = Console.ReadLine().Split().Select(int.Parse).ToArray();
        g.Solve();
    }
}


Measured memory_bytes: 22460
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int ans = 1;
        if (b == 1) {
            System.out.println(0);
            return;
        }
        b -= a;
        while (b > 0) {
            ans++;
            b -= (a - 1);
        }
        System.out.println(ans);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 22100
parseInt(x)=parse(Int,x)
parseMap(x::Array{SubString{String},1})=map(parseInt,x)

function main()
	n,m = readline()|> split |> parseMap
	a = Tuple[]
	for i in 1:n
		x,y=readline()|> split |> parseMap
		push!(a,(x,y))
	end
	a = sort(a,by=x->x[1])
	k = 0
	c = 0
	for i in 1:n
		if m-k <= a[i][2]
			c += a[i][1]*(m-k)
			break
		else
			k += a[i][2]
			c += a[i][1]*a[i][2]
		end
	end
	println(c)
end

main()


Measured memory_bytes: 173060
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mode        998244353
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323


void solve()
{
       ll n,a,b,c;
       cin>>a>>b>>c>>n;
       if(n&1) cout<<b-a;
       else cout<<a-b;
}


int main()
{
    speed_up
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
    return 0;
}


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

#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-funroll-loops")
#pragma GCC target("avx,sse4")

#define mms(a,n) memset(a,0,sizeof((a)[0])*(n))
#define mmp(a,b,n) memcpy(a,b,sizeof((b)[0])*(n))
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fo(i,l,r) for(register int i=l,_lim_=r;i<=_lim_;i++)
#define fd(i,r,l) for(register int i=r,_lim_=l;i>=_lim_;i--)
#define fos(i,l,r,d) for(register int i=l,_lim_=r;i<=r;i+=d)
#define fol(i,l,r) for(register ll i=l,_lim_=r;i<=_lim_;i++)
#define fdl(i,r,l) for(register ll i=r,_lim_=l;i>=_lim_;i--)
#define fosl(i,l,r,d) for(register ll i=l,_lim_=r;i<=r;i+=d)
#define Clear(a) memset(a,0,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(b))
#define ALL(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ldb;
typedef double db;
typedef pair<int,int> pi;

const int N=100005;
int n,m;bool vi[N];
vector<int>e[N];
int dfs(int u,int fa){
	if(e[u].size()>2)return u;
	for(int v:e[u])if(v!=fa)return dfs(v,u);
	return u;
}

int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),u++,v++,e[u].pb(v),e[v].pb(u);
	fo(i,1,n)if(e[i].size()==1)vi[dfs(i,0)]=true,m++;
	fo(i,1,n)if(vi[i])m--;if(!m)m++;
	printf("%d\n",m);
	return 0;
}

Measured memory_bytes: 6272
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<functional>
using namespace std;
int stoi(string x){stringstream ss;ss<<x;int tmp;ss>>tmp;return tmp;}
string itos(int x){stringstream ss;ss<<x;return ss.str();}
int main(){
	int t[]={500,100,50,10,5,1};
	int n,cnt=0;
	while(cin>>n,n){
	cnt=0;
	n=1000-n;
	for(int i=0;i<6;i++){
	while(t[i]<=n)n-=t[i],cnt++;
	}
	cout<<cnt<<endl;
	}
	return 0;
}

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

const int NMAX = 4e2 + 5;
const int CMAX = 1e3 + 0;

int col[NMAX][4];

map<long long, int> cnt;

inline long long encrypt( int arr[4] ) {
    long long ans = numeric_limits<long long> :: max();
    
    for( int k = 0; k <= 3; k ++ ) {
        ans = min( ans, 1LL * arr[(0 + k) % 4] * CMAX * CMAX * CMAX +
                        1LL * arr[(1 + k) % 4] * CMAX * CMAX +
                        1LL * arr[(2 + k) % 4] * CMAX +
                        1LL * arr[(3 + k) % 4] );
    }
    
    return ans;
}

inline long long encrypt( int a, int b, int c, int d ) {
    int arr[4] = { a, b, c, d };
    return encrypt( arr );
}

inline int countrot( int a, int b, int c, int d ) {
    if( a == b && b == c&& c == d )
        return 4;
    if( a == c && b == d )
        return 2;
    return 1;
}

int main( void ) {
    
    int n;
    cin >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        cin >> col[i][0] >> col[i][1] >> col[i][2] >> col[i][3];
        cnt[encrypt( col[i] )] ++;
    }
    
    long long ans = 0;
    for( int i = 1; i <= n; i ++ ) {
        for( int j = i + 1; j <= n; j ++ ) {
            long long edg1 = encrypt( col[i] ), edg5 = encrypt( col[j] );
            
            cnt[edg1] --; cnt[edg5] --;
            for( int k = 0; k <= 3; k ++ ) {
                long long edg2 = encrypt( col[i][0], col[j][(1 + k) % 4], col[j][(0 + k) % 4], col[i][1] );
                long long edg3 = encrypt( col[i][1], col[j][(0 + k) % 4], col[j][(3 + k) % 4], col[i][2] );
                long long edg4 = encrypt( col[i][2], col[j][(3 + k) % 4], col[j][(2 + k) % 4], col[i][3] );
                long long edg6 = encrypt( col[j][(1 + k) % 4], col[i][0], col[i][3], col[j][(2 + k) % 4] );
                
                long long aux = 1;
                aux *= cnt[edg2] * countrot( col[i][0], col[j][(1 + k) % 4], col[j][(0 + k) % 4], col[i][1] ); cnt[edg2] --;
                aux *= cnt[edg3] * countrot( col[i][1], col[j][(0 + k) % 4], col[j][(3 + k) % 4], col[i][2] ); cnt[edg3] --;
                aux *= cnt[edg4] * countrot( col[i][2], col[j][(3 + k) % 4], col[j][(2 + k) % 4], col[i][3] ); cnt[edg4] --;
                aux *= cnt[edg6] * countrot( col[j][(1 + k) % 4], col[i][0], col[i][3], col[j][(2 + k) % 4] ); cnt[edg6] --;
                ans += aux; cnt[edg2] ++; cnt[edg3] ++; cnt[edg4] ++; cnt[edg6] ++;
            }
            
            cnt[edg1] ++; cnt[edg5] ++;
        }
    }
    
    cout << ans / 3 << endl;
    return 0;
}

Measured memory_bytes: 80128
import java.util.*;
public class Main {
	
	static int MOD = 1_000_000_007;
	static int MAX = 100_000;
	static long[] fac = new long[MAX+1];
	static long[] finv = new long[MAX+1];
	static long[] inv = new long[MAX+1];
	
	static void COMinit() {
		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;
		}
	}
	
	static long cmb(int n, int k){
		if(n < k || k < 0) return 0;
		return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
	}

	public static void main(String[] args) {
		COMinit();
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		if(S == 3) {
			System.out.println(1);
			return;
		}
		long ans = 0;
		for(int i = 0; i < S / 3; i++) {
			int x = S - (i + 1) * 2 - 1;
			if(x >= 1)
				ans = (ans + cmb(x, i)) % MOD;
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 37972
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 85;
const int tmp = 80 * 80 * 2;
int h,w,x;
int a[N][N],b[N][N];
bool dp[N][N][N * N * 4];
int main()
{
    scanf("%d%d", &h, &w);
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            scanf("%d", a[i] + j);
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            scanf("%d", &x), a[i][j] -= x;
    dp[1][1][tmp + a[1][1]] = 1;
    dp[1][1][tmp - a[1][1]] = 1;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            for (int k = 0; k <= tmp * 2; ++k)
                if (dp[i][j][k])
                {
                    dp[i][j + 1][k + a[i][j + 1]] = 1;
                    dp[i][j + 1][k - a[i][j + 1]] = 1;

                    dp[i + 1][j][k + a[i + 1][j]] = 1;
                    dp[i + 1][j][k - a[i + 1][j]] = 1;
                }
    int ans = 1e9;
    for (int k = 0; k <= tmp * 2; ++k)
        if (dp[h][w][k])
            ans = min(ans, abs(tmp - k));
    printf("%d\n", ans);
    return 0;
}

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

#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
#define PB push_back
#define mkp make_pair
#define mins(a,b) a=min(a,b)

typedef long long ll;


map<ll, int> ma;
set<ll> se;

ll myhash(vector<int> &v) {
	ll ret = 0;
	rep(i, v.size()) {
		ret *= 11;
		ret += v[i];
	}
	return ret;
}


vector<int> w;

int dfs(int d, vector<int> &v, bool f) {
	ll h = myhash(v);
	if(f) {
		if(ma.find(h) != ma.end()) {
			return ma[h] + d;
		}
	}
	else {
		if(v == w) {
			return d;
		}
		if(d == (v.size() - 1) / 2) {
			ma[h] = d;
			return 1010;
		}
	}
	if(d == (v.size() - 1) / 2) return 1010;
	int ret = 1010;
	rep(i, v.size()) {
		rep(j, i) {
			reverse(v.begin() + j, v.begin() + i + 1);
			mins(ret, dfs(d + 1, v, f));
			reverse(v.begin() + j, v.begin() + i + 1);
		}
	}
	return ret;
}


int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	rep(i, n) cin >> v[i], v[i]--;
	w.assign(n, 0);
	rep(i, n) w[i] = i;
	if(v == w) {
		cout << 0 << endl;
		return 0;
	}
	int ans = n - 1;
	mins(ans, dfs(0, v, false));
	mins(ans, dfs(0, w, true));
	cout << ans << endl;
}

Measured memory_bytes: 18988
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

const ll max_n = 1001001;
vector<ll> fac(max_n, 0);

void calc() {
    fac[0] = 1;
    for (int i = 1; i < max_n; i++) {
        fac[i] = fac[i-1]*((ll)i);
        fac[i] %= MODLL;
    }
}

int main () {

    ll n,m; cin >>n>>m;

    calc();

    if (abs(n - m) > 1) {
        cout << 0 << endl;
    } else if (n != m) {
        ll ans = fac[n]*fac[m];
        ans %= MODLL;
        cout << ans << endl;
    } else if (n == m) {
        ll ans = fac[n]*fac[m]*((ll)2);
        ans %= MODLL;
        cout << ans << endl;
    } 

    return 0;
}




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

size_t solv(size_t N,
            size_t x,
            std::vector<size_t> const& A) {
  for (size_t i=0; i<N; i++) {
    if (A[i] > x) {
      return i;
    }
    x -= A[i];
  }

  if (x > 0) {
    return N-1;
  }

  return N;
}

int main() {
  size_t N, x;

  std::cin >> N;
  std::cin >> x;

  std::vector<size_t> A(N);

  for (size_t i=0; i<N; i++) {
    std::cin >> A[i];
  }

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

  std::cout << solv(N, x, A) << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <list>
#define INF 10000000000ll
#define MOD 1000000007ll
#define EPS 1e-10
#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define DUMP(a) for(long long dump=0; dump<(ll)a.size(); dump++) { cout<<a[dump]; if(dump!=(ll)a.size()-1) cout<<" "; else cout<<endl; }
#define ALL(v) v.begin(),v.end()
#define pb push_back
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef long double ld;
using namespace std;

int main(){
	int x[10][10];
	REP(i, 10){
		REP(j, 10){
			if(i > j) x[i][j] = 0;
			else if(i == j) x[i][j] = pow(2, i);
			else if((i + 1) == j) x[i][j] = pow(2, i);
			else x[i][j] = 2 * x[i][j-1];
		}
	}
	string s;
	cin >> s;
	int d[s.size()];
	REP(i, s.size()) d[i] = (int)(s[i] - '0');
	ll ans = 0;
	REP(i, s.size()){
		REP(j, s.size()){
			ans += x[i][j] * d[i] * pow(10, s.size() - 1 - j);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
import math
import bisect
prime = [2]
max = 10 ** 5 + 7
limit = int(math.sqrt(max))
data = [i + 1 for i in range(2, max, 2)]

while limit > data[0]:
    prime.append(data[0])
    data = [j for j in data if j % data[0] != 0]
prime = prime + data

x = int(input())
ans = bisect.bisect_left(prime, x)
print(prime[ans])

Measured memory_bytes: 44524
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) range(i,0,b)
#define debug(x) cout << "debug" << x << endl;
using namespace std;

int main(){
    int n;
    while(cin >> n){
        int mi = 10000000, ma = -100000000;
        long long sum = 0;
        int inp;
        rep(i,n){
            cin >> inp;
            if(inp < mi) mi = inp;
            if(inp > ma) ma = inp;
            sum+= inp;
        }
            if(!n){
                mi = ma = sum = 0;
            }
        cout << mi << ' ' << ma << ' ' << sum << endl;
    }
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  int x, a;
  cin >> x >> a;

  cout << (x < a ? 0 : 10) << endl; 

  return 0;
}


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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

vector<int> b, ans;
int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n; b.resize(n);
    rep (i, n) cin >> b[i];

    rep (k, n) {
        reprev (i, b.size()) {
            if (b[i] == i + 1) {
                ans.push_back(b[i]);
                b.erase(b.begin() + i, b.begin() + i + 1);
                break;
            }
        }
    }
    if (!b.empty()) {
        cout << "-1\n";
    } else {
        reverse(all(ans));
        for (int i : ans) cout << i << "\n";
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/rdmd
import std.c.stdio;
void main(){
	long n;
	for(;~scanf("%lld",&n)&&n;){
		long r=0;
		int i=2;
		for(;;i++){
			long x=n-cast(long)i*(i-1)/2;
			if(x<i)break;
			if(x%i==0)r++;
		}
		printf("%lld\n",r);
	}
}

Measured memory_bytes: 2372
#include<bits/stdc++.h>
#define MAX 1024
#define inf 1<<29
#define linf 1e16
#define eps (1e-8)
#define mod 1000000007
#define pi acos(-1)
#define phi (1.0+sqrt(5))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int n;
bool b[MAX];
int s[MAX];

int solve(){
  vpi vp;
  FOR(i,0,n)if(b[i])vp.pb(mp(s[i],i));
  sort(all(vp));
  int res=0;
  bool del[MAX]={};
  FOR(i,0,vp.size()){
    int index=vp[i].s;
    if(del[index])continue;
    res++;
    FOR(j,index+1,n){
      if(!b[j] && s[index]<=s[j])break;
      del[j]=true;
    }
    RFOR(j,index,0){
      if(!b[j] && s[index]<=s[j])break;
      del[j]=true;
    }
  }
  return res;
}

int main()
{
  cin>>n;
  FOR(i,0,n){
    string tmp;
    cin>>tmp>>s[i];
    b[i]=(tmp=="y" ? true : false);
  }
  cout<<solve()<<endl;
  return 0;
}

Measured memory_bytes: 3188
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    string s; cin >> s;
    int n = sz(s),ans=0,a=0;
    for (int i=0;i<n-2;i++){
        string str = s.substr(i,3); 
        if (str=="ABC") {
            ans++; ans += a;
            s[i] = 'B'; s[i+1]='C';
            s[i+2] = 'A'; 
            i++;
        }
        else if (s[i]=='A') a++;
        else a=0;
    }
    cout << ans << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0; 
}
/*

ABC --> BCA... 
 
intput: ABCABC 
output: 3 
 
input: ABCACCBABCBCAABCB 
output: 6 
 
*/

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

#define rep(i,n) for(int i = 0;i < (int)(n);i++)
int main(){
    int a,b;
    char op;
    
    rep(i,20000){
        cin >> a >> op >> b;
        if(op == '?') break;
        if(op == '+') cout << a + b << endl;
        if(op == '-') cout << a - b << endl;
        if(op == '*') cout << a * b << endl;
        if(op == '/') cout << a / b << endl;
    }
}



Measured memory_bytes: 3120
N = int(input())
S = input()

ans = 0
for n in range(1000):
    n = str(n).zfill(3)
    i = 0
    for j in range(N):
        if S[j] == n[i]:
            i += 1
            if i == 3:
                ans += 1
                break

print(ans)


Measured memory_bytes: 40940
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S,T;
  cin>>S>>T;
  int a=0;
  for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)){
      S.at(i)=T.at(i);
      a++;
    }
  }
  cout<<a<<endl;
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, Y;
  cin >> N >> Y;
  bool can = false;
  for (int i=0; i<=N; i++) {
      for (int j=0; j<=N-i; j++) {
          int k = N - (i + j);
          int sum = 10000 * i + 5000 * j + 1000 * k;
          if (sum == Y) {
              can = true;
              cout << i << " " << j << " " << k << endl;
              break;
          }
      }
      if (can) break;
  }
  if (!can) cout << -1 << " " << -1 << " " << -1 << endl;
  return 0; 
}

Measured memory_bytes: 256