akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>

#define int long long

using namespace std;

class Solver{

};

signed main() {
	while (true) {
		int n;
		cin >> n;
		if (n == 0)break;

		string s;
		cin >> s;
		int a = 0;
		for (int i = s.size() - 1; i >= 0; i--) {
			if (s[i] == '1')a += pow(2, s.size() - 1 - i);
		}
		a += pow(2, 52);

		int sum = a;
		int dig = 0;
		int remain = n;
		int max = pow(2, 53);
		while (a > 0 && remain > 0) {
			int cnt = (max - sum) / a;
			if ((max - sum) % a)cnt++;

			if (remain >= cnt) {
				dig++;
				sum += a * cnt;
				sum /= 2;
				a /= 2;
				remain -= cnt;
			}
			else {
				sum += a * remain;
				remain = 0;
			}
		}

		int mask = pow(2, 11);
		while (mask > 0) {
			if ((dig & mask) > 0)cout << 1;
			else cout << 0;
			mask = mask >> 1;
		}
		mask = pow(2, 51);
		while (mask > 0) {
			if ((sum & mask) > 0)cout << 1;
			else cout << 0;
			mask = mask >> 1;
		}
		cout << endl;
	}
}


Measured memory_bytes: 3368
import math
N = int(input())
ans = 0
num = {i:0 for i in range(1, N+1)}
upper = int(math.sqrt(N)) + 1
for x in range(1, upper):
    for y  in range(1, upper):
        z = 1
        v = x**2 + y**2 + z**2 + x*y + y*z + z*x
        if v > N:
            break
        for z in range(1, upper):
            v = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if v in num.keys():
                num[v] += 1
            if v > N:
                break
for n in range(1, N+1):
    print(num[n])

Measured memory_bytes: 69648
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {t:usize}
    for _ in 0..t {
        input! {n:usize,
        klr:[(usize,i64,i64);n]}
        let mut left = Vec::new();
        let mut right = Vec::new();
        let mut same_sum = 0;
        for &(k, l, r) in klr.iter() {
            if l > r {
                left.push((k, l, r));
            } else if r > l {
                right.push((n - k, r, l));
            } else {
                same_sum += l;
            }
        }
        println!("{}", same_sum + calc(&mut left) + calc(&mut right));
    }
}
fn calc(camels: &mut Vec<(usize, i64, i64)>) -> i64 {
    camels.sort_by_key(|&x| -x.1 + x.2);
    let n = camels.len();
    let mut ret = 0;
    let mut not_used = Vec::new();
    for i in 0..=n {
        not_used.push(i);
    }
    for &(k, l, r) in camels.iter() {
        // k 未満の最小のインデックスで未使用のものを探す
        let bef = not_used.upper_bound(&k) - 1;
        if bef == 0 {
            ret += r;
        } else {
            not_used.remove(bef);
            ret += l;
        }
    }
    return ret;
}
pub trait BinarySearch<T> {
    fn lower_bound_by<F: Fn(&T) -> bool>(&self, f: F) -> usize;
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}
impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound_by<F: Fn(&T) -> bool>(&self, f: F) -> usize {
        let mut ng = -1;
        let mut ok = self.len() as i64;
        while (ok as i32 - ng as i32).abs() > 1 {
            let mid = (ok + ng) / 2;
            if f(&self[mid as usize]) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        ok as usize
    }
    fn lower_bound(&self, x: &T) -> usize {
        self.lower_bound_by(|y| y >= x)
    }
    fn upper_bound(&self, x: &T) -> usize {
        self.lower_bound_by(|y| y > x)
    }
}


Measured memory_bytes: 16152
#include <stdio.h>

int isprime(int n) {
 for(int i = 2; i * i <= n; i++) {
	 if(n % i == 0) return 0;
 }
 return 1;
}

int main(){
	int n,i,min,max;
	int number[10000+2] = {0};
	for(i = 2;i < 10000;i++){
		number[i] = isprime(i);
	}
	while(scanf("%d",&n)){
		if(n == 0)break;
		max = 0; min = 0;
		for(i = n;i > 0;i--){
			//printf("%d  ",i);
			if(number[i] && number[i-2]){
				min = i-2;
				max = i;
				//printf("%d %d\n",i,i-2);
				break;
			}
		}
		printf("%d %d\n",min,max);
	}
	return 0;
}

Measured memory_bytes: 1072
#include <iostream>

 using namespace std;

int main()
{
   int i, h, m, s;
   cin >> i;
   h = i / 3600;
   m = i % 3600 / 60;
   s = i % 3600 % 60;
   cout << h << ":" << m << ":" << s << endl;
}


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

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

    int tmp = 0;
    for (int i = 1; i <= k; ++i)
    {
        tmp = (tmp * 10 + 7) % k;
        if (tmp == 0)
        {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
}

Measured memory_bytes: 3632
#include<stdio.h>

int main()
{
  int c,i,r,A,B,C;
  c = 0;
  i = 0;
  r = 0;

  scanf("%d%d%d",&A,&B,&C);

  while(c < C){
    r ++;
    c += A;
    i ++;

    if(i == 7){
      c += B;
      i = 0;
    }

  }
  printf("%d\n",r);
  return 0;

}



Measured memory_bytes: 2104
<?php
$nums = explode(' ', trim(fgets(STDIN)));
$step = trim(fgets(STDIN));
for ($i=0; $i < $step; $i++) {
  $max = max($nums);
  $key = array_keys($nums, $max);
  $nums[$key[0]] *= 2;
}
echo array_sum($nums)."\n";


Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define rep(i,n) for(int i=0;i<(int)(n);i++)
static const int mod = 1e+7;
static const long long INF = 1LL << 60;
typedef long long ll;

ll a[100010][3];
ll dp[100010][3];
int main(){
    int N; cin >> N;
    rep(i,N){
        rep(j,3)cin>>a[i][j];
    }
    rep(i,N){
        rep(j,3){
            rep(k,3){
                if(j == k)continue;
                chmax(dp[i+1][k], dp[i][j]+a[i][k]);
            }
        }
    }
    ll res = 0;
    //ここで答えを求めている
    rep(j,3)chmax(res, dp[N][j]);
    cout << res << endl;
}

Measured memory_bytes: 4992
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(_,v.size())cout<<" "<<v[_];cout<<endl;
#define show2d(v) rep(_,v.size()){rep(__,v[_].size())cout<<" "<<v[_][__];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 1e18+10 : 1e9+10;
int dx[]={0,1,0,-1,1,1,-1,-1};
int dy[]={1,0,-1,0,1,-1,1,-1};//RDLU
typedef ll Def;
Def d[110][110][11][4];
class DIJ{
	public:
	Def n,m,A;
	vs in;
	DIJ(Def size,Def w,vs fi,Def q){
		n=size;
		in=fi;
		m=w;
		A=q;
	}
	void dij(){
		rep(i,110)rep(j,110)rep(l,11)rep(q,4)
			d[i][j][l][q]=inf;
		int gx,gy;
		priority_queue<tp>q;
		rep(i,in.size())rep(j,in[0].size())
			if(in[i][j]=='G')gx=i,gy=j;
			else if(in[i][j]=='S'){
				if(i+1<n&&in[i+1][j]!='#'){
					d[i+1][j][0][1]=0;
					q.push(tp(0,i+1,j,0,1));
				}
			}
			
		while(!q.empty()){
			Def cost,x,y,a,to;
			tie(cost,x,y,a,to)=q.top();
			cost*=-1;
			q.pop();
			if(cost>d[x][y][a][to])continue;
			rep(k,4){
				int nx=x+dx[k];
				int ny=y+dy[k];
				int na=a,nb=cost;
				int nto=k;
				if(nx<0||ny<0||nx>=n||ny>=m)continue;
				if(in[nx][ny]=='#')continue;
				if(in[x][y]=='S'&&nto-to)continue;
				if(in[nx][ny]=='S'&&nto%2)continue;
				if((to+2)%4==nto)continue;
				if(nto!=to){
					if(to%2){
						if((to+1)%4==nto)na++;
						else nb++;
					}else{
						if((to+1)%4==nto)nb++;
						else na++;
					}
				}
				if(na>A||nb>A)continue;
				if(nb<d[nx][ny][na][nto]){
					d[nx][ny][na][nto]=nb;
					q.push(tp(-nb,nx,ny,na,nto));
				}
			}
		}
		int out=inf;
		rep(i,11)rep(j,4)if(d[gx][gy][i][j]!=inf){
			cmin(out,i+d[gx][gy][i][j]);
		}
		if(out==inf)cout<<-1<<endl;
		else cout<<out<<endl;
	}
};
signed main(){
	int n,m,k;
	cin>>n>>m>>k;
	vs in(n);
	rep(i,n)cin>>in[i];
	DIJ dij(n,m,in,k);
	dij.dij();
}








Measured memory_bytes: 8504
def main():
    _ = input()
    
    b0, b1, b2 = 0, 0, 0
    for c in input().split():
        n = int(c)
        if n % 4 == 0: b2 += 1
        elif n % 2 == 0: b1 += 1
        else: b0 += 1

    if b1 == 0:
        if b0 < b2 + 2:
            print("Yes")
        else:
            print("No")
    else:
        if b0 < b2 + 1:
            print("Yes")
        else:
            print("No")
            

if __name__ == "__main__":
    main()

Measured memory_bytes: 11096
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,i,j,k,st,ed,head[N],adj[N],nxt[N],w1[N],w2[N],fa[N],d[N];
bool v[N];
void dfs(int x,int dad,int d)
{
	if(d>j)
	{
		i=x;
		j=d;
	}
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad)
			dfs(adj[y],x,d+1);
}
void Dfs(int x,int dad)
{
	for(int y=head[x];y;y=nxt[y])
		if(adj[y]!=dad)
		{
			fa[adj[y]]=x;
			Dfs(adj[y],x);
		}
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&j,&k);
		adj[i*2-1]=k;
		nxt[i*2-1]=head[j];
		head[j]=i*2-1;
		adj[i*2]=j;
		nxt[i*2]=head[k];
		head[k]=i*2;
		++d[j],++d[k];
	}
	i=1,j=0;
	dfs(1,-1,0);
	st=i;
	j=0;
	dfs(i,-1,0);
	ed=i;
	Dfs(st,-1);
	for(i=ed;i;i=fa[i])
		for(j=head[i];j;j=nxt[j])
			v[adj[j]]=true;
	for(i=1;i<=n;++i)
		if(!v[i])
		{
			printf("-1");
			return 0;
		}
	k=0;
	for(i=ed;i;i=fa[i])
	{
		if(i!=st&&i!=ed)
		{
			for(j=1;j<=d[i]-2;++j)
				w1[k+j]=k+j+1;
		}
		w1[k+(i==st||i==ed?1:d[i]-1)]=k+1;
		k+=(i==st||i==ed?1:d[i]-1);
	}
	swap(st,ed);
	for(i=1;i<=n;++i)
		fa[i]=0,v[i]=false;
	Dfs(st,-1);
	for(i=ed;i;i=fa[i])
		for(j=head[i];j;j=nxt[j])
			v[adj[j]]=true;
	for(i=1;i<=n;++i)
		if(!v[i])
		{
			printf("-1");
			return 0;
		}
	k=0;
	for(i=ed;i;i=fa[i])
	{
		if(i!=st&&i!=ed)
		{
			for(j=1;j<=d[i]-2;++j)
				w2[k+j]=k+j+1;
		}
		w2[k+(i==st||i==ed?1:d[i]-1)]=k+1;
		k+=(i==st||i==ed?1:d[i]-1);
	}
	w1[n+1]=0,w2[n+1]=1;
	for(i=1;i<=n+1;++i)
		if(w1[i]!=w2[i])
		{
			if(w1[i]<w2[i])
			{
				for(i=1;i<=n;++i)
					printf("%d ",w1[i]);
			}
			else
			{
				for(i=1;i<=n;++i)
					printf("%d ",w2[i]);
			}
		}
	return 0;
}


Measured memory_bytes: 9856
//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*
    I LOVE CLARICE STARLING

     ♥LOVE♥        ♥LOVE♥
  ♥LOVE♥♥LOVE♥  ♥LOVE♥♥LOVE♥
♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥
   ♥LOVE♥♥LOVE♥♥LOVE♥♥LOVE♥
      ♥LOVE♥♥LOVE♥♥LOVE♥
         ♥LOVE♥♥LOVE♥
            ♥LOVE♥
               ♥


        EXPLAINATION BELOW->
*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
void solve()
{
    double r;cin>>r;
    cout<<sp(16)<<2*pi*r<<"\n";
}
int main()
{
   fastio
   solve();
  return 0;
}
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>
//if you want to apply lowerbound on set use s.lower_bound(key),not the one used for vector
/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/

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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

int N, K;
double tb[110];

signed main() {
    tb[0] = 1;
    for (int i = 1; i < 110; i++)tb[i] = tb[i - 1] * 0.5;
    cin >> N >> K;
    double sum = 0;
    for (int i = 1; i <= N; i++) {
        int cnt = 0, cur = i;
        while (cur < K)cur *= 2, cnt++;
        sum += tb[cnt];
    }
    cout << fixed << setprecision(20);
    cout << sum / N << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll long long
string a,b;
char t[2000];
int main(){
cin>>a>>b;
int as=a.size(),bs=b.size();
int num=as/2,pos=0;
bool ok=0,ok2;


/*for(int k=0;k<2;k++){
int i=0,j=0;
string tmp="";
bool f=k;


while(true){
	if(f){//aからとる
		if(a[pos]==a[i]){tmp.push_back(a[i]);pos++;f=!f;}
		i++;
	}

	else if(!f){
		if(a[pos]==b[j]){tmp.push_back(b[j]);pos++;f=!f;}
		j++;
	}

	if(j>=bs)break;
	if(tmp.size()==as)break;
}

	if(tmp==a)ok=1;
}*/

for(int k=0;k<2;k++){
pos=0;
rep(l,2000)t[l]=' ';

for(int i=k;i<as;i+=2){
	 t[pos++]=a[i];
}

for(int i=0;i<bs;i++){
	int c=0;
	if(b[i]==t[c]){
		for(int j=0;j<bs;j++){
			if(b[j]==t[c])c++;
		}
		if(c==pos)ok=1;
	}

}
}

if(ok||as==1)cout<<"Yes"<<endl;
else cout<<"No"<<endl;

	return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> cntMemo(100010,0);
    ll sum = 0;
    rep(i,n){
        int a;
        cin >> a;
        cntMemo[a]++;
        sum += (ll)a;
    }
    int q;
    cin >> q;
    rep(i,q){
        int b,c;
        cin >> b >> c;
        sum += (ll)cntMemo[b] * (c - b);
        cntMemo[c] += cntMemo[b];
        cntMemo[b] = 0;
        cout << sum << endl;
    }
}


Measured memory_bytes: 3780
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int a,b,c;
  cin>>a>>b>>c;
  if(b-a==c-b)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;

long long powermode(long a,long b)
{
		if(b==0)
		return 1;
		long res = (powermode(a,b/2)%mod);
		if(b%2==0)
		return (res*res)%mod;
		else 
		{
			return (((res*res)%mod)*a)%mod ;
		}
}


int main()
{
	long n;
	cin>>n;
	long long ans = ((powermode(10,n)-(2*powermode(9,n))%mod)%mod+powermode(8,n))%mod;
	ans =  (ans+mod)%mod;
	cout<<ans%mod<<endl;
}


Measured memory_bytes: 3592
import java.util.*;
public class Main{
 public static void main(String arg[])
 {
   Scanner sc=new Scanner(System.in);
   int k=sc.nextInt();
   StringBuilder sb=new StringBuilder();
   for(int i=0;i<k;i++)
   {
    sb.append("ACL"); 
     
   }
   System.out.print(sb);
 }
}

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

int dp[100005];
//dp[i] 足場[i]にいくときの最小コスト


int main(){
  int n;
  int h[100001];
  cin >> n;
  for(int i=1;i<=n;i++)cin >> h[i];

  dp[1]=0;
  dp[2]=abs(h[2]-h[1]);
  for(int i=3;i<=n;i++){
    int a, b;
    a = dp[i-1]+abs(h[i]-h[i-1]);
    b = dp[i-2]+abs(h[i]-h[i-2]);
    //cout << "[" << a << "][" <<b << "]"<<endl;
    dp[i]=min(a,b);
  }

  cout << dp[n] << endl;  
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=300005;

int main(){
    char s[5];
    cin >> s;
    sort(s,s+3);
    if(strcmp(s,"abc")==0) printf("Yes\n");
    else printf("No\n");
    return 0;
}


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

int solve(int N, int W, vector<int>& w, vector<int>& v, map<pair<int, int>, int>& Memo) {
	if (W <= 0 || N < 0) return 0;
	if (Memo.find({ N,W }) != Memo.end()) return Memo[{N, W}];
	Memo[{N, W}] = max((W - w[N] >= 0 ? solve(N - 1, W - w[N], w, v, Memo) + v[N] : 0), solve(N - 1, W, w, v, Memo));
	return Memo[{N, W}];
}

int main() {
	int N, W;
	cin >> N >> W;
	vector<int> w(N),v(N);
	for (int i = 0; i < N; i++) cin >> w[i] >> v[i];
	map<pair<int, int>, int> Memo;
	cout << solve(N - 1, W, w, v, Memo) << endl;
}


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

const int MAX = 2e5 + 111;

int n, z;

bool ask(int n) {
    cout << n << "\n";
    fflush(stdout);
    string x;
    cin >> x;
    if (x == "Vacant") {
        exit(0);
    }
    return (x == "Male");
}

void bin(int l, int r) {
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (ask(mid) == (z ^ (mid % 2 == 1)))
            l = mid;
        else
            r = mid;
    }
    ask(l);
    ask(r);
}

int main() {
/*#ifdef LOCAL
    freopen("xxx.in", "r", stdin);
    freopen("xxx.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);*/
    cin >> n;
    z = ask(0);
    cerr << z << "\n";
    bin(0, n);
    return 0;
}

Measured memory_bytes: 852
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.20 03:31:22
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;




template<typename T>
struct Dijkstra {
private:
    int V;
    struct edge { int to; T cost; };
    vector<vector<edge>> G;
public:
    const T inf = numeric_limits<T>::max();
    
    
    vector<T> d; 
    Dijkstra(int V) : V(V) {
        G.resize(V);
    }
    
    
    void add_edge(int from, int to, T weight, bool directed = false) {
        G[from].push_back({to,weight});
        if (!directed) G[to].push_back({from,weight});
    }
    void build(int s) {
        d.assign(V, inf); 
        typedef tuple<T, int> P; 
        priority_queue<P, vector<P>, greater<P>> pq;
        d[s] = 0; 
        pq.push(P(d[s], s)); 
        while (!pq.empty()) {
            P p = pq.top(); pq.pop();
            int v = get<1>(p);
            
            if (d[v] < get<0>(p)) continue; 
            for (const edge &e : G[v])
            {
                
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    pq.push(P(d[e.to], e.to));
                }
            }
        }
    }
};
int main() {
    int n,m,s,t;cin >> n >> m >> s >> t;
    s--;t--;
    Dijkstra<ll> g1(n),g2(n);
    for (int i = 0; i < m; i++) {
        int u,v,a,b;cin >> u >> v >> a >> b;
        u--;v--;
        g1.add_edge(u,v,a);
        g2.add_edge(u,v,b);
    }
    g1.build(s);
    g2.build(t);
    vector<pair<ll,int>> dist(n);
    for (int i = 0; i < n; i++) {
        dist[i].first = g1.d[i] + g2.d[i];
        dist[i].second = i;
    }
    sort(dist.begin(), dist.end());
    //cout << dist << endl;
    int now = 0;
    for (int i = 0; i < n; i++) {
        while(dist[now].second < i) {
            now++;
        }
        cout << ll(1e15) - dist[now].first << endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  set<string> arare;
  for (int i = 0; i < N; i++) {
    string a;
    cin >> a;
    arare.insert(a);
  }
  cout << (arare.size() == 3 ? "Three" : "Four") << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
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 N  100005

void solve()
{
    ll h;
    cin>>h;
    ll bit=-1;
    rep(i,0,40)
    {
        if((h>>i)&1ll)
            bit=i;
    }
    bit++;
    cout<<((1ll<<bit)-1)<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin>>s;
    vector<int> v(3,0);
    for(auto a:s){
        switch(a){
            case 'a':
                v[0]++;break;
            case 'b':
                v[1]++;break;
            case 'c':
                v[2]++;break;
        }
    }if(s.length()==2){
        if(v[0]==2||v[1]==2||v[2]==2){
            cout<<"NO";
        }else{
            cout<<"YES";
        }
    }else{
        if(max(v[0],max(v[1],v[2]))-min(v[0],min(v[1],v[2]))>1){
            cout<<"NO";
        }else{
            cout<<"YES";
        }
    }
}


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

int main() {
    int d,t,s;
    cin >> d >> t >> s;

    double cast_d = static_cast<double>(d);
    double cast_s = static_cast<double>(s);
    double cast_t = static_cast<double>(t);

    double a = (cast_d / cast_s);
//    std::cout << a << std::endl;
    if (a <= cast_t ) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;
    return 0;
}

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

using namespace std;

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

    unordered_map<string, long long> ump;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        ump[s]++;
    }

    auto ans = 0L;
    for (auto &x:ump) {
        if (x.second > 1) ans += x.second * (x.second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 10660
#include <iostream>

using namespace std;

int main() {
  int N, A, B{}, ans{1}, d{};
  cin >> N >> B;
  while (cin >> A) {
    if (!d && A != B) d = A > B ? 1 : -1;
    else if (d * (A - B) < 0) ++ans, d = 0;
    B = A;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3540
class PriorityQueue
  attr_accessor :data, :size

  def initialize(array = [])
    @data = []
    array.each { |a| push(a) }
  end

  def push(element)
    current = @data.size
    while current > 0
      p_index = parent(current)
      break if @data[p_index] <= element
      @data[current] = @data[p_index]
      current = p_index
    end
    @data[current] = element
  end

  def pop
    ret = @data.first
    x = @data.last
    current = 0
    while have_child?(current)
      a_index = left_child_index(current)
      b_index = right_child_index(current)
      a_index = b_index if @data[b_index] && @data[b_index] < @data[a_index]
      break if @data[a_index] >= x
      @data[current] = @data[a_index]
      current = a_index
    end
    @data[current] = x
    @data.pop

    ret
  end

  def size
    @data.size
  end

  def front
    @data.first
  end

  def empty?
    @data.empty?
  end

  private

  def parent(num)
    (num - 1) / 2
  end

  def left_child_index(num)
    2 * num + 1
  end

  def right_child_index(num)
    2 * num + 2
  end

  def have_child?(index)
    left_child_index(index) < @data.size
  end
end

n, m = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)
pq = PriorityQueue.new(nums.map { |i| -i } )
m.times { pq.push((pq.pop / 2.0).ceil) }
puts -pq.data.inject(:+) 


Measured memory_bytes: 10324
line = gets
line.chomp!

/(\d+)\s+(\d+)/ =~ line

n = $1.to_i
y = $2.to_i

fin = false
i = 0
while i <= n and not fin
  m1 = y - 10000*i
  if m1 == 0 and i == n
    printf("%d 0 0",i)
    fin = true
    break
  elsif m1 < 0
    printf("-1 -1 -1")
    fin = true
    break
  else
    j = 0
    while j <= n-i and not fin
      m2 = m1 - 5000*j
      k = n -i -j
      if m2 == 0
        if k == 0
          printf("%d %d 0",i,j)
          fin = true
        end
        break
      elsif m2 < 0
        break
      end
      if 1000*k == m2 and k >= 0
        printf("%d %d %d",i,j,k)
        fin = true
        break
      end
      j += 1
    end
  end
  i += 1
end

if not fin
  printf("-1 -1 -1")
end


Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
long long dp[N][105];
int main()
{
   int n, w, x;
   long long ans=-1,c;
   vector < pair <int , long long> > v;
    memset(dp, -1, sizeof dp);
   cin >> n >> w;
   for ( int i=0; i< n; i++){
    cin >> x >> c;
    v.push_back({x, c});
   }
   dp[w][0]=0;
   if ( w- v[0].first >=0){
    dp[w- v[0].first][0]= v[0].second;
   }
   for ( int j=0; j<n; j++){
    for (int i =0; i<= w; i++){
        if (dp[i][j] != -1){
        if (j+1 < n){
            dp[i][j+1] = dp[i][j];
            if (i-v[j+1].first >=0){
                dp[i-v[j+1].first][j+1] = max(dp[i-v[j+1].first][j+1], dp[i][j]+v[j+1].second);
            }
        }
        }
        ans  = max (ans , dp[i][j]);
    }
   }
   cout << ans;
    return 0;
}


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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    ll a,b;
    cin >> a >> b;
    if(a <= 0 && b >= 0){
        cout << "Zero" << endl;
    } else  if(a > 0 && b > 0){
        cout << "Positive" << endl;
    } else if(a < 0 && b < 0){
        if(abs(a-b+1) % 2 == 0){
            cout << "Positive" << endl;
        } else {
            cout << "Negative" << endl;
        }
    }
}

Measured memory_bytes: 3588
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**10]*n
dp[0]=0
for i in range(n):
    for j in range(1,k+1):
        if i+j<n:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
print(dp[n-1])

Measured memory_bytes: 52448
a,b = map(int,input().split())
s=input()
if s[a] != '-' :
    print('No')
else :
    ans = 'Yes'
    for i in range(len(s)) :
        if i==a :
            continue
        if s[i] == '-' :
            ans = 'No'
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    map<int, int> m;
    m[1] = 0;
    m[2] = 2;
    m[3] = 0;
    m[4] = 1;
    m[5] = 0;
    m[6] = 1;
    m[7] = 0;
    m[8] = 0;
    m[9] = 1;
    m[10] = 0;
    m[11] = 1;
    m[12] = 0;
    int x, y;
    cin >> x >> y;
    if(m[x] == m[y])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int n,count = 0;
    scanf("%d", &n);
    int p[n];
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &p[i]);
    }
    for(int i = 1 ; i < n-1 ; i++){
        if(p[i-1] > p[i] && p[i] > p[i+1]){
            count++;
        }else if(p[i-1] < p[i] && p[i] < p[i+1]){
            count++;
        }
    }
    printf("%d\n",count);
    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>
#include<stdio.h>
#include <cstdint>
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;

int F;

int main() {

	cin >> F;
	cout << (F - 30) / 2 << endl;

	return 0;
}


Measured memory_bytes: 3092
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;
using ll = long long;

#define REP(i, a) for (int i = 0; i < (a); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a)-1; i >= (b); --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond, yes, no) \
    { cout << ((cond) ? (yes) : (no)) << endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(), (list).rend())
#define ASSERT(cond, mes) assert(cond&& mes)

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template <typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())
    is >> v[i];
    return is;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a) n = a;
    if (n > b) n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u / GCD(u, v) * v;
}

template <typename T>
std::vector<T> enum_div(T n) {
    std::vector<T> ret;
    for (T i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) { ret.push_back(n / i); }
        }
    }
    return ret;
}

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

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

struct ToUpper {
    char operator()(char c) {
        return toupper(c);
    }
};

struct ToLower {
    char operator()(char c) {
        return tolower(c);
    }
};

vector<ll> A(51);
vector<ll> P(51);
ll rec(int n, ll k) {
    if (n == 0) return 1;
    if (k == 1) return 0;
    if (k <= A[n - 1] + 1) return rec(n - 1, k - 1);
    if (k <= A[n - 1] + 2) return P[n - 1] + 1;
    if (k <= A[n - 1] * 2 + 2)
        return P[n - 1] + 1 + rec(n - 1, k - A[n - 1] - 2);
    return 2 * P[n - 1] + 1;
}

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

    int N;
    ll K;
    cin >> N >> K;

    A[0] = 1;
    P[0] = 1;
    REP(i, 50) {
        A[i + 1] = A[i] * 2 + 3;
        P[i + 1] = P[i] * 2 + 1;
    }

    cout << rec(N, K) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int n, i, flagp, flagw, flagg, flagy, cnt;
char a;

int main()
{
	scanf("%d ", &n);
	for(i=0; i<n; i++)
	{
		scanf("%c ", &a);
		if(a=='P' && flagp==0)
		{
			flagp=1;
			cnt++;
		}
		else if(a=='W' && flagw==0)
		{
			flagw=1;
			cnt++;
		}
		else if(a=='G' && flagg==0)
		{
			flagg=1;
			cnt++;
		}
		else if(a=='Y' && flagy==0)
		{
			flagy=1;
			cnt++;
		}
	}
	if(cnt==3) printf("Three");
	else if(cnt==4) printf("Four");
}

Measured memory_bytes: 128
use std::io::Read;

fn read<T: std::str::FromStr>() -> T {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn gcd(a: u64, b: u64) -> u64 {
    if b != 0 {
        gcd(b, a % b)
    } else {
        a
    }
}

/// Enumerate divisors.
///
/// The time complexity is O(sqrt(n)).
///
/// Output: if n = 6, then {1, 2, 3, 6}.
fn divisors(n: u64) -> Vec<u64> {
    let mut res = Vec::new();
    let mut x = 1;
    while x * x <= n {
        if n % x == 0 {
            res.push(x);
            if x * x != n {
                res.push(n / x);
            }
        }
        x += 1;
    }
    res.sort();
    res
}

/// Perform prime factorization.
///
/// The time complexity is O(sqrt(n)).
///
/// Input: n is an integer greater than or equal to 2.
/// Output: if n = 540 = 2^2 * 3^3 * 5, then {(2, 2), (3, 3), (5, 1)}.
fn prime_factor(mut n: u64) -> Vec<(u64, u64)> {
    let mut res = Vec::new();
    let mut x = 2;
    while x * x <= n {
        let mut num = 0;
        while n % x == 0 {
            n /= x;
            num += 1;
        }
        if num != 0 {
            res.push((x, num));
        }
        x += 1;
    }
    if n != 1 {
        res.push((n, 1));
    }
    res
}

fn main() {
    let a: u64 = read();
    let b: u64 = read();
    let c = gcd(a, b);
    let primes = prime_factor(c);
    println!("{}", primes.len() + 1);
}


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

int main(){
    int n,a,b,p1=0,p2=0,p3=0;
    cin >> n >> a >> b;
    for(int i = 0;i < n;i ++){
        int p;
        cin >> p;
        if(p<=a) p1 ++;
        else if(p<=b) p2 ++;
        else p3 ++; 
    }
    cout << min(p1,min(p2,p3)) << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {

        int rate = int.Parse(Reader.ReadLine());

        string ans = "AGC";
        if(rate <1200) {
            ans = "ABC";
        } else if(rate < 2800) {
            ans = "ARC";
        }
        Console.WriteLine(ans);
    
    }


    public class Reader
    {
        static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"


1200





";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define si set <ll>
#define vi vector <ll>
#define popcount(x) __builtin_popcountll(x)
#define mii map <ll,ll>
#define vpi vector <pair <ll,ll> >
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mem0(a) memset(a,0,sizeof(a))
#define rep(i,a,n) for(ll i=a ; i<n ; i++)
#define ld long double
#define rall(a) (a).rbegin(),(a).rend()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
 
ll power(ll b,ll e,ll m)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b%m,e/2,m)%m;
  return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b,e/2);
  return power(b*b,e/2);
}  
bool isPowerOfTwo(ll x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

bool isPrime(ll n)
{
  if(n==1) return 0;
  for(ll i=2;i*i<=n;i++)
    if(n%i==0)
      return 0;
  return 1;
}



void solve()
{
  ll k;
  cin>>k;
  rep(i,0,k) cout<<"ACL";
}

int main()
{
  ll tt=1;
  // cin>>tt;
  while(tt--)
  {
    solve();
    cout<<"\n";
  }
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    System.out.println(N * A < B ? N * A : B);
  }
}

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

void pf(int64_t a,set<int64_t> &s){
  int64_t n=2;
  while(n<=sqrt(a)){
    if(a%n==0){
      a/=n;
      s.insert(n);
    }else{
      n++;
    }
  }
    s.insert(a);
}

int64_t gcd(int64_t a,int64_t b){
  int64_t r=max(a,b)%min(a,b);
  if(r==0){
    return min(a,b);
  }
  return gcd(min(a,b),r);
}

int main(){
  int64_t A,B;
  cin >> A >> B;
  set<int64_t> s;
  s.insert(1);
  pf(gcd(A,B),s);
  cout << s.size() << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll X;

int main() {
	cin >> X;
	if (X % 10 == 0) {
		if ((X % 100) / 10 * 200 + X % 100 <= X) {
			cout << 1 << endl;
			return 0;
		}
	}
	else if (X % 10 <= 5) {
		if ((X % 100) / 10 * 200 + 100 + X % 100 <= X) {
			cout << 1 << endl;
			return 0;
		}
	}
	else {
		if ((X % 100) / 10 * 200 + 200 + X % 100 <= X) {
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}

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



double a, b, x;

int main(){
	cin >> a >> b >> x;
	x /= a;
	
	double th = 0.0;
	if ( x >= a*b*0.5 ){
		// 断面が四角形の内にこぼれる
		double y = a*b-x; // 容器の水が入っていない部分
		
		/*
		  b' = r sin(th)
		  a = r cos(th)
		  a * b' * 0.5 = y
		  th = ?
		  
		  b' = 2y/a
		  b'/a = tan(th)
		  
		  2y/a^2 = tan(th)
		  th = arctan( 2y/a^2 )
		*/
		
		th = atan(2.0*y/(a*a));
	}
	else {
		// 断面が三角形になってからこぼれる
		/*
		  b = r sin(th)
		  a' = r cos(th)
		  a' * b * 0.5 = x
		  th = ?
		  
		  a' = 2x/b
		  b/a' = tan(th)
		  b = 2x/b * tan(th)
		  
		  th = arctan( b^2 / 2x )
		*/
		th = atan(b*b*0.5/x);
	}
	
	cout << std::setprecision(8) << (th*360.0/(2.0*M_PI)) << endl;
	
	return 0;
}



Measured memory_bytes: 384
n,k = map(int, input().split())
p = list(map(int, input().split())) 
c = list(map(int, input().split()))
g = []
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g.append(y)
  else:
    g.append(max(e))
print(max(g))


Measured memory_bytes: 78812
import math
a, b, x = map(int, input().split())
if x == (a**2*b)/2:
    print(45)
elif x > (a**2*b)/2:
    print(math.degrees(math.atan((2*(b-x/(a**2)))/a)))
else:
    print(math.degrees(math.atan(a*b**2/(2*x))))


Measured memory_bytes: 9300
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=2e7+10;
const LL inf=2e16+10;
LL x[maxn];
struct AC
{
    struct zp
    {
        int lson,rson;
        LL sum;
    }tree[maxn];
    int cont,root;
    void init()
    {
        cont=0;
        root=-1;
    }
    int newnode()
    {
        tree[cont].lson=tree[cont].rson=-1;
        tree[cont].sum=0;
        cont++;
        return cont-1;
    }
    void update(int &k,LL l,LL r,LL num)
    {
        if(k==-1) k=newnode();
        tree[k].sum++;
        if(l==r) return ;
        LL mid=(l+r)>>1;
        if(num<=mid)
            update(tree[k].lson,l,mid,num);
        else
            update(tree[k].rson,mid+1,r,num);
    }
    LL query(int k,LL l,LL r,LL ql,LL qr)
    {
        if(k==-1) return 0;
        if(l==ql&&r==qr)
            return tree[k].sum;
        LL mid=(l+r)>>1;
        if(qr<=mid)
            return query(tree[k].lson,l,mid,ql,qr);
        else if(ql>mid)
            return query(tree[k].rson,mid+1,r,ql,qr);
        else
            return query(tree[k].lson,l,mid,ql,mid)+query(tree[k].rson,mid+1,r,mid+1,qr);
    }
}ac;
int main()
{
    int n;
    LL m;
    while(~scanf("%d%lld",&n,&m))
    {
        ac.init();
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&x[i]);
            x[i]-=m;
        }
        for(int i=1;i<n;i++)
            x[i]+=x[i-1];
        ac.update(ac.root,-inf,inf,0);
        LL ans=0;
        for(int i=0;i<n;i++)
        {
            ans+=ac.query(ac.root,-inf,inf,-inf,x[i]);
            ac.update(ac.root,-inf,inf,x[i]);
        }
        printf("%lld\n",ans);
    }
}

Measured memory_bytes: 98560
#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;cin>>n;
    priority_queue<double> v;
    rep(i,n){
        int a;cin>>a;
        v.push(-a);
    }
    double sum=0;
    for(int i=0;i<n-1;i++){
        double a=v.top();
        v.pop();
        double b=v.top();
        v.pop();
        v.push((a+b)/2.0);
    }

    cout <<-v.top();

    
}

Measured memory_bytes: 3736
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include<functional>
#include<ios>
#include<iomanip>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;


int main()
{
	int N;
	string ok="Yes";
	cin>>N;
	int bt=0,bx=0,by=0;
	for(int i=0;i<N;i++)
	{
		int t,x,y,d,tt;
		cin>>t>>x>>y;
		d=abs(x-bx)+abs(y-by);
		tt=(t-bt);
		if(d>tt||(tt)%2!=d%2)
		{
			ok="No";
			break;
		}
		bt=t;
		bx=x;
		by=y;
	}
	cout<<ok<<endl;
}

Measured memory_bytes: 256
import sys
from collections import Counter
finput = sys.stdin.readline

N, M = [int(elem) for elem in finput().split(' ')]
A_list = [int(elem) % M for elem in finput().split(' ')]
assert len(A_list) == N

cuml_A_list = [0] * N
current_sum = 0
for i, A in enumerate(A_list):
    current_sum += A
    current_sum %= M
    cuml_A_list[i] = current_sum

counter = Counter(cuml_A_list)
total_count = 0
for key, value in counter.items():
    if key == 0:
        total_count += value * (value - 1) // 2 + value
    else:
        total_count += value * (value - 1) // 2

print(total_count)


Measured memory_bytes: 55260
#include<stdio.h>
#include <stdlib.h>
int main(void){
	double f;
	int a,b;
	scanf("%d %d",&a,&b);
	f=(a+b)/2;
	if((a+b)%2==0){
	printf("%.0f",f);
	}else{
	printf("%.0f",f+1);
	}
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
 
int main(){
    int N;
    unsigned long long X;
    unsigned long long sum[200010];
    cin >> N >> X;
    for (int i = 1; i <= N; i++){
        //仮想配列かどうかはスピードに影響を与えない。
        unsigned long long tmp;
        cin >> tmp;
        //後々の計算量削減のため、この時点で和を取っておく。
        sum[i] = sum[i-1] + tmp;
    }
    unsigned long long min_energy = 0;
    for (int k=1; k <= N / 2 + 1; k++){
        unsigned long long energy = 0;
        //weightをint型にしたらオーバーフローした。なぜ？
        int weight = 5;
        for (int i=0; i <= N/k; i++){
            if (i == 0){
                weight = 5;
            } else {
                weight = 5 + 2*(i - 1);
            }
            int M = N - k*i;
            int m = (M - k) >= 0 ? M - k : 0L;
            energy += (sum[M] - sum[m]) * weight;
            //printf("%d,%d,%llu\n",k,weight,sum[M]-sum[m]);
        }
        energy += (N + k)*X;
        if (k == 1) min_energy = energy;
        if (min_energy >= energy){
            min_energy = energy;
        }
    }
    printf("%llu",min_energy);
}

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

static const long long inf = (1LL << 32);

int n;
long long d[100][100];

void floyd() {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            if(d[i][k] == inf) continue;
            for(int j = 0; j < n; j++) {
                if (d[k][j] == inf) continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

int main() {
    int e, u, v, c;
    cin >> n >> e;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = ( (i == j) ? 0 : inf);
        }
    }
    
    for (int i = 0; i < e; i++) {
        cin >> u >> v >> c;
        d[u][v] = c;
    }
    
    floyd();
    
    bool negative = false;
    for (int i = 0; i < n; i++) if (d[i][i] < 0) negative = true;
    
    if (negative) {
        cout << "NEGATIVE CYCLE" << endl;
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) cout << " ";
                if (d[i][j] == inf) cout << "INF";
                else cout << d[i][j];
            }
            cout << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3176