akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,sum=1;
    vector<long long>v;
    long long n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        v.push_back(a);
    }
     if(v[0]==v[1]){
            v[0]=v[0]-1;
        }
    for(int i=1;i<n-1;i++){
        if(v[i]==v[i+1]){
            if(v[i]>v[i-1]){
                v[i]=v[i]-1;
            }
        }
        if(v[i]>v[i+1]){
            v[i]=v[i]-1;
        }
    }
    for(int i=0;i<n-1;i++){
        if(v[i]<=v[i+1]){
            sum++;
            //cout<<v[i]<<" "<<sum<<endl;
        }
    }
  //  cout<<sum;
    if(sum==n) cout<<"Yes";
    else cout<<"No";
    return 0;
}



Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,sum=0,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        if((i%3==0)||(i%5==0))
            continue;
        else
        sum+=i;
    }
    cout<<sum<<endl;





}


Measured memory_bytes: 3636
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

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

  int64_t h,w;
  cin>>h>>w;
  if(h==1||w==1){
    cout<<1<<endl;
  }else if(h%2==0||w%2==0){
    cout<<(h*w)/2<<endl;
  }else{
    int64_t large=h/2+1;
    int64_t small=h/2;
    cout<<(large+small)*(w/2)+large<<endl;
  }


  return 0;
}




Measured memory_bytes: 256
//
// Created by yamunaku on 2019/12/29.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    ll n,a,b;
    cin >> n >> a >> b;
    n %=12;
    rep(i,n){
        if(i%2==0){
            a = a-b;
        }else{
            b = a+b;
        }
    }
    cout << a SP b << endl;
    return 0;
}


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

int main()
{
    int a, b, c, d, e, f;
    cin >> a >> b >> c;
    d = max({a, b, c});
    e = min({a, b, c});
    f = a+b+c-(d+e);
    d*=10, d+=f+e;
    cout << d;

}


Measured memory_bytes: 3564
#include<stdio.h>
#include<stdlib.h>

int main (void){
  int z=0;
  int y[10000];
  for(;;){
  int x;
  scanf("%d",&x);
  if(1<=x<=10000 && x!=0){
  y[z]=x;
  z++;
  }
  else{
    break;
  }
  }

  int z1,z2;
  for(z1=0;z1<z;z1++){
    z2=z1+1;
    printf("Case %d: %d\n",z2,y[z1]);
  }

  return(0);
}



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

int rev(int x){
    int reverse = 0;
    while(x > 0){
        reverse = reverse*10 + x%10;
        x /= 10;
    }
    return reverse;
}

int main(){
    int a,b,ans = 0;
    cin >> a >> b;
    for(int i=a;i<=b;i++){
        int k = rev(i);
        if(k==i){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const int maxn = 1e3 + 5;
using namespace std;

int a,b,c;

int main(){
	scanf("%d %d %d", &a, &b, &c);
	if(a + b == c || a + c == b || b + c == a) printf("Yes\n");
	else printf("No\n");
	return 0;
}

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

int main() {
  int K;
  cin >> K;
  int total = 0;
  for (int a = 1; a < K + 1; a++) {
    for(int b = a; b < K + 1; b++) {
      for(int c = b; c < K + 1; c++) {
        int M = 1;
        for (int i = 1; i < a + 1; i++) {
          if (a % i == 0 && b % i == 0 && c % i == 0) {
            M = i;
          }
        }
        if (a == b && b == c) {
          total += M;
        }
        else if (a < b && b < c) {
          total += M * 6;
        }
        else {
          total += M * 3;
        }
      }
    }
  }
  cout << total << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 110000

int f[MAX_N];

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

    if(n==100000){
        cout << '1' << endl;
        return 0;
    }

    rep(i,MAX_N){
        f[i] = 46;
    }
    f[0] = 0;
    queue<P> que;
    f[n] = 0;
    srep(i,1,10){
        if((n*i)%10 < f[n*i/10]){
            f[n*i/10] = (n*i) % 10;
            que.push(P((n*i/10),(n*i) % 10));
        }
    }

    while(que.size() > 0){
        P p = que.front();
        que.pop();
        rep(i,10){
            int a = (n*i + p.first) / 10;
            int b = (n*i + p.first) % 10 + p.second;
            if(b < f[a]){
                f[a] = b;
                que.push(P(a,b));
            }
        }
    }

    int ans = 999;

    srep(i,1,100000){
        int tmp = f[i];
        int ii = i;
        rep(j,5){
            tmp += ii % 10;
            ii /= 10;
        }
        ans = min(ans, tmp);
    }

    cout << ans << endl;
    return 0;
}
 
 


Measured memory_bytes: 2304
N = int(input())
a = list(map(int,input().split()))

ans = 0

for i in range(N):
	judge = 0
	while judge == 0:
		if a[i] % 2 == 0:
			ans += 1
			a[i] = a[i]//2
		if a[i] % 2 == 1:
			judge = 1
	
print(ans)


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

vector<int> g[1000010];
int id[1010][1010];

int main()
{
	int N;
	cin >> N;
	vector<vector<int>> A( N, vector<int>( N - 1 ) );
	for( int i = 0; i < N; i++ ) {
		for( int j = 0; j < N - 1; j++ ) {
			cin >> A[i][j];
			A[i][j]--;
		}
	}

	int n = 0;
	for( int i = 0; i < N; i++ ) {
		for( int j = i + 1; j < N; j++ ) {
			id[i][j] = n;
			n++;
		}
	}
	for( int i = 0; i < N; i++ ) {
		for( int j = 0; j < i; j++ ) {
			id[i][j] = id[j][i];
		}
	}
	for( int i = 0; i < N; i++ ) {
		for( int j = 0; j < N - 2; j++ ) {
			g[id[i][ A[i][j]] ].push_back( id[i][ A[i][j + 1] ] );
		}
	}
	int V = N * (N - 1) / 2;
	vector<int> indeg( V );
	for( int i = 0; i < V; i++ ) {
		for( int to : g[i] ) indeg[to]++;
	}
	stack<int> done;
	for( int i = 0; i < V; i++ ) {
		if( indeg[i] == 0 ) done.push( i );
	}
	vector<int> order;
	while( !done.empty() ) {
		int cur = done.top();
		done.pop();
		order.push_back( cur );
		for( int to : g[cur] ) {
			indeg[to]--;
			if(indeg[to] == 0) done.push(to);
		}
	}
	if( order.size() != V ) {
		cout << -1 << endl;
		return 0;
	}
	vector<int> dp( V );
	for( int i = 0; i < V; i++ ) {
		int cur = order[i];
		for( int to : g[cur] ) {
			dp[to] = max( dp[to], dp[cur] + 1 );
		}
	}
	int ans = *max_element( begin( dp ), end( dp ) ) + 1;

	cout << ans << endl;
}


Measured memory_bytes: 53236
#include "bits/stdc++.h"


using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,s,n) for(int i=(s);i<(n);++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define REPR(i,s,n) for(int i=(s);i>=(n);--(i))
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define DOUBLE fixed << setprecision(10)
#define fi first
#define se second
const double pi = acos(-1.0);
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef deque<ll> dll;
typedef pair<ll, ll> P;
typedef vector<P> vP;
const ll mod = 1e9 + 7;
ll dx[4] = { 1,0,-1,0 };
ll dy[4] = { 0,1,0,-1 };
template <typename T>
bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
};
template <typename T>
bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
};
void Pvll(vll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) cout << v[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}
void Pvvll(vvll v) {
	cout << "------------------------------------------------\n";
	rep(i, v.size()) {
		rep(j, v[i].size()) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void Ps(string s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) cout << s[i] << " ";
	cout << endl;
	cout << "------------------------------------------------\n";
}

void Pvs(vs s) {
	cout << "------------------------------------------------\n";
	rep(i, s.size()) {
		rep(j, s[i].size()) {
			cout << s[i][j] << " ";
		}
		cout << endl;
	}
	cout << "------------------------------------------------\n";
}

void Yes(bool x) {
	if (x) cout << "Yes\n";
	else cout << "No\n";
}

void YES(bool x) {
	if (x) cout << "YES\n";
	else cout << "NO\n";
}

void yes(bool x) {
	if (x) cout << "yes\n";
	else cout << "no\n";
}

void Yay(bool x) {
	if (x) cout << "Yay!\n";
	else cout << ":(\n";
}


ll  n, m, r, l, k, h, w, ans = 0, ret = M;
bool flag = false, flag2 = false, flag3 = false;
string s,t;

void INIT() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << DOUBLE;
}

int main() {
	INIT();

	ll d;
	cin >> n >> d;
	cout << (n / (1+(2 * d))) + (bool)(n % (1+(2 * d))) << endl;

	return 0;
}


Measured memory_bytes: 256
/*
	---------author:O7Oo7oO7O-------------
*/

#include <bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

using ll = long long int;



int main()
{
	IOS

	int n,m;
	cin>>n>>m;
	vector<int> adj[n+1];

	vector<int> H(n+1);
	for(int i=1;i<=n;i++)
		cin>>H[i];
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		
	}

	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int flag=0;
		for(int it:adj[i])
		{
			if(H[i]<=H[it])
				flag=1;
		}
		if(flag==0)
			cnt++;
	}

	cout<<cnt<<"\n";
}

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

using namespace std;

int main (void) {
    string S;
    long long K;
    cin >> S >> K;

    bool found = false;
    for ( int i=0; i<K; i++ ) {
        if ( S.at(i) != '1' ) {
            cout << S.at(i) << endl;
            found = true;
            break;
        }
    }
    if ( !found )
        cout << '1' << endl;

    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
def solve():
    mod = 10**9+7
    L = input()
    N = len(L)-1
    dp = [0]*2
    dp[0] = 1
    dp[1] = 2
    for i in range(1, N):
        if L[i]=='0':
            dp[0], dp[1]=dp[0]*3, dp[1]
        else:
            dp[0], dp[1]=dp[0]*3+dp[1], dp[1]*2
    print((dp[0]+dp[1])%mod)
solve()


Measured memory_bytes: 45660
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define vv(T) vector<vector<T>>
using namespace std;
using ll = long long;
using vint = vector<int>;
using vvint = vector<vector<int>>;
using vll = vector<long long>;
using vvll = vector<vector<long long>>;
using vbool = vector<bool>;
using vvbool = vector<vector<bool>>;
using qint = queue<int>;
using sint = stack<int>;
using pii = pair<int, int>;

int main(){
    bool x;
    cin >> x;

    cout << !x << endl;
    return 0;
}


Measured memory_bytes: 3556
#include<stdio.h>
int main(){
        int a,b,seki,syu;
        scanf("%d", &a);
        scanf("%d", &b);
        seki = a * b;
        syu = 2 * a + 2 * b;
        printf("%d " , seki);
        printf("%d\n", syu);
        return 0;
}

Measured memory_bytes: 596
N = int(input())

#L0=2
#L1=1

#L0=2
#L1=1
#L2=L0+L1=3
#L3=L1+L2=4
#L4=L2+L3=7
#L5=L3+L4=11

if N==0:
  ans = 2
if N==1:
  ans = 1
else:
  ans_left=2
  ans_right=1
  for i in range(N-1):
    ans = ans_left + ans_right
    ans_left = ans_right
    ans_right = ans
    
print(ans)
#def Lucas(i):
#  if i==0:
#    return 2
#  if i==1:
#    return 1
#  else:
#    return Lucas(i-1)+Lucas(i-2)
  
#print(Lucas(N))



Measured memory_bytes: 2940
import std.stdio, std.conv, std.math, std.string, std.range, std.array, std.algorithm, std.typecons;

void main(){
    auto n = readln().strip().to!int();
    auto v = readln().strip().split().map!(to!int)().array();

    int[int] sp1, sp2;

    foreach(i, e; v) {
        if(i % 2 == 0) {
            sp1[e] ++;
        } else {
            sp2[e] ++;
        }
    }

    auto s1 = sort!("a[1] > b[1]")(zip(sp1.keys, sp1.values)).array;
    auto s2 = sort!("a[1] > b[1]")(zip(sp2.keys, sp2.values)).array;

    int k1 = s1[0][0];
    int k2 = s2[0][0];

    if(k1 == k2) {
        s1 ~= tuple(0, 0);
        s2 ~= tuple(0, 0);
        auto s10_21 = s1[0][1] + s2[1][1];
        auto s11_20 = s1[1][1] + s2[0][1];
        if(s10_21 > s11_20) {
            k1 = s1[0][0];
            k2 = s2[1][0];
        } else {
            k1 = s1[1][0];
            k2 = s2[0][0];
        }
    }

    writeln((n+1)/2 - sp1.get(k1, 0) + n/2 - sp2.get(k2, 0));
}

Measured memory_bytes: 13756
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i = (s);i<(int)(n);i++)

int main(){
    int N;
    cin >> N;
    int n = N % 10;
    if(n == 2 || n == 4 || n == 5||n == 7 || n == 9)cout << "hon" << endl;
    else if(n == 3 )cout << "bon" << endl;
    else cout << "pon" << endl;
}


Measured memory_bytes: 3632
n = int(input())
a = {}
a_list = list(map(int,input().split()))
for i in range(n):
    a[a_list[i]] = i+1
a_sorted = sorted(a.items(), key=lambda x:x[0])
b = []
for j in range(n):
    b.append(str(a_sorted[j][1]))
print(' '.join(b))

Measured memory_bytes: 31472
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

    int a[4][4]={};
    rep(i,3){
        int u,v;cin>>u>>v;u--,v--;
        a[u][v]=1;a[v][u]=1;
    }
    rep(i,4){
        int c=0;
        rep(j,4){
            c+=a[i][j];
        }
        if(c>2){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}


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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int a, b;
    cin >> a >> b;
    int ans = a, cnt = 1;
    if(b == 1){
        cout << 0 << endl;
        return 0;
    }
    while(ans < b){
        ans += a - 1;
        cnt++;
    }
    cout << cnt << endl;
}


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

int fsod(int i) {
	int sum = 0;
	while (i > 0) {
		sum += i % 10;
		i /= 10;
	}
	return sum;
}


int main()
{
	int N, A, B;
	int total = 0;
	cin >> N >> A >> B;

	for (int i = 1; i <= N; i++) {
		int sum = fsod(i);
		if (A <= sum && sum <= B) {
			total += i;
		}
	}

	cout << total << endl;

	return 0;
}


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

int a[10001], b[10001];
long long cnt;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<n;i++) scanf("%d",&b[i]);
    long long min_need = 0;
    for(int i=0;i<n;i++){
        cnt += (b[i] - a[i]);
        if(a[i] < b[i]) min_need += (b[i] - a[i] + 1) / 2;
    }
    if(cnt < min_need){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
}


Measured memory_bytes: 384
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]

    def find(self, target):
        if self.parent[target] < 0:
            return target
        else:
            self.parent[target] = self.find(self.parent[target])
            return self.parent[target]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
    ans = 0
    for i in range(n):
        ans = max(ans, uf.get_size(i))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14672
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound


signed main() {
    int N;
    string resl, resm, resr;
    cin >> N;
    cout << 0 << endl;
    cin >> resl;
    if (resl == "Vacant")return 0;
    cout << N - 1 << endl;
    cin >> resr;
    if (resr == "Vacant")return 0;
    cout << N / 2 << endl;
    cin >> resm;
    if (resm == "Vacant")return 0;

    int left = 0, right = N - 1;
    if (((N / 2) % 2 == 0) == (resl == resm)) {
        //空席は後半
        resl = resm;
        left = N / 2;
    } else {
        //空席は前半
        resr = resm;
        right = N / 2;
    }

    for (;;) {
        int n = right - left + 1;
        int m = (left + right) / 2;
        cout << m << endl;
        cin >> resm;
        if (resm == "Vacant")return 0;
        if (((m - left) % 2 == 0) == (resl == resm)) {
            //空席は後半
            resl = resm;
            left = m;
        } else {
            //空席は前半
            resr = resm;
            right = m;
        }
    }
    return 0;
}


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

using namespace std;
int main()
{
    int n;
    cin >> n;
    // int p[n];

    int maxv = 0;
    int sumprice = 0;
    for (int i = 0; i < n; i++)
    {
        int price;
        cin >> price;
        maxv = max(maxv, price);
        sumprice += price;
    }

    sumprice -= maxv / 2;
    cout << sumprice << endl;
}


Measured memory_bytes: 256
K = 100

n = gets.chomp.to_i
h = gets.chomp.split(' ').map(&:to_i)

a = [nil] * K
K.times do |i|
  a[i] = [0] * n
end

h.each_with_index do |v, i|
  (0...v).each do |j|
    a[j][i] = 1
  end
end

def count(v)
  c = 0
  p = 0
  v.size.times do |i|
    if p == 0 && v[i] == 1 then
      c += 1
    end
    p = v[i]
  end
  return c
end

s = 0
K.times do |i|
  s += count(a[i])
end
puts s.to_s

Measured memory_bytes: 3836
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int main(){
  i64 A,B;
  cin>> A >> B;
  i64 d = B - A;
  cout << (d) * (d + 1) / 2 - B << endl;
}


Measured memory_bytes: 256
// **** WHEN THE GOING GETS TOUGH, THE TOUGH GETS GOING. ****

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]

typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
typedef vector<ii> vii;
typedef vector<lii> lvii;

#define min_prq(t) priority_queue<t,vector<t>,greater<t>>
#define max_prq(t) priority_queue<t>
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " is " << a << endl;
	err(++it, args...);
}

//-----------------------------------------------------------------------------------------------------------------------------------------------------------------
#define mod 1000000007
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

ll mod_sum() { return 0LL; }
template<typename T, typename... Args>
T mod_sum(T a, Args... args) { return ((a + mod_sum(args...))%mod + mod)%mod; }

ll mod_product() { return 1LL; }
template<typename T, typename... Args>
T mod_product(T a, Args... args) { return (a*mod_product(args...))%mod; }
//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

string s[100][100];
void pre()
{
	for(int i=0;i<100;i++)
	{
		for(int j=0;j<100;j++) 
		{
			s[i][j]=(i<50)?'#':'.';
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	ll n,m;
	cin>>n>>m;
	pre();
	n--;m--;
	for(int i=0;i<49;i+=2)
	{
		for(int j=0;j<100;j+=2)
		{
			if(n<=0) break;
			s[i][j]='.';
			n--;
		}
		if(n<=0) break;
	}
	for(int i=51;i<100;i+=2)
	{	
		for (int j = 0; j < 100; j+=2)
		{
			if(m<=0) break;
			s[i][j]='#';
			m--;
		}
		if(m<=0) break;
	}
	cout<<"100 100"<<endl;
	for (int i = 0; i < 100; ++i)
	{
		for (int j = 0; j < 100; ++j)
		{
			cout<<s[i][j];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
set<int>mp;
int qq[10];
int main()
{
    for(int i=0;i<5;i++)
        cin>>qq[i];
    int k;
    cin>>k;
    sort(qq,qq+5);
    //for(int i=0;i<5;i++)
       // cout<<":"<<qq[i];
    if(qq[4]-qq[0]>k)
        cout<<":(";
    else
        cout<<"Yay!";
    return 0;
}


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

int main(){
    int N;
    cin >> N;
    int A[N];
    rep(i,N){
        cin >> A[i];
    }
    long long sum=0,c;
    rep(i,N-1){
        if(A[i]>A[i+1]){
            c=A[i]-A[i+1];
            sum+=c;
            A[i+1]+=c;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 4380
#include <stdio.h>

int main(void){
    int i,n,t1,t2,p=0;
    scanf("%d",&n);
    int a[n+1];
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(i=1;i<=n;i++){
        t1=a[i];
        t2=a[t1];
        if(i==t2){
            p++;
        }
    }
    printf("%d",p/2);
    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define hhh cerr<<"hhh"<<endl
#define see(x) cerr<<(#x)<<'='<<(x)<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}

const int maxn = 3e5+7;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;



int main() {
    int a=read(), b=read(), c=read(), k=read();
    if(k<=a) printf("%d\n", k);
    else if(k<=a+b) printf("%d\n", a);
    else printf("%d\n", a-(k-(a+b)));
}

Measured memory_bytes: 3764
#include <iostream>
#include <math.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
int main() {
    int N,A,B;
    cin >> N >> A >> B;
	(N*A >B)?printf("%d",B):printf("%d",N*A); 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(z) for(int i=1;i<=z;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define vi vector<int>
#define pb push_back
#define si set<int>
#define mod  1000000007
#define cl(n,m) (n-1)/m  + 1 ;
#define T() int TT; cin>>TT; while(TT--)
#define P pair<int,int>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const int  N = 3e5 + 5;
int e[N] , w[N] ;
signed main(){
	int n , mx = LLONG_MAX;
	
	string s ;
	cin >> n;
	cin >> s;
	for( int i = 0 ;i<n ;i++){
		if( s[i] == 'W') w[i] = w[i-1] + 1 ;
		else 
			w[i] = w[i-1] ;
	}
	for( int i = n-1 ;i>=0 ;i--){
		if( s[i] == 'E') e[i] = e[i+1 ] + 1 ;
		else e[i] = e[i+1] ;
	}

	for( int i = 0 ;i<n ;i++){
		mx = min( mx, w[i-1] + e[i+1]) ;
	}
	cout << mx ;
}

Measured memory_bytes: 5380
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

long long extgcd(long long a, long long b, long long &x, long long &y) {
	long long d = a;
	if(b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1;
		y = 0;
	}
	return d;
}

long long mod_inverse(long long a, long long m) {
	long long x, y;
	extgcd(a, m, x, y);
	return (x % m + m) % m;
}

pair<long long, long long> linear_congruence(const vector<long long> &A, const vector<long long> &B, const vector<long long> &M) {
	long long x = 0, m = 1;

	for(unsigned i = 0; i < A.size(); ++i) {
		if(B[i] == -1) continue;

		long long a = A[i] * m, b = B[i] - A[i] * x, d = __gcd(M[i], a);
		if(b % d != 0) return make_pair(0, -1);
		long long t = b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d);
		x = x + m * t;
		m *= M[i] / d;
	}

	return make_pair(x % m, m);
}

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

	int n, m, d;
	cin >> n >> m >> d;

	vector<long long> M(m);
	for(auto &e : M) cin >> e;

	vector<long long> A(m, 1);

	for(int i = 0; i < d; ++i) {
		vector<long long> B(m);
		for(auto &e : B) cin >> e;

		long long b, mod;
		tie(b, mod) = linear_congruence(A, B, M);

		n = n - (n - b + mod) % mod;

		if(mod == -1 || n < 0) {
			n = -1;
			break;
		}
	}

	cout << n << endl;

	return EXIT_SUCCESS;
}

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

int main() {
  int n;
  cin >> n ;
 vector<int> d(n);
  for(int i=0 ;i<n; i++){
    cin >> d.at(i);
  }
  int sum=0;
  for(int i=0;i<n;i++){
    sum+=d.at(i);
  }
  int sumsum=0;
  for (int  i=0; i<n;i++){
    sumsum+=(d.at(i)*d.at(i));
  }
  cout <<(sum*sum-sumsum)/2 <<endl;
  
      
      
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VL vector<long long>
#define VPII vector<pair<int,int>>
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long>>
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 998244353;
const int SIZE = 1e6+10;
bitset<4000>X,d[4000];
bitset<4000>A[6];
int len[6],Xn;
char s[SIZE];
int N;
void read(bitset<4000>&input,int& l){
    RS(s);
    l=LEN(s);
    input=bitset<4000>(s);
}
int mi_len=0,mi_id=0;
void add(bitset<4000>a,int l){
    for(int j=l;j>=mi_len;j--){
        if(a[j])a^=d[j];
    }
    if(a.none())return;
    for(int j=mi_len-1;j>=0;j--){
        if(a[j]){
            for(int i=mi_len-1;i>=j;i--){
                d[i]=a<<(i-j);
            }
            int original_len=mi_len;
            mi_len=j;
            add(a<<(original_len-j),original_len);
            return;
        }
    }
}
int main(){
    RI(N);
    read(X,Xn);
    REP(i,N)read(A[i],len[i]);
    mi_len=4000;
    REP(i,N){
        if(mi_len>len[i]){
            mi_len=len[i];
            mi_id=i;
        }
    }
    mi_len--;
    for(int i=3999;i>=mi_len;i--){
        d[i]=A[mi_id]<<(i-mi_len);
    }
    REP(i,N){
        if(i==mi_len)continue;
        add(A[i],len[i]-1);
    }
    bitset<4000>fin=X;
    LL an=0;
    for(int i=Xn-1;i>=mi_len;i--){
        //for(int j=i;j>=0;j--)printf("%d",(int)d[i][j]);
        //puts("");
        an*=2;
        if(X[i])an++;
        an%=MOD;
        if(fin[i])fin^=d[i];
    }
    bool suc=1;
    for(int i=mi_len-1;i>=0;i--){
        if(fin[i]){
            if(!X[i]){
                suc=0;
            }
            break;
        }
    }
    if(suc)an++;
    printf("%lld\n",an%MOD);
    return 0;
}


Measured memory_bytes: 6528
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
//int dx[4] = { 1,0,0,-1 };
//int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 55

const int INF = 1e9 + 7;



int main() {


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

	string s, t;
	cin >> s >> t;
	int s_len = s.length();
	int t_len = t.length();
	bool ans = false;
	int maxi = -1;

	for (int i = 0; i <= s_len-t_len; i++)
	{
		bool exist = true;
		string tmp = s.substr(i, t_len);//部分文字列
		for (int j = 0; j < t_len; j++) {
			if (tmp[j] != t[j])
			{
				if (tmp[j] != '?')
				{
					exist = false;
					break;
				}
			}
		}
		if (exist)
		{
			maxi = max(maxi, i);
		}
	}

	if (maxi == -1)
	{
		cout << "UNRESTORABLE" << endl;
	}
	else
	{
		for (int i = maxi; i < maxi + t_len; i++) {
			s[i] = t[i - maxi];
		}
		for (int i = 0; i < s_len; i++)
		{
			if (s[i] == '?')
			{
				s[i] = 'a';
			}
		}
		cout << s << endl;
	}


	return 0;
}


Measured memory_bytes: 256
n = int(input())
s = [int(input()) for _ in range(n)]

tmp = sum(s)
if tmp % 10 != 0:
    print(tmp)
else:
    tmp2 = float('inf')
    for i in range(n):
        if s[i] % 10 != 0 and s[i] < tmp2:
            tmp2 = s[i]
    if tmp2 == float('inf'):
        print(0)
    else:
        print(tmp - tmp2)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<(int)(m);i++)
#define rrep(i,n,m) for(int i=((int)(n)-1);i>=m;i--)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    cout<<(n>=2*k-1 ? "YES" : "NO")<<endl;
}


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

const int N = 3e5 + 7;

int a[N], b[N], p = 1, mrk[N];

int main() {
	int n, x;
	cin >> n >> x;
	if (x == 1 || x == 2 * n - 1) {
		cout << "No";
		return 0;
	}

	cout << "Yes" << endl;
	if (n == 2) {
		cout << "1 2 3";
		return 0;
	}
	if (x == 2) {
		a[n - 1] = x + 2;
		a[n] = x;
		a[n + 1] = x - 1;
		a[n + 2] = x + 1;
		mrk[x - 1] = mrk[x + 2] = mrk[x] = mrk[x + 1] = 1;
	}
	else {
		a[n - 1] = x - 2;
		a[n] = x;
		a[n + 1] = x + 1;
		a[n + 2] = x - 1;
		mrk[x - 1] = mrk[x - 2] = mrk[x] = mrk[x + 1] = 1;		
	}
	
	for (int i = 1; i <= 2 * n - 1; i++) {
		if (a[i] > 0)
			continue;
		while (mrk[p])
			p++;
		a[i] = p;
		mrk[p] = 1;		
	}
	for (int i = 1; i <= 2 * n - 1; i++)
		cout << a[i] << endl;
	return 0;
}












Measured memory_bytes: 3072
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


X = int(input())


#d = get_sieve_of_eratosthenes(X+10000)
d = seachPrimeNum(X+1000)
#print(d)
for k,sd in enumerate(d):
    if sd>=X:
        nextprime=d[k]
        break

print(nextprime)

#for xx in range(x,x+1000):


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    dsu u(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        u.merge(a, b);
    }

    int ans = 0;
    rep(i, N-1) {
        if (!u.same(0, i+1)) {
            ans++;
            u.merge(0, i+1);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MD 1000000007
#define INF 1ll<<60
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main(){
    ll n;
    cin>>n;
    n--;
    cout<<n*(n+1)/2<<endl;
    return 0;
}

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

mod=998244353

if D[0]!=0:
    print(0)
    exit()

n=[0]*N
n[0]=1
for i in range(1,N):
    if D[i]==0:
        print(0)
        exit()
    n[D[i]]+=1

ans=1
cnt=n[0]+n[1]
for i in range(2,N):
    if n[i]==0:
        if cnt!=N:
            print(0)
            exit()
        else:
            break
    ans=ans*n[i-1]**n[i]
    ans=ans%mod
    cnt=cnt+n[i]
print(ans)


Measured memory_bytes: 14020
#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
using namespace std;


int main()
{
	int n;
	cin >> n;
	vector<int>t(n), x(n), y(n);
	for (int i = 0; i < n; i++)cin >> t[i] >> x[i] >> y[i];
	x.insert(x.begin(),0);
	y.insert(y.begin(),0);
	t.insert(t.begin(), 0);
	for (int i = 0; i < n; i++) {
		int arrowNum = t[i + 1] - t[i];
		int arrowNumX = x[i + 1] - x[i];
		int arrowNumY = y[i + 1] - y[i];

		if (arrowNum >= arrowNumX && arrowNum - arrowNumX >= arrowNumY && (arrowNum - arrowNumX - arrowNumY) % 2 == 0) continue;
		else return cout << "No" << endl,0;
	}
	cout << "Yes" << endl;
}

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

#define M 1046527

long long StrToID(std::string str){
	long long id = 0;
	for (int i = 0; i < str.length(); ++i){
		switch(str[i]){
			case 'A': id = 1 + id*10; break; 
			case 'C': id = 2 + id*10; break;
			case 'G': id = 3 + id*10; break;
			case 'T': id = 4 + id*10; break;
			default : break;
		}
	}
	return id;
}

bool includeNum(long long fig, std::vector<long long> S){
	for (int i = 0; i < S.size(); ++i){
		if(S[i]==fig) return true;
	}
	return false;
}

int main(int argc, char const *argv[]){
	std::vector< std::vector<long long> > Dictionary(M);
	int N,key;
	long long id;
	std::string cmd,str;
	std::cin >> N;

	for (int i = 0; i < N; ++i){
		std::cin >> cmd >> str;
		id = StrToID(str);
		key = id % M;
		if(cmd=="insert"){
			if(!includeNum(id,Dictionary[key])) Dictionary[key].push_back(id);
		}else if(cmd=="find"){
			if(includeNum(id,Dictionary[key])){
				std::cout << "yes" << std::endl;
			}else{
				std::cout << "no" << std::endl;
			}
		}else{
			//exception
		}
	}
	return 0;
}


Measured memory_bytes: 35044
#include <iostream>

using namespace std;

int main() {
    int n, cnt = 0;
	cin >> n;
	
	bool ans = false;
	while (n--) {
		int a, b;
		cin >> a >> b;
		if (a == b) cnt++;
		if (cnt == 3) ans = true;
		if (cnt && a != b) cnt = 0;
	}	
	
	if (ans) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  ll X, Y; cin >> X >> Y;
  ll d = Y / X;
  int ans = 0;
  while (d > 0) {d >>= 1; ans++;}
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws) main2();
  return 0;
}



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

int main() {
	int r, g, b;
	cin >> r >> g >> b;
	int num = 100 * r + 10 * g + b;
	if (num % 4 == 0) {
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define push_back pb
#define make_pair mp
using ll =  long long;
const int INF = 0x3f3f3f3f;

const int MAX_N = 10007;
int N;
string s[MAX_N];

void solve()
{
	long long ans = 0;
	for(int i=0;i<N;++i){
		const string& ss=s[i];
		const int len=ss.length();
		for(int j=1;j<len;++j){
			if(ss[j]=='B'&&ss[j-1]=='A') ans++;
		}
	}
	int enA = 0, stB = 0, both = 0;
	for(int i=0;i<N;++i){
		const string& ss=s[i];
		if(ss[0]=='B'&&ss.back()=='A') both++;
		else if(ss[0]=='B') stB++;
		else if(ss.back()=='A') enA++;
	}
	if(!enA && !stB){
		if(both) ans += both-1;
	}
	else if(enA && stB){
		ans += both+1;
		both=0;
		enA--,stB--;
		ans += min(enA, stB);
	}
	else if(enA){ //stB is zero
		ans+=both;
	}
	else if(stB){
		ans+=both;
	}
	cout << ans << "\n";
}

int main()
{	
	ios::sync_with_stdio(false);
	cin >> N;
	for(int i=0;i<N;++i) cin >> s[i];
	solve();
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define FOR(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define FORUL(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define FORULE(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#if defined(_MSC_VER) || __cplusplus > 199711L
#define AUTOVAR(newvar,v) auto newvar = (v)
#else
#define AUTOVAR(newvar,v) __typeof(newvar) r = (v)
#endif
#define PB(x) push_back(x)
#define MP(x,y) make_pair((x),(y))
#define MEMSET(m,v) memset(m,v,sizeof(m))

typedef long long				 ll;
typedef unsigned long long		ull;

#define DEBUG 1

#if DEBUG
#define DOUT cout<<"["<<__LINE__<<"]:"
#else
#define DOUT 0 && cout
#endif

using namespace std;

#define MAXN 100
#define MAXB (1000*100)

int N;
int A[MAXN+5];
int B[MAXN+5];

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	cin >> N;
	FOR(n,N-1) {
		cin >> B[n];
	}

	// 1 2 3 4 5
	// 2 3 4 5
	// 2 2 3 

	// 5 4 3 2 1
	// 5 4 3 2
	// 5 4 
	FOR(n,N) {
		if(n==0) {
			A[n] = B[n];
			continue;
		}
		if(n==N-1) {
			A[n] = B[n-1];
			continue;
		}
		A[n] = min(B[n-1],B[n]);
	}
	int ans = 0;
	FOR(n,N) {
		ans += A[n];
	}
	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 256
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

#ifdef DEBUG
#else
    #define cerr if (false) cerr
#endif

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int k;
    cin >> k;
    int r = 7;
    forn (i, 0, 1e6 + 50) {
        if (r % k == 0) {
            cout << i + 1;
            return 0;
        }
        r = (1LL * r * 10 + 7) % k;
    }
    cout << -1;
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 10000000000000000
#define ll long long


ll *par, *rk;

void init(ll n){
  n++;
  par = new ll[n];
  rk = new ll[n];
  for(ll i = 0; i < n; i++){
    par[i] = i;
    rk[i] = 0;
  }
}

ll find(ll x){
  if(par[x] == x)
    return x;
  else
    return par[x] = find(par[x]);
}

void merge(ll x, ll y){
  x = find(x);
  y = find(y);
  if(rk[x] > rk[y]){
    par[y] = x;
  }else if(rk[x] < rk[y]){
    par[x] = y;
  }else{
    par[x] = y;
    rk[y]++;
  }
}

bool same(ll x, ll y){
  return find(x) == find(y);
}

using namespace std;

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

  init(n);  for(ll i = 0; i < q; i++){
    ll com, x, y;
    cin >> com >> x >> y;
    if(com == 0){
      merge(x,y);
    }else{
      if(same(x,y))
	cout << 1 << endl;
      else
	cout << 0 << endl;
    }
  }
}

Measured memory_bytes: 3208
//Mir_123
//Credits:- Shashank Keshav
/*Life begins beyond your comfort zone*/
/*Either solve hard questions
  or else don't solve any question*/
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<iterator>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define bin binary_search
#define vmin *min_element
#define vmax *max_element
bool cmp_sec(pair<ll,ll> &a,pair<ll,ll> &b)
{
  if(a.second!=b.second)
    return a.second<b.second;
  return a.first<b.first;
}
//Use set if your want your array to be auto sorted
//sort takes log(N) time
int main(void)
{
  ll n;
  cin>>n;
  vector<ld>p(n);
  for(ll i=0;i<n;i++)cin>>p[i];
  vector<vector<ld> >dp(n,vector<ld>(n+1,0.0));
  dp[0][0]=1-p[0];dp[0][1]=p[0];
  for(ll i=1;i<n;i++)
  {
    dp[i][0]=dp[i-1][0]*(1-p[i]);
    for(ll j=1;j<=i+1;j++)
    {
      dp[i][j]=dp[i-1][j-1]*p[i]+dp[i-1][j]*(1-p[i]);
    }
  }
  ld ans=0.0;
  for(ll i=(n/2)+1;i<=n;i++)ans+=dp[n-1][i];
  cout << fixed << setprecision(12) << ans << endl;
  return 0;
}


Measured memory_bytes: 141056
#include <bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
	int n, a, b;
	cin>>n>>a>>b;
	if(a > b)
		swap(a,b);
	int ans, count = 0;
	if(a==b)
		ans = 0;
	else if((b-a)%2==0)
	{
		ans = (b-a)/2;
	}
	else
	{
		if(b-a == 1)
			ans = min(b-1, n-a);
		else
		{
			if(a-1>n-b)
			{
				ans = n-b+1 + (b-a-1)/2;
			}
			else
				ans = a+ (b-a-1)/2;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3604
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)
s_01 = ('01' * N)[:N]
s_10 = ('10' * N)[:N]

S = np.array(list(S), dtype=str)
s_01 = np.array(list(s_01), dtype=str)
s_10 = np.array(list(s_10), dtype=str)
a = np.count_nonzero(S != s_01)
b = np.count_nonzero(S != s_10)
print(min(a, b))


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

int main()
{
  int n;
  while(1){
    cin >> n;
    if(n == 0) break;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a,a+n);
    int ans = INT_MAX;
    for(int i = 1; i < n; i++)
      ans = min(a[i]-a[i-1], ans);
    cout << ans << endl;
  }
}

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

int main(void)
{
    int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
    int k;
    cin >> k;

    cout << a[k - 1] << endl;
}

Measured memory_bytes: 256
import itertools
import math
import functools

def l(x1, y1, x2, y2):
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)

def f(a, b):
    return l(a[0], a[1], b[0], b[1])

n = int(input())
xy = [tuple(map(int, input().split())) for i in range(n)]

s = []
for p in itertools.permutations(xy):
    r = 0
    for i in range(len(p)-1):
        r += (f(p[i], p[i+1]))
    s.append(r)
print(sum(s) / len(s))


Measured memory_bytes: 4912