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

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.next();

            Console.WriteLine(n.Contains("9")?"Yes":"No");
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
const int MAX_N = 1 << 17;
int n,dat[2*MAX_N-1];
int MAX=(1<<31);

//初期化
void init(int n_){
	n=1;
	while(n<n_) n*=2;
	for(int i=0;i<2*n-1;i++){
		dat[i]=MAX;
	}
}

//k弁目の値をaに変更
void update(int k,int a){
	//葉の節点
	k+=n-1;
	dat[k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[k]=min(dat[k*2+1],dat[k*2+2]);
	}
}

//[a,b)の最小値を求める
//後ろのほうの引数は、計算の簡単のための引数
//kは節点の番号、l,rはその節点が[r,l)に対応づいていることを表す
//したがって、外からquery(a,b,0,0,n)として呼ぶ
int query(int a,int b,int k, int l, int r){
	if(r<=a||b<=l) return MAX;
	if(a<=l&&r<=b)return dat[k];
	else{
		int vl = query(a,b,k*2+1,l,(l+r)/2);
		int vr = query(a,b,k*2+2,(l+r)/2,r);
		return min(vl,vr);
	}
}






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

	//input
	int n_,q;
	cin >>n_ >> q;
	MAX--;
	init(n_);
	for(int i=0;i<q;i++){
		ll a,b,c;
		cin >> a >> b >> c;
		if(a==0)update(b,c);
		else {
			if(b>c)swap(b,c);
			c++;
			cout << query(b,c,0,0,n) << endl;
		}
	}
	

	

}






Measured memory_bytes: 4220
/*input
141421 35623

*/ 
#include <iostream>
#include <bits/stdc++.h>
#include <math.h> 
    
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define gc getchar_unlocked
#define fo(i,n) for(ll i=0;i<n;i++)
#define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define int long long
#define si(x)   scanf("%d",&x)
#define sl(x)   scanf("%lld",&x)
#define ss(s)   scanf("%s",s)
#define pi(x)   printf("%d\n",x)
#define pl(x)   printf("%lld\n",x)
#define ps(s)   printf("%s\n",s)
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define ms(a,x) memset(a, x, sizeof(a));
#define endl "\n"
typedef pair<int, int>  pii;
typedef vector<int>     vi;
typedef vector<pii>     vpii;
typedef vector<vi>      vvi;
int mpow(int base, int exp); 
void ipgraph(int m);
//void dfs(int u, int par);
const int mod = 1000000007;
const int N = 1000000001;
const int MAX = 1e5+1;


int32_t main() {
    IOS;
	int n,k;
	cin>>n>>k;
	int ans = 0;
	for(int i=k;i<=n+1;i++){
		int mini = (i*(i-1)/2)%mod;
		int maxi = (n*i-(mini)+mod)%mod;
		ans += (maxi - mini+1+mod)%mod;
	}
	cout<<ans%mod<<endl;
	return 0;
}






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

using namespace std;
 
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl;
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}
typedef long long ll;
#define int ll
 
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
#define Sp(p) cout<<setprecision(25)<< fixed<<p<<endl;
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
// vi dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
const ll MOD = 1000000007;
// const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'


const int N = 112345;
vii G(N);

int dfs(int now) {
    int res = 1;
    vi perm;
    vi ch;
    rep (i, G[now].size()) {
        perm.push_back(i + 1);
        ch.push_back(dfs(G[now][i]));
    }
    sort(all(perm));
    sort(all(ch));
    reverse(all(ch));
    // DEBUG(now);
    // DEBUG_VEC(ch);

    rep (i, perm.size()) {
        chmax(res, perm[i] + ch[i]);
    }
    return res;
}

signed main() {
    int n;
    cin >> n;
    vi a(n - 1);
    rep (i, n - 1) {
        cin >> a[i];
        a[i]--;
        G[a[i]].push_back(i + 1);
    }

    cout << dfs(0) - 1 << endl;
}


Measured memory_bytes: 25292
'''
https://beta.atcoder.jp/contests/agc027/submissions/3201641
'''
n, m = map(int, input().split())
s = list(input())

deg = [{'A':0, 'B':0} for _ in range(n)]  # deg[0 - (n - 1)][0 - 1] = 0
g = [list() for _ in range(n)]  # g[0 - (n - 1)] = []

for i in range(m):  # クエリを配列に代入
    x, y = map(int, input().split())
    x, y = x - 1, y - 1  # 1-indexed -> 0-indexed
    deg[x][s[y]] += 1  # 頂点 x に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    deg[y][s[x]] += 1  # 頂点 y に隣接する頂点の個数を管理 : A か B かに応じて, その文字のカウントを 1 増やす
    g[x].append(y)  # 頂点 x に隣接する頂点のリストに y を追加
    g[y].append(x)  # 頂点 y に隣接する頂点のリストに x を追加

was = [False for _ in range(n)]  # was[j] = True なら 頂点 j は que に追加済み
que = []  # A か B が隣接しないため, 連結リストから除外する頂点

for i in range(n):  # 全頂点をループ
    if deg[i]['A'] == 0 or deg[i]['B'] == 0:  # A か B が隣接しないなら
        que.append(i)  # 除外頂点リスト que に追加
        was[i] = True  #  was[j] = True は, 除外頂点リスト que に追加済を意味する

for q in que:  # A か B が隣接していない, 除外頂点リストの各頂点をループ（ que はループ中に追加されうる）
    for j in g[q]:  # 除外頂点に隣接する頂点をループ
        deg[j][s[q]] -= 1  # "除外頂点に隣接する頂点" に隣接する頂点の個数を管理 : 除外頂点の文字のカウントを減らす
        if deg[j]['A'] == 0 or deg[j]['B'] == 0:  # "除外頂点に隣接する頂点" に A か B が隣接しないなら
            if not was[j]:  # 頂点 j が que に追加済みの頂点でないなら, que に追加する / 追加済みなら, 隣接する頂点の個数管理は, 終了済み
                was[j] = True
                que.append(j)  # 除外頂点リスト que に追加, ループ回数増える

# 除外頂点を取り除いた後に, 頂点が残っていれば, AABB... を作成できる
# 頂点が残っていなければ, つまり, que に全ての頂点が入っていれば, AABB...を作成できない
print('No' if len(que) == n else 'Yes')

Measured memory_bytes: 103152
#include<iostream>
#include<cstdio>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<map>
#include<numeric>
#include<queue>
#include<functional>
#include<cassert>
#include<set>
#define rep(a,b) for(int a=0;a<b;++a)
#define REP(a,b,c,d) for(int a=b;a<c;a+=d)
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define mod 1000000007
using namespace std;
using ll = long long;
using p_i = pair<int, int>;
int main() {
	string S; cin >> S;
	rep(i, S.size()) {
		if (i != S.size() - 1) {
			if (S[i] == 'A'&&S[i+1]=='C') {
				yes;
				return 0;
			}
		}
	}
	no;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int dp[4101][2101],s[4101][2101],n,m,k,ans=0;
inline int S(int x,int y){return y>=0?s[x][y]:0;}
int main()
{
	cin>>n>>m>>k;
	dp[0][0]=s[0][0]=1;
	for(int i=1;i<=m;i++)s[0][i]=s[0][i-1];
	for(int i=1;i<n+m;i++)
	{
		for(int j=0;j<=m;j++)dp[i][j]=(S(i-1,j)-S(i-1,j-k)+mod)%mod;
		for(int j=0;j<=m;j++)s[i][j]=(S(i,j-1)+dp[i][j])%mod;
		int pos=i*(k-1)-n+1;
		while(pos<=m)ans=(ans+(mod+dp[i][pos]-dp[i-1][pos])%mod)%mod,pos+=k-1;
	}
	cout<<ans<<endl;
}


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

// THINK: INT vs LONG LONG?

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

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

	int ans = (int) 1e9 + 5;
	for (int i = 0; i < n; ++i) {
		// start here, go right
		// end at a[i - 1]
		int cur = k - (a[i] - a[i - 1]);
		if (!i) cur = k - (k + a[i] - a.back());
		ans = min(ans, cur);
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3944
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

// #define DEBUG 100

using namespace std;
using ll = unsigned long long;
using pii = pair<int, int>;

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7,maxn = 100010;
const double PI = acos(-1);

int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    int angle, d;
    cin >> angle;

    d = __gcd(angle, 360);
    int mul = angle*360/d;

    cout << mul/angle << endl;
    
    return 0;
}

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

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

  if (a == b && b != c || b == c && c != a || c == a && a != b) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

const int MAX_LENGTH = 3001;

int dp[MAX_LENGTH][MAX_LENGTH];
int path[MAX_LENGTH][MAX_LENGTH];

void print_path(int path_lenght, string &s, int m, int n) {
    stack<char> seq;

    int i = m;
    int j = n;
    while (path_lenght > 0) {
        int dir = path[i][j];
        if (dir == 0) {
            seq.emplace(s[i - 1]);
            --path_lenght;
            --i;
            --j;
        } else if (dir == -1) {
            --i;
        } else {
            --j;
        }
    }

    while (!seq.empty()) {
        char c = seq.top();
        seq.pop();
        cout << c;
    }
    cout << endl;
}

void solve(string &s, string &t) {
    size_t m = s.length();
    size_t n = t.length();

    for (int i = 0; i < 3001; ++i) {
        dp[0][i] = 0;
        dp[i][0] = 0;
        path[i][0] = 0;
        path[0][i] = 0;
    }

    for (size_t i = 1; i <= m; ++i) {
        for (size_t j = 1; j <= n; ++j) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                path[i][j] = 0;
            } else {
                int from_left = dp[i - 1][j];
                int from_top = dp[i][j - 1];
                if (from_left > from_top) {
                    dp[i][j] = from_left;
                    path[i][j] = -1;
                } else {
                    dp[i][j] = from_top;
                    path[i][j] = 1;
                }
            }
        }
    }

    // Reconstruct the path
    int length = dp[m][n];
    // cout << length << endl;
    print_path(length, s, m, n);
}

int main() {
    string s, t;

    cin >> s >> t;
    solve(s, t);

    return 0;
}

Measured memory_bytes: 70656
def euclid(a, b):
  if b == 0:
    gcdr = a
  else:
    gcdr = euclid(b, a%b)
  return gcdr

N, X = map(int,input().split())
Xn = list(map(int,input().split()))

Xn.append(X)
# print(Xn)
Xn.sort()
B = []

for i, x in enumerate(Xn):
    if i < len(Xn)-1:
        B.append(Xn[i+1]-Xn[i])
A = B[0]
# print(B)
for i in B:
    A = euclid(A,i)
print(A)


Measured memory_bytes: 63640
package main

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

func newScanner() *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	return scanner
}

func scanInt() int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}

func scanInts(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
	}
	return a
}

var sc = newScanner()

func main() {
	x, y, a, b, c := scanInt(), scanInt(), scanInt(), scanInt(), scanInt()
	p := scanInts(a)
	q := scanInts(b)
	r := scanInts(c)
	p = append(p, math.MaxInt32)
	q = append(q, math.MaxInt32)
	r = append(r, 0)
	sort.Sort(sort.Reverse(sort.IntSlice(p)))
	sort.Sort(sort.Reverse(sort.IntSlice(q)))
	sort.Sort(sort.Reverse(sort.IntSlice(r)))

	ans := int64(0)
	for i := 1; i <= x; i++ {
		ans += int64(p[i])
	}
	for i := 1; i <= y; i++ {
		ans += int64(q[i])
	}

	for p[x] < r[0] || q[y] < r[0] {
		ans += int64(r[0])
		r = r[1:]
		if p[x] < q[y] {
			ans -= int64(p[x])
			x--
		} else {
			ans -= int64(q[y])
			y--
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 9088
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <map>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
int v[1 + nmax];

int main() {
  int n;
  ll result = 0;
  std::cin >> n;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  for(int i = 1;i <= n; i++) {
    if(v[i - 1] == 1 && 0 < v[i]) {
      v[i]--;
      result++;
    }
    result += v[i] / 2;
    v[i] %= 2;
  }
  std::cout << result;
  return 0;
}


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

int main() {
	int X,N,i,j,ans,l,s;
	cin >> X >> N;
	vector<int> data(100);
	for (i = 0; i < N; i++) {
		cin >> data[i];
	}

	for (i = 0; i < 100; i++) {
		l = X + i;
		for (j = 0; j < N; j++) {
			if (l == data[j]) break;
		}
		if (l == 101) break;
		if (l != data[j]) break;
	}
	for (i = 0; i < 100; i++) {
		s = X - i;
		for (j = 0; j < N; j++) {
			if (s == data[j]) break;
		}
		if (s == 0) break;
		if (s != data[j]) break;
	}

	if (l - X < (s - X)*(-1)) {
		ans = l;
	}
	else if ((s - X)*(-1) < l - X) {
		ans = s;
	}
	else if (l - X == (s - X)*(-1)) {
		ans = s;
	}

	cout << ans << endl;

	return 0;
}

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

using namespace std;

int main(){
    long long a,ans=0;
    cin>>a;
    if(a&1){
        cout<<ans<<endl;
        return 0;
    }
    long long k=5;
    for(int i=1;i<=30;i++){
        ans+=(a/k)/2;
        k*=5;
        if(k>=a)
            break;
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int A,B;
    cin >> A >> B;
    cout << max(0, A - B * 2) << endl;
}

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

int main(){
    ll n, k; cin >> n >> k;

    ll ans = 0;
    if(n < k) ans = min<ll>(n, abs(n - k));
    else {
        ll tmp = n%k;
        ans = min<ll>(tmp, abs(tmp - k));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

struct state {
	int p, l, c;
	state(int p, int l, int c) : p(p), l(l), c(c) {};
	bool operator<(const state &o)const {
		return o.c<c;
	}
};

int main() {
	int N, M, L;
	while(cin >> N >> M >> L, N) {
		int A, B, D, E;
		vvi dist(N, vi(N, INF)), enemy(N, vi(N, INF));
		REP(i, M) {
			cin >> A >> B >> D >> E;
			dist[A-1][B-1] = dist[B-1][A-1] = D;
			enemy[A-1][B-1] = enemy[B-1][A-1] = E;
		}

		vvi cost(N, vi(L+1, INF));
		priority_queue<state> Q;
		Q.push(state(0, L, 0));
		int ans = INF;
		while(!Q.empty()) {
			state st = Q.top();
			Q.pop();

			if(st.p == N-1) {
				ans = min(ans, st.c);
				continue;
			}

			REP(t, N) {
				if(st.p != t && dist[st.p][t] != INF) {
					if(dist[st.p][t] <= st.l) {
						int nl = st.l-dist[st.p][t];
						if(st.c < cost[t][nl]) {
							cost[t][nl] = st.c;
							Q.push(state(t, nl, st.c));
						}
					}
					int nc = st.c+enemy[st.p][t];
					if(nc < cost[t][st.l]) {
						cost[t][st.l] = nc;
						Q.push(state(t, st.l, nc));
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1664
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getInt()
	}
	return ret
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func main() {
	sc.Split(bufio.ScanWords)
	N, x := getInt(), getInt()
	a := getInts(N)
	sort.Ints(a)
	ans := 0
	for i := 0; i < N; i++ {
		if a[i] <= x {
			ans++
			x -= a[i]
		} else {
			x = max(0, x-a[i])
		}
	}
	if x > 0 {
		ans--
	}
	out(ans)
}


Measured memory_bytes: 1776
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <set>
#include <cmath>
#include <cassert>
using namespace std;

// 1-indexed
template <class X>
class FenwickTree {
    int n;
    vector<X> a;
public:
    FenwickTree(int n) : n(n), a(n+1, 0) {}
    X get(int i) {
        X sm = 0;
        for(; i > 0; i -= i&-i) sm += a[i];
        return sm;
    }
    void add(int i, X x) {
        for(; i <= n; i += i&-i) a[i] += x;
    }
    X at(int i){return get(i) - get(i-1);}
};

int main(){
    int N, M;
    cin >> N >> M;
    vector<tuple<int, int, int>> v(N);
    for(int i=0; i<N; i++){
        int l, r;
        cin >> l >> r;
        int diff = r - l + 1;
        v[i] = make_tuple(diff, l, r);
    }
    sort(v.begin(), v.end());

    int idx = 0;
    FenwickTree<int> ft(M+1);
    int base = N;

    vector<int> ans;
    for(int d=1; d<=M; d++){
        for(int i=idx; i<N; i++){
            int diff, l, r;
            tie(diff, l, r) = v[i];
            if(diff < d){
                base--;
                ft.add(l, 1);
                ft.add(r+1, -1);
                idx = i+1;
            }else break;
        }
        int cnt = 0;
        for(int dd=d; dd<=M; dd+=d){
            cnt += ft.get(dd);
        }
        ans.push_back(cnt+base);
    }
    for(int x : ans)
        cout << x << endl;
    return 0;
}


Measured memory_bytes: 5368
#include<stdio.h>
int main(void){
    int H,W;
    int h,w;
    int i=0;
        while(scanf("%d %d",&H,&W)==2){
        if(H==0 && W==0) break;
         for(h=0; h<H; h++){
             if(h==0 || h==H-1){
            for(w=0; w<W; w++){
                printf("#");
            }
            printf("\n");
             }

             else{
                 printf("#");
                 for(i=0;i<W-2;i++){
                     printf(".");
                 }
                 printf("#");
                 printf("\n");
             }
        }
        printf("\n");
        }
    return 0;
}


Measured memory_bytes: 2040
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]


N, M, K = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる
C, D = [0] * K, [0] * K  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

for i in range(K):
    C[i], D[i] = map(int, input().split())
    C[i] -= 1
    D[i] -= 1
    if uf.is_same(C[i], D[i]):
        direct[C[i]].append(D[i])
        direct[D[i]].append(C[i])

ans = [0] * N
for i in range(N):
    ans[i] = uf.group_size(i) - len(direct[i]) - 1
print(*ans)

Measured memory_bytes: 41488
#include <iostream> 
#include <algorithm> 
#include <cstring> 
#include <cstdio>
#include <vector> 
#include <queue> 
#include <cstdlib> 
#include <iomanip>
#include <cmath> 
#include <ctime> 
#include <map> 
#include <set> 
using namespace std; 
#define lowbit(x) (x&(-x)) 
#define max(x,y) (x>y?x:y) 
#define min(x,y) (x<y?x:y) 
#define MAX 100000000000000000 
#define MOD 1000000007
#define pi acos(-1.0) 
#define ei exp(1) 
#define PI 3.141592653589793238462
#define INF 0x3f3f3f3f3f 
#define mem(a) (memset(a,0,sizeof(a))) 
typedef long long ll;
ll n;
ll a[55];
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=50;i++)
    {
        a[i]=n/50+i-1;
    }
    n%=50;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=50;j++)
        {
            a[j]--;
        }
        a[i]+=51;
    }
    printf("50\n");
    for(int i=1;i<=50;i++)
    {
        if(i!=1) printf(" ");
        printf("%lld",a[i]);
    }
    printf("\n");
    return 0;
}

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

int main()
{
    long long N, k;
    cin >> N;

    //for(int i = 1; i < N/2; ++i){
    for(long long i = int(sqrt(N)); i > 0; --i){
    
        //cout << i << ":" << (N%i) << endl;

        if( (N%i) == 0){
            k = (i-1)+(N/i)-1;
            cout << k << endl;
            return 0;
        }
    }

    cout << k << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
	long n = long.Parse(Console.ReadLine());//int.Parseは文字列を整数に変換。
  long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
  long answer = 0;

  for(long i = 0; i < n; i++)
  {
    nums[i] -= i + 1;
  }

  Array.Sort(nums);

  for(int i = 0; i < n; i++)
  {
    answer += Math.Abs(nums[i] - nums[n/2]);
  }
  
	Console.WriteLine(answer);//WriteLineをWriteとすると、改行なしで出力。
	}
}

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

using namespace std;

int main()
{
    int a,b,c,d,e,f,g,h,i,j;
    string s,s1;
    vector<pair<int,int> >v;
    vector<int>v1;
    map<int,int>m;
    map<int,int>::iterator it;

    cin>>a;

    deque<int>dq;

    for(i=1; i<=a; i++)
    {
        cin>>c;
        if(i%2!=0)
        {

            dq.push_front(c);
        }
        else
        {
            dq.push_back(c);
        }
    }

    if(a%2!=0)
    {
        for( i=0; i<a; i++)
        {
            cout<<dq[i]<<" ";
        }
        cout<<endl;
    }
    else
    {
        for( i=a-1; i>=0; i--)
        {
            cout<<dq[i]<<" ";
        }
        cout<<endl;
    }
    return 0;


}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int PREP = (cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(9), 0);
//int SEGV = getenv("D") || (exit(system("D= SEGFAULT_SIGNALS=all catchsegv ./prog.exe") >> 8), 0);
int main() {
    Int K, N; cin >> K >> N;
    vector<int> A(N); for (auto &a : A) cin >> a;
    A.push_back(A[0] + K);
    Int ans = K;
    for (int i = 0; i < N; i++) {
        ans = min(ans, K - (A[i + 1] - A[i]));
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

from decimal import *


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    a, b, c = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    if Decimal(a).sqrt() + Decimal(b).sqrt() < Decimal(c).sqrt():
        print('Yes')
    else:
        print('No')


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 3 9"""
        output = """No"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3 10"""
        output = """Yes"""
        self.assertIO(input, output)


Measured memory_bytes: 6636
#include <cstdio>
#include <algorithm>

using namespace std;
 
int N, K;
int p[1005];
int ans;
 
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 0; i < N; i++) scanf("%d", &p[i]);
  sort(p, p + N);
  for (int i = 0; i < K; i++) ans += p[i];
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 1724
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
    
using namespace std;    
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int main(){

    ll N;
    cin >> N;
    vector<ll> prime;
    for(ll i = 2; i <= N; i++){
        int cnt = 0;
        for(ll j = 1; j <= N; j++){
            if(i % j == 0) cnt ++;
        }
        if(cnt == 2) prime.push_back(i);
    }


    vector<ll> prime_cnt(prime.size());
    for(ll i = 2; i <= N; i++){
        ll p = i;
        int index = 0;
        while(p != 1){
            while(p % prime[index] == 0){
                p = p / prime[index];
                prime_cnt[index] ++;
            }
            index ++;
        }
    }

    ll ans = 1;
    for(ll i = 0; i < prime_cnt.size(); i++){
        ans *= (prime_cnt[i] + 1);
        ans %=  1000000007;
    }
    cout << ans << endl;
}


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

#define REP(i,n) for(int i=0;i<(int)n;++i)

using namespace std;

struct UnionFind {
  vector<int> p;
  UnionFind (int n) : p(n, -1) {}
  int root(int x) { return p[x] < 0 ? x : p[x] = root(p[x]); }
  void merge(int x, int y) { if (root(x) != root(y)) p[root(y)] = x; }
};

int main() {
  while(1){
    int h,w;
    cin>>h>>w;
    if(!h)break;
    vector<string> m(h);
    REP(i,h){
      cin>>m[i];
    }
    UnionFind uf(h*w);
    REP(i,h)REP(j,w-1){
      if(m[i][j] == m[i][j+1])
        uf.merge(i*w+j, i*w+j+1);
    }
    REP(i,h-1)REP(j,w){
      if(m[i][j] == m[i+1][j])
        uf.merge(i*w+j,(i+1)*w+j);
    }
    set<int> roots;
    REP(i,h)REP(j,w)
      roots.insert(uf.root(i*w+j));
    cout << roots.size() << endl;
  }
  return 0;
}

Measured memory_bytes: 3344
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[10000];

int main()
{
    int n,x;
    while(cin>>n>>x)
    {
        int i;
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        int num=0;
        sort(a,a+n);
        for(i=0;i<x;i++)
            num+=a[i];
        printf("%d\n",num);
    }
    return 0;
}

Measured memory_bytes: 3832
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <cstdlib>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}

vector<ll> fact, factinv, inv;
ll mod = 998244353;
void prenCkModp(ll n) {
	fact.resize(n + 5);
	factinv.resize(n + 5);
	inv.resize(n + 5);
	fact.at(0) = fact.at(1) = 1;
	factinv.at(0) = factinv.at(1) = 1;
	inv.at(1) = 1;
	for (ll i = 2; i < n + 5; i++) {
		fact.at(i) = (fact.at(i - 1) * i) % mod;
		inv.at(i) = mod - (inv.at(mod % i) * (mod / i)) % mod;
		factinv.at(i) = (factinv.at(i - 1) * inv.at(i)) % mod;
	}

}
ll nCk(ll n, ll k) {
	return (fact.at(n) * ((factinv.at(k) * factinv.at(n - k)) % mod)) % mod;
}
int modPow(long long a, long long n, long long p) {
	if (n == 0) return 1; // 0乗にも対応する場合
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}

int main() {
	ll X, Y;
	cin >> X >> Y;
	string S = "No";
	if (2 * X <= Y && 4 * X >= Y&&Y%2==0) {
		S = "Yes";
	}
	cout << S << endl;
}

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

using namespace std;

int main()
{
	int n, c, p=0;
	bool pr[1000001];
	fill(pr, pr+1000001, true);
	pr[0] = pr[1] = false;
	
	for(int i = 2; i < 1000001; i++){
		if(pr[i]){
			for(int j = 2*i; j < 1000001; j+=i){
				pr[j] = false;
			}
		}
	}

	while(1){
		cin >> n;
		if(n == 0){
			break;
		}
		c = 0;
		for(int i = 2; i <= n/2; i++){
			if(pr[i]){
				if(pr[n-i]){
					c++;
				}
			}
		}
		cout << c << endl;
	}
	
	return 0;
}

Measured memory_bytes: 0
a = input()
b = input()
c = input()

OFFSETS = 9000


def comp(x, y):
    return (x == '?') or (y == '?') or (x == y)


def check(s, t):
    check_st = [True] * (OFFSETS * 2 + 10)
    for i, si in enumerate(s):
        for j, tj in enumerate(t):
            if not comp(si, tj):
                check_st[i - j + OFFSETS] = False
    return check_st


ans = len(a) + len(b) + len(c)
check_ab = check(a, b)
check_bc = check(b, c)
check_ac = check(a, c)
# print(check_ab)
# print(check_bc)
# print(check_ca)

for b_idx in range(-len(b) - len(c), len(a) + len(c) + 1):
    for c_idx in range(-len(b) - len(c), len(a) + len(b) + 1):
        if check_ab[b_idx + OFFSETS] and check_ac[
                c_idx + OFFSETS] and check_bc[c_idx - b_idx + OFFSETS]:
            l_idx = min(0, b_idx, c_idx)
            r_idx = max(len(a), b_idx + len(b), c_idx + len(c))
            ans = min(ans, r_idx - l_idx)

print(ans)


Measured memory_bytes: 52912
#include<iostream>
#include<string>
#include<vector>
using namespace std;
string word;
vector<string> line;
long long int answer(int);
long long int henkan();
int main() {
	cin >> word;
	line.push_back("");
	line.back().push_back(word[0]);
	cout << answer(1) << endl;
	return 0;
}

long long int answer(int place) {
	if (place == (int)word.size()) {
		return henkan();
	}
	long long int re=0;
	line.push_back("");
	line.back().push_back(word[place]);
	re+=answer(place + 1);
	line.pop_back();
	line.back().push_back(word[place]);
	re += answer(place + 1);
	line.back().pop_back();
	return re;
}

long long int henkan() {
	long long int re=0;
	long long int dummy;
	for (int i = 0; i < (int)line.size(); ++i) {
		dummy = line[i][0]-'0';
		for (int j = 1; j < (int)line[i].size(); ++j) {
			dummy *= 10;
			dummy += line[i][j] - '0';
		}
		re += dummy;
	}
	return re;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	double a[101];
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	double bunbo = 0.0;
	for(int i = 0; i < n; i++){
		bunbo += 1.0 / a[i];
	}
	printf("%.10f\n", 1.0 / bunbo);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e12;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1

ll sq(ll num) { return num*num; }
ll mod_pow(ll x, ll n) {
	if (n == 0)return 1;
	if (n == 1)return x%MOD;
	ll res = sq(mod_pow(x, n / 2));
	res %= MOD;
	if (n % 2 == 1) {
		res *= x;
		res %= MOD;
	}
	return res;
}
ll mod_add(ll a, ll b) { return (a + b) % MOD; }
ll mod_sub(ll a, ll b) { return (a - b + MOD) % MOD; }
ll mod_mul(ll a, ll b) { return a*b % MOD; }

string t, num;

int main() {
	while (cin >> t >> num && !(t == "0"&&num == "0")) {
		ll n = -1;
		bool f = 1;
		vector<int> ans;
		rep(i, (1 << (num.size() - 1))) {
			ll sum = 0;
			vector<int> k;
			ll nn = num[0] - '0';
			rep(j, num.size() - 1) {
				if (i & (1 << j)) {
					nn *= 10;
				}
				else {
					sum += nn;
					k.push_back(nn);
					nn = 0;
				}
				//cout << "!!" << nn << endl;
				nn += num[j + 1] - '0';
			}
			sum += nn;
			//cout << "!" << sum << endl;
			if (nn != 0 || num.back() == '0')k.push_back(nn);
			if (sum <= stoi(t)) {
				if (sum > n) {
					n = sum;
					f = 1;
					ans = k;
				}
				else if (sum == n) {
					f = 0;
				}
			}
		}
		if (!f)cout << "rejected" << endl;
		else {
			if (n == -1)cout << "error" << endl;
			else {
				cout << n << " ";
				rep(i, ans.size()) {
					if (i != 0)cout << " ";
					cout << ans[i];
				}
				cout << endl;
			}
		}
	}
}


Measured memory_bytes: 3180
#include<iostream>
#include<iomanip>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<iomanip>


using namespace std;

int cnt;
//vector<string> memo;

char tonum(char word) {
	if(word == 'R') return '1';
	if(word == 'G') return '2';
	if(word == 'B') return '3';
	if(word == 'W') return '4';
	if(word == 'r') return '5';
	if(word == 'g') return '6';
	if(word == 'b') return '7';
	if(word == 'w') return '8';

	return '0';
}

void calc(int num, string rest, string ing) {
	string bkup_r = rest;
	string bkup_i = ing;

	if(num==9) {
		cnt++; return;
	}

	if(num == 0) {
		for(int i=0; i<9; i++) {
			for(int j=0; j<4; j++) {
				ing.push_back(rest[j%4 + i*4]);
				ing.push_back(rest[(j+1)%4 + i*4]);
				ing.push_back(rest[(j+2)%4 + i*4]);
				ing.push_back(rest[(j+3)%4 + i*4]);
//				if(find(memo.begin(), memo.end(), ing) != memo.end())
//					return;
//				else {
//					memo.push_back(ing); 
					calc(1, rest.erase(i*4, 4), ing);  
//				}
				rest = bkup_r;
				ing = "";
			}
		}
	}
	else if(num<3) {
		for(int i=0; i<rest.size(); i++) {
			if(abs((int)ing[2+(num-1)*4] - (int)rest[i]) == 4) {
				ing.push_back(rest[i%4 + i/4*4]);
				ing.push_back(rest[(i+1)%4 + i/4*4]);
				ing.push_back(rest[(i+2)%4 + i/4*4]);
				ing.push_back(rest[(i+3)%4 + i/4*4]);
//				if(find(memo.begin(), memo.end(), ing) != memo.end())
//					return;
//				else {
//					memo.push_back(ing); 
					calc(num+1, rest.erase(i/4*4, 4), ing);  
//				}
				rest = bkup_r;
				ing = bkup_i;
			}
		}
	}
	else if(num%3 == 0) {
		for(int i=0; i<rest.size(); i++) {
			if(abs((int)ing[3+(num-3)*4] - (int)rest[i]) == 4) {
				ing.push_back(rest[(i+3)%4 + i/4*4]);
				ing.push_back(rest[i%4 + i/4*4]);
				ing.push_back(rest[(i+1)%4 + i/4*4]);
				ing.push_back(rest[(i+2)%4 + i/4*4]);
//				if(find(memo.begin(), memo.end(), ing) != memo.end())
//					return;
//				else {
//					memo.push_back(ing); 
					calc(num+1, rest.erase(i/4*4, 4), ing);  
//				}
				rest = bkup_r;
				ing = bkup_i;
			}
		}
	}
	else {
		for(int i=0; i<rest.size(); i++) {
			if(abs((int)ing[2+(num-1)*4] - (int)rest[i]) == 4 &&
				abs((int)ing[3+(num-3)*4] - (int)rest[(i+1)%4 + i/4*4]) == 4) {
				ing.push_back(rest[i%4 + i/4*4]);
				ing.push_back(rest[(i+1)%4 + i/4*4]);
				ing.push_back(rest[(i+2)%4 + i/4*4]);
				ing.push_back(rest[(i+3)%4 + i/4*4]);
//				if(find(memo.begin(), memo.end(), ing) != memo.end())
//					return;
//				else {
//					memo.push_back(ing); 
					calc(num+1, rest.erase(i/4*4, 4), ing);  
//				}
				rest = bkup_r;
				ing = bkup_i;
			}
		}
	}
}

int main() {
	int n;
	char input;
	string pieces;

	cin >> n;
	for(int t=0; t<n; t++) {
//			memo.clear();
			pieces = "";
		for(int i=0; i<36; i++) {
			cin >> input;
			pieces.push_back(tonum(input));
		}
		cnt = 0;
		calc(0, pieces, "");
		cout << cnt << endl;
	}

	return 0;
}

Measured memory_bytes: 1236
//Ruthless Coding 
#include <bits/stdc++.h>

#define uni(x)      (x).resize(unique(all(x)) - (x).begin())
#define fprint(v)   for(auto x : v) cout << x << ' '
#define ALL(x)      (x).begin(), (x).end()
#define MP(x, y)    make_pair(x, y)
#define PII         pair<int, int>
#define SZ(x)       int((x).size())
#define PB(x)       push_back(x)
#define ll          long long
#define S           second 
#define F           first
#define nl          '\n'

using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
mt19937_64 rnd;

const int N = 2e5 + 5;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    vector<double> a(n);
    for(auto &x : a){
        cin >> x;
    }
    sort(ALL(a));
    double val = a[0];
    for(int i = 1; i < n; i++){
        val = (val + a[i]) / (2.0);
    }
    cout << fixed << setprecision(10) << val;
    return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
typedef long long LL;

int main() {
  int N, K; std::cin >> N >> K;
  if (K == 1) std::cout << 0 << std::endl;
  else        std::cout << N - K << std::endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#include <cstring>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

typedef long long int ll;
using ll = long long int;
using ull = long long unsigned int;
using Int = long long int;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//edit
class Solve {
public:
    void solve() {
        Int N;
        cin >> N;
        vector<Int> A(N);
        for (int i = 0; i < N; ++i) {
            cin >> A[i];
        }

        vector<vector<Int>> iA(N + 1);
        for (int i = 0; i < N; ++i) {
            iA[A[i]].push_back(i);
        }
        if (iA[1].size() == 0) {
            cout << -1 << endl;
            return;
        }

        int ans = -1;
        int pt = 0;
        for (int i = 1; i <= N; ++i) {
            auto tmp = lower_bound(all(iA[i]), pt);
            if (tmp == iA[i].end()) {
                break;
            }
            pt = *tmp;
            ans = i;
        }
        ans = N - ans;
        cout << ans << endl;

    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    Solve().solve();


    return 0;
}


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

using namespace std;

int main()
{
	int N;
	int ans = 0;
	cin >> N;

	vector<int> A(N);
	for (int i = 0;i < N;i++)
		cin >> A[i];
	
	if (A.size() > 2)
	{
		for (int i = N - 1;i > 0;i--)
		{
			if (A[i] == A[i - 1])
			{
				A.erase(A.begin() + i);
				i--;
			}
		}

		for (int i = 0;i < A.size() - 2;i++)
		{
			if ((A[i] < A[i + 1] && A[i + 1] > A[i + 2])
				|| (A[i] > A[i + 1] && A[i + 1] < A[i + 2]))
			{
				ans++;
				i++;
			}
		}
	}

	cout << ans + 1 << endl;

	return 0;
}


Measured memory_bytes: 640
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

import heapq
from math import floor, ceil

def main():
    n, m = LI()
    a_s = LI()
    minus_as = [-i for i in a_s]
    heapq.heapify(minus_as)
    ans = 0
    for i in range(m):
        v = heapq.heappop(minus_as)
        v = ceil(v / 2)
        heapq.heappush(minus_as, v)
    print(-1 * int(sum(minus_as)))





if __name__ == '__main__':
    main()

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

void tes(){
	while (1){
		int n, k;
		cin >> n >> k;
		vector<int>a(n);
		for (int i=0;i<n;i++) cin >> a[i];
		for (int t=0;t<k;t++){
			vector<int>tmp=a;
			for (int i=0;i<n;i++){
				int cnt=0;
				for (int j=0;j<n;j++){
					if (a[j]>=abs(j-i)) cnt++;
				}
				tmp[i]=cnt;
				cout << tmp[i] << " ";
			}
			cout << "\n";
			a=tmp;
		}
	}
}

const int maxk=100;
int n, k, a[200003], bit[200003];

void update(int x, int val){
	while (x<=n){
		bit[x]+=val;
		x+=x&-x;
	}
}

int sum(int x){
	int ret=0;
	while (x>0){
		ret+=bit[x];
		x-=x&-x;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//	tes();
	cin >> n >> k;
	for (int i=0;i<n;i++) cin >> a[i];
	if (k>maxk){
		for (int i=0;i<n;i++) cout << n << " ";
		cout << "\n";
		return 0;
	}
	for (int t=0;t<k;t++){
		memset(bit,0,sizeof bit);
		for (int i=1;i<=n;i++){
			update(max(1,i-a[i-1]),1);
			update(min(n+1,i+a[i-1]+1),-1);	
		}
		for (int i=1;i<=n;i++) a[i-1]=sum(i);
	}
	for (int i=0;i<n;i++) cout << a[i] << " ";
	cout << "\n";
}

Measured memory_bytes: 5216