akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define vi vector<int>
#define LLMAX 4000000000000000000LL
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ii pair<int,int>
#define MOD 1000000007
const double EPS = (1e-5);
long long binpow(long long a, long long b){long long res = 1;while (b > 0){if (b & 1)res = res * a;a = a * a;b >>= 1;}return res;}
int findXOR(int n){switch (n % 4){case 0:return n;case 1:return 1;case 2:return n + 1;case 3:return 0;}}
int rangeXOR(int l, int r){return (findXOR(l - 1) ^ findXOR(r));}
int getbit(int mask, int bit){return (mask & (1 << bit));}void setbit(int& mask, int bit, int val){if (val)mask |= (1 << bit);else mask &= ~(1 << bit);}
//ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
//ll lcm(ll a, ll b){return a * (b / gcd(a, b));}
const int N = 4e6+10;
const int M = 1e6+3;
const ll INF = 1e4+1;
int a[N];
int dp[N];
int n;
int calc2(int i)
{
	if (i == n - 1)
	{
		//reached last cell
		//base case
		return 0;
	}
	if (dp[i] != -1)//you check if u visited that state before so you return it
		return dp[i];
	int ret = INT_MAX;
	//first choice jump to cell i + 1
	if (i + 1 < n) //check if you can jump so u dont get runtime error
		ret = min(ret, abs(a[i] - a[i + 1]) + calc2(i + 1));//compute it
	if (i + 2 < n)
		ret = min(ret, abs(a[i] - a[i + 2]) + calc2(i + 2));
	return dp[i] = ret;// save the state after you calculate it so you dont recompute it again
	//better complexity O(Number of Distinct States)
}
int calc(int i)
{
	if (i == n - 1)
	{
		//reached last cell
		//base case
		return 0;
	}
	int ret = INT_MAX;
	//first choice jump to cell i + 1
	if (i + 1 < n) //check if you can jump so u dont get runtime error
		ret = min(ret, abs(a[i] - a[i + 1]) + calc(i + 1));//compute it
	if (i + 2 < n)
		ret = min(ret, abs(a[i] - a[i + 2]) + calc(i + 2));
	return ret;// but very bad complexity O(2 ^ n)
}
void solve()
{
	memset(dp, -1, sizeof dp); // make all dp array = -1 so you know if they are computed yet or not
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	cout<<calc2(0);
}
int main(void)
{
	//freopen("commandos.in", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tc = 1;
	//cin >> tc;
	//scanf("%d", &tc);
	while (tc--)
	{
		solve();
	}
}

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

using namespace std;

template <class T>inline T updmax(T& a, T b) {return a = max(a, b);}
template <class T>inline T updmin(T& a, T b) {return a = min(a, b);}

class Solution {
public:
	void solve() {
		int n;
		cin >> n;
		vector<int> d(n, 0);
		for(int i=0; i<n; i++)cin >> d[i];
		sort(d.begin(), d.end());
		int ret = 0;
		for(int i=0; i < n; i++){
			for(int j=i+1; j < n; j++){
				auto it = lower_bound(d.begin(), d.end(), d[i]+d[j]);
				it--;
				ret += distance(d.begin(), it)-j;
			}
		}
		cout << ret << "\n";
		
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int N, i;
	char S[100];
	char T[100];
	
	scanf("%d", &N);
	scanf("%s %s", S, T);
	
	for(i=0; i<N; i++){
		printf("%c%c", S[i], T[i]);
	}
	
return 0;
}

Measured memory_bytes: 128
n, y = map(int, input().split())

satu10000 = -1
satu5000 = -1
satu1000 = -1

i = 0
flag = 0
while(i <= n):
  j = 0
  while(i+j <= n):
    k = n - i - j
    if 10000*i + 5000*j + 1000*k == y:
      satu10000 = i
      satu5000 = j
      satu1000 = k
      flag = 1
      break
    j += 1
  if flag == 1:
    break
  i += 1

print(str(satu10000) + ' ' + str(satu5000) + ' ' + str(satu1000))


Measured memory_bytes: 3064
fun main(arg: Array<String>) {
    val S = next()
    val A = S.split("T").map { it.length }.toIntArray()
    val (X, Y) = listOfInt()
    val xy = Array(2) { mutableSetOf<Int>() }
    xy[0].add(0); xy[1].add(0)
    for ((index, dis) in A.withIndex()) {
        val p = mutableSetOf<Int>()
        if (index % 2 == 0) { //x
            if (index == 0) p.add(dis)
            else
            for (d in xy[0]) {
                p.add(d + dis)
                p.add(d - dis)
            }
            xy[0] = p
        } else { //y
            for (d in xy[1]) {
                p.add(d + dis)
                p.add(d - dis)
            }
            xy[1] = p
        }
    }
    val ans = if (xy[0].contains(X) && xy[1].contains(Y)) "Yes" else "No"
    println(ans)
//System.err.println("x\n${xy[0].sorted().joinToString("\n")}")
//System.err.println("y\n${xy[1].sorted().joinToString("\n")}")
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }



Measured memory_bytes: 118664
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
vector<int>g[100010];
int mod = 1000000000+7;
int dp[1000010][3];
int N;
void make()
{
   cin >> N;
   for(int i=0;i<N-1;i++)
   {
       int x,y;
       cin >> x >> y;
       x--;y--;
       g[x].pb(y);
       g[y].pb(x);
   }
}
void dfs(int u,int p)
{
        dp[u][0] = dp[u][1] =1;
    for(auto it:g[u])
    {
    
        if(it==p)continue;
        dfs(it,u);
        dp[u][0] = ((dp[u][0]*(dp[it][0]+dp[it][1])%mod));
        dp[u][1] = (dp[u][1]*dp[it][0])%mod;

    }
}

void ok()
{
   dfs(0,-1);
   cout<<(dp[0][0]+dp[0][1])%mod<<"\n";
      

}


int32_t main()
{
  
    int test=1;;
    
    while( test-- )
    {
        make();
        ok();
    }
}

Measured memory_bytes: 16256
H, W = gets.split.map(&:to_i)

k, m, r = Array.new(W, 0), Array.new(W, 0), 0
dot = '.'
H.times do
  l = 0
  s = gets.chomp
  (0 ... W).each do |j|
    if s[j] == dot
      if l == 0
        t = j + 1
        while t < W && s[t] == dot
          t += 1
        end
        l = t - j
      end
      k[j] += 1
      m[j] = l if l > m[j]
    else
      x = k[j] + m[j]
      r = x if x > r
      l = 0
      k[j] = 0
      m[j] = 0
    end
  end
end
(0 ... W).each{|j| x = k[j] + m[j]; r = x if x > r}
puts r - 1


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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


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

    int N, A;
    cin >> N >> A;

    if(N % 500 <= A){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}



Measured memory_bytes: 256
<?php

$str = trim(fgets(STDIN));
$arr = explode(' ', $str);
$arr2 = array_count_values($arr);
$word1 = array_search(max($arr2), $arr2);
$word2 = '';

foreach ($arr as $s) {
    if (strlen($s) > strlen($word2)) {
        $word2 = $s;
    }
}

printf("%s %s\n", $word1, $word2);

Measured memory_bytes: 6584
#include <iostream>
#include <string>

int main()
{
	std::string s;
	int k;

	std::cin >> s;
	std::cin >> k;

	//　頭から見ていく。
	// ('z' - at(i) + 1 ) % 26 で、aまでの距離 dが取れるので、kがそれより大きければ
	// k-=dして、at(i) =  'a'とする
	// kがそれより小さい場合は、次の文字へいく
	// 最後まで終わったあと、最後の文字に +kする

	for (int i = 0; i < s.size(); i++) {
		int d;
		if ((d = ('z' - s.at(i) + 1) % 26) <= k) {
			k -= d;
			s.at(i) = 'a';
		}
	}

	if (k > 0) {
		int abcIndex = *(s.rbegin()) - 'a';
		abcIndex = (abcIndex + k) % 26;
		*(s.rbegin()) = abcIndex + 'a';
	}

	std::cout << s << std::endl;

}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using ll = long long;
using namespace std;
typedef unsigned long long ull;
typedef pair<ll, ll>P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()

ll h, w, n, chx[10] = { 0 }, chy[10] = { 0 }, d[1010][1010] = { 0 };
char c[1010][1010];

int bfs(ll a, ll b, ll e, ll f) {
	queue<P> que;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			d[j][i] = INF;
		}
	}
	que.push(make_pair(a, b));
	d[a][b] = 0;
	while (que.size()) {
		P p = que.front();que.pop();
		if (p.first == e&&p.second == f) {
			break;
		}
		for (int i = 0;i < 4;i++) {
			ll nx = p.first + dx[i], ny = p.second + dy[i];
			if (0 <= nx&&nx < w && 0 <= ny&&ny < h&&c[nx][ny] != 'X'&&d[nx][ny] == INF) {
				que.push(make_pair(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
	return d[e][f];
}


int main() {
	ll ans = 0;
	cin >> h >> w >> n;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			cin >> c[j][i];
			if (c[j][i] == 'S')chx[0] = j, chy[0] = i;
			else if (c[j][i] != 'S'&&c[j][i] != '.'&&c[j][i] != 'X') {
				chx[int(c[j][i] - '0')] = j, chy[(int)(c[j][i] - '0')] = i;
			}
		}
	}
	for (int i = 0;i < n;i++) {
		ans += bfs(chx[i], chy[i], chx[i + 1], chy[i + 1]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 12024
H, W = map(int, input().split())
A = [0] * H
for _ in range(H):
    A[_] = input()
l = []
l2 = []
count = 0

for i in range(W):
    for j in range(H):
        if A[j][i] == '.':
            count += 1
    if count == H:
        l.append(i)
    count = 0
l.sort(reverse = True)
for k in range(H):
    for m in l:
        A[k] = A[k][:m] + A[k][m + 1:]
# print(A)
# for l in range(H):
#     if A[l] == '.' * len(A[l]):
#         l2.append(l)
# for _ in l2:
#     A.pop(_)
B = [i for i in A if i != '.'*len(A[0])]
# print(B)
for _ in range(len(B)):
    print(B[_])

Measured memory_bytes: 3064
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define gcd(a,b) __gcd(a,b)
#define pb push_back
#define DRACO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define GO ll t; cin>>t; while(t--)
#define mod  1000000007
#define vect vector<long long int>
#define fore(p) for(auto& x:p)
#define bins binary_search
#define vecti vector<int>::iterator
#define bitout __builtin_popcount
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(), x.rend()
#define PY 3.141592653589793238
#define F first
#define S second
ll power(ll a,ll b){
    ll res = 1;
    while(b > 0)
    {
        if(b%2 == 1) res *= a;
        a *= a;
        b /= 2;
    }
    return res;
}
double dis(double a,double b ,double c , double d)
{
    return (sqrt((a-c)*(a-c)+(b-d)*(b-d)));
}

int main() 
{   DRACO
    ll i,j,k,l,n,m;
    cout.precision(10);
    //GO
    {   
        ll x, t;
        cin >> n >> x >> t;
        
        if(n%x==0)
            n = n/x;
        else
            n = n/x + 1;
        
        cout<< n*t;
        
        
    }
return 0;
}
//check the corner cases(n==1)
//try checking in reverse order
//check your logic again

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
const int N=998244353;
int n,k;
int l[21],r[21];
long long dp[200010];
long long add[200010];
inline int read()
{
	int num=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') {num=(num<<1)+(num<<3)+ch-'0'; ch=getchar();}
	return num*f;
}
int main()
{
	n=read(),k=read();
	for(int i=1;i<=k;i++) l[i]=read(),r[i]=read();	
	dp[1]=1; add[1]=1;
	for(int i=2;i<=n;i++)
		for(int j=1;j<=k;j++)
			dp[i]=(dp[i]+add[max(0,i-l[j])]-add[max(i-r[j]-1,0)])%N,add[i]=(add[i-1]+dp[i])%N;
	printf("%lld",(dp[n]+N)%N);
	return 0;
}

Measured memory_bytes: 6880
n,k=map(int,input().split())
if 2*k-1>n:
  print(-1)
  exit()
for i in range(1,n+1):
  if i<=n//2:
    b=2*n+k-i*2
    c=2*n+k+n//2-i
  else:
    b=2*n+k+1-(i-n//2)*2
    c=k+3*n-(i-n//2)
  print(k+i-1,b,c)


Measured memory_bytes: 49880
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // std::ifstream in("input.txt");
    // std::cin.rdbuf(in.rdbuf());
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    map<ll, vector<ll>> m;
    rep(i, n) m[a[i]].push_back(i);
    vector<ll> vals;
    for(auto x : m) vals.push_back(x.first);
    reverse(all(vals));
    vals.push_back(0);
    vector<ll> ans(n, 0);
    ll cnt = 0, idx = LONG_LONG_MAX;
    rep(i, sz(vals) - 1) {
        rep(ii, sz(m[vals[i]])) {
            idx = min(idx, m[vals[i]][ii]);
        }
        cnt += sz(m[vals[i]]);
        ans[idx] += cnt * (vals[i] - vals[i + 1]);
    }
    rep(i, n) printf("%lld\n", ans[i]);
    return 0;
}


Measured memory_bytes: 14456
AB = list(map(int, input().split()))
soto = AB[0] - 1
B = AB[1]
if soto % 4 == 0:
    tmp1 =soto
elif soto % 4 == 1:
    tmp1 = 1
elif soto % 4 == 2:
    tmp1= soto + 1
else :
    tmp1 = 0

if B % 4 == 0:
    tmp2 =B
elif B % 4 == 1:
    tmp2 = 1
elif B % 4 == 2:
    tmp2= B + 1
else :
    tmp2 = 0

ans = tmp1 ^ tmp2
print(ans)

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

int main() {
	int n;
	cin>>n;
  double arr[n];
	for(int i=0;i<n;i++){
	    cin>>arr[i];
	}
	
   double dp[n+1][n+1];
   for(int i=0;i<=n;i++)
	dp[i][0]=1.0;
	
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=i;j++){
	        dp[i][j]=dp[i-1][j-1]*arr[i-1]+dp[i-1][j]*(1-arr[i-1]);
	        
	    }
	}
	
   double res=0.0;
	
	for(int i=0;i<=n;i++){
	    if(i>n-i)
	    res=max(res,dp[n][i]);
	}
	cout<<setprecision(10);
	cout<<res<<"\n";
	return 0;
}

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

ll N, K;

int main(){
	cin >> N >> K;
	
	// 頂点1を他の全ての点とつなぐと、 Kmax=(N-1)(N-2)/2
	// ここに add 本の線を引いて最短距離を1にすると K = Kmax - add になる
	
	ll Kmax = (N-1)*(N-2)/2;
	if ( K > Kmax ){
		cout << "-1" << endl;
		return 0;
	}
	ll add = Kmax - K;
	cout << (N-1 + add) << endl;
	
	for ( int i = 1; i <= N; i++ ){
		for ( int j = i+1; j <= N; j++ ){
			if ( i == 1 )
				cout << i << " " << j << endl;
			else {
				if ( add > 0 ){
					add--;
					cout << i << " " << j << endl;
				}
				else
					return 0;
			}
		}
	}
	
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
#include<complex>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;
const double eps = 1E-18;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += MOD - a.x) >= MOD) x -= MOD;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= MOD;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res *= a;
	}

	mint operator^(const ll& t)const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}

	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime MOD
	mint inv() const {
		return pow(MOD - 2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream& os, const mint& m) {
		os << m.x;
		return os;
	}
};

///////////////////////////

int main() {
	ll N, M, Q;
	cin >> N >> M >> Q;
	vector<ll> a(Q + 1);
	repn(i, Q) cin >> a[i];

	vector<ll> ar(M + 1,0);
	vector<ll> lg(N + 1, 0);

	for (ll i = Q; i >= 1; i--) {
		if(ar[a[i]]==0){
			ar[a[i]] = lg[N] + 1;
			lg[N]++;
		}

		else {
			auto itr = upper_bound(++lg.begin(), lg.end(), ar[a[i]]-1);
			//cout << i << endl << flush;
			ll j = distance(lg.begin(), itr) - 1;
			//cout << j << endl << flush;
			if (j >= 1&&lg[j]==ar[a[i]]-1) { lg[j]++; }
		}
	}

	vector<ll> seq(M+1);
	repn(i, M) {
		if (ar[i] > 0) { seq[ar[i]] = i; }
		//cout << ar[i] << " " << i << endl << flush;
	}
	ll c = lg[N] + 1;
	//cout << c << endl;
	repn(i, M) {
		if (ar[i] == 0) { seq[c] = i; c++; }
	}

	string ans = "Yes";
	for (ll i = lg[1] + 1; i <= min(lg[N],M-1); i++) {
		if (seq[i] > seq[i + 1]) { ans = "No"; }
	}

	cout << ans << endl;
}


Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> neg, pos;
    rep(i, n){
        cin >> a[i];
        if(a[i] < 0)neg.push_back(a[i]);
        else pos.push_back(a[i]);
    }
    sort(ALL(a));

    ll ans = a.back()-a.front();
    for(ll i=1; i < n-1; ++i)ans += abs(a[i]);
    cout << ans << endl;
    
    if(n == 2){
        cout << a.back() << " " << a.front();
        return 0;
    }
    
    if(neg.empty()){
        cout << a.front() << " " << a.back() << endl;
        a.front() -= a.back();
        a.pop_back();
        while(a.size() > 2){
            cout << a.front() << " " << a.back() << endl;
            a.front()-=a.back();
            a.pop_back();
        }
        cout << a.back() << " " << a.front();
    }
    else if(pos.empty()){
        cout << a.back() << " " << a.front() << endl;
        a.back() -= a.front();
        a.erase(a.begin());
        while(a.size() > 2){
            cout << a.back() << " " << a.front() << endl;
            a.back()-=a.front();
            a.erase(a.begin());
        }
        cout << a.back() << " " << a.front();
    }
    else {
        ll ps = pos.back();
        pos.pop_back();
        ll ng = neg.back();
        neg.pop_back();
        while(!pos.empty()){
            cout << ng << " " << pos.back() << endl;
            ng -= pos.back();
            pos.pop_back();
        }
        while(!neg.empty()){
            cout << ps << " " << neg.back() << endl;
            ps -= neg.back();
            neg.pop_back();
        }
        cout << ps << " " << ng << endl;
    }
}

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

char s[100005];

int main()
{
	scanf( "%s", s + 1 );
	int len = strlen(s + 1), tot = 0;
	int lf = 1, rg = len;
	while(lf < rg)
	{
		if(s[lf] != s[rg])
		{
			if(s[lf] == 'x') ++tot, ++lf;
			else if(s[rg] == 'x') ++tot, --rg;
			else 
			{
				puts("-1");
				return 0;
			}
		}
		else ++lf, --rg;
	}
	cout << tot << endl;
	return 0;
}
/*
xabxa
*/

Measured memory_bytes: 384
n = int(input())

if n < 105:
    print(0)
elif 105 <= n < 135:
    print(1)
elif 135 <= n < 165:
    print(2)
elif 165 <= n < 189:
    print(3)
elif 189 <= n < 195:
    print(4)
else:
    print(5)

Measured memory_bytes: 2940
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

A,B = IL()
print(max(A+B,A-B,A*B))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  string x;
  cin>>n>>x;
  vector<char>word(n);
  for(int i;i<n;i++){
    word.at(i)=x[i];
  }
  int count=0;
  for(int i;i<n-2;i++){
    if(word.at(i)=='A'){
      if(word.at(i+1)=='B'){
        if(word.at(i+2)=='C'){
          count++;
        }
      
      }
    }
  }
  cout<<count<<endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a,b,c;
int main()
{
cin>>a>>b;
c=a+b;
if(c%2==0)cout<<c/2;
if(c%2!=0)cout<<c/2+1;
cout<<endl;
return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            System.out.println((sc.nextInt() * 100 + sc.nextInt() * 10 + sc.nextInt()) % 4 == 0 ? "YES" : "NO");
        }
    }
}


Measured memory_bytes: 22356
#include<stdio.h>

int H[250];

#define NLI NULL

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

  for(i = 1; i < n + 1; i++){
    printf("node %d: key = %d, ", i, H[i]);
    if(i != 1)
      printf("parent key = %d, ", H[i / 2]);
    if(i * 2 <= n)
      printf("left key = %d, ", H[i * 2]);
    if(i * 2 + 1 <= n)
      printf("right key = %d, ", H[i * 2 + 1]);
    printf("\n");
  }
  
  return 0;
}



Measured memory_bytes: 2048
n = int(input())
x = list(map(int, input().split()))

# 最も体力がいる時でも 100**2(体力) * 100（個数） = 10**6　を超えることはない
hp_old = 10**6

# 全探索
for p in range(1, 101, 1):
    hp_new = 0
    for xi in x:
        # 体力計算
        hp_new += (xi - p) ** 2
    # 体力の最小値を求める
    hp = min(hp_new, hp_old)
    # 上記の体力を現状最小値の体力と定義する
    hp_old = hp

print(hp)

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

using namespace std;

int main()
{
	int a, b, c;
	cin >> a >> b >> c;
	int d = a%b;
	while (d != c)
	{
		d = (d+a)%b;
		if (d == a%b)
		{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}


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

int main() {
  for(int N, M; cin >> N >> M && (N|M); ) {
    vector<int> h(N), w(M);
    for(int i = 0; i < N; ++i) cin >> h[i];
    for(int j = 0; j < M; ++j) cin >> w[j];
    map<int, int> m;
    for(int i = 0; i < N; ++i) {
      for(int j = i, k = 0; j < N; ++j) {
        k += h[j];
        m[k] += 1;
      }
    }
    int res = 0;
    for(int i = 0; i < M; ++i) {
      for(int j = i, k = 0; j < M; ++j) {
        k += w[j];
        if(m.count(k)) res += m[k];
      }
    }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 14624
#include <iostream>
#include <stdio.h>
using namespace std;



int main(void) {
	int A, B, C = 0;
	cin >> A >> B >> C;

	int D = C - A + B;

	if (D < 0) {
		cout << '0' << endl;
	}
	else {
		cout << C - A + B << endl;
	}

	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.141592653589793
#define MOD 1000000007


int main(){
	int n, k;
	scanf("%d%d", &n, &k);
	double pre = 0;
	for(int i=1; i<=n; i++){
		double temp = 1.0/n;
		int point = i;
		while(point < k){
			point *= 2;
			temp /= 2;
		}
		pre += temp;
	}
	printf("%.12f\n", pre);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

class Dice {
private:
	int number[6];
	int state[6];
public:
	Dice();
	~Dice();
	void initialize();
	void setNumber(int index, int num);
	void roll(char d);
	void move(string d);
	int getNumber(int idx);
	int getTop();
	int getSide(int t, int f);
	bool cmp(Dice dice1);
};

Dice::Dice() {
	initialize();
}

Dice::~Dice() {
}

void Dice::initialize() {
	for (int i = 0; i < 6; i++)
		state[i] = i+1;
}

void Dice::setNumber(int index, int num) {
	number[index] = num;
}

void Dice::roll(char d) {
	int nextIndex[4][6] = {
		{1, 5, 2, 3, 0, 4},
		{3, 1, 0, 5, 4, 2},
		{2, 1, 5, 0, 4, 3},
		{4, 0, 2, 3, 5, 1},
	};
	int *idx, nextState[6];
	switch (d) {
		case 'N': idx = nextIndex[0]; break;
		case 'E': idx = nextIndex[1]; break;
		case 'W': idx = nextIndex[2]; break;
		case 'S': idx = nextIndex[3]; break;
		default: return;
	}
	for (int i = 0; i < 6; i++)
		nextState[i] = state[idx[i]];
	for (int i = 0; i < 6; i++)
		state[i] = nextState[i];
}

void Dice::move(string d) {
	int oldIndex[4][6] = {
		{1, 5, 2, 3, 0, 4},
		{3, 1, 0, 5, 4, 2},
		{2, 1, 5, 0, 4, 3},
		{4, 0, 2, 3, 5, 1},
	};
	for (int i = 0; i < d.size(); i++) {
		int newNumber[6] = {0};
		int *idx;
		char c = d[i];
		switch (c) {
			case 'N': idx = oldIndex[0]; break;
			case 'E': idx = oldIndex[1]; break;
			case 'W': idx = oldIndex[2]; break;
			case 'S': idx = oldIndex[3]; break;
			default: return;
		}
		for (int i = 0; i < 6; i++)
			newNumber[i] = number[idx[i]];
		for (int i = 0; i < 6; i++)
			number[i] = newNumber[i];
	}
}

int Dice::getNumber(int idx) {
	return number[state[idx]-1];
}

int Dice::getTop() {
	return getNumber(0);
}

int Dice::getSide(int t, int f) {
	string s = "NNNNENNNN";
	for (int i = 0; i < s.size(); i++) {
		if (number[state[1]-1] == f) {
			break;
		}
		char c = s[i];
		roll(c);
	}
	s = "EEEEE";
	for (int i = 0; i < s.size(); i++) {
		if (number[state[0]-1] == t)
			break;
		char c = s[i];
		roll(c);
	}
	return getNumber(2);
}

bool Dice::cmp(Dice op) {
	string s = "SWWWWNEEEEENEEEENNEEEESEEEEESEEEE";
	for (int i = 0; i < s.size(); i++) {
		char c = s[i];
		op.roll(c);
		int flag = 0;
		for (int i = 0; i < 6; i++)
			if (op.getNumber(i) != number[i]) {
				flag = 1;
				break;
			}
		if (flag == 0)
			return true;
	}
	return false;
}

int main() {
	Dice *dice;
	int n, m;
	cin >> n;
	dice = new Dice[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 6; j++) {
			cin >> m;
			dice[i].setNumber(j, m);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (dice[i].cmp(dice[j]) == true) {
				cout << "No" << endl;
				return 0;
			}
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

int main() {
    string a;
    string b[3];
    cin >> a;
    int count = 0;

    b[0] = a[0];
    b[1] = a[1];
    b[2] = a[2];

    for(int i = 0;i < 3;i++){
        if(b[i] == "o"){
            count++;
        }
    }
    cout << 700 + 100 * count << endl;
}

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

public class Main {
    static ArrayList<Integer> [] adj;
    static int [] dp;
    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        int n = sc.nextInt(); adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            int x = sc.nextInt();
            adj[x].add(i);
            adj[i].add(x);
        }
        dp = new int[n + 1];
        dfs(1, -1);
        out.println(dp[1]);
        out.close();
    }

    static void dfs(int cur, int par) {
        ArrayList<Integer> children = new ArrayList<>();
        for (Integer next: adj[cur]) {
            if (next != par) {
                dfs(next, cur);
                children.add(next);
            }
        }
        if (children.size() == 0) dp[cur] = 0;
        else if (children.size() == 1) dp[cur] = 1 + dp[children.get(0)];
        else {
            Collections.sort(children, Comparator.comparingInt(i -> -dp[i]));
            dp[cur] = 0;
            for (int i = 0; i < children.size(); i++) {
                dp[cur] = Math.max(dp[cur], i + 1 + dp[children.get(i)]);
            }
        }
    }


    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            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;
        }


    }

}

Measured memory_bytes: 91092
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i, n) ;for (int i = 0;i < (int)(n);i++)
#define rep2(i, s, n) ;for (int i = s; i < (int)(n);i++)
#define ALL(vec)  (vec).begin(),(vec).end()
#define pi 3.1415926535897932384626433832795
#define MAX_INF 9223372036854775807
#define MIN_INF (922337203685477587+1)
#define sosuu 1000000007

lli Euclid(lli a,lli b)
{
 
  lli r;
 
  if(a<b){
    swap(a,b);
  }
 
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
  return b;
}

int main() {
  int N;
  cin >> N;
  lli a;
  lli ans;
  rep(i, N-1){
  cin >> a;
    if(i==0){
    cin >> ans;}
    
    ans=Euclid(a,ans);
  
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main(int argc, char const* argv[])
{
	int room[4][3][10] = {};
	int b, f, r, v;

	int input;
	std::cin >> input;

	for (size_t i = 0; i < input; i++)
	{
		std::cin >> b >> f >> r >> v;
		room[b - 1][f - 1][r - 1] += v;
	}

	for (size_t ib = 0; ib < 4; ib++)
	{
		for (size_t jf = 0; jf < 3; jf++)
		{
			for (size_t kr = 0; kr < 10; kr++)
				std::cout << " " << room[ib][jf][kr];

			std::cout << std::endl;
		}
		if(ib != 3)
			std::cout << "####################" << std::endl;
	}

	return 0;
}

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

int main()
{
    int n, cnt = 0;
    string s;

    cin >> n;
    cin >> s;

    rep(i, n) {
        if (s[i] == 65) {
            i++;
            if (s[i] == 66) {
                i++;
                if (s[i] == 67) cnt++;
                else i--;
            }
            else i--;
        }
    }

    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
buf=input().split()
a=[None for i in range(n)]
for i in range(n):
    a[i]=int(buf[i])
cnt=[0 for i in range(45)]
for i in a:
    for j in range(45):
        cnt[j]+=i%2
        i//=2
        if i==0:
            break
res=0
for i in range(44,-1,-1):
    toadd=2**i
    if toadd>k:
        continue
    if cnt[i]<=n//2 and res+toadd<=k:
        res+=toadd
ress=0
for i in a:
    ress+=res^i
print(ress)

Measured memory_bytes: 71840
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;cin>>n>>k;
    vector<int> a(n);
    rep(i,n) cin>>a[i];
    vector<int> startidx;
    startidx.push_back(-1);
    vector<set<int>> idx(2*(1e+5)+10);
    int cnt = 0;
    int val = -1;
    rep(i,n){
        if (val != a[i]) {
            cnt = 1;
        } else {
            cnt++;
        }
        if(cnt<=2) {
            idx[a[i]].insert(i);
        }
    } 
    bool flg = true;
    int now = 0;
    while(now != 0 || flg) {
        flg = false;
        auto it = upper_bound(begin(idx[a[now]]), end(idx[a[now]]), now);
        if (it == idx[a[now]].end()) {
            startidx.push_back(now);
            now = *lower_bound(begin(idx[a[now]]), end(idx[a[now]]), 0);
        }
        else {
            now = *it;
        }
        now = (now+1) % n;
    }
    DEBUG{
        for(auto x: startidx) cout << x << " ";
        cout << endl;
    }
    ll start = (k-1) % (startidx.size());
    deque<int> que;
    vector<bool> flgs(4e+5,false);
    DEBUG{
        cout << "start: " << start << endl;
    }
    if(start != 0) {
        repr(i,startidx[start],n) {
            if(flgs[a[i]]) {
                while(que.back() != a[i]) {
                    flgs[que.back()] = false;
                    que.pop_back();
                }
                que.pop_back();
                flgs[a[i]] = false;
            }else {
                que.push_back(a[i]);
                flgs[a[i]] = true;
            }
        }
    }
    rep(i,n) {
        if(flgs[a[i]]) {
            while(que.back() != a[i]) {
                flgs[que.back()] = false;
                que.pop_back();
            }
            que.pop_back();
            flgs[a[i]] = false;
        }else {
            que.push_back(a[i]);
            flgs[a[i]] = true;
        }
    }
    while(!que.empty()) {
        cout << que.front();
        que.pop_front();
        cout << (que.empty() ? "\n" : " ");
    }
    return 0;
}


Measured memory_bytes: 22772
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int n,l;
	while(cin>>n>>l)
	{
		string str[105];
		for(int i=0;i<n;i++)
		  cin>>str[i];
		sort(str,str+n);
		for(int j=0;j<n;j++)
		 cout<<str[j];
		 cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
//#pragma comment(linker, "/STACK:134217728")

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <memory>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;

#define FOR(i, a, b) for(i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(i = (a) - 1; i >= (b); --i)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
#define PB push_back
#define MP make_pair

VInt E[1 << 18];

bool dfs(int a, int p, int r, int z)
{
	int i;
	FOR(i, 0, SIZE(E[a]))
	{
		int b = E[a][i];
		if (b == p || b == z) continue;
		if (b == r) return true;
		if (dfs(b, a, r, z)) return true;
	}
	return false;
}

bool f(VInt cnt)
{
	int n = SIZE(cnt);
	int i;
	FOR(i, 0, n) if (cnt[i] % 2 != 0) return false;
	FOR(i, 0, n) if (cnt[i] > 4) return true;
	VInt v;
	FOR(i, 0, n) if (cnt[i] == 4) v.push_back(i);
	if (SIZE(v) < 2) return false;
	if (SIZE(v) > 2) return true;
	int a = v.front();
	int b = v.back();
	return dfs(a, -1, a, b) || dfs(b, -1, b, a);
}

int main()
{
	int N, M;
	scanf("%d%d", &N, &M);
	VInt cnt(N, 0);
	int i;
	FOR(i, 0, M)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		--a;
		--b;
		++cnt[a];
		++cnt[b];
		E[a].push_back(b);
		E[b].push_back(a);
	}

	printf("%s\n", f(cnt) ? "Yes" : "No");

	return 0;
};


Measured memory_bytes: 11904
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string n;
    cin >> n;
    if(n[0] == n[2]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

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

int main(){
    int s1,s2;
    cin>>s1>>s2;
    if(s1==s2)cout<<"Draw"<<endl;
    else if((s1>s2&&s2!=1)||s1==1)cout<<"Alice"<<endl;
    else if((s2>s1&&s1!=1)||s2==1)cout<<"Bob"<<endl;    
    return 0;
}

Measured memory_bytes: 3596
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = sum(b)
for i in range(len(a)-1):
    if a[i+1] - a[i] == 1:
        ans += c[a[i]-1]
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1000001];
ll solve(ll n,ll a[])
{
    if(n<=0)
    return 0;
    if(dp[n]!=-1)
    return dp[n];
    
    return dp[n]=min(abs(a[n-2]-a[n])+solve(n-2,a),abs(a[n-1]-a[n])+solve(n-1,a));
}

int main()
{
    ll n;
    cin>>n;
    
    ll a[n],i;
    for(i=0;i<=100000;i++)
    dp[i]=-1;
    for(i=0;i<n;i++)
    cin>>a[i];
    cout<<solve(n-1,a);
}

Measured memory_bytes: 8064
#include<stdio.h>

int str_len(const char s[]){
    int len = 0;
  
    while(s[len]) len++;  
    return len;
}

int main(void){
   int cnt = 0,new_cnt = 0, max,i,n;
   char str[11];
   
   scanf("%s", str);

 n = str_len(str); 

   for(i = 0; i < n + 1; i++){
       if(str[i] == 'A') cnt++;
       else if(str[i] == 'T') cnt++;
       else if(str[i] == 'C') cnt++;
       else if(str[i] == 'G') cnt++;
       else {
          cnt = 0;
       }
     if(new_cnt < cnt) new_cnt = cnt;
   }
   
   printf("%d", new_cnt);
   
 return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


double eps = 1e-7;
struct Point {
    double x,y,z;
};

Point operator+(Point p,Point q){
    return Point{p.x+q.x, p.y+q.y, p.z+q.z};
}

Point operator-(Point p,Point q){
    return Point{p.x-q.x, p.y-q.y, p.z-q.z};
}

Point operator*(double k, Point p){
    return Point{k*p.x, k*p.y, k*p.z};
}

double dot(Point p,Point q){
    return p.x*q.x + p.y*q.y + p.z*q.z;
}

Point proj(Point x, Point s,Point t){
    x=x-s; t=t-s;
    double k = dot(x,t)/dot(t,t);
    return s + k * t;
}

Point cont(Point x, Point s, Point t){
    Point m=proj(x,s,t);
    return 2*m-x;
}

double cross(Point s, Point t, Point c,double r){
    Point h = proj(c,s,t);
    double d = dot(c-h,c-h);
    if(d>r*r)return -1;
    return dot(t-s,h-s)/dot(t-s,t-s)-sqrt((r*r-d)/dot(t-s,t-s));
}

void solve(int n){
    Point s ={0,0,0};
    Point t;
    cin>>t.x>>t.y>>t.z;
    Point a[n];
    double r[n];
    rep(i,n)cin>>a[i].x>>a[i].y>>a[i].z>>r[i];
    rep(_,10){
        int idx=-1;
        double mi=inf;
        rep(i,n){
            double res = cross(s,t,a[i],r[i]);
            if(res>eps&&res<mi){
                mi=res;
                idx=i;
            }
        }
        if(idx==-1){
            cout<<s.x<<" "<<s.y<<" "<<s.z<<endl;
            return;
        }
        Point ns = s + mi*(t-s);
        t = cont(s,a[idx],ns);
        s = ns;
    }
}
int main(){
    int n;
    cout<<fixed<<setprecision(12);
    while(cin>>n,n!=0)solve(n);
    return 0;
}


Measured memory_bytes: 3180
#include <iostream>
#include <string>
#include <algorithm>
#include <array>
#include <sstream>
#include <stdio.h>
#include <math.h>

using namespace std;

inline bool isprime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

array<int, 10000> a;

int main(void) {
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);

    auto r = count_if(a.begin(), a.begin() + n, [](const int& e) { return isprime(e); });
    cout << r << endl;
    // ostringstream os;
    // for(int i = 0; i < n; ++i) {
    //     if(isprime(a[i])) os << a[i] << " ";
    // }
    // auto s = os.str();
    // cout << s.substr(0, s.size() - 1) << endl;
}



Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 5;
const ll MOD = 1e9 + 7;
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pis pair<ll,string>
#define F first
#define S second
#define LCM(a,b) ((a*b)/__gcd(a,b))
#define inf 1e15
#define test ll cse;cin>>cse;for(ll _i=1;_i<=cse;_i++)
#define PI 3.14159265
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const double EPS = 1E-9;
typedef vector< vector<double> > matrix;
typedef vector<int> vi;


bool isPrime(ll n) {
    if(n <= 1) return false;
    if(n <= 3) return true;

    if(n % 2 == 0) return false;
    if(n % 3 == 0) return false;

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

unordered_map< ll, ll > powerOfPrimeDivisors(ll number) {
    unordered_map< ll, ll > P;

    ll n = number;
    ll sqrtn = (ll)sqrt(n + 10);

    while(n % 2 == 0) { n /= 2; P[2]++;}
    while(n % 3 == 0) { n /= 3; P[3]++;}

    for (ll i = 5; i <= sqrtn; i = i + 6) {
        while(n % i == 0) { n /= i; P[i]++;}
        while(n % (i+2) == 0) { n /= (i+2); P[i + 2]++;}
    }

    if(n != 1) P[n]++;
    return P;
}

int prime[N];

void sieve() {
    memset(prime, 0, sizeof(prime));
    prime[0] = prime[1] = 1;

    for (int i = 2; i < N; i++) {
        if (prime[i] == 0) {
            for (int j = i; j < N; j += i) prime[j] += 1;
        }
    }
}


int main() {
    fast;

    // sieve();
    ll n; cin >> n;

    if(n <= 1)
        cout << 0 << "\n";
    else if( isPrime(n) )
        cout << 1 << "\n";
    else {
        unordered_map< ll, ll > primefactor = powerOfPrimeDivisors(n);

        int ans = 0;
        for(auto e: primefactor) {
            ll powerOfDiv = e.second;

            for(ll i = 1; powerOfDiv >= i; i++) {
                ans++;
                powerOfDiv -= i;
            }
        }

        cout << ans << "\n";
    }
    return 0;
}

Measured memory_bytes: 3676
N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n
    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj 
            else: 
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi 
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
        
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()


Measured memory_bytes: 24820
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

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

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

int main() {
    ll x, p;
    cin >> x >> p;
    ll k = (x+1)/2;
    printf("%.15Lf", (100/(long double)p)*k);
    return 0;
}


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

string s;
int k;
long dp[101][5][2];
int main() {
  cin >> s >> k;
  const int n = s.size();
  dp[0][0][1] = 1;
  for (int i = 0; i < n; ++i) {
    int d = s[i] - '0';
    for (int j = 0; j <= k; ++j) {
      if (d == 0) {
        dp[i + 1][j + 0][1] += dp[i][j][1];
        dp[i + 1][j + 0][0] += dp[i][j][0];
        dp[i + 1][j + 1][0] += 9 * dp[i][j][0];
      } else {
        dp[i + 1][j + 0][0] += dp[i][j][1];
        dp[i + 1][j + 1][0] += (d - 1) * dp[i][j][1];
        dp[i + 1][j + 1][1] += dp[i][j][1];
        dp[i + 1][j + 0][0] += dp[i][j][0];
        dp[i + 1][j + 1][0] += 9 * dp[i][j][0];
      }
    }
  }
  cout << dp[n][k][0] + dp[n][k][1] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, a, b;
    cin >> x >> a >> b;
    if(abs(x-a)>abs(x-b)) {
        cout << "B" << endl;
    } else {
        cout << "A" << endl;
    }
}

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

namespace _1_B
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (x[0] < x[1])
            {
                Array.Reverse(x);
            }
            while (x[1] > 0)
            {
                int r = x[0] % x[1];
                x[0] = x[1];
                x[1] = r;
            }
            Console.WriteLine(x[0]);
        }
    }
}

Measured memory_bytes: 9552
#include<iostream>
#define INF (1 << 30)
using namespace std;
typedef long long ll;
 
int main() {
    ll x, y;
    cin >> x >> y;
    ll ans = INF;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            ll n = x, m = y;
            if (i == 1) n = -n;
            if (j == 1) m = -m;
            if (n <= m) ans = min(ans, i + j + m - n);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
typedef long long int ll ;
long long int power(long long int a,long long int n,long long int m) ;
 long long int power(long long int a,long long int n,long long int m)
{  if(n==0)
   return 1 ;
   long long int x=power(a,n/2,m) ;
   if(n%2!=0)
    return (((a*x)%m)*(x)%m)%m ;
    else return (x*x)%m ;
}



int main()
{ long long int n,i,j,x,y,m,k,t,sum,count,cnt,b,c,d,j1,z,a,o;
   cin>>x>>y ;
   if(y>=x)
    cout<<"unsafe" ;
   else cout<<"safe" ;
   return 0 ; }


Measured memory_bytes: 3636
N = int(input())
H_list = list(map(int, input().split()))

r = 0
res = 0
for i in range(N - 1):
    if H_list[i] >= H_list[i + 1]:
        r += 1
        if r > res:
            res = r
    else:
        r = 0

if __name__ == "__main__":
    print(res)


Measured memory_bytes: 14228
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define FASTIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inf 1e18
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define mod 1000000007
#define pb push_back
#define all(s) s.begin(),s.end()
#define pie 3.14159265358979323846
#define fr(i,a,b)  for(ll i=a;i<b;i++)
#define frr(i,a,b) for(ll i=b-1;i>=a;i--)
#define gcd __gcd
#define con continue
#define pii pair<ll,ll>
signed main(){
    FASTIO;
    ll tt=1;
    //cin>>tt;
    while(tt--){
         string s;cin>>s;
         ll ss=0;
         for(auto x:s){
            ss+=x-'0';
         }
         if(ss%9==0)cout<<"Yes\n";
         else cout<<"No\n";
    }
}


Measured memory_bytes: 3760
#include <stdio.h>
int main(){
	int m[11],i,j,x;
	for(i=1;i<=10;i++){
		scanf("%d\n",&m[i]);
	}
	for(i=1;i<=10;i++){
		for(j=1;j<=9;j++){
			if(m[j]<m[j+1]){
				x=m[j+1];
				m[j+1]=m[j];
				m[j]=x;	
			}
		}
	}
	for(i=1;i<=3;i++){
		printf("%d\n",m[i]);
	}
	return 0;
}

Measured memory_bytes: 0