akhauriyash/Code-Regression huggingface dataset:
MOD = 10**9 + 7
def rep_sqr(base, k):
    ans = 1
    while k > 0:
        if k & 1:
            ans = ans * base % MOD
        base = base * base % MOD
        k >>= 1
    return ans

n, k = map(int, input().split())

ans = 0
# 全てのgcdについて
gcd = [0 for i in range(k+1)]
for i in reversed(range(1, k+1)):
    d = k // i
    # i, 2i, 3i, ...を含めてd個
    gcd[i] = rep_sqr(d, n)
    # 倍数を上から削除
    j = i * d
    while j > i:
        gcd[i] -= gcd[j]
        j -= i
    ans += gcd[i] * i
    ans %= MOD

print(ans)

Measured memory_bytes: 73616
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;

typedef long long ll;

const ll MOD_CONST = 1000000007;

ll gcd(ll a, ll b,int num) {
	if (a > b) {
		swap(a, b);
	}
	if (num > 0) {
		return gcd(b%a+( MOD_CONST%a*num)%a, a,0);
	}
	if (a == 0) {
		return b;
	}
	
	return gcd(b%a, a,num);
	
}

int main() {
	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector<ll> inv_mod(1000001);
	inv_mod[1] = 1;
	for (int i = 2; i <= 1000000; i++) {
		inv_mod[i] = (MOD_CONST - ((MOD_CONST / i) * inv_mod[MOD_CONST%i]) % MOD_CONST) % MOD_CONST;
	}

	ll lcm = 1;
	map<ll, int> m;
	ll m_num = 0;

	for (int i = 0; i < n; i++) {

		int num = a[i];
		for (int j = 2; j*j <= a[i]; j++) {
			int cnt = 0;
			while (num%j == 0) {

				cnt++;
				num /= j;
			}


			if (cnt > 0 && m[j] < cnt) {

				m[j] = cnt;
			}
		}

		if (num != 1) {
			if (m[num] < 1) {
				m[num] = 1;
			}
		}
		/*
		ll g = gcd(a[i], lcm,m_num);

		cout << g << endl;
		if (lcm*a[i] > MOD_CONST) {
			m_num++;
		}
		lcm = (((lcm * a[i]) % MOD_CONST)*inv_mod[g]) % MOD_CONST;
		m_num *= a[i];
		*/

	}

	for (auto it = m.begin(); it != m.end(); it++) {
		for (int i = 0; i < it->second; i++) {
			lcm = (lcm*it->first) % MOD_CONST;

		}
		//cout << it->first  << " " << it->second<< endl;
	}


	//cout << lcm << endl;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans = (ans + (lcm * inv_mod[a[i]]) % MOD_CONST) % MOD_CONST;
		//cout << (lcm * inv_mod[a[i]]) % MOD_CONST << endl;
	}



	cout << ans << endl;
}


Measured memory_bytes: 8704
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x<y?x:y)
#define ABS(x) (x>0?x:-(x))
#define INF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

typedef long long int lli;

void swap(int* a, int* b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void ll_swap(lli* a, lli* b)
{
    lli tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int gcd(int a, int b)
{
    if (a < b)
        swap(&a, &b);

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

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

long power(long x, int n) {
    long ans = 1;
    while (n > 0) {
        if ((n & 1) == 1) {
            ans = ans * x;
        }
        x = x * x;
        n >>= 1;
    }
    return ans;
}

lli comb(lli n, lli r)
{
    if (n == 0)
        return 0;

    if (r == 0 || r == n)
        return (1);
    else if (r == 1)
        return (n);
    return (comb(n - 1, r - 1) + comb(n - 1, r));
}

/*
#define MAX 100000
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
// 二項係数計算
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
*/   

int main()
{
    int M, N, K, L;
    int a[100000];
    lli count = 0;
    lli temp, temp2;
    char S[10];
  
    scanf("%s", &S);

    if (S[2] == S[3] && S[4] == S[5])
        printf("Yes");
    else
        printf("No");


}


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

# N < Kの場合があることに注意


INT_MIN = -1 * (10**10)

ans = INT_MIN

NK = min(N, K)
for left in range(0,NK+1):
    for right in range(0, NK+1-left):
        #print("========")
        #print(left, right)
        #print(V[:left], V[left:N-right], V[N-right:])
        
        rest_ope = K-left-right
        #print(rest_ope)
        my_v = V[:left]+V[N-right:]
        sum_v = 0
        for i, x in enumerate(sorted(my_v)):
            if x < 0 and i < rest_ope:
                continue
            else:
                sum_v += x
        #print(sum_v)
        ans = max(ans, sum_v)
        
print(ans)
            
            



Measured memory_bytes: 40560
//Let's join Kaede Takagaki Fan Club !!
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <atcoder/all>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
#define all(x) x.begin(),x.end()
template<class T>
void dmp(T a){
	rep(i,a.size()) cout << a[i] << " ";
	cout << endl;
}
template<class T>
bool chmax(T&a, T b){
	if(a < b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
bool chmin(T&a, T b){
	if(a > b){
		a = b;
		return 1;
	}
	return 0;
}
template<class T>
void g(T &a){
	cin >> a;
}
template<class T>
void o(const T &a,bool space=false){
	cout << a << (space?' ':'\n');
}
//ios::sync_with_stdio(false);
const ll mod = 998244353;
template<class T>
void add(T&a,T b){
	a+=b;
	if(a >= mod) a-=mod;
}
struct S{
	ll sum, sum_base;
};
struct F{
	ll ch_digit;
};
S op(S l, S r){ return S{(l.sum+r.sum)%mod, (l.sum_base+r.sum_base)%mod}; }
S e(){ return S{0, 0}; }
S mapping(F l, S r){
	if(l.ch_digit == -1) return r;
	else return S{(r.sum_base*l.ch_digit)%mod, r.sum_base};
}
F composition(F l, F r){
	if(l.ch_digit == -1) return r;
	return l;
}
F id(){
	return F{-1};
}
int n, q;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> q;
	vector<S>ini;
	ll v = 1;
	for(int i=0;i<n;i++){
		ini.pb(S{v, v});
		v = v * 10LL % mod;
	}
	reverse(ini.begin(), ini.end());
	lazy_segtree<S, op, e, F, mapping, composition, id>kaede(ini);
	rep(i, q){
		int l, r; ll d; cin >> l >> r >> d; l--;
		kaede.apply(l, r, F{d});
		cout << kaede.all_prod().sum << '\n';
	}
}

Measured memory_bytes: 16764
#include <bits/stdc++.h>
#define ALL(A) (A).begin(),(A).end()
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)

const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

using namespace std;

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	cin >> N;
	vector<pair<ll,ll>> v;
	for(ll i = 1;i*i <=N;i++){
		if(N%i==0)v.push_back(pair<ll,ll>(i,N/i));
	}
	ll ans = 1LL<<60;
	for(auto x:v){
		ll a = x.first;
		ll b = x.second;
		ans = min(ans,a+b-2);
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
from collections import Counter
s = list(input())
n = len(s)
c = Counter(s)
mod = 10**9+7


left_a  = 0
left_b  = 0
left_c  = 0
left_q  = 0
right_a = c['A']
right_b = c['B']
right_c = c['C']
right_q = c['?']

def add_ans():
    lhs = left_a * pow(3, left_q, mod) + left_q*pow(3, left_q-1, mod)
    rhs = right_c * pow(3, right_q, mod) + right_q*pow(3, right_q-1, mod)
    return  (lhs * rhs)%mod

ans = 0
for i in range(n):
    if s[i] == 'A':
        left_a  += 1
    if s[i] == 'B':
        ans = (ans+ add_ans())%mod
    if s[i] == 'C':
        right_c -= 1
    if s[i] == '?':
        right_q -= 1
        ans = (ans+ add_ans())%mod
        left_q  += 1
print(ans)



Measured memory_bytes: 10008
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  long long ans = 1e9;
  for(int i = -100; i <= 100; i++){
    long long cnt = 0;
    for(int j = 0; j < n; j++){
      cnt += (a[j]-i)*(a[j]-i);
    }
    ans = min(cnt, ans);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vsi = vector<queue<int>>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void bfs(vsi &g, vi &d, queue<int> &q, int v, int depth) {
  queue<int> nq;
  while (!q.empty()) {
    int f = q.front(); q.pop();

    while (!g[f].empty()) {
      nq.push(g[f].front()); g[f].pop();
    }

    if (d[f] == -1) d[f] = depth;
  }
  
  q = nq;
  if (q.empty()) return;
  bfs(g, d, q, q.front(), depth + 1);
}

int main() {
  int n;
  cin >> n;
  
  vsi g(n);
  rep(i, n) {
    int k, u;
    cin >> k >> u;

    rep(j, u) {
      int v;
      cin >> v;

      g[i].push(v - 1);
    }
  }

  vi d(n, -1);
  queue<int> q;
  q.push(0);
  bfs(g, d, q, 0, 0);

  rep(i, n) printf("%d %d\n", i + 1, d[i]);
}



Measured memory_bytes: 3296
#include<bits/stdc++.h>
using namespace std;
int main(){
  int r,d,x;
  cin>>r>>d>>x;
  int a=0;
  for(int i=0;i<10;i++){
    if(i==0){
      cout<<x*r-d<<endl;
      a=x*r-d;
    }
    else{
      cout<<a*r-d<<endl;
      a=a*r-d;
    }
  }
}

Measured memory_bytes: 3560
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, q = map(int, readline().split())
    s = readline().rstrip().decode()
    ac = [0]    
    cnt = 0
    for i in range(1, n):
        if (s[i-1] == 'A') and (s[i] == 'C'):
            cnt += 1
            ac.append(cnt)
        else:
            ac.append(cnt)
    query = []
    for _ in range(q):
        l, r = map(int, readline().split())
        l -= 1
        r -= 1
        print(ac[r]-ac[l])
if __name__ == '__main__':
    main()


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

int main(){
  int k, sum;

  while( cin>>k && k ){
    sum=0;
    for( int i=0,j,len=k*(k-1)/2;i<len;i++ ){
      cin >> j;
      sum +=j;
    }
    sum = sum/(k-1);
    cout << sum << endl;
  }
  return 0;
}

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

using namespace std;

typedef long long ll;

#define REP(i, n) for (ll i = 0; i < ll(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i < ll(b); i++)
#define FORD(i, a, b) for (ll i = b - 1; i >= ll(a); i--)
#define WRAP(y, x, h, w) (0 <= y && y < h && 0 <= x && x < w)

#define ALL(x) (x).begin(), (x).end()

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main()
{
    int a;
    cin>>a;
    cout<<a+a*a+a*a*a<<endl;;
}

Measured memory_bytes: 3596
import java.util.*;

/**
 * Created by zhangrunfeng on 2/21/20
 */
public class Main {

    class Node {
        List<Integer> adjNodeList;

        public Node() {
            this.adjNodeList = new ArrayList<>();
        }
    }

    private int N;
    private Node[] nodes;
    private int[] colors;
    private int[] next;

    public Main(Scanner sc) {
        N = sc.nextInt();
        nodes = new Node[N];
        for (int i = 0; i < N; i++) {
            nodes[i] = new Node();
        }

        colors = new int[N];
        next = new int[N];

        int edgeNum = sc.nextInt();
        for (int i = 0; i < edgeNum; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            nodes[u].adjNodeList.add(v);
            nodes[v].adjNodeList.add(u);
        }

        process();

        int qesNum = sc.nextInt();
        for (int i = 0; i < qesNum; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            if (colors[u] == colors[v]) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
        }
    }

    public void process() {
        int color = 1;
        for (int i = 0; i < N; i++) {
            if (colors[i] == 0) {
                dfs(i, color);
                color++;
            }
        }
    }

    private int getNext(int node) {
        for (int i = next[node]; i < nodes[node].adjNodeList.size(); i++) {
            int nextNode = nodes[node].adjNodeList.get(i);
            if (colors[nextNode] == 0) {
                next[node] = i+1;
                return nextNode;
            }
        }
        return -1;
    }

    public void dfs(int node, int color) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(node);
        colors[node] = color;

        while (!st.isEmpty()) {
            int currNode = st.peek();
            int nextNode = getNext(currNode);
            if (nextNode > 0) {
                st.push(nextNode);
                colors[nextNode] = color;
            } else {
                st.pop();
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Main m = new Main(sc);
    }
}


Measured memory_bytes: 116600
n,k=map(int,input().split())
x=list(map(int,input().split()))
P=[i for i in x if i>=0]
Q=[abs(i) for i in x if i<0]
ans=10**18
if len(P)>=k:
  ans=min(ans,P[k-1])
if len(Q)>=k:
  ans=min(ans,Q[-k])
for i in range(1,k):
  if i<=len(Q) and k-i<=len(P):
    ans=min(ans,Q[-i]*2+P[k-i-1],Q[-i]+P[k-i-1]*2)
print(ans)

Measured memory_bytes: 14564
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    ll N, K;
    cin >> N >> K;
    vec<ll> A(N);
    rep(i, N) {
        cin >> A[i];
        --A[i];
    }
    int logK = 0;
    while ((1LL << logK) < K)
        ++logK;
    vec<vec<int>> dbl(logK+1, vec<int>(N));
    rep(i, N) dbl[0][i] = A[i];

    for (int i = 0; i < logK; ++i) {
        for (int j = 0; j < N; ++j) {
            dbl[i + 1][j] = dbl[i][dbl[i][j]];
        }
    }
    
    int now = 0;
    for (int i = 0; i < logK; ++i) {
        if(K&1) now = dbl[i][now];
        K = (K>>1);
    }
    cout << now + 1 << endl;
}


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

int a, b;

int main() {
    cin >> a >> b;
    rep(i, 1, 2000) {
        if ((int)(1.0 * i * 0.08) == a && (int)(1.0 * i * 0.1) == b) {
            printf("%d\n", i); return 0;
        }
    }
    puts("-1");
    return 0;
}


Measured memory_bytes: 256
from sys import stdin
input=[]
for i in range(3):
  input.append(stdin.readline().rstrip())
  
#print(input)
a_card=list(input[0])
b_card=list(input[1])
c_card=list(input[2])

trash=a_card[0]
a_card.pop(0)
output=0
while(output==0):
  if len(a_card)==0 and trash=="a":
    output="A"
    break
  elif len(b_card)==0 and trash=="b":
    output="B"
    break
  elif len(c_card)==0 and trash=="c":
    output="C"
    break

  if trash=="a":
    trash=a_card[0]
    a_card.pop(0)
  elif trash=="b":
    trash=b_card[0]
    b_card.pop(0)
  elif trash=="c":
    trash=c_card[0]
    c_card.pop(0)
  #print(trash)
  
    
print(output)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<fstream>
#include<queue>
#include<vector>
#include<cstring>
#define MAX 1100
#define INF 10000000

using namespace std;

 

int H, W, N;
int ans;
int d[MAX][MAX];
int gl[MAX][2];
char fac[MAX][MAX];
typedef pair <int, int> P;

void Bfs(int n){
	typedef pair <int, int> P;
	queue <P> que;
	int sx = gl[n][0];
	int sy = gl[n][1];
	int gx = gl[n+1][0];
	int gy = gl[n+1][1];
	int xi[4] = {-1,1,0,0};
	int yi[4] = {0,0,-1,1};
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			d[i][j] = INF;
		}		
			
	//将起点加入队列//记录距离
	que.push(P(sx, sy));
	d[sx][sy] = 0;	
	//队列不为空一直遍历
	while(!que.empty()){
		P p = que.front();
		que.pop();
		if(p.first==gx && p.second==gy)break;
		//四向遍历，加队列 
		for(int i=0; i<4; i++){
			int x = p.first + xi[i];
			int y = p.second + yi[i];
			//在迷宫内，可以经过，第一次经过 
			if(x>=0 && y>=0 && x<H && y<W && fac[x][y]!='X' && d[x][y]==INF){
				d[x][y] = d[p.first][p.second]+1;
				que.push(P(x, y));
			}
		} 
	}
}

int main(){
	cin >> H >> W >> N;
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++){
			cin >> fac[i][j];
			if(fac[i][j] == 'S'){
				gl[0][0] = i;
				gl[0][1] = j;
			}
			if((int)fac[i][j]-48>=1 && (int)fac[i][j]-48<=N){
				gl[(int)fac[i][j]-48][0] = i;
				gl[(int)fac[i][j]-48][1] = j;
			}
		}	
	ans = 0;
	//分为N个循环，终点为起点，寻找下一个终点
	for(int i=0; i<N; i++){
		memset(d, INF, sizeof(d));
		Bfs(i);
		ans+=d[gl[i+1][0]][gl[i+1][1]];
	}
	cout << ans << endl;;
	return 0;
} 


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

char tolower(char ch){
  if( 'A' <= ch && ch <= 'Z' ){
    return ch-'A'+'a';
  }else{
    return ch;
  }
}

int main(){
  int count=0;
  string W;
  cin>>W;
  for(int i=0;i<(int)W.size();i++){
    W[i]=tolower(W[i]);
  }
  string str;
  while(1){
    cin>>str;
    if(str=="END_OF_TEXT")break;
    for(int i=0;i<(int)str.size();i++){
      str[i]=tolower(str[i]);
    }
    if(str==W){
      count++;
    }
  }
  cout<<count<<endl;
  return 0;
}



Measured memory_bytes: 3172
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
        int n;
        double t,sum=0;
        string str;
        cin >> n;
        for(int i=0;i<n;i++){
                cin >> t >> str;
                if(str == "JPY")        sum+=t;
                else sum+=(t*380000);
        }
        cout << sum;
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main()
{
	int a, b, c;
	
	std::cin >> a;
	std::cin >> b;
	std::cin >> c;
	
	if(a+b == c)
	{
		std::cout << "Yes" << std::endl;
	}
	else if(a+c == b)
	{
		std::cout << "Yes" << std::endl;
	}
	else if(b+c == a)
	{
		std::cout << "Yes" << std::endl;
	}
	else
	{
		std::cout << "No" << std::endl;
	}

	return 0;
}


Measured memory_bytes: 256
#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;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int N;
int p[330000];
bool spot[330000];

bool check(vint v) {
    vint ruimax(v), ruimin(v);
    for (int i = 1; i < v.size(); i++)ruimax[i] = max(ruimax[i], ruimax[i - 1]);
    for (int i = (int)v.size() - 2; i >= 0; i--)ruimin[i] = min(ruimin[i], ruimin[i + 1]);
    for (int i = 0; i < v.size(); i++) {
        int cur = ruimin[0] + i * 2;
        if (v[i] > cur) {
            if (ruimax[i] > v[i])return false;
        } else if (v[i] < cur) {
            if (ruimin[i] < v[i])return false;
        }
    }
    return true;
}

signed main() {
    cin >> N;
    for (int i = 1; i <= N; i++)cin >> p[i];
    vint kakcur[2];
    int kakmax[2];
    kakmax[0] = 0;
    kakmax[1] = -1;
    for (int i = 1; i <= N; i++) {
        if (p[i] % 2 != i % 2) {cout << "No" << endl; return 0;}
        if (p[i] == i) {
            if (p[i] != kakmax[i % 2] + 2) {cout << "No" << endl; return 0;}
            if (!check(kakcur[i % 2])) {cout << "No" << endl; return 0;}
            kakcur[i % 2].clear();
            spot[i - 1] = spot[i] = spot[i + 1] = true;
        } else {
            kakcur[i % 2].push_back(p[i]);
        }
        kakmax[i % 2] = max(kakmax[i % 2], p[i]);
    }
    if (!check(kakcur[0])) {cout << "No" << endl; return 0;}
    if (!check(kakcur[1])) {cout << "No" << endl; return 0;}
    for (int i = 1; i <= N; i++)if (!spot[i]) {cout << "No" << endl; return 0;}

    cout << "Yes" << endl;
}


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

struct UnionFind {
  vector<int> siz;
  vector<int> par;  // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

  UnionFind(int N) : par(N) {  //最初は全てが根であるとして初期化
    for (int i = 0; i < N; i++){
      par[i] = i;
    }
  }
  void init(int x){
    //par.resize(x);
    siz.assign(x,1);
    for(int i=0;i<x;i++){
      par[i]=i;
    }
  }

  int root(int x) {  // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x)
      return x;
    return par[x] = root(par[x]);
  }

  void unite(int x, int y) {  // xとyの木を併合
    int rx = root(x);         // xの根をrx
    int ry = root(y);         // yの根をry
    if (rx == ry){
      return;  // xとyの根が同じ(=同じ木にある)時はそのまま
    }
    if(siz[rx]<siz[ry]){
      int temp=rx;
      rx=ry;
      ry=temp;
    }
    siz[rx]+=siz[ry];
    //cout<<"rx="<<rx<<" ry="<<ry<<endl;
    //cout<<"siz[rx]="<<siz[rx]<<" siz[ry]="<<siz[ry]<<endl;
    par[ry] = rx;  // xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
  }

  bool same(int x, int y) {  // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }

  int size(int x){
    //cout<<"root(x)="<<root(x)<<endl;
    return siz[root(x)];
  }
};

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  UnionFind tree(n);
  tree.init(n);
  int a,b;
  for(int i=0;i<m;i++){
    cin>>a>>b;
    a--;
    b--;
    tree.unite(a,b);
  }
  int ans=-1;
  for(int i=0;i<n;i++){
    ans=max(ans,tree.size(i));
    //cout<<tree.siz[i]<<" "<<tree.par[i]<<endl;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4744
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0);
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'

using namespace std;

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

Measured memory_bytes: 256
n, m = map(int, input().split())
ab = []
for i in range(n):
    a = list(map(int, input().split()))
    ab += [a]
ab.sort(key=lambda x: x[0])
count = 0
sum_drink = 0
for i in range(n):
    for j in range(ab[i][1]):
        sum_drink += ab[i][0]
        count+=1
        if count >= m:
            print(sum_drink)
            exit()

Measured memory_bytes: 29020
import sys
 
chash = {}
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    chash[ chr( i ) ] = 0

lines = sys.stdin.readlines()
for i in range( len( lines ) ):
	for j in range( len( lines[i] ) ):
	    if lines[i][j].isalpha():
	        chash[ lines[i][j].lower() ] += 1
 
for i in range( ord( 'a' ), ord( 'z' )+1 ):
    print( "{:s} : {:d}".format( chr( i ), chash[ chr( i ) ] ) )	

Measured memory_bytes: 6728
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        // 整数の入力
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] likeNum = new int[M];
        for (int i=0;i<M;i++){
            likeNum[i] = 0;
        }

        for(int i=0;i<N;i++){
            int K = sc.nextInt();
            for(int j=0;j<K;j++){
                likeNum[sc.nextInt() - 1]++;
            }
        }

        int result=0;
        for(int i=0;i<M;i++){
            if(likeNum[i] == N){
                result++;
            }
        }
        System.out.println(result);

    }
}


Measured memory_bytes: 25644
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

int gcd(int a, int b){
    if (b > a) return gcd(b, a);
    else if(b == 0) return a;
    else return gcd(b, a % b);
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    
    while(T--) {
        int A, B, C, D;
        cin >> A >> B >> C >> D;
        if (A < B || B > D) {
            cout << "No" << endl;
            continue;
        }
        //cout << gcd(B, D) << " " <<  (gcd(B, D) - A % gcd(B, D) % gcd(B, D)) + C - B << endl;
        if (((gcd(B, D) - A % gcd(B, D) % gcd(B, D)) + C - B) >= 0) 
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
    }


    return 0;
}
// A, A - B, A - B + D, A - 2B + D, A - 2B + 2D, A - 3B + 2D
// 9 7 5 9      No  (gcd(7, 9) = 1)
// 9 7 6 9      Yes 
// 14 10 7 12   No  (gcd(10, 12) = 2)
// 14 10 8 12   Yes
// 14 10 9 12   Yes
// 14 10 7 11   No  (gcd(10, 11) = 1)
// 14 10 8 11   No
// 14 10 9 11   Yes
// 9 10 5 10    No
// 10 10 5 10   Yes
// 11 10 5 10   Yes
// 16 10 5 10   No

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

int main() {
	int N;
	cin >>N;
	int sum = 0;
            long long a;
            for(int i=0;i<N;i++){
            	cin >> a;
            	while(a%2==0){
            		sum++;
            		a = a/2;
            	}
            }
	cout << sum<< endl;
}

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

int main(){
  
  int a,b,k;
  
  cin >> a >> b;
  
//  if(b>a){
 //   k=(b+a)/2;
//  }else if(b < a){
//     k = (a -b)/2;
//  }
   k=(b+a)/2;
  if((a+b) == (2*k)||b-a == 2*k){
  	cout << abs(k) << endl;
  }
  else{
    cout <<"IMPOSSIBLE" << endl;
  }
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

#define MAX 100000
#define INF 2140000000
#define MOD 1000000007

int main() {
	int n;
	cin >> n;
	vector<pair<int, int> > a(n);
	vector<int> b(n);

	for (int i = 0; i < n; ++i) {
		cin >> a[i].second >> a[i].first;
	}

	sort(a.begin(), a.end());

	long long cum = 0;

	for (int i = 0; i < n; ++i) {
		cum += a[i].second;

		if (cum > a[i].first) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;

	return 0;
}

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

int main() {

  long long int n;
  cin >> n;

  long long int t = 0;
  long long int x = 0;
  long long int y = 0;

  bool ans = true;

  for ( long long int i = 0; i < n; i++ ) {

    long long int in_t, in_x, in_y;
    cin >> in_t >> in_x >> in_y;

    long long int dx = x - in_x;
    if ( dx < 0 ) dx = -dx;
    long long int dy = y - in_y;
    if ( dy < 0 ) dy = -dy;
    long long int d = dx + dy;

    long long int dt = in_t - t;

    if ( dt < d || ( dt - d ) % 2 != 0 ) {
      ans = false;
    }

    t = in_t;
    x = in_x;
    y = in_y;

  }

  if ( ans == true ) {
    cout << "Yes" << endl;
  }else {
    cout << "No" << endl;
  }

  return 0;

}


Measured memory_bytes: 256
(declaim (optimize (speed 3) (debug 0) (safety 0)))
(let ((N (read))
      (S1 (read-line))
      (S2 (coerce (read-line) 'list)))
  (labels ((f (list acc)
             (if list 
                 (if (eql (first list) (second list))
                     (f (cddr list) (cons 2 acc))
                     (f (cdr list) (cons 1 acc)))
                 (cons 0 acc)))
           (g (list acc)
             (if (and list
                      (cdr list))
                 (case (first list)
                   (1 (case (second list)
                        (1 (g (cdr list) (* acc 2)))
                        (2 (g (cdr list) (* acc 2)))))
                   (2 (case (second list)
                        (1 (g (cdr list) acc))
                        (2 (g (cdr list) (* acc 3)))))
                   (0 (case (second list)
                        (1 (g (cdr list) 3))
                        (2 (g (cdr list) 6)))))
                 (mod acc 1000000007))))
   (format t "~A~%" (g (f S2 nil) 0))))

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

class Main {
    static boolean there (int[][] a, int pos, int n) {
        for (int i = 0; i < n; i++) {
            if (a[i][pos] == 0) return false;
        }
        return true;
    }
    static int func (int[][] a, int pos, int n) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(a[i][pos], min);
        }
        return min;
    }
    public static void main(String args[]) {
        FastReader sc = new FastReader();
        StringBuilder sb = new StringBuilder("");
        int n = sc.nextInt();
        int[][] a = new int[n][26];
        for (int i = 0; i < n; i++) {
            String x = sc.next();
            for (int ii = 0; ii < x.length(); ii++) {
                a[i][x.charAt(ii) - 'a']++;
            }
        }
        for (int i = 0; i < 26; i++) {
            if (there(a, i, n)) {
                int k = func(a, i , n);
                for (int ii = 0; ii < k; ii++) {
                    sb.append((char)(97 + i));
                }
            }
        }
        System.out.println(sb);
    }

    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

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

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

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

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

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

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

Measured memory_bytes: 20820
N = int(input())
S =[]
for i in range(N):
  s = list(str(input()))
  s.sort()
  s = ''.join(s)
  S.append(s)
from collections import Counter
l = Counter(S)
count = []
for i in l.values():
  count.append(i*(i-1)/2)
print(int(sum(count)))


Measured memory_bytes: 19756
n = int(input())
s,t = input().split()

ans = ""
count_s = 0
count_t = 0
for i in range(n*2):
    if i%2 == 0:
        ans += s[count_s:count_s+1]
        count_s += 1
    else:
        ans += t[count_t:count_t+1]
        count_t += 1
print(ans)

Measured memory_bytes: 38256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7


def main():
    a = int(input())
    b = int(input())
    h = int(input())
    return (a+b) * h // 2




print(main())


Measured memory_bytes: 7968
#include <bits/stdc++.h>
using namespace std;
 
int main ()
{
	int n;
	cin >> n;

	long long dp[n][3];

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

	for (int i = 1; i < n; i++) {
		dp[i][0] += max(dp[i-1][1], dp[i-1][2]);
		dp[i][1] += max(dp[i-1][0], dp[i-1][2]);
		dp[i][2] += max(dp[i-1][0], dp[i-1][1]);
	}

	cout << max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2])) << endl;



	return 0;
	
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll sum[2*N];
ll n,x,mod;
int main() {
    cin >> n >> x >> mod;
    map<int, int> m;
    ll s=-1,e,i=1;
    while(1) {
        sum[i]=x +sum[i-1];
        if (m[x] == 0) m[x]++;
        else if (m[x] == 1) {
            if(s==-1) s = i;
            m[x]++;
        } else{
            e = i - 1;
            break;
        }
        x=((x%mod)*(x%mod))%mod;
        i++;
        //if(x<0) cout<<x<<endl;
    }

    ll k=(e-s+1);
    if(s>k) s-=k,e-=k;
    //cout<<s<<" "<<e<<endl;
    ll ans=0;
    ll res=sum[e]-sum[s-1];
    ans=sum[s-1]+res*((n-(s-1))/k)+(sum[s+(n-(s-1))%k-1]-sum[s-1]);
    //else ans=sum[s-1];
    cout<<ans;
    return 0;
}


Measured memory_bytes: 6660
/* Isn't passion overrated?*/

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ll long long
#define mod 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
int main()
{
    ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll sum = 0;
    ll t = min(k,a);
    sum += t;
    k -= t;
    a -= t;
    t = min(k,b);
    k -= t;
    b -= t;
    t = min(k,c);
    sum -= t;
    k -= t;
    c -= t;
    cout<<sum;
    return 0;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x,y;
	cin>>x>>y;
	if(x%y==0){
		cout<<-1<<endl;
	}else{
		cout<<x<<endl;
	}
	return 0;
}


Measured memory_bytes: 3624
while True:
    H, W = map(int, input().split())
    if H == W == 0:
        break
    line = '#.' * (W // 2 + 1)
    for i in range(H):
        if i % 2:
            print(line[1:W+1])
        else:
            print(line[:W])
    print()


Measured memory_bytes: 5608
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	c := make(map[string]int)
	max := -1
	for i := 0; i < n; i++ {
		var str string
		fmt.Scan(&str)

		v, ok := c[str]
		if !ok {
			c[str] = 1
		} else {
			c[str] = v + 1
		}
		if c[str] > max {
			max = c[str]
		}
	}

	strs := make([]string, 0)
	for str, count := range c {
		if count == max {
			strs = append(strs, str)
		}
	}
	sort.Strings(strs)

	for _, str := range strs {
		fmt.Println(str)
	}
}


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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
  for(auto &e:u) fill_v<T>(e,v...);
}


/*
int main(void) {
  int64 N, X;
  cin >> N >> X;
  int64 D = 0, cnt = 1;
  REP(i, N) {
    int64 L;
    cin >> L;
    D += L;
    cnt += D <= X;
  }
  cout << cnt << endl;
}
*/

int main(void) {
  int64 X, A;
  cin >> X >> A;
  if (X < A) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }
}

Measured memory_bytes: 256
n = int(input())
s = input()
bad = [0] * n
pair = 0
b_num = []
ans = 0
for i in range(n - 1):
    if s[i] == "B":
        b_num.append(i)
        continue
    for j in range(i + 1, n):
        if s[j] == "B" or s[j] == s[i]: continue
        pair += 1
        if 2 * i - j >= 0:
            bad[2 * i - j] += 1
        if (j - i) % 2 == 0:
            bad[(i + j) // 2] += 1
        if 2 * j - i < n:
            bad[2 * j - i] += 1
if s[-1] == "B":
    b_num.append(n - 1)

for k in b_num:
    ans += pair - bad[k]
print(ans)

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

double kai(int n){
    double p=1;
	for(int i=0;i<n;i++) p/=2;
    double pp=(1-p)/p;
    return 1+p*pp+p*pp*pp;
}

int main(){
	int n,m,ans;
  	cin>>n>>m;
    int time=100*n+1800*m;
  	ans=time*kai(m);
    cout<<ans<<endl;
}  

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,n,m) for(int i=n;i<int(m);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int vx[]={0,0,-1,1};
int vy[]={1,-1,0,0};
int dx[]={1,0,-1,1,-1,1,0,-1};
int dy[]={1,1,1,0,0,-1,-1,-1};

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	

const ll mod=1e9+7;
const int INF=INT_MAX/2;
const int N_MAX=100010;

int calcpow(int i, int k){
	int res=0;
	while(i<k){
		i*=2;
		res++;
	}
	return res;
}
int main(){
	int n,k;
	cin>>n>>k;
	double ans=0;

	for(int i=1;i<=n;i++){
		ans+=(1.0/n * pow(0.5,calcpow(i,k)));
	}
	printf("%.13f\n",ans);
	return 0;
}



Measured memory_bytes: 256
#include<stdio.h>

#define MAX 50000
#define sqrtMAX 224

int main(void)
{
  int n;
  int b[MAX+1] = {0};
  int p[5134] = {0};
  int c[MAX+1] = {0};
  int i, j;
  int count;

  // ツエツδ可トツスツテツネツスツづ個づ督づゥツつ「
  b[0] = 1;
  b[1] = 1;
  for(i=4; i<=MAX; i+=2)
      b[i] = 1;
  for(i=3; i<sqrtMAX; i+=2)
      for(j=i+i; j<=MAX; j+=i)
          b[j] = 1;

  // ツ素ツ青板づーツ板イツつォツ出ツつキ
  count = 0;
  for(i=0; i<=MAX; i++) {
    if(b[i])
      continue;
    p[count++] = i;
  }

  for(i=0; i<count; i++) {
    for(j=i; j<count; j++) {
      if(p[i]+p[j] > MAX)
	break;
      c[p[i]+p[j]]++;
    }
  }

  while(scanf("%d", &n)!=EOF) {
    if(n==0)
      break;
    printf("%d\n", c[n]);
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
const double pi = 3.14159265358979;

int n;
long long a[100000];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	__int128 prod = 1;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	for(int i = 0; i < n; i++){
		prod *= a[i];
		if(prod > (__int128)1e18){
			cout << "-1\n";
			return 0;
		}
	}
	long long prn = prod;
	cout << prn << "\n";
	return 0;
}

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

int main(){
    int x, y;
    cin >> x >> y;
    if (x == 2 && y == 2) cout << "Yes" << endl;
    else if ((x==4 || x==6 || x==9 || x==11) && (y==4 || y==6 || y==9 || y==11)) cout << "Yes" << endl;
    else if ((x==1 || x==3 || x==5 || x==7 || x==8 || x==10 || x==12) && (y==1 || y==3 || y==5 || y==7 || y==8 || y==10 || y==12)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
        
    public void solve(){
        Scanner sc=new Scanner(System.in);
		
       while(true){
	   	int n=sc.nextInt();
		if(n==0) break;
		int cnt=0;
		boolean flag=false;
		for(int i=0;i<n;i++){
			int k=sc.nextInt();
			if(k>0) cnt++;
			if(k>1) flag=true;
		}
		if(!flag) System.out.println("NA");
		else System.out.println(cnt+1);
       }
    }
	public static void main(String[]args){
		Main obj=new Main();
		obj.solve();
	}
}

Measured memory_bytes: 158668
from sys import setrecursionlimit
setrecursionlimit(10**9)
N, X = map(int, input().split())

# A:厚さ P:パティの数
a = [1]
p = [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= a[n-1] + 1:
        return f(n-1, x-1)
    else:
        return p[n-1] + 1 + f(n-1, x-2-a[n-1])

print(f(N, X))


Measured memory_bytes: 38384
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
using namespace std ;

#define MAXN 107
int n ;
int a[ MAXN ] ;

int ans[ MAXN ] ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    for ( int i = n ; i >= 1 ; -- i ) {
        int j ;
        for ( j = i ; j >= 1 ; -- j ) {
            if ( a[ j ] == j ) { break ; }
        }
        if ( j == 0 ) { printf ( "-1\n" ) ; return ; }
        ans[ i ] = j ;
        for ( int t = j ; t < i ; ++ t ) {
            a[ t ] = a[ t + 1 ] ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        printf ( "%d\n" , ans[ i ] ) ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}


Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n,k=LI()
  a=LI()

  a.sort()
  b=[]

  _a=a[0]
  c=1
  for x in a[1:]:
    if _a==x:
      c+=1
    else:
      b.append([_a,c])
      _a=x
      c=1
  b.append([_a,c])

  b=sorted(b,key=lambda x:x[1])

  ans=0
  for i in range(len(b)-k):
    ans+=b[i][1]

  return ans

print(main())


Measured memory_bytes: 37132
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned long long ll;
int main() {
    string str;
    cin>>str;
    ll len=str.size(),a1,ans=0,c[125]={0};
    for(a1=0;a1<len;++a1){
        ++c[str[a1]];
    }
    for(a1=97;a1<=122;++a1){
        ans=ans+c[a1]*(len-c[a1]);
    }
    cout<<ans/2+1<<"\n";
	return 0;
}


Measured memory_bytes: 640
function main(input){
  const lines = input.split('\n');
  const NW = lines.shift().split(' ').map(x => parseInt(x));
  const N = NW[0]
  const W = NW[1]
  const items = lines.map(line => line.split(' ').map(x => parseInt(x)));

  const first = items.shift();
  const first_weight = first[0];
  const first_value = first[1];
  var value_sum = first_value;
  dp = [0]

  for(var i=1;i<=value_sum;i++){
    dp[i]=first_weight;
  }

  for(var i=0;i<items.length;i++){
    var current_weight = items[i][0];
    var current_value = items[i][1];
    value_sum += current_value;

    for(var value=value_sum;value>0;value--){

      if(value >= current_value){
        var prev_weight = dp[value - current_value];
        if(dp[value]==undefined){
          dp[value] = current_weight + prev_weight;
        }else{
          dp[value] = Math.min(prev_weight+current_weight, dp[value]);
        }
      }else{
        if(dp[value]==undefined){
          dp[value]=current_weight;
        }else{
          dp[value]=Math.min(current_weight, dp[value]);
        }
     }
    }
  }

  var result = 0;

  for(var i=dp.length-1;i>=0;i--){
    if(dp[i]<=W){
      result = i;
      break;
    }
  }

  console.log(result);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 48076
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String X = sc.next();
		String Y = sc.next();
		char x = X.toCharArray()[0];
		char y = Y.toCharArray()[0];
		if (x < y) System.out.println("<");
		else if (y < x) System.out.println(">");
		else System.out.println("=");
	}
}

Measured memory_bytes: 23124
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>
#include <cstdint>
#include <complex>
#include <bitset>

#define rep(i,n) for (int i = 0; i < (n); ++i)

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

const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};


int N = 1 << 18;
int bit[1 << 18];

void add(int a, int w) { 
    for (int x = a; x <= N; x += (x & -x)) bit[x] += w;
}

int sum(int a) {
    int res = 0;
    for (int x = a; x > 0; x -= (x & -x)) res += bit[x];
    return res;
}


int main() {
    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];

    ll median = ll(n) * ll(n+1) / 2 / 2 + 1;

    int left = 0;
    int right = 1e9;
    int mid;
    while (right - left > 1) {
        mid = (right + left) / 2;
        ll cnt = 0;

        vector<int> b(n);
        rep(i, n) {
            if (a[i] <= mid) {
                b[i] = 1;
            } else {
                b[i] = -1;
            }
        }
        vector<int> bcum(n+1);
        rep(i, n) {
            bcum[i+1] = bcum[i] + b[i];
        }

        // bcum[i] - bcum[j] > 0 (i > j)となるものを数える
        memset(bit, 0, sizeof(bit));
        for (int i = 0; i <= n; i++) {
            add(bcum[i] + 1e5+1, 1);
            cnt += sum(bcum[i]-1 + 1e5+1);
        }

        if (cnt < median) left = mid;
        else right = mid;
    }

    cout << right << endl;



    return 0;
}


    


Measured memory_bytes: 2496
#include <bits/stdc++.h>
#include <ext/hash_map>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

#define REP(i,n) for( (i)=0 ; (i)<(n) ; (i)++ )
#define rep(i,x,n) for( (i)=(x) ; (i)<(n) ; (i)++ )
#define REV(i,n) for( (i)=(n) ; (i)>=0 ; (i)-- )
#define FORIT(it,x) for( (it)=(x).begin() ; (it)!=(x).end() ; (it)++ )
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
#define rforeach(it,c) for(__typeof((c).rbegin()) it=(c).rbegin();it!=(c).rend();++it)
#define foreach2d(i, j, v) foreach(i,v) foreach(j,*i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define MMS(x,n) memset(x,n,sizeof(x))
#define mms(x,n,s) memset(x,n,sizeof(x)*s)
#define pb push_back
#define mp make_pair
#define NX next_permutation
#define UN(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define CV(x,n) count(all(x),(n))
#define FIND(x,n) find(all(x),(n))-(x).begin()
#define ACC(x) accumulate(all(x),0)
#define PPC(x) __builtin_popcountll(x)
#define LZ(x) __builtin_clz(x)
#define TZ(x) __builtin_ctz(x)
#define mxe(x) *max_element(all(x))
#define mne(x) *min_element(all(x))
#define low(x,i) lower_bound(all(x),i)
#define upp(x,i) upper_bound(all(x),i)
#define NXPOW2(x) (1ll << ((int)log2(x)+1))
#define PR(x) cout << #x << " = " << (x) << endl ;

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;

const int OO = (int) 2e9;
const double eps = 1e-9;

const int N = 200005;

int n;
int h[N], a[N];
ll dp[N];
ll mx[1 << 19];

void update(int idx, ll val, int node = 0, int l = 0, int r = n - 1) {
	mx[node] = max(mx[node], val);
	if (l >= r)
		return;
	int m = (l + r) >> 1;
	if (idx <= m)
		update(idx, val, (node << 1) + 1, l, m);
	else
		update(idx, val, (node << 1) + 2, m + 1, r);
}

ll query(int fr, int to, int node = 0, int l = 0, int r = n - 1) {
	if (fr > r || to < l)
		return 0;
	if (l >= fr && r <= to)
		return mx[node];
	int m = (l + r) >> 1;
	ll v1 = query(fr, to, (node << 1) + 1, l, m);
	ll v2 = query(fr, to, (node << 1) + 2, m + 1, r);
	return max(v1, v2);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
#ifndef ONLINE_JUDGE
//	freopen("in.txt", "rt", stdin);
//	freopen("out.txt", "wt", stdout);
#endif
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		h[i]--;
	}
	for (int i = 0; i < n; i++)
		cin >> a[i];
	ll res = 0;
	for (int i = n - 1; i >= 0; i--) {
		dp[i] = query(h[i] + 1, n - 1) + a[i];
		update(h[i], dp[i]);
		res = max(res, dp[i]);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 7424
using System;
using System.Linq;
namespace aaaaaaaaaaaa
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var r = (a[0] + a[1] - 1) / a[1] * a[2];

            Console.WriteLine(r);
        }
    }
}


Measured memory_bytes: 28296