akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

inline int ctoi(char c) { if(c < '0' || '9' < c) throw invalid_argument("ctoi error"); return c - '0'; }
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, k, n) for(int i = (int)(k); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

template <typename T>
inline T gcd(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("gcd error: x <= 0 or y <= 0");
	
	if(x < y) swap(x, y);
	T r = x % y;

	while(r != 0){
		x = y;
		y = r;
		r = x % y;
	}

	return y;
}
template <typename T>
inline T lcm(T x, T y){
	if (x <= 0 || y <= 0) throw invalid_argument("lcm error: x <= 0 or y <= 0");

	return x * y / gcd(x, y);
}

int main(){
	int n, m;
	cin >> n >> m;

	vector<vector<int>> path(n);

	rep(i, m){
		int a, b;
		cin >> a >> b;

		path[a - 1].push_back(b - 1);
		path[b - 1].push_back(a - 1);
	}

	if(path[0].size() == 0){
		cout << "No";

		return 0;
	}

	vector<int> ans(n);
	vector<bool> steped;
	steped.resize(n, false);
	steped[0] = true;

	queue<int> que;
	que.push(0);

	int now = 0;
	bool flag = true;

	while(flag){
		now = que.front();
		if(que.size() != 0) que.pop();
		else break;

		rep(i, path[now].size()){
			int next = path[now][i];

			if(!steped[next]){
				steped[next] = true;
				ans[next] = now;
				que.push(next);
			}
		}

		rep(i, n){
			if(!ans[i]) break;

			if(i == n - 1) flag = false;
		}
	}
	
	cout << "Yes" << endl;
	REP(i, 1, n){
		cout << ans[i] + 1 << endl;
	}

	return 0;
}

Measured memory_bytes: 10052
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*

*/
int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  ll N, K; cin >> N >> K;
  vector<ll> A(N+10, 0), seen(N+10, 0);
  rep(i, N) cin >> A[i+1];
  ll i = 1;
  while (seen[i] < 2 && K){
    seen[i]++;
    K--;
    i = A[i];
  }
  ll count = 0;
  rep(i, N+1){
    if (seen[i] == 2)
      count++;
  }
  if (count > 0)
    K %= count;
  while (K){
    K--;
    i = A[i];
  }
  cout << i << endl;
}


Measured memory_bytes: 6320
#include <iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<numeric>
#include<algorithm>
#include<complex>
#include<stdlib.h>
#include<map>
#define ll long long

using namespace std;

int main(){
   	int n,k;
	cin >> n >> k;
	cout << n-k+1 << endl;
    	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<stdio.h>
using namespace std;

int main(){
    int a,b,c,x,y;
    cin>>a>>b>>c>>x>>y;
    
    int mx=a*x+b*y;
    if(x<y){
        swap(x,y);
        swap(a,b);
    }
    int cnt=0;
    y=y-1;
    x=x-1;
    
    while(x>=0){
        cnt++;
        
        long long sum=x*a+y*b+c*cnt*2;
        if(mx>sum){
            mx=sum;
        }
        x=x-1;
        if(y>0){y=y-1;}
        else y=0;
    }
    
    cout<<mx<<endl;
    

return 0;
}

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

int main() {
    int n;
    string s;
    int x = 0, ans = 0;
    cin >> n >> s;
    rep(i,n){
        if(s[i]=='I') x++;
        else x--;
        ans = max(ans, x);
    }
    cout << ans << endl;
    return 0;
}

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

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

int main() {
    int n;
    cin >> n;
    VI a(n);
    int sum = 0;
    REP(i,n){
        a[i] = in();
        sum += a[i];
    }
    double ave = (double)sum / n;
    double mi = 1e9;
    int ans;
    REP(i,n){
        double d = fabs(a[i] - ave);
        if (d < mi - 1e-8){
            mi = d;
            ans = i;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vc vector
#define a first
#define b second
#define pb push_back
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (100000)

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

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

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

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

void Main(){
  int N, K, S; cin >> N >> K >> S;
  rep(i, 0, K){
    cout << S;
    if(i != N - 1) cout << " ";
  }
  rep(i, K, N){
    cout << (S + 1) % INF;
    if(i != N - 1) cout << " ";
  }
  cout << endl;
  return;
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();

  return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h> 
using namespace std; 
  
int a[1000007];
int b[1000007];
// Driver program 
int main() 
{ 
    int n;
    cin>>n;
    int m = 0;
    for(int i=0;i <n; i++){
        cin>>a[i];
        if(a[i]>m)
            m= a[i];
    }
    int f = 0;
    for(int i=0; i<n; i++){
        int j = a[i];
        for(; j<=m; j+=a[i]){
            b[j]++;
        }
    }
    int cnt = 0;
    for(int i=0; i<n; i++){
        // cout<<b[i]<<" ";
        if(b[a[i]]==1)
            cnt++;
    }
    cout<<cnt;
} 


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

int main() {
  int N;
  cin >> N;
  vector<int> L(N);
  for (int i = 0; i < N; i++) cin >> L[i];
  sort(L.begin(), L.end());
  int otherL = 0;
  for (int i = 0; i < N - 1; i++) otherL += L[i];
  if (L[N - 1] < otherL) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 *
 * @author k16075kk
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int l = sc.nextInt();

        long[][] A = new long[n][m];
        long[][] B = new long[m][l];
        long[][] C = new long[n][l];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                A[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < l; j++) {
                B[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
                for (int k = 0; k < m; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l - 1; j++) {
                System.out.print(C[i][j] + " ");
            }
            System.out.println(C[i][l - 1]);
        }
    }
}



Measured memory_bytes: 52320
N = $stdin.gets.chomp.to_i
A = $stdin.gets.chomp.split(' ').map(&:to_i)

a = [0] + A + [0]
complete = 0
(a.length - 1).times do |i|
    complete += (a[i] - a[i+1]).abs
end

A.length.times do |i|
    three = a[i, 3]
    sum = complete - (three[0] - three[1]).abs - (three[1] - three[2]).abs + (three[0] - three[2]).abs
    print sum, "\n"
end

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<pair<pair<int,int>,int>> py(m);
    for(int i=0;i<m;i++){
        cin >> py[i].first.first >> py[i].first.second;
        py[i].second=i;
    }
    sort(py.begin(),py.end());
    vector<pair<int,int>> ans(m);
    int rem=0;
    int count=1;
    for(auto x:py){
        //cout << x.first.first << " " << x.first.second << endl; 
        while(rem!=x.first.first){
            rem++;
            count=1;
        }
        ans[x.second]={x.first.first,count};
        count++;
    }
    for(auto x:ans){
        printf("%06d%06d\n",x.first,x.second);
    }

}

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

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;
  
  long long ans = 1;
  int r = 0, g = 0, b = 0;
  int rg = 0, gb = 0, br = 0;
  int nr = 0, ng = 0, nb = 0;
  for (int i = 0; i < 3 * n; ++i) {
    if (s[i] == 'R') {
      if (gb > 0) {
        ans *= gb;
        gb--;
      } else {
        if (g > 0) {
          ans *= g;
          g--;
          rg++;
        } else if (b > 0) {
          ans *= b;
          b--;
          br++;
        } else {
          ans *= n - nr;
          r++;
        }
      }
      nr++;
    } else if (s[i] == 'G') {
      if (br > 0) {
        ans *= br;
        br--;
      } else {
        if (b > 0) {
          ans *= b;
          b--;
          gb++;
        } else if (r > 0) {
          ans *= r;
          r--;
          rg++;
        } else {
          ans *= n - ng;
          g++;
        }
      }
      ng++;
    } else {
      if (rg > 0) {
        ans *= rg;
        rg--;
      } else {
        if (r > 0) {
          ans *= r;
          r--;
          br++;
        } else if (g > 0) {
          ans *= g;
          g--;
          gb++;
        } else {
          ans *= n - nb;
          b++;
        }
      }
      nb++;
    }
    ans %= 998244353;
  }
  cout << ans << endl;
  return 0;
}



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

using namespace std;
typedef long long ll;

ll n, a, b;

int main()
{
  cin >> n >> a >> b;
  if(a<b) swap(a, b);
  if((a-b)%2 == 0) cout << (a-b)/2ll<< endl; //including a == b
  else{
    ll ans1 = (n-b)+1;
    ll posa = a + ans1;
    ans1 += (n-posa)/2ll;

    ll ans2 = a-1+1;
    ll posb = b-a ; //posa=0
    ans2 += (posb-1)/2ll;
    cout << min(ans1, ans2);
  }
  return 0;
}


Measured memory_bytes: 256
n=int(input())
import math

i=2
l=0
k=int(math.sqrt(n))+1
s=[0]*k
while i<k:
    if s[i]==0:
        z=i
        while n%z==0:
            n//=z
            #print(z,n)
            z*=i
            l+=1
        while n%i==0:
            n//=i
            
            
    for j in range(i,k,i):
        s[j]=1
    i+=1
if n>1:
    r=0
    for i in range(2,k):
        if n%i==0:
            r=1
            break
    if r==0:
        l+=1
print(l)

Measured memory_bytes: 81148
#include "stdio.h"

int main()
{
	int input;

	if (scanf("%d", &input) == EOF)
	{
		return 0;
	}

	switch (input)
	{
	case 22:
		printf("Christmas Eve Eve Eve\n");
		break;
	case 23:
		printf("Christmas Eve Eve\n");
		break;
	case 24:
		printf("Christmas Eve\n");
		break;
	case 25:
		printf("Christmas\n");
		break;
	default:
		break;
	}

	return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {
	long N, P;
	List<Long> coords;
	long limit;
	long result = 1;

	Main() {
		Scanner in = new Scanner(System.in);
		N = in.nextLong();
		P = in.nextLong();
		in.close();
		calcLimit();
	}

	void calcLimit() {
		long times = N;
		limit = P;
		while (times >= 2) {
			limit = (long) Math.sqrt((double) limit);
			times /= 2;
		}
	}

	void calc() {
		for (long v = limit; v > 0; --v) {
			if (Math.pow(v, N) > P) {
				continue;
			}
			if (P % (long)Math.pow(v, N) == 0) {
				result = v;
				break;
			}
		}
	}

	public static void main(String[] args) {
		Main ins = new Main();
		ins.calc();
		System.out.println(ins.result);
	}

}

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

struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

int main() {
    int N, M;
    int *p;
    cin >> N >> M;
    p = new int[N+1];
    for(int i=1; i<=N; i++) {
        cin >> p[i];
    }

    UnionFind uf(N+1);
    for(int i=1; i<=M; i++) {
        int x, y;
        cin >> x >> y;
        uf.unionSet(x, y);
    }

    int ans = 0;
    for(int i=1; i<=N; i++) {
        if(uf.findSet(p[i], i)) {
            ans++;
        }
    }
    
    delete p;
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>

const int MAX_V = 1000000; // 100万まて?の素数表を作る
int prime[MAX_V+1]; // 1か?素数,0か?素数て?ない

int main() {
    int i, k, n;
    int ans[2] ={};
    for(i = 2; i <= MAX_V; i++) {
        prime[i] = 1; // 素数と仮定
    }
    for(i = 2; i*i <= MAX_V; i++) {
        if(prime[i]) {
            for(k = 2 * i; k <= MAX_V; k += i) {
                prime[k] = 0; // 素数の2倍以上の倍数は素数ではない
            }
        }
    }
    
    while(1) {
        scanf("%d", &n);
        if(n == 0) break;
        for(int i = n; i >= 5; i--) {
            if(prime[i] == 1) {
                ans[1] = i;
                if(prime[i - 2] == 1) {
                    ans[0] = i - 2;
                    break;
                }
            }
        }
        printf("%d %d\n", ans[0], ans[1]);
    }
    
    return 0;
}

Measured memory_bytes: 4932
#include <stdio.h>

int main(void) {
	char S[128];
	int i;
	if (scanf("%127s", S) != 1) return 1;
	for (i = 0; S[i] != '\0'; i += 2) {
		if (S[i] != 'h' || S[i + 1] != 'i') {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 128
sx, sy, tx, ty = map(int,input().split())
x_dif = tx-sx
y_dif = ty-sy

print("U"*y_dif + "R"*x_dif + \
      "D"*y_dif + "L"*x_dif + \
      "L" + "U"*(y_dif+1) + "R"*(x_dif+1) + "D"\
      "R" + "D"*(y_dif+1) + "L"*(x_dif+1) + "U")

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

signed main(){

  int d;
  vector<int> c(26);
  cin>>d;
  for(auto& ci:c)cin>>ci;
  vector<vector<int>> s(d,vector<int>(26));
  for(auto& si:s)for(auto& sij:si)cin>>sij;

  vector<int> t(d);
  for(auto& ti:t)cin>>ti,ti--;

  vector<int> last(26,0);

  vector<int> v(d);
  auto calc_satisfaction_level = [&](int d,int i){
    int res = s[d][i];
    for(int j=0;j<26;++j){
      if(i==j)continue;
      res -= c[j]*(d-last[j]+1);
    }
    return res;
  };

  for(int i=0;i<d;++i){
    int tmp = calc_satisfaction_level(i,t[i]);
    if(i>0)v[i]=v[i-1]+tmp;
    else v[i] = tmp;
    last[t[i]] = i+1;
  }

  for(auto vi:v)cout<< vi <<endl;

}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
 
//Made with <3 by MinumCoklatPanas
typedef long long ll;
const int INF = 1e9;
const ll INFF = 1e18;
const int MAXN = 510;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
const double INFD = 1E9;
const double EPS = 1e-9;

int cnt[200010];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1 ; i < n ; i++)
	{
		int ta;
		cin >> ta;
		cnt[ta]++;
	}
	for (int i = 1 ; i <= n ; i++)
		cout << cnt[i] << endl;
	return 0;
}

Measured memory_bytes: 4336
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
	int n;
	cin >> n;


	long long arr[n+10];


	for(int i=0;i<n;i++){
		cin >> arr[i];
	}

	sort(arr,arr+n);

	cout << abs(arr[n/2-1]-arr[n/2])<< endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    int n;
    cin >> n;
    vector<int> a;
    rep(i, n){ int tmp; cin >> tmp; a.push_back(tmp);}

    int q;
    cin >> q;
    vector<P> bc(q);
    rep(i, q){
        cin >> bc[i].first  >> bc[i].second;
    }

    ll fsum = 0;
    rep(i, n) fsum += a[i]; 

    ll baket[100010] = {0};
    rep(i, n) baket[a[i]]++;

    rep(i, q){
        ll src = bc[i].first;
        ll dst = bc[i].second;

        fsum += baket[src]*(dst-src);
        baket[dst] += baket[src];
        baket[src] = 0;
        cout << fsum << endl;
    }


    
}


Measured memory_bytes: 5368
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_ 
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;

int main(void) {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> g(n);
    REP(i, m) {
        ll s, t;
        cin >> s >> t;
        s--, t--;
        g[s].push_back(t);
    } 

    using R = long double;
    R ans = INF;
    {
        vector<R> dp(n);
        dp[n-1] = 0;
        for(ll i=n-2; i>=0; --i) {
            ll sz = g[i].size();
            for(auto to: g[i]) dp[i] += (dp[to] + 1) / sz;
        }
        chmin(ans, dp[0]);
    }
    REP(j, n-1) {
        if(g[j].size() == 1) continue;
        vector<R> dp(n);
        dp[n-1] = 0;
        for(ll i=n-2; i>=0; --i) {
            ll sz = g[i].size();
            R ma = 0;
            if(i==j) sz--;
            for(auto to: g[i]) {
                if(i==j) chmax(ma, (dp[to] + 1) / sz);
                dp[i] += (dp[to] + 1) / sz;
            }
            if(i==j) dp[i] -= ma;
        }
        chmin(ans, dp[0]);
        dump(j, dp);
    }
    cout << fixed << setprecision(9) << ans << endl;

    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn int
using ll = long long;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };

int a[1000000];
#define  MAX 10000
struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;
vector<Node*> nodes;

void preParse(Node *u) {
	if (u == NIL)
		return;
	cout << ' ' << u->key;
	preParse(u->left);
	preParse(u->right);
}

void inParse(Node* u) {
	if (u == NIL)
		return;
	inParse(u->left);
	cout << ' ' << u->key;
	inParse(u->right);
}

void postParse(Node* u) {
	if (u == NIL)
		return;
	postParse(u->left);
	postParse(u->right);
	cout << ' ' << u->key;
}

void insert(int key) {
	Node *y = NIL;
	Node *x = root;
	Node* z = new Node;
	nodes.pb(z);
	z->key = key;
	z->left = NIL;
	z->right = NIL;
	while (x != NIL) {
		y = x;
		if (z->key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL) {
		root = z;
	}
	else {
		if (z->key < y->key) {
			y->left = z;
		}
		else {
			y->right = z;
		}
	}
}

Node* find(Node* u,int key) {
	while (u != NIL && u->key != key) {
		if (key < u->key)
			u = u->left;
		else
			u = u->right;
	}
	return u;
}

signed main() {
	int n, i, x;
	string com;
	cin >> n;
	rep(i, n) {
		cin >> com;
		if (com == "find") {
			int k;
			cin >> k;
			auto t = find(root, k);
			if (t == NIL)
				cout << "no" << endl;
			else
				cout << "yes" << endl;
		}
		if (com == "insert") {
			cin >> x;
			insert(x);
		}
		if (com == "print") {
			inParse(root);
			cout << endl;
			preParse(root);
			cout << endl;
		}
	}
	for (auto n : nodes)
		delete n;
	return 0;
}


Measured memory_bytes: 24608
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
using lint = long long;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (int i = 0; i < (int)vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

#ifdef _DEBUG
template <class Head>
void dump(const char* str, Head &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + 1, t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	map<int, int> color;
	int f_color = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		if(a / 400 < 8) color[a / 400]++;
		else f_color++;
	}

	cout << max((int)color.size(), 1) << " ";
	cout << (int)color.size() + f_color << "\n";

	return 0;
}

Measured memory_bytes: 256
N, A, B = map(int, input().split())
 
ans = (B-A)//2
if A%2 == B%2:
    print(ans)
else:
    if A-1 >= N-B:
        ans += N-B+1
        print(ans)
    elif N-B > A-1:
        ans += A
        print(ans)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <stdio.h>
#pragma optimize("O3")
#define sync                    \
ios_base::sync_with_stdio(0); \
cin.tie(0);                   \
cout.tie(0)
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (a - 1); i >= (b); i--)
#define all(a) (a).begin(), (a).end()
#define endl "\n"
#define ll long long
#define pb push_back
#define PII pair<int, int>
#define PLL pair<long long, long long>
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vll vector<long long>
#define mii map<int, int>
#define mll map<long long, long long>
#define MOD 1000000007
#define MAX 1000000007
#define MOD2 1234567891
#define SZ(a) (int) a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define TIE(l, r) Node *l, *r; tie(l, r)
#define EPS 0.00000001
#define PI 3.14159265359
void dout() { cerr << endl; }
#define MAXN 100001

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << H << ' ';
    dout(T...);
}

/*,--. ,--.
  |  .'   /  ,--,--.  ,---.   ,---.   ,--,--.
  |  .   '  ' ,-.  | | .-. | | .-. | ' ,-.  |
  |  |\   \ \ '-'  | | '-' ' | '-' ' \ '-'  |
  `--' '--'  `--`--' |  |-'  |  |-'   `--`--'
                     `--'    `--'             */



void solve() {
    char a;
    cin >> a;
    if (islower(a))
        cout << 'a';
    else
        cout << "A";
}

int main() {
    solve();


    cerr << "Time elapsed: " << clock() / (double) CLOCKS_PER_SEC << endl;
    return 0;
}



Measured memory_bytes: 3776
#include <algorithm>
#include <climits>
#include <iostream>

constexpr int NINF = std::numeric_limits<int>::min();
using namespace std;

int dp[100000 + 1][3];

void solve() {
  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    for (int x = 0; x < 3; x++) {
      int a;
      cin >> a;
      int xb = (x + 1) % 3;
      int xc = (x + 2) % 3;
      dp[i + 1][x] = max(dp[i][xb] + a, dp[i][xc] + a);
    }
  }

  cout << max(max(dp[N][0], dp[N][1]), dp[N][2]) << endl;
}

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


Measured memory_bytes: 1408
import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int[] array = new int[3];
		for(int i = 0; i < 3; i++) {
			array[i] = scan.nextInt();
		}
		Arrays.sort(array);
		System.out.println(array[2] - array[0]);
		
	}
}

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

 using namespace std;
 typedef long long ll;
 #define rep(i, n) for(int i = 0; i < (int)(n); i++)

 int main() {
   int N;
   ll K, tmp1, tmp2;
   vector<ll> A(100001);
   cin >> N >> K;
   rep(i, N) {
     cin >> tmp1 >> tmp2;
     A.at(tmp1) += tmp2;
   }
   for (int i = 1; i <= 100000; i++) {
     if (K <= A.at(i)) {
       cout << i << endl;
       break;
     }
     else K -= A.at(i);
   }
 }


Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {
	int a[100][100], b[100];
	int n, m, c, i, j;
	
	scanf("%d %d", &n, &m);
	
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	
	for (i = 0; i < m; i++){
        scanf("%d", &b[i]);
    } 
	
	for (i = 0; i < n; i++) {
		c = 0;

		for (j = 0; j < m; j++) c += a[i][j] * b[j];
		printf("%d\n", c);
	}
	
	return 0;
}


Measured memory_bytes: 2104
N, T=map(int, input().split())

'''aux=[input().split() for _ in range(N)]
aux.sort()'''

c, aux=[], []
for i in range(N):
	x, y=map(int, input().split())
	
	if(y<=T):
		aux=[[int(x), int(y)]]	
		c.extend(aux)
			

if (len(c)==0):
	print("TLE")
else:
	aux=min(c)
	print(aux[0])

Measured memory_bytes: 3064
import sys
N = int(input())
A = [int(a) for a in sys.stdin.readline().split()]

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1

evenodd = [0,0]
for k in dic:
  evenodd[dic[k]%2] += 1
if evenodd[0]%2==0:
  print(len(dic))
else:
  print(len(dic)-1)
  






Measured memory_bytes: 62108
n = int(input())
p = [float(i) for i in input().split()]

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

for i in range(n):
    for j in range(n+1):
        if not j:
            dp[i+1][j] = dp[i][j]*(1-p[i])
        else:
            dp[i+1][j] = dp[i][j]*(1-p[i]) + dp[i][j-1]*p[i]

print(sum(dp[n][((n+1)//2):]))

Measured memory_bytes: 223792
s=input()
l=[]
j=0
for i in range(len(s)):
  if s[i]=='A':
    j+=1
  elif s[i]=='T':
    j+=1
  elif s[i]=='C':
    j+=1
  elif s[i]=='G':
    j+=1
  else:
    l.append(j)
    j=0
l.append(j)
L=max(l)
print(L)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n;
    cin >> n;

    vector<int64_t> b(n);
    for (auto&& bb : b) {
        cin >> bb;
    }

    vector<int64_t> ops;
    for (auto i : irange(0L, n)) {
        int64_t j = n - i;
        for (auto it = b.rbegin(); it != b.rend(); ++it) {
            auto&& bb = *it;
            if (bb == -1) {
                continue;
            }

            if (j == bb) {
                ops.push_back(bb);
                bb = -1;
                break;
            }
            --j;
        }

        if (ops.size() < i + 1) {
            cout << "-1" << endl;
            return 0;
        }
    }

    for (auto it = ops.rbegin(); it != ops.rend(); ++it) {
        cout << *it << endl;
    }
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  string S; cin >> S;
  int N = S.size();
  int ans = 0;
  for (int i = 1; i < N; ++i) {
    if (S[i - 1] != S[i]) { ++ans; }
  }
  printf("%d\n", ans);
  return 0;
}


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

def run_length(s) -> list:
  res = [[s[0], 1]]
  for i in range(1, len(s)):
    if res[-1][0] == s[i]:
      res[-1][1] += 1
    else:
      res.append([s[i], 1])
  return res

print(len(run_length(S)))

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

int main() {
	int H, W, C[10][10], X[10] = {}, ans = 0;
	cin >> H >> W;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> C[i][j];
		}
	}
	for (int k = 0; k < 10; k++) {
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				C[i][j] = min(C[i][j], C[i][k] + C[k][j]);
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			int A;
			cin >> A;
			if (A != -1) X[A]++;
		}
	}
	for (int i = 0; i < 10; i++) {
		ans += X[i] * C[i][1];
	}
	cout << ans;
}

Measured memory_bytes: 256
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

S = sys.stdin.readline().rstrip()
ans = ''

if (S=='Sunny'):
    ans = 'Cloudy'
elif (S=='Cloudy'):
    ans = 'Rainy'
else:
    ans = 'Sunny'

print(ans)


Measured memory_bytes: 5588
#include<stdio.h>

int main(){
	int board[17][17]={0};
	int i,j,n,x,y,p,q;

	while(scanf("%d%d",&x,&y),x+y){
		scanf("%d",&n);
		for(i=0;i<17*17;i++)
			board[i%17][i/17]=-1;
		for(i=0;i<n;i++){
			scanf("%d%d",&p,&q);
			board[p][q]=0;
		}

		/*
		for(i=1;i<=x;i++){
			for(j=1;j<=y;j++){
				printf("%d ",board[i][j]);
			}puts("");
		}
		*/
		
		board[1][1]=1;

		for(i=1;i<17;i++){
			if(board[1][i]<0)board[1][i]=board[1][i-1];
			if(board[i][1]<0)board[i][1]=board[i-1][1];
		}
		for(i=2;i<=x;i++){
			for(j=2;j<=y;j++){
				if(board[i][j]<0){
					board[i][j]=board[i][j-1]+board[i-1][j];
				}
			}
		}

		/*
		for(i=1;i<=x;i++){
			for(j=1;j<=y;j++){
				printf("%d ",board[i][j]);
			}puts("");
		}
		*/
		
		printf("%d\n",board[x][y]);
	}
	return 0;
}

Measured memory_bytes: 600
import java.util.Arrays;
import java.util.Scanner;

//Sum of Different Primes
public class Main{

	int N = 1120, num;
	int[] p;
	int[][][] dp;
	
	int get(int x, int index, int rest){
		if(rest==0){
			if(x==0)return dp[x][index][rest] = 1;
			else return dp[x][index][rest] = 0;
		}
		if(dp[x][index][rest]!=-1)return dp[x][index][rest];
		int res = 0;
		for(int i=index;i<num;i++){
			if(x<p[i])break;
			res += get(x-p[i], i+1, rest-1);
		}
		return dp[x][index][rest] = res;
	}
	
	void run(){
		num = 0;
		p = new int[187];
		boolean[] prime = new boolean[N+1];
		Arrays.fill(prime, true);
		prime[0]=prime[1]=false;
		for(int i=2;i<=N;i++)if(prime[i]){
			p[num++] = i;
			for(int j=i+i;j<=N;j+=i)prime[j]=false;
		}
		dp = new int[N+1][num+1][15];
		for(int i=0;i<=N;i++)for(int j=0;j<=num;j++)for(int k=0;k<=14;k++)dp[i][j][k]=-1;
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt(), k = sc.nextInt();
			if((n|k)==0)break;
			System.out.println(get(n, 0, k));
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include<atcoder/all>

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

#define fi first
#define se second
#define all(A) A.begin(),A.end()

using namespace std;
using namespace atcoder;

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


ll T;

ll i, j, k;
int main(){
    scanf("%lld",&T);

    
    while(T--){
        ll N, M, A, B;
        scanf("%lld%lld%lld%lld", &N, &M, &A, &B);
        printf("%lld\n", floor_sum(N, M, A, B));
    }

    return 0;
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
#define ll long long int
#define MM 1000005
#define MOD 1000000007
#define sync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

bool comp(const pair<ll,ll> &p1,const pair<ll,ll> &p2)
{
    if(p1.first!=p2.first)
        return p1.first>p2.first;
    else
        return p1.second<p2.second;
}
ll check(ll n)
{
    ll hh=n/60,p=0;
    ll mm=n%60;
    while(hh>0){
        if(hh%10==7){
            p=1;break;
        }
        hh/=10;
    }
    while(mm>0){
        if(mm%10==7){
            p=1;break;
        }
        mm/=10;
    }
    return p;
}
int  main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    sync
    ll t=1;
    //cin>>t;
    ll tt=t;
    while(t--)
    {
        ll i,j,k,n,m,q,x=0,y=0,z=0,p=0,mx=1,sum=0;
        cin>>n;
        for(ll ii=0;ii<n;ii++){
            cin>>m>>i>>j;
            p=abs(x-i)+abs(y-j);
            if(m<p){
                mx=0;
            }
            else{
                if((m-p)%2!=0)
                    mx=0;
            }
        }
        if(mx)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] a=new int[101];
        int i,t,j,n,co=0;
        n = sc.nextInt();
        for(i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        for(i=n-1;i>0;i--){
            for(j=n-1;j>=n-i;j--){
                if(a[j]<a[j-1]){
                    t=a[j];
                    a[j]=a[j-1];
                    a[j-1]=t;
                    co++;
                }
 
            }
        }
 
        for(i=0;i<n;i++){
            if(i==0)System.out.print(a[i]);
            else System.out.print(" "+a[i]);
        }
        System.out.println();
        System.out.println(co);
    }
}



Measured memory_bytes: 26556
#include <iostream>

using namespace std;
char c[] = {'-', '0', '+'};

void bt(int x)
{
	int q = (x + 1) / 3;
	int r = (x + 1) % 3;
	if (q)
	{
		bt(q);
	}
	cout << c[r];
}

void solve()
{
	int x;
	cin >> x;
	bt(x);
	cout << endl;
}

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

Measured memory_bytes: 1156
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

N, M = map(int, input().split())

UF = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    UF.merge(x, y)

UF.updatePars()

ans = len(set(UF.pars))
print(ans)


Measured memory_bytes: 13932
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
	int sum = 0, t = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') t = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ sum = sum * 10 + ch - '0'; ch = getchar(); }
	return sum * t;
}

int n, A, B;

int main(){
	n = read(); A = read(); B = read();
	printf("%lld\n", max(1LL * (B - A) * (n - 2) + 1, 0LL));
}

Measured memory_bytes: 128
A, B = map(int,input().split())
nums = []
for i in range(A,B+1):
  str_i = str(i)
  if all(str_i[x] == str_i[-x-1] for x in range(int(len(str_i)/2))):
    nums.append(int(str_i))

print(len(nums))

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

void solve() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a > b)
		swap(a, b);
	if (a > c)
		swap(a, c);
	if (b > c)
		swap(b, c);
	int x = c - b + (c - (a + c - b) + 1) / 2 + (c - (a + c - b)) % 2;
	cout << x;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	for (int i = 1; i <= t; i++) {
		solve();
	}
}

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

int main() {
    int x;
    int y;
    cin >> x;
    cin >> y;
    if((y-1)%(x-1)==0){
        cout << (y-1)/(x-1);
    }else{
        cout << (y-1)/(x-1)+1;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
	int n,m;
	cin >> n >> m;
	char a[51][51],b[51][51];
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			cin >> a[i][j];
		}
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			cin >> b[i][j];
		}
	}
	int flag,i,j,k,l;
	for(i=0; i<n; i++){
		for(j=0; j<n; j++){
			flag=0;
			for(k=0; k<m; k++){
				for(l=0; l<m; l++){
					if(i+k>n || j+l>n)break;
					if(a[i+k][j+l]!=b[k][l]){
						flag=1;
						break;
					}
				}
				if(flag==1)break;
			}
			if(!flag){
				cout << "Yes" << endl;
				return 0;
			}
			cout << endl;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>pii;
typedef pair<pii, ll>pi3;
ll mod = 1000000007;
int main()
{
	ll num;
	scanf("%lld", &num);
	for (ll i = 1; i <= 3500; i++)
	{
		for (ll j = 1; j <= 3500; j++)
		{
			ll s = 4LL *i*j - num*j - num*i;
			ll t = num*i*j;
			if (s <= 0)continue;
			if (t%s == 0)
			{
				printf("%lld %lld %lld\n", i, j, t / s);
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
//
//  main.cpp
//  CoderProj
//
//  Created by Minoru Hayashi on 2020/05/02.
//  Copyright © 2020 Minoru Hayashi. All rights reserved.
//
//  ABC16８8
//
//

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for (int i=0; i<(n); i++)
#define REP2(i,x,n) for (int i=x; i<(n); i++)
#define ALL(n) begin(n), end(n)

using ll = long long;

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

 const ll INF = 1LL<<60;
// const int INF = 1<<29;
// const int MOD = 1000000007;
//#define __DBG__



void solve(void){
  
  int N;
  
  cin >> N;
  
  int A = N % 10;
  
  if(A==3){
    cout << "bon" << endl;
  }
  else if(A==0||A==1||A==6||A==8){
    cout << "pon" << endl;
  }
  else
  {
    cout << "hon" << endl;
  }
  
  return;
}



#define TESTCASES 1

int main() {


    cin.tie(0);
    ios::sync_with_stdio(false);

    REP(i,TESTCASES){
      solve();
    }
 
    return 0;
}




Measured memory_bytes: 3576
/*
Author: CNYALI_LK
LANG: C++
PROG: B.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
	int s=0,base=1;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=-base;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	return s*base;
}
char WriteIntBuffer[1024];
template<class T>void write(T a,char end){
	int cnt=0,fu=1;
	if(a<0){putchar('-');fu=-1;}
	do{WriteIntBuffer[++cnt]=fu*(a%10)+'0';a/=10;}while(a);
	while(cnt){putchar(WriteIntBuffer[cnt]);--cnt;}
	putchar(end);
}
char s[102424];
int sa[102424],a[102424];
int S[102424][2];
#define judge(x) (x?1:0)
int ok(int n,int k){
	S[0][0]=S[0][1]=0;
	for(int i=1;i<=n;++i){
		S[i][a[i]]=S[i-1][a[i]];
		if(i-S[i][a[i]]+judge(S[i][a[i]])>=k){
			return 1;	
		}
		S[i][a[i]^1]=i+1;
		if(i>=k){
			chkmin(S[i][0],S[i][1]);
			chkmin(S[i][1],S[i][0]);
		}
	}
	return 0;
}
int main(){
#ifdef cnyali_lk
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
#endif
	int n,tu=0;
	scanf("%s",s);
	n=strlen(s);
	for(int i=1;i<=n;++i){
		a[i]=s[i-1]^'0';
	}
	int l=1,r=n,mid;
//	printf("%d\n",ok(n,2));
	while(l<=r){
		mid=(l+r)>>1;
		if(ok(n,mid))l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",l-1);

	return 0;
}



Measured memory_bytes: 1536
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}

	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	h := getNextInt(scanner)
	w := getNextInt(scanner)
	k := getNextInt(scanner)
	aa := make([][]string, h)
	sx := -1
	sy := -1
	for i := 0; i < h; i++ {
		aa[i] = strings.Split(getNextString(scanner), "")
		for j := 0; j < w; j++ {
			if aa[i][j] == "S" {
				sx = j
				sy = i
			}
		}
	}
	q := make([]takahashi, 0)
	q = append(q, newt(sy, sx, 0))
	dy := [4]int{-1, 0, 0, 1}
	dx := [4]int{0, -1, 1, 0}
	ans := math.MaxInt32
	visited := makeInts(h, w)
	for len(q) > 0 {
		p := q[0]
		q = q[1:]

		visited[p.y][p.x] = 1
		ans = minint(ans, shortest(p.y, p.x, h, w))
		if p.k == k {
			continue
		}
		for i := 0; i < 4; i++ {
			xx := p.x + dx[i]
			yy := p.y + dy[i]
			if yy < 0 || yy >= h {
				continue
			}
			if xx < 0 || xx >= w {
				continue
			}
			if aa[yy][xx] == "#" {
				continue
			}
			if visited[yy][xx] == 1 {
				continue
			}
			visited[yy][xx] = 1
			q = append(q, newt(yy, xx, p.k+1))
		}
	}
	fmt.Fprintln(writer, 1+covered(ans, k))
}

func covered(v, k int) int {
	return (v + k - 1) / k
}
func makeInts(h, w int) [][]int {
	index := make([][]int, h, h)
	data := make([]int, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}
func minint(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func shortest(y, x, h, w int) int {
	return minint(minint(x, w-x-1), minint(y, h-y-1))
}
func newt(y, x, k int) takahashi {
	return takahashi{
		y: y,
		x: x,
		k: k,
	}
}

type takahashi struct {
	y, x, k int
}


Measured memory_bytes: 32640
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
void func(int p);
typedef pair<int,int>P;
int n;
array<array<int,101>,101>arr;
array<P,101>arrp;
array<bool,101>arrb;
int Time;
int main(void){
	int u,k,v;
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			arr[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
		cin>>u>>k;
		for(j=0;j<k;j++){
			cin>>v;
			arr[u][v]=1;
		}
	}
	arrb.fill(false);
	Time=0;
	for(i=1;i<=n;i++){
		if(!arrb[i]){
			func(i);
		}
	}
	for(i=1;i<=n;i++){
		cout<<i<<" "<<arrp[i].F<<" "<<arrp[i].S<<endl;
	}
	return 0;
}
void func(int p){
	int i,j;
	//cout<<p<<endl;
	arrb[p]=true;
	Time++;
	arrp[p].F=Time;
	for(i=1;i<=n;i++){
		if(arr[p][i]==1){
			if(!arrb[i]){
				func(i);
			}
		}
	}
	Time++;
	arrp[p].S=Time;
}
	


Measured memory_bytes: 3128
using System;
using System.Collections.Generic;
using System.Linq;

namespace AC
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(new string('x', Read().Count()));
            Console.ReadKey();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 11348
N = int(input())
T,A = map(int, input().split())

h_list = list(map(int, input().split()))
a_list = []
for h in h_list:
    candi = T - h * 0.006
    ac = float(abs(candi - A))
    a_list.append(ac)
print(a_list.index(min(a_list)) + 1)


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

int n, m, c[10];
string ans = "";

void dfs(int num, int use, int res){
    if(use == 0){
        cout << ans << endl;
        exit(0);
    }
    if(num == 10)   return;
    for(int i = min(use, res/c[num]); i >= 0; i--){
        for(int j = 0; j < i; j++)  ans += (char)('0'+num);
        dfs(num+1, use-i, res-c[num]*i);
        ans = ans.substr(0, ans.size()-i);
    }
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < 10; i++) cin >> c[i];
    dfs(0, n, m);
    cout << "NA" << endl;
    return 0;
}


Measured memory_bytes: 3240
// finish date: 2018/08/19
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;

const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


bool ex(int n) {
    int cnt =0;
    FOR(i, 1, n + 1) if (n % i == 0) cnt++;
    if(cnt==8) return true;
    else return false;

}

int main() {
    int N;
    cin >> N;

    int cnt = 0;
    for (int i = 1; i <= N; i += 2) {
        if (ex(i)) cnt++;
    }
    cout << cnt << endl;

    return 0;
}



Measured memory_bytes: 256
import math
N = int(input())
S = [0]*N
lim = math.sqrt(N)
lim = math.floor(lim)
for i in range(1,lim):
  for j in range(1,lim):
    for k in range(1,lim):
        temp = int(i**2+ j**2 + k**2 + i*j + j*k + k*i)
        if temp <N+1:
          S[temp-1] += 1
for i in range(N):
  print(S[i])


Measured memory_bytes: 9148