akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main(void){
    string S, T;
    cin >> S >> T;
    bool result{true};

    for(int i=0; i<S.size(); ++i){
        if(S[i]!=T[i]){
            result = false;
        }
    }
    if(result){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }

}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
#define endl '\n'
#define F first
#define S second
const int MAX_N=4e2+4;

int n;
int a[MAX_N];
ll dp[MAX_N][MAX_N], na[MAX_N][MAX_N];

int main()
{
	memset(dp,0x7F,sizeof(dp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]), dp[i][i]=0, na[i][i]=a[i];
	for(int d=1;d<n;d++) for(int i=1,j=i+d;j<=n;i++,j++) for(int k=i;k<j;k++)
	{
		ll tmp=dp[i][k]+dp[k+1][j]+na[i][k]+na[k+1][j];
		if(dp[i][j]>tmp)
		{
			dp[i][j]=tmp;
			na[i][j]=na[i][k]+na[k+1][j];
		}
		else if(dp[i][j]==tmp)
			na[i][j]=min(na[i][j],na[i][k]+na[k+1][j]);
	}
	printf("%lld\n",dp[1][n]);
	return 0;
}



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

bool Include3(int n){
    if(n%10==3){
        return true;
    }
    n/=10;
    if(n){
      return Include3(n);  
    } 
    return false;
}
void CheckNum(int n){
    if(n%3==0){
        cout << " " << n;
        return;
    }
    if(n>9){
        if(Include3(n)){
            cout << " " << n;
        }
    }
}


int main(void){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
       CheckNum(i);
    }
    cout << endl;
}

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

class Flow{
public:
    int t,s,d;
    bool operator<(const Flow &f)const{
        return f.t>this->t;
    }
};

int main(){
    int n,m;
    while(cin>>n>>m&&!(n==0&&m==0)){
        vector<Flow> v;
        for(int i = 0; i < m; i++){
            Flow f;
            cin>>f.t>>f.s>>f.d;
            v.push_back(f);
        }
        sort(v.begin(),v.end());
        bool isInfected[20001];
        fill(isInfected,isInfected+20001,false);
        isInfected[1]=true;
        int cnt=1;
        for(int i = 0; i < v.size(); i++){
            if(isInfected[v[i].s]&&!isInfected[v[i].d]){
                isInfected[v[i].d]=true;
                cnt++;
            }
        }
        cout<<cnt<<endl;
    }
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin >> n;
    if(n % 2) n *= 2;

    cout << n << endl;

    return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')


Measured memory_bytes: 352836
#include <stdio.h>

int main(void)
{
    char sa[110],sb[110],sc[110],tarn;
    int ai,bi,ci;

    fgets(sa,sizeof(sa),stdin);
    fgets(sb,sizeof(sb),stdin);
    fgets(sc,sizeof(sc),stdin);

    for(ai=0,bi=0,ci=0,tarn='a';;){
        if(tarn == 'a'){
            tarn = sa[ai];
            if(tarn == '\n'){
                printf("A\n");
                break;
            }
            ai++; 
        }else if(tarn == 'b'){
            tarn = sb[bi];
            if(tarn == '\n'){
                printf("B\n");
                break;
            }
            bi++; 
        }else{
            tarn = sc[ci];
            if(tarn == '\n'){
                printf("C\n");
                break;
            }
            ci++; 
        }
    }

    return 0;
}

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

using namespace std;

int a[100005];

int main(){
	int N, ans; cin >> N;
	for(int i = 0; i < N; ++i) cin >> a[i];
	ans = a[0];
	for(int i = 1; i < N; ++i) ans ^= a[i];
	cout << (ans ? "No" : "Yes") << endl;
}

Measured memory_bytes: 640
M,f=1000003,[1]
for i in range(1,M):f.append(f[i-1]*i%M)
for _ in'_'*int(input()):x,d,n=map(int,input().split());t=x*pow(d,M-2,M)%M;print([pow(x,n,M),(M-n>=t>0)*1and f[t+n-1]*pow(f[t-1],M-2,M)*pow(d,n,M)%M][d>0])

Measured memory_bytes: 93804
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[1009], b[1009], dp[1000009];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (b[i] > b[j]) {
				swap(a[i], a[j]);
				swap(b[i], b[j]);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = b[i]; j >= a[i]; j--) {
			dp[j] = max(dp[j], dp[j - a[i]] + 1);
		}
	}
	cout << *max_element(dp, dp + 1000001) << endl;
	return 0;
}

Measured memory_bytes: 6876
#71b
S = list(input())

setS = set(S)
all_alphabet = set([chr(i) for i in range(97, 97+26)])

not_include_alphabet = list(all_alphabet - setS)
not_include_alphabet.sort(reverse=False)

if len(not_include_alphabet)>0:
    print(not_include_alphabet[0])
else:
    print("None")

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

int main() {
  vector<long long>A(3);
  bool check = false;
  for (int i = 0; i < 3; i++) {
    cin >> A.at(i);
    if (A.at(i) % 2 == 0) {
      check = true;
    }
  }
  if (check) {
    cout << 0;
  }
  else {
    sort(A.begin(), A.end());
    cout << A.at(0) * A.at(1);
  }
}

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

#ifdef DEBUG
#include "inc/debug.hpp"
#else
#define debug(...) 42
#endif

int main() {
    int H, W, A, B;
    cin >> H >> W >> A >> B;

    for (int i=0; i<H; ++i) {
        for (int j=0; j<W; ++j) {
            if ((i < B && j < A) || (B <= i && A <= j)) cout << 1;
            else cout << 0;
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define leadinz zero str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
string text="abcdefghijklmnopqrstuvwxyz";
const int maxn=1e6+7;
//        .--------------.
//        | Try First One|
//        '--------------'
//                |     .--------------.
//                |     |              |
//                V     V              |
//              .--------------.       |
//              |      AC.     |<---.  |
//              '--------------'    |  |
//              (True)|  |(False)   |  |
//           .--------'  |          |  |
//           |           V          |  |
//           |  .--------------.    |  |
//           |  |   Try Again  |----'  |
//           |  '--------------'       |
//           |                         |
//           |  .--------------.       |
//           '->| Try Next One |-------'
//              '--------------'
ll bin_pow(ll a,ll b,ll m)
{
    ll res=1;
    a%=m;
    while(b>0)
    {
        if(b&1)
            res=res*a%m;
        b>>=1;
        a=a*a%m;
    }
    return res;
}
bool miller_rabin(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=bin_pow(a,d,n);
    if(x==1 || x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==n-1)
            return true;
    }
    return false;
}
bool prime(ll n,ll k)
{
    if(n==1 || n==4)
        return false;
    if(n<=3)
        return true;
    ll d=n-1;
    while(d%2==0)
        d/=2;
    for(int i=0; i<k; i++)
    {
        if(!miller_rabin(d,n))
            return false;
    }
    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int>v(26,100005);
    int n;
    cin>>n;
    int a[n+2];
    map<int,int>mp;
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);
    int mn=a[0];
    int mx=a[n-1];
    int ans=INT_MAX;
    for(int i=mn; i<=mx; i++)
    {
        int sum=0;
        for(int j=0; j<n; j++)
        {
            int x=abs(i-a[j]);
            sum+=x*x;
        }
        ans=min(sum,ans);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
from collections import deque
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=1)
    return divisors

n,k = map(int,input().split())
a = list(map(int,input().split()))
S = sum(a)
for gcd in make_divisors(S):
    li = deque(sorted([x % gcd for x in a]))
    count = 0
    L = li.popleft()
    R = li.pop()
    while li:
        if L >= gcd-R:
            L -= gcd-R
            count += gcd-R
            R = li.pop()
        else:
            R += L
            count += L
            L = li.popleft()
    count += L
    if count <= k:
        print(gcd)
        exit()

Measured memory_bytes: 74564
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, k, c;
char s[N];
int L[N], R[N];
int main() {
	scanf("%d%d%d", &n, &k, &c);
	scanf("%s", s + 1);
	int cur = 1, d = 0;
	while (cur <= n) {
		if (s[cur] == 'o') {
			L[++d] = cur;
			cur += c;
		}
		cur++;
	}
	cur = n, d = 0;
	while (cur >= 1) {
		if (s[cur] == 'o') {
			R[++d] = cur;
			cur -= c;
		}
		cur--;
	}
	if (L[k + 1])puts("");
	else {
		reverse(R + 1, R + d + 1);
		for (int i = 1; i <= d; i++) {
			if (L[i] == R[i])printf("%d\n", L[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 3200
#define _USE_MAT_DEFINES
#include<iostream>
#include <iomanip>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <stack>
#include <deque>
#include <numeric>
#include <functional>
using namespace std;

#define INF 1e9
#define MOD 1000000007;//1e9+7

void solve() {
    long long N, ans = 0;
    cin >> N;
    vector<long long>H(N + 1, 0), memo(N + 1, 0);
    for (int i = 1; i <= N; i++){
        cin >> H[i];
        if (H[i] <= H[i - 1])memo[i] = memo[i - 1] + 1;
        ans = max(ans, memo[i]);
    }
    cout << ans;
}

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

Measured memory_bytes: 1792
// Working program with FastReader
import java.io.BufferedReader; 

import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer;
import java.lang.*;
public class Main
{ 
	static class FastReader 
	{ 
		BufferedReader br; 
		StringTokenizer st; 

		public FastReader() 
		{ 
			br = new BufferedReader(new
					InputStreamReader(System.in)); 
		} 

		String next() 
		{ 
			while (st == null || !st.hasMoreElements()) 
			{ 
				try
				{ 
					st = new StringTokenizer(br.readLine()); 
				} 
				catch (IOException e) 
				{ 
					e.printStackTrace(); 
				} 
			} 
			return st.nextToken(); 
		} 

		int nextInt() 
		{ 
			return Integer.parseInt(next()); 
		} 

		long nextLong() 
		{ 
			return Long.parseLong(next()); 
		} 

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

		String nextLine() 
		{ 
			String str = ""; 
			try
			{ 
				str = br.readLine(); 
			} 
			catch (IOException e) 
			{ 
				e.printStackTrace(); 
			} 
			return str; 
		} 
	} 

	long gcd(long a, long b) {
		if(b==0) {
			return a;
		}
		return gcd(b,a%b);
	}
	public static void main(String[] args) {
		FastReader ob = new FastReader();
		int t = ob.nextInt();
		String s[] = new String[t];
		int time[] = new int[t];
		for (int i1 = 0; i1 < t; i1++) {
			s[i1] = ob.next();
			time[i1] = ob.nextInt();

		}
		String x = ob.next();
		boolean flag=false;
		int sum=0;
		for (int i1 = 0; i1 < t; i1++) {
			if(flag) {
				sum+=time[i1];
			}

			if(!flag && x.compareTo(s[i1])==0) {
				flag=true;
			}
			
		}
		System.out.println(sum);
		
		
	}

} 


Measured memory_bytes: 23124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int R = scanner.nextInt();

		if ((R >= 0) &&(R < 1200)) {
			System.out.println("ABC");
		} else if ((R >= 1200) && (R < 2800)) {
			System.out.println("ARC");
		} else {
			System.out.println("AGC");
		}

	}

}

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

def pop_cnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
    return c

pop_S = 0
for s in S:
    if s == "1":
        pop_S += 1

p1 = pop_S + 1
p2 = pop_S - 1
#print(p1, p2)

mod_sum1 = 0
mod_sum2 = 0
for i, s in enumerate(S):
    if s == "1":
        mod_sum1 = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        if p2:
            mod_sum2 = (mod_sum2 + pow(2, N - i - 1, p2)) % p2
#print(mod_sum1, mod_sum2)

cnt = [0] * (p1 + 2)

for i in range(1, p1 + 1):
    cnt[i] = cnt[i % pop_cnt(i)] + 1
#print(cnt)

for i, s in enumerate(S):
    if s == "0":
        mod_sum = (mod_sum1 + pow(2, N - i - 1, p1)) % p1
        #print(mod_sum)
        print(cnt[mod_sum] + 1)
    else:
        if pop_S == 1:
            print(0)
        else:
            mod_sum = (mod_sum2 - pow(2, N - i - 1, p2)) % p2
            #print(mod_sum)
            print(cnt[mod_sum] + 1)


Measured memory_bytes: 79240
import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        String[] s = new String[N];

        for(int i = 0; i < N; i++){
            s[i] = sc.next();
        }

        String ans = "Yes";
        for(int i = 0; i < N-1; i++){
            if(s[i].charAt(s[i].length() - 1) != s[i+1].charAt(0)){
                ans = "No";
 //               System.out.println(s[i]);
                break;
            }
        }
        for(int i = 0; i < N - 1; i++)
        {
            for(int j = i+1; j < N; j++){
                boolean bl = true;
                int k = 0;
                if(s[i].length() == s[j].length()){
                    while(bl == true && k < s[i].length()) {
                        if(s[i].charAt(k) != s[j].charAt(k)){
 //                           System.out.println(s[i] + " " + s[j]);
                          bl = false;
                        }
                        k++;
                    }
                    if(bl == true){
                        ans = "No";
                        break;
                    }
                }
 //               System.out.println(bl);
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF (long long)(1e18)
#define MOD (int)(1e9+7)
#define MAX_N 103
#define MAX_V 10
#define MAX_M 101
#define yn(f) (f?"Yes":"No")
#define YN(f) (f?"YES":"NO")
#define pro "はいプロ　世界一○○が上手　○○界のtourist　○○時代の終焉を告げる者　実質○○　○○するために生まれてきた男"

signed main(){
	cout<<fixed<<setprecision(7);
	int n = 0, m = 0;
	int a = 0, b = 0, c = 0, d = 0, e = 0;
	bool f = true, flag = true;
	string S;
	cin>>a>>b>>c;
	if(a==b)cout<<c<<endl;
	else if(b==c)cout<<a<<endl;
	else cout<<b<<endl;
	//cin>>n;
	
	//for(int i = 0; i < n; i++){
	//}
	
	// cout<<yn(f)<<endl;
	// cout<<YN(f)<<endl;
	
	return 0;
}

Measured memory_bytes: 768
N = int(input())
P = [int(k) for k in input().split()]

maxes = []
mins  = []

max = 0
min = 0
result = 0

for i in range(N):
    if i == 0:
        max = P[i]
        min = P[i]
    else:
        if(max < P[i]):
            max = P[i]
        if(min > P[i]):
            min = P[i]

    maxes.append(max)
    mins.append(min)

for i in range(N):
    if mins[i] == P[i]:
        result = result + 1

print(result)


Measured memory_bytes: 25768
import math
n,h = map(int,input().split())
A = 0; b = []; ans = 0
for _ in range(n):
    u,v = map(int,input().split())
    A = max(A,u); b.append(v)

for B in sorted(b,key=lambda x:-x):
    if h <= 0 or B <= A:break
    h -= B
    ans += 1
print(max(0,math.ceil(h/A)) + ans)

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

// See debug.cc for usage etc
#define DEBUG 0

template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}

#if DEBUG
  #define DLOG(...)        cerr << dbgFormat(__VA_ARGS__) << endl
  #define DCALL(func, ...) func(__VA_ARGS__)
#else
  #define DLOG(...)
  #define DCALL(func, ...)
#endif

constexpr int maxN = 1e5;
int N;
vector<int> pos, neg, ax(maxN), ay(maxN);

int main() {
#if !DEBUG
  ios_base::sync_with_stdio(false);
#endif
  cout << setprecision(20);

  cin >> N;
  int numZ = 0;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if (x == 0) numZ++;
    else if (x > 0) pos.push_back(x);
    else neg.push_back(x);
  }
  for (int j = 0; j < numZ; j++) {
    if (pos.size() == 0) pos.push_back(0);
    else neg.push_back(0);
  }

  sort(pos.rbegin(), pos.rend());
  sort(neg.begin(), neg.end());

  ll pHead, nHead;
  if (pos.size() == 0) {
    pHead = neg.at(neg.size() - 1);
    nHead = neg.at(neg.size() - 2);
    neg.pop_back();
    neg.pop_back();
  }else if (neg.size() == 0) {
    nHead = pos.at(pos.size() - 1);
    pHead = pos.at(pos.size() - 1);
    pos.pop_back();
    pos.pop_back();
  }else {
    pHead = pos.at(pos.size() - 1);
    pos.pop_back();
    nHead = neg.at(neg.size() - 1);
    neg.pop_back();
  }
  
  int idx = 0;
  ll vp = pHead;
  for (int t : neg) {
    ax.at(idx) = vp;
    ay.at(idx) = t;
    vp -= t;
    idx++;
  }
  ll vn = nHead;
  for (int t : pos) {
    ax.at(idx) = vn;
    ay.at(idx) = t;
    vn -= t;
    idx++;
  }
  ax.at(idx) = vp;
  ay.at(idx) = vn;
  cout << vp - vn << "\n";
  for (int i = 0; i <= idx; i++) {
    cout << ax.at(i) << " " << ay.at(i) << "\n";
  }
  return 0;
}



Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T>using numr=std::numeric_limits<T>;
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; }
const int INF = 1e9;
const ll LLINF = 1e16;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    string s,t;
    cin >> s >>t;
    if(s.substr(0,s.size()) == t.substr(0,s.size())) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3676
N = int(input())
X = list(map(int,input().split()))

L = sorted(X)
MS, ML = L[(N//2)-1], L[(N//2)]

if MS == ML:
    for _ in range(N):
        print(MS)
else:
    for i in range(N):
        if X[i] >= ML:
            print(MS)
        else:
            print(ML)


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

int n,m;
string s;

int main(){
	cin>>s;
	n = s.length();
	if(n % 2 == 1){
		cout<<"No"<<endl;
	}else{
		for(int i = 1;i <= n - 1;i+=2){
			if(s[i - 1] == 'h' && s[i] == 'i'){
				m++;
			}else{
				break;
			}
		}
		if(m == n / 2){
			cout<<"Yes"<<endl;
		}
		else{
			cout<<"No"<<endl;
		}
	}
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
ret = []

for i in range(N):
    if i % 2 == 0:
        ret.append(A[i])
ret.reverse()
for i in range(N):
    if i % 2 == 1:
        ret.append(A[i])

if N % 2 == 0:
    ret.reverse()

print(*ret)


Measured memory_bytes: 26360
#include <bits/stdc++.h>
using namespace std;
string s, t, u;
int a, b;
int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> s >> t >> a >> b >> u;
    if (s == u) a--;
    else b--;
    cout << a << ' ' << b;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
#include <functional>
#include <numeric>
#include <stack>
#include <tuple>

using namespace std;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 100000000;
const long long LINF = 1000000000000000000;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-6;
using pii = std::pair<int, int>;
using ll = long long;
#define SORT(v) std::sort(v.begin(), v.end())

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,k;
	cin >> n >>k;
  vector<pii> a(n);
  
  for(int i=0;i<n;++i){
    cin >> a[i].first >> a[i].second;
  }
  SORT(a);
  for(int i=0;i<n;i++){
    int temp=a[i].second;
    k-=temp;
    if(k<=0){
      cout << a[i].first <<endl;
      return 0;
    }
  }
	return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
typedef pair<int, pair<int, int> > Edge;
typedef vector<Edge> vE;
typedef priority_queue<Edge, vector<Edge>, greater<Edge> > pqlE;

#define MAX_V 210

struct edge { int to, cap, rev; };

vector<edge> G[MAX_V];	// ??°???????????£??\???????????¨???
int level[MAX_V];	// s??????????????¢
int iter[MAX_V];	// ???????????§??????????????£??????

					// from??????to??????????????????cap???????????°?????????????????????
void add_edge(int from, int to, int cap)
{
	G[from].push_back(edge{ to, cap, (int)G[to].size() });
	G[to].push_back(edge{ from, 0, (int)G[from].size() - 1 });
}

// s????????????????????¢???BFS??§?¨????
void bfs(int s) {
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (int i = 0; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[e.to] < 0) {
				level[e.to] = level[v] + 1;
				que.push(e.to);
			}
		}
	}
}

// ?¢?????????????DFS??§??¢???
int dfs(int v, int t, int f) {
	if (v == t)return f;
	for (int &i = iter[v]; i < G[v].size(); i++) {
		edge &e = G[v][i];
		if (e.cap > 0 && level[v] < level[e.to]) {
			int d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

// s??????t???????????§???????±???????
int max_flow(int s, int t) {
	int flow = 0;
	while (true) {
		bfs(s);
		if (level[t] < 0)return flow;
		memset(iter, 0, sizeof(iter));
		int f;
		while ((f = dfs(s, t, INF)) > 0) {
			flow += f;
		}
	}
}

int main() {
	int X, Y, E;
	cin >> X >> Y >> E;
	rep(i, E) {
		int x, y;
		cin >> x >> y;
		add_edge(x, X + y, 1);
	}
	rep(x, X) {
		add_edge(X + Y, x, 1);
	}
	rep(y, Y) {
		add_edge(X + y, X + Y + 1, 1);
	}

	cout << max_flow(X + Y, X + Y + 1) << endl;

	return 0;
}

Measured memory_bytes: 3212
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    string s;
    while(cin >> s, s != "#"){
        for (auto &&i : s) i -= '0';
        int cur = 0;
        for (auto &&i : s) {
            if(cur == 0) cur = (i ? 2 : 1);
            else if(cur == 1) cur = (i ? 3 : -1);
            else if(cur == 2) cur = (i ? -1 : 1);
            else if(cur == 3) cur = (i ? 5 : 4);
            else if(cur == 4) cur = (i ? 2 : 5);
            else if(cur == 5) cur = (i ? 1 : 2);
        }
        if(cur == 5) puts("Yes");
        else puts("No");
    }
    return 0;
}


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

int main() {
  int a, b;
  cin >> a >> b;
  char s[a][b];
  for (int i=0;i<a;i++){
    for (int j=0;j<b;j++){
      cin >> s[i][j];
    }
  }
  for (int i=0;i<a;i++){
    for (int j=0;j<b;j++){
      cout << s[i][j];
    }
    cout << endl;
    
    for (int j=0;j<b;j++){
      cout << s[i][j];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 256
N, A, B, C, D = list(map(int, input().split()))
S = input()

A -= 1
B -= 1
C -= 1
D -= 1


def moveA(A, dest=True):
    if A == C:
        return A, True
    elif dest is True and A+1 == C and B != A+1:
        A += 1
    elif dest is True and A+2 == C and B != A+2:
        A += 2
    elif A+1 < N and S[A+1] == "." and B != A+1:
        A += 1
    elif A+2 < N and S[A+2] == "." and B != A+2:
        A += 2
    else:
        return A, True

    return A, False


def moveB(B, dest=True):
    if B == D:
        return B, True
    elif dest is True and B+1 == D and A != B+1:
        B += 1
    elif dest is True and B+2 == D and A != B+2:
        B += 2
    elif B+1 < N and S[B+1] == "." and A != B+1:
        B += 1
    elif B+2 < N and S[B+2] == "." and A != B+2:
        B += 2
    else:
        return B, True

    return B, False


if C < D:
    while B != D:
        B, stop = moveB(B)
        if stop:
            break
        # print(A, '=', C, ',', B, '=', D)

    while A != C:
        A, stop = moveA(A)
        if stop:
            break
        # print(A, '=', C, ',', B, '=', D)
else:
    while A < B and A != C:
        A, stop = moveA(A, dest=False)
        if stop:
            B, stop = moveB(B, dest=False)
            if stop:
                # for i in range(-3 + A, 4 + A):
                #     if i == A:
                #         print('A', end='')
                #     elif i == B:
                #         print('B', end='')
                #     else:
                #         print(S[i], end='')
                # print()
                # print(A, B, C, D)
                # print(A+2 < N and S[A+2] == "." and B != A+2)
                # print(S[A+2] == ".")
                # print(B != A+2)
                break
        # print(1, A, '=', C, ',', B, '=', D)

    while A != C:
        A, stop = moveA(A)
        if stop:
            # print('A', S[A-4:A+3], A, '=', C, ',', B, '=', D)
            break
        # print(2, A, '=', C, ',', B, '=', D)

    while B != D:
        B, stop = moveB(B)
        if stop:
            # print('B', S[B-4:B+3], A, '=', C, ',', B, '=', D)
            break
        # print(3, A, '=', C, ',', B, '=', D)

if A == C and B == D:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 43772
#include<stdio.h>

#define INFTY 2000000000
#define MAX 500000

int n;
long long count=0;

long long merge(long int A[],long int n,long int left,long int mid,long int right)
{
	int n1=mid-left;
	int n2=right-mid;
	int L[MAX/2+2],R[MAX/2+2];
	int i,j;
	long long int cnt=0;
	
	for(i=0;i<n1;i++)
	{
		L[i]=A[left+i];
	}
	
	for(i=0;i<n2;i++)
	{
		R[i]=A[mid+i];
	}
	
	L[n1]=INFTY;
	R[n2]=INFTY;
	
	i=0;
	j=0;
	
	for(int k=left;k<right;k++)
	{
		if(L[i]<=R[j])
		{
			A[k]=L[i];
			i=i+1;
		}
		else
		{
			A[k]=R[j];
			j=j+1;
			cnt+=n1-i;
		}
	}
	
	return cnt;
}

long long mergeSort(long int A[],long int n,long int left,long int right)
{
	long int x1,x2,x3;
	
	if(left+1<right)
	{
		int mid=(left+right)/2;
		x1=mergeSort(A,n,left,mid);
		x2=mergeSort(A,n,mid,right);
		x3=merge(A,n,left,mid,right);
		return x1+x2+x3;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	scanf("%d",&n);
	
	long int A[n];
	long int i;
	
	for(i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
	}
	
	int left=0,right=n;
	
	count=mergeSort(A,n,left,right);
	
	printf("%lld\n",count);
	
	return 0;
}


Measured memory_bytes: 4088
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using ll = long long;
const int INF = 2147483647;
const ll MOD = 1000000007;
// const ll INF = 1000000000000000000LL;

int main() {
  int n;
  cin >> n;
  if(n%1000==0) cout << 0 << endl;
  else
    cout << abs(n%1000-1000) << endl;
  return 0;
}


Measured memory_bytes: 3632
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  if(a % MOD < 0) return MOD + (a % MOD);
  else return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}


int main(){
  ll x,y,z,k; cin >> x >> y >> z >> k;
  
  vl cakex(x); vl cakey(y); vl cakez(z);
  
  rep(i,x) cin >> cakex[i];
  rep(i,y) cin >> cakey[i];
  rep(i,z) cin >> cakez[i];
  
  vl waitxy(max(x*y,k),0LL);
  
  //for(ll a : waitxy) cout << a << endl;
  
  for(ll i=0; i < x; i++){
    for(ll j=0; j < y; j++){
      waitxy[y*i + j] = cakex[i] + cakey[j];
    }
  }
  
  sort(all(waitxy)); reverse(all(waitxy));
  vl waitall(k*z,0LL);
  
  
  
  for(ll i=0; i < k; i++){
    for(ll j=0; j < z; j++){
      waitall[i*z + j] = cakez[j] + waitxy[i];
      //cout << waitxy[i] << ' ' << cakez[j] << ' ' << waitall[i*z + j] << endl;
    }
  }

  
  //for(ll a : cakez) cout << a << endl;
  
  
  sort(all(waitall)); reverse(all(waitall));
  
  rep(i,k){
    cout << waitall[i] << endl;
  }
  
  
}

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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    int X,K;
    cin >> X >> K;

    vector<int> r(K);
    rep(i,0,K) cin >> r[i];

    vector<int> x1(K),x2(K),y(K);
    x1[0]=min(r[0],X);
    x2[0]=X;
    rep(i,1,K){
        int d=r[i]-r[i-1];
        if(i%2==0){
            if(y[i-1]+(x2[i-1]-x1[i-1])-d<=0) x1[i]=x2[i]=y[i]=0;
            else if(y[i-1]-d<=0){
                x1[i]=x1[i-1]-(y[i-1]-d);
                x2[i]=x2[i-1];
                y[i]=0;
            }else{
                x1[i]=x1[i-1];
                x2[i]=x2[i-1];
                y[i]=y[i-1]-d;
            }
        }else{
            if(y[i-1]+d>=X) x1[i]=x2[i]=y[i]=X;
            else if(y[i-1]+(x2[i-1]-x1[i-1])+d>=X){
                x1[i]=x1[i-1];
                x2[i]=x2[i-1]-(y[i-1]+(x2[i-1]-x1[i-1])+d-X);
                y[i]=y[i-1]+d;
            }else{
                x1[i]=x1[i-1];
                x2[i]=x2[i-1];
                y[i]=y[i-1]+d;
            }
        }
    }

    int Q;
    cin >> Q;
    rep(i,0,Q){
        int t,a;
        cin >> t >> a;
        if(t<=r[0]) cout << max(a-t,0) << endl;
        else{
            int j=upper_bound(r.begin(),r.end(),t)-r.begin()-1;
            int ans;
            if(a<x1[j]) ans=y[j];
            else if(a<x2[j]) ans=y[j]+(a-x1[j]);
            else ans=y[j]+(x2[j]-x1[j]);
            if(j%2==0) ans=min(ans+t-r[j],X);
            else ans=max(ans-(t-r[j]),0);
            cout << ans << endl;
        }
    }
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 2816
# -*- coding: utf-8 -*-
import sys
import itertools#これは色々使える組み込み関数みたいなやつ
import math#数学的計算はこれでいける。普通に0.5乗しても計算可能
#w=input()
A, B, C, K=input().split()
A=int(A)
B=int(B)
C=int(C)
K=int(K)
i=0
ID_list=[]
ID_sublist=[]
gate_possible_list=[]
A_dummy=0
B_dummy=0
C_dummy=0
#センテンスを暗記するのではなく、まずinput()を書いて、膨らます感じで記述する。すると#思考の流れ通りに書ける。素晴らしい！
#for i in range(K):
# ID_list.append(i+1)
#print(ID_list)
#for i in range(N)
#gate_list =  [list(map(int, input().split(" ")))for i in range(M)]
#センテンスを暗記するのではなく、まずinput()を書いて、膨らます感じで記述する。すると#思考の流れ通りに書ける。素晴らしい！

#x=[]
#y=[]
#t, x, y = [0]*(N+1), [0]*(N+1), [0]*(N+1)#N+1個の空のリストを作成(原点を入れて##るから一つ増える)
#delta_t=0
#delta_x=0
#delta_y=0
#l=0
#t[0],x[0],y[0]=[0, 0, 0]
#とりあえず入力までは完成した．
#for i in range(N):
# t[i+1], x[i+1], y[i+1] = map(int, input().split())
#child_i =  list(map(int, input().split()))
#w_len=len(w)
#w_list=list(w)
#print(len(w_list))
#print(w_list)
#child_il=sorted(child_i)
#print(child_il)#リストの右端のほうが大きい
i=0
if A==B==C:
    print(0)
    sys.exit()
#for i in range(K):
#    A_dummy=B+C
#    B_dummy=A+C
#    C_dummy=A+B
#    A=A_dummy
#    B=B_dummy
#    C=C_dummy

if abs(A-B)>10**18:
    print("Unfair")
    sys.exit()

if K%2==0:
    print(A-B)
    sys.exit()

if K%2==1:
    print(-(A-B))
    sys.exit()


Measured memory_bytes: 3064
import qualified Data.ByteString.Char8 as BC
import qualified Data.IntMap as M
import Data.Maybe (fromJust)
import Data.List
import Data.Array.IO
import Control.Monad

type Arr = IOUArray Int Int
type ArrB = IOUArray Int Bool
type Edge = (Int, Int)
type Graph = M.IntMap [Int]

main = do
  [n,m] <- map read . words <$> getLine :: IO [Int]
  a <- getIntListBC
  edge <- if m > 0
            then map (\[x,y] -> (x,y)) <$> getInt2DListBC
            else return [] :: IO [(Int, Int)]
  parent <- newArray (-1, n-1) 0 :: IO Arr
  mark <- newArray (1, n) False :: IO ArrB
  let weight = sort $ zip a [0..n-1]
  let graph = foldl' makeGraph M.empty edge
  foldM (solve graph) parent [0..n-1]
  l <- length . group . sort . tail <$> getElems parent
  weight' <- select parent mark l weight
  single <- length . filter (==1) . map length . group . sort . tail <$> getElems parent
  ans1 <- if l > 1 then readArray parent (-1) else return 0
  let ans2 = sum . map fst . take (l-2) $ weight'
  if single > (n - single) - (l - single - 1)*2
    then putStrLn "Impossible"
    else print $ ans1 + ans2

solve :: Graph -> Arr -> Int -> IO Arr
solve graph arr i = dfs graph i arr i

--DFS : 前pre 現在i
dfs :: Graph -> Int -> Arr -> Int -> IO Arr
dfs graph p mark i = do
  n <- readArray mark i
  if n /= 0
    then return mark
    else do
      writeArray mark i $ p+1
      let ne = M.lookup i graph
      if ne /= Nothing
        then return =<< foldM (dfs graph p) mark $ fromJust ne
        else return mark

--重み無し隣接リスト
makeGraph :: Graph -> Edge -> Graph
makeGraph graph (x, y) =
  let nX = M.lookup x graph
      nY = M.lookup y graph
      vX = if nX == Nothing
             then M.insert x [y] graph
             else M.insert x (y : (fromJust nX)) graph
  in if nY == Nothing
       then M.insert y [x] vX
       else M.insert y (x : (fromJust nY)) vX

select :: Arr -> ArrB -> Int -> [(Int, Int)] -> IO [(Int, Int)]
select _      _    _ []          = return []
select _      _    0 s           = return s
select parent mark n ((w, v):ws) = do
  p <- readArray parent v
  used <- readArray mark p
  if used
    then do
      l <- select parent mark n ws
      return $ (w, v):l
    else do
      writeArray mark p True
      s <- readArray parent (-1)
      writeArray parent (-1) $ s + w
      select parent mark (n-1) ws

bsToInt :: BC.ByteString -> Int
bsToInt = fst . fromJust . BC.readInt

getIntListBC :: IO [Int]
getIntListBC = map bsToInt . BC.words <$> BC.getLine

getInt2DListBC :: IO [[Int]]
getInt2DListBC = map (map bsToInt . BC.words) . BC.lines <$> BC.getContents


Measured memory_bytes: 46588
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	int n;
	cin >> n;
	
	for (int i = 0; i < 100; i++){
		for (int j = 0; j < 100; j++){
			if (4*i+7*j == n){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
	return 0;
}

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

using namespace std;

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

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
/*
template<class... T>
ostream& operator<<(ostream& os, tuple<T...>& t) {
	for (size_t i = 0; i < tuple_size< tuple<T...> >::value; ++i) {
		if (i) os << " ";
		os << get<0>(t);
	}
	return os;
}
*/
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	ll L;
	while (cin >> L) {
		vector<int> r;
		{
			string str; getline(cin, str);
			stringstream ss; ss << str;
			int val;
			while ( ss >> val ) {
				r.pb(val);
			}
		}
		int N = r.size();
		vector< vector< vector<ld> > > dp;
		vector< vector<ld> > dp0(N+1, vector<ld>((1 << N), linf)); dp0[0][0] = 0;
		REP(t, N) {
			dp = vector< vector< vector<ld> > >(N+1, vector< vector<ld> >(N+1, vector<ld>((1 << N), linf)));
			dp[0] = dp0;
			REP(i, N) {
				REP(j, N+1) {
					REP(k, (1 << N)) {
						if (dp[i][j][k] >= linf-eps) continue;
						dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
						if ((k & (1 << i)) == 0) {
							int nk = k | (1 << i);
							int nj = i+1;
							ld nv = linf;
							if (j == 0) {
//								if (dp[i][j][k] > eps) cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
								assert(dp[i][j][k] < eps);
								nv = min(nv, (ld)2*r[i]);
							}
							else {
								int prev = j-1;
								int r1 = r[prev], r2 = r[i];
								ld dx = sqrt((r1+r2)*(r1+r2) - abs(r1-r2)*abs(r1-r2));
								nv = min(nv, dp[i][j][k]-r[prev]+dx+r[i]);
							}
							dp[i+1][nj][nk] = min(dp[i+1][nj][nk], nv);
						}
					}
				}
			}
			dp0 = dp[N];
		}
		ld ans = linf;
		REP(i, N+1) ans = min(ans, dp0[i][(1<<N)-1]);
//		cout << fixed << setprecision(10) << ans << endl;
		if (ans <= L+eps) {
			cout << "OK" << endl;
		}
		else {
			cout << "NA" << endl;
		}
	}
}

Measured memory_bytes: 26440
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;



void Solve(int n){
  int result=100;
  int result_s,result_t,result_u,result_v;
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  for(int ai=0;ai<=a;ai++){
    for(int bi=0;bi<=b;bi++){
      for(int ci=0;ci<=c;ci++){
        for(int di=0;di<=d;di++){

          int paid=ai*10+bi*50+ci*100+di*500;
          if(paid>=n){

            int s=a-ai,t=b-bi,u=c-ci,v=d-di;
            int change=paid-n;
            bool invalid=false;
            while(change>=500){
              if(di>0){
                invalid=true;
                break;
              }
              change-=500;
              v++;
            }
            if(invalid) continue;

            while(change>=100){
              if(ci>0){
                invalid=true;
                break;
              }
              change-=100;
              u++;
            }
            if(invalid) continue;

            while(change>=50){
              if(bi>0){
                invalid=true;
                break;
              }
              change-=50;
              t++;
            }
            if(invalid) continue;

            while(change>=10){
              if(ai>0){
                invalid=true;
                break;
              }
              change-=10;
              s++;
            }
            if(invalid) continue;

            if(s+t+u+v<result){
              result=s+t+u+v;
              result_s=ai;
              result_t=bi;
              result_u=ci;
              result_v=di;
            }

          }

        }
      }
    }
  }
  if(result_s){
    cout<<10<<" "<<result_s<<endl;
  }
  if(result_t){
    cout<<50<<" "<<result_t<<endl;
  }
  if(result_u){
    cout<<100<<" "<<result_u<<endl;
  }
  if(result_v){
    cout<<500<<" "<<result_v<<endl;
  }

}

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

  int count=0;
  while(true){
    count++;

    int n;
    cin>>n;
    if(n==0){
      break;
    }
    if(count>=2){
      cout<<endl;
    }

    Solve(n);

  }

  return 0;
}



Measured memory_bytes: 3132
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define MAX 100
int top;
int S[1000]={0}; //charだからエラー起きてた

int initialize(){
    top = 0;
}

int push(int X){
    //if(isFull()) printf("エラー（オーバーフロー）");
    top++;
    S[top] = X;
}

int pop(){
    //if(isEmpty()) printf("エラー（アンダーフロー）");
    top--;
    return S[top+1];
}


int main(){
    int x=0,A=0,B=0;
    char s[1000]={0};

    initialize();
    
    while( scanf("%s", s) != EOF ){
        if ( s[0] == '+' ){
            push(pop()+pop());
        } else if ( s[0] == '-' ){
            B = pop();
            A = pop();
            push(A-B);
        } else if ( s[0] == '*' ){
            push(pop()*pop());
        } else {
            x = atoi(s);
            push(x);
        }
    }

    printf("%d\n",S[top]);
    
  return 0;
}


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


#define f(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define char_f(i,a) for(int i=(int)(a);(char)s[i]!='\0';i++)
#define rf(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define llf(i,a,b) for(long long int i=(long long int)(a);i<=(long long int)(b);i++)
#define llrf(i,a,b) for(long long int i=(long long int)(a);i>=(long long int)(b);i--)



#define ll long long
#define fi first
#define se second
#define pb push_back
#define pop pop_back
#define mem(ara) memset((ara),0,sizeof(ara))
#define memn(ara) memset((ara),-1,sizeof(ara))
#define b begin()
#define e end()
#define em emplace
#define eb emplace_back





#define si set<int>
#define sd set<double>
#define sll set<long long int>
#define ss set<string>
#define sc set<char>

#define pii pair<int,int>
#define pli pair<long long int,int>
#define pil pair<int,long long int>
#define pll pair<long long int,long long int>
#define pci pair<char,int>
#define pic pair<int,char>
#define pcl pair<char,long long int>
#define plc pair<long long int,char>

#define pss pair<string,string>
#define pcc pair<char,char>

#define pis pair<int,string>
#define psi pair<string,int>
#define pls pair<long long int,string>
#define psl pair<string,long long int>
#define pdd pair<double,double>
#define pcs pair<char,string>
#define psc pair<string,char>



#define vi  vector<int>
#define vll vector<long long int>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vii vector<pii>



#define mod 1000000007
#define mx (1<<30)-1
#define llmx (1ll<<62)
#define n_size 100005
#define g_size 10000005
double PI=acos(-1);



///unsigned int uMAX=4294967295;
///unsigned ll int ullMAX=18446744073709551615;





int arr[g_size];



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

	int n,m,T,res;

	int maxi=-mx,mini=mx,count=0;

	int i,j,k;

	bool flag;

	string s1,s2,s3;

	char s[100000];

	int ara[n_size],ara2[n_size];

	cin>>s1>>s2>>s3;

	printf("%c%c%c\n",toupper(s1[0]),toupper(s2[0]),toupper(s3[0]));



}


Measured memory_bytes: 256
#include<stdio.h>
int  k(int a,int b,int c);
int main(void)
{
int i,a;
int b[1001],c[1001],d[1001],flag;
scanf("%d",&a);
for(i=0;i<a;i++){
scanf("%d%d%d",&b[i],&c[i],&d[i]);
}
for(i=0;i<a;i++){
flag=k(b[i],c[i],d[i]);
if(flag<0) printf("YES\n");
else printf("NO\n");
}
return 0;
}
int k(int a,int b,int c){
if(c*c==a*a+b*b) return -1;
if(b*b==a*a+c*c) return -1;
if(a*a==b*b+c*c) return -1;
else return 0;
}

Measured memory_bytes: 0
#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>
using namespace std;

int main() {
    int n,i;
    cin>>n;
    int a[n];
    int b[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i = 0;i < n;i++) {
        int c = 0;
        while(a[i] % 2 == 0) {
            a[i] /= 2;
            c++;
        }
        b[i] = c;
    }

    int minm = b[0];
    for(i = 1;i < n;i++) {
        minm = min(minm, b[i]);
    }
    cout  << minm << endl;













    return 0;
}


Measured memory_bytes: 256