akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

int vs[100000+10];
int cs[100000+10];
map<int,ll> hist;

int main(void) {
  int N, M;
  scanf("%d%d", &N, &M);
  hist[0] = 1;
  REP(i, N) {
    scanf("%d", &vs[i]);
    cs[i+1] = (cs[i] + vs[i]) % M;
    hist[cs[i+1]]++;
  }
  ll res = 0;
  for(auto e : hist) {
    res = res + e.second * (e.second-1) / 2;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 30
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define FORALL(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FOREACH(i,c) for(auto (i) : (c))
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cout<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

class P
{
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P operator-(const P&q){P t;t.x=x-q.x;t.y=y-q.y;return t;}
  P operator-=(const P&q){x-=q.x;y-=q.y;return *this;}
  template<typename T> P operator*(T d){return P(x*d,y*d);}
  template<typename T> P operator*=(T d){x*=d;y*=d;return *this;}
  template<typename T> P operator/(T d){return P(x/d,y/d);}
  template<typename T> P operator/=(T d){x/=d;y/=d;return *this;}
  bool operator<(const P&q){return (x!=q.x)?(x<q.x):(y<q.y);}
  bool operator>(const P&q){return (x!=q.x)?(x>q.x):(y>q.y);}
  double norm(void){return sqrt(x*x+y*y);}
  double arg(void){return acos(x/this->norm())*P(1,0).sign(*this);}
  P rotate(double t){double c=cos(t),s=sin(t);return P(c*x-s*y,s*x+c*y);}
  P reverseX(void){return P(-x,y);}
  P reverseY(void){return P(x,-y);}
  P unit(void){return (*this)/(*this).norm();}
  P floor(void){return P((int)x,(int)y);}
  double dot(const P&q){return x*q.x+y*q.y;}
  double det(const P&q){return x*q.y-y*q.x;}
  int sign(const P&q){double d = (*this).det(q); return (d>0)-(d<0);}
  bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}
  P intersection(P p1,P p2,P q1,P q2){return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}
};

int main()
{
  P p1,p2,q,r;
  while(~scanf("%lf,%lf,%lf,%lf,%lf,%lf",&p1.x,&p1.y,&p2.x,&p2.y,&q.x,&q.y))
  {
    double th = (p2-p1).arg();
    r = p1+(q-p1).rotate(-th).reverseY().rotate(th);
    printf("%lf %lf\n",r.x,r.y);
  }
  return 0;
}

Measured memory_bytes: 3616
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

# 入力
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))


# バックトラック法により解を求める関数。i=1のとき、Xの手番、i=-1のときYの手番
@lru_cache(maxsize=None)
def f(i, m):
    return (
        max(
            abs(W - a[-1]) if m == N else abs(a[-(m + 1)] - a[-1]),
            max(f(-i, k) for k in range(1, m))
        ) if i == 1 and m >= 2 else
        min(
            abs(a[-(m + 1)] - a[-1]),
            min(f(-i, k) for k in range(1, m))
        ) if i == -1 and m >= 2 else
        abs(a[-2] - a[-1]) if N >= 2 else
        abs(W - a[-1])
    )


# 出力
ans = f(1, N)
print(ans)


Measured memory_bytes: 48860
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split('\n');

while (line = lines.shift()) {
  const dim = line.split(' ');
  const a = dim[0];
  const b = dim[1];
  const area = a * b;
  const perimeter = a * 2 + b * 2;
  console.log(area, perimeter);
} 


Measured memory_bytes: 15380
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    public static String repeat(char c, int n){
        String ans = "";
        for(int i=0;i<n;i++) ans = ans + c;
        return ans;
    }
    public static int[] countChar(String s){
        int[] ans = new int[26];
        for(int i=0;i<s.length();i++){
        	ans[s.charAt(i)-'a']++;
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] count = new int[26];
        for(int i=0;i<26;i++)count[i]=100;
        for(int n=0;n<N;n++){
        	String s = sc.next();
        	int[] a = countChar(s);
        	for(int i=0;i<26;i++) count[i]=Math.min(count[i],a[i]);
        }
        for(int i=0;i<26;i++){
        	char c = (char)('a'+i);
        	System.out.print(repeat(c,count[i]));
        }
        System.out.println();
    }
}


Measured memory_bytes: 23252
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]
    guki = list(map(int, input().split()))
    ans=0
    for i in range(2 ** n): # ｎは2進法にしたときの桁数
        # スイッチon/offリスト作る
        switch=[False]*n
        for j in range(n):
            # 一番右の桁から１になってるかどうかチェッ
            if (i >> j) & 1:
                switch[n-j-1]=True

        # 電球ごとに光ってるかチェック
        # 何個の電球が光ってるかカウント
        light=0
        for k in range(m):
            # 電球に対応しているスイッチが何個onになってるかカウント
            cnt=0
            for x in range(l[k][0]):
                if switch[l[k][x+1]-1]:
                    cnt+=1
            if cnt%2==guki[k]:
                light+=1
        if light==m:
            ans+=1
    print(ans)
resolve()

Measured memory_bytes: 42480
//#include <stdio.h>
#include <bits/stdc++.h>
#include <climits>
using namespace std;
int main(){
    int n;
    cin >> n;
    int i=0;
    vector<int> list;
    list.push_back(0);
    long long sum=0;
   while(sum <n){
       i++;
       sum+=i;
       list.push_back(i);
   }
   list.erase(list.begin() + sum-n);
   
   for (int i = 0; i < list.size(); i++)
   {
       if(list.at(i)!=0){
       cout << list.at(i) << endl;
}
}
    return 0;
}

Measured memory_bytes: 384
import java.util.*;

class Main{
	public static void main(String[] args){
    	Scanner scn = new Scanner(System.in);
      	int A = scn.nextInt();
      	int B = scn.nextInt();
      	int C = scn.nextInt();
      	int min = A + B + C - Math.max(A, Math.max(B, C));
      	System.out.println(min);
      	scn.close();
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define Decimal fixed << setprecision(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}
constexpr int INF = 1 << 30 - 1;
constexpr long long LLINF = 1LL << 60;
constexpr long long MOD = 1000000007;

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


int main()
{
  int N;
  cin >> N;
  vector<ll> A(N), T(N);
  REP(i, N) cin >> A[i];
  REP(i, N) cin >> T[i];

  vector<bool> Af(N, false), Tf(N, false);
  for (int i = 1; i < N; i++) {
    if (A[i - 1] == A[i]) Af[i] = true;
  }
  for (int i = N - 2; i >= 0; i--) {
    if (T[i] == T[i + 1]) Tf[i] = true;
  }

  ll ans = 1;
  REP(i, N) {
    if (!Af[i] && !Tf[i]) ans *= (A[i] == T[i] ? 1 : 0);
    if ( Af[i] && !Tf[i]) ans *= (A[i] >= T[i] ? 1 : 0);
    if (!Af[i] &&  Tf[i]) ans *= (A[i] <= T[i] ? 1 : 0);
    if ( Af[i] &&  Tf[i]) (ans *= min(A[i], T[i])) %= MOD;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
N,M=map(int, input().split())
L=[]
for i in range(M):
    a,b=map(int, input().split())
    L.append((a-1,b-1))



class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
        return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        #rnkが大きい方に結合
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
        # rnkが同じ（深さに差がない場合）は1増やす
        if(self.rnk[x] == self.rnk[y]):
            self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


uni=UnionFind(N)
L=L[::-1]
ans=[N*(N-1)//2]

for i in range(0,M):
    a,b=L[i]
    size_a=uni.Count(a)
    size_b=uni.Count(b)
    if i!=M-1:
        if not uni.isSameGroup(a,b):
            ans.append(ans[-1]-size_a*size_b)
        else:
            ans.append(ans[-1])
    uni.Unite(a,b)

ans=ans[::-1]
for a in ans:
    print(a)

Measured memory_bytes: 94100
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int n, m;
int cnt[10010];
char ch[1001][1001];
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%s", ch[i]+1);
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++){
            cnt[ch[i][j] - 'a'] ++;
        }
    
    if((n&1) && (m&1)){
        int ff = 0;
        for(int i = 0; i < 26; i ++)
            cnt[i] %= 4;
        int all = n/2 + m/2, cc = 0;
        for(int i = 0; i < 26; i ++){
            if(cnt[i] == 2){
                cc ++;
            }
        }
        if((all - cc)&1 || cc > all){
            printf("No");
            return 0;
        }
        
        for(int i = 0; i < 26; i ++)
            if(cnt[i] & 1){
                if(!ff)
                    ff = 1;
                else{
                    printf("No");
                    return 0;
                }
            }
    }
    else if((n&1) || (m&1)){
        for(int i = 0; i < 26; i ++)
            cnt[i] %= 4;
        int p = n&1 ? m/2 : n/2;
        int cct = 0, ff = 0;
        for(int i = 0; i < 26;  i ++){
            if(cnt[i] & 1){
                printf("No");
                return 0;
            }
            if(cnt[i] == 2){
                cct ++;
                if(cct > p){
                    printf("No");
                    return 0;
                }
            }
        }
        if((p-cct)&1){
            printf("No");
           return 0;
        }
    }
    else{
        for(int i = 0; i < 26; i ++){
            if((cnt[i]%4)){
                printf("No");
                return 0;
            }
        }
    }
    printf("Yes");
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n;
    cin>>n;
    int a=0,p=0;
    vector<int> s(n);
    for (int i=0;i<n;i++){
        cin>>s.at(i);
    }
    for (int i=0;i<n;i++){
        a=s.at(a)-1;
        if(a==1){
            p=i+1;
            break;
        }
    }
    if (p!=0)cout<<p<<endl;
    else cout<<-1<<endl;
}

Measured memory_bytes: 640
#include <iostream>
     
    using namespace std;
     
    int main(){
      int n;
      cin >> n;
      if (n % 10 == 7){
        cout << "Yes";
        return 0;
      }
      int m = n % 100;
      if (m / 10 == 7){
        cout << "Yes";
        return 0;
      }
      if (n / 100 == 7){
        cout << "Yes";
        return 0;
      }
      cout << "No";
      return 0;
    }

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



int main() {
    int a, b, c;
    cin >> a >> b;

    c = b;
    
    while(c) {
        a *= 10;
        c /= 10;
    }

    a += b;
    c = sqrt(a);

    cout << (a == c*c ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
N = list(map(int,input().split()))
ans = list(map(str,N))
print(" ".join(ans))
for i in range(n-1):
	v = N[i+1]
	j = i
	while j >= 0 and N[j] > v:
		N[j+1] = N[j]
		j -= 1
		N[j+1] = v
	ans = list(map(str,N))
	print(" ".join(ans))


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

using namespace std;

// A, B, S
// B = S - A
// X, X+D, X+2D, X+3D, ... X+(N-1)D
// X+iD = nX+sD ( s = \sigma ^ n)
// (m-n)X + (s-t)D = 0


int main(void) {
    long n, x, d;
    cin >> n >> x >> d;
    if(d==0) {
        if(x==0) {
            cout << 1 << endl;
        } else {
            cout << n+1 << endl;
        }
        return 0;
    }
    if(d < 0) x = -x, d = -d;

    map<long, vector<pair<long,long>>> v;

    for(long c=0; c<=n; c++) {
        long a = c*(c-1)/2;
        long b = c*(n-1 + n-c)/2;

        v[(100*d+((c*x)%d))%d].push_back({c*x/d + a, c*x/d + b + 1});
    }

    long r = 0;
    for(auto &w: v) {
        auto &l = w.second;
        sort(l.begin(), l.end());
        long b = -1e18;
        long a = b;
        for(auto &x: l) {
            if(x.first > b) {
                r += b-a;
                a = x.first;
                b = x.second;
            } else {
                b = max(b, x.second);
            }
        }
        r += b-a;
    }
    cout << r << endl;
}


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

int main()
{
    
    string s;
    cin>>s;
    if(s.length()==2)
        cout<<s<<endl;
    else if(s.length()==3)
    {
        reverse(s.begin(),s.end());
        cout<<s<<endl;
    }
return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
    	Scanner sn = new Scanner(System.in);
     	Long x = Math.abs(sn.nextLong());
      	Long k = sn.nextLong();
      	Long d = sn.nextLong();
      	Long div = x / d; 
      	if( div == 0) {
          	if(k%2 == 0) {
        		System.out.println(x);	            
            } else {
                System.out.println(d - x);	
            }
        } else {
        	Long aux = k - div;
          	if(aux >= 0) {
            	if( (aux%2) == 0) {
            	System.out.println(Math.abs(x%d));	
            	} else {
            		System.out.println(Math.abs((x%d) - d));
            	}
            } else {
            	System.out.println(Math.abs(x) - (k * d));
            }
        }
    }
}

Measured memory_bytes: 35808
import Control.Monad (replicateM)
import Data.List (sort)

main :: IO ()
main = do
  (n, m) <- readPair
  abs <- replicateM n readPair
  print $ solve m abs

readPair :: IO (Int, Int)
readPair = do
  [x, y] <- map read . words <$> getLine
  return (x, y)

solve :: Int -> [(Int, Int)] -> Int
solve m xys = go m $ sort xys
  where
    go m ((x, y) : xys)
      | m > y     = x * y + go (m - y) xys
      | otherwise = x * m

Measured memory_bytes: 75132
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<ll>
#define vvint vector<vint>
#define P pair<ll,ll>
#define INT_MAX 2147483647
#define MOD 998244353
#define PI 3.14159265358979323846
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;

#define MAX 1000000000000

int main(void) {
	int n; cin >> n;
	vint l(n);
	rep(i, n) {
		cin >> l[i];
	}
	sort(all(l));
	int ans = 0;
	for (int i = 0; i < n-2; i++) {
		for (int j = i+1; j < n-1; j++) {
			for (int k = j + 1; k < n;k++) {
				if (l[i] != l[j] && l[j] != l[k] && l[k] != l[i]) {
					if (l[k] < l[i] + l[j]) {
						ans++;
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
import java.util.Scanner;

class Main { 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int sum = in.nextInt();
            System.out.println(sumOfFourIntegers(sum));
        }
        
    }
    static int sumOfFourIntegers(int sum) {
        int count = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < 10; k++) {
                    int rest = sum - i - j - k;
                    if (rest <= 9 && rest >= 0) count += 1;
                }
            }
        }
        return count;
    }
}

Measured memory_bytes: 18776
import math
k=int(input())
totl=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
      m=math.gcd(i,j)
      m=math.gcd(m,k)
      totl+=m
print(totl)
      

Measured memory_bytes: 67672
A, B, C, D = gets.chomp.split(" ").map(&:to_i)

def cnt_baisu(a, b, x)
  d, m = a.divmod(x)
  i = d + (m.zero? ? 0 : 1)
  d, m = b.divmod(x)
  d - i + 1
end

puts B - A + 1 - (cnt_baisu(A, B, C) + cnt_baisu(A, B, D) - cnt_baisu(A, B, C.lcm(D)))


Measured memory_bytes: 1788
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;




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



	int t;
	cin >> t;
	int left = 0;
	int right = T;
	int sum = 0;
	rep(i, 1, n) {
		cin >> t;
		if (t >= right) {
			sum += right - left;
			left = t;
			right = t + T;
		}
		else if (t + T >= right) {
			right = t + T;
		}
	}
	sum += right - left;

	cout << sum << endl;


	return 0;
}


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

#define pb push_back
#define debug(x) cerr<<#x<<'='<<x<<endl
#define set0(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}

int n,u,v,depth[1100],fa[1100];
vector<int> G[1100];

int mx[1100],sz;
void dfs(int num,int f = -1){
	int cnt = 0;
	for(auto ct:G[num]){
		if(ct == f)continue;
		cnt++;
		fa[ct] = num;
		depth[ct] = depth[num]+1;
		dfs(ct,num);
	}
	mx[depth[num]] = max(mx[depth[num]],cnt);
}

ll calc1(int p){
	ll ans = 1;
	memset(mx,0,sizeof(mx));
	depth[p] = 0; dfs(p);
	for(int i=0;i<sz/2;i++) ans*=mx[i];
	return ans;
}
ll calc2(int u,int v){
	memset(mx,0,sizeof(mx));
	depth[u] = 0; dfs(u,v);
	depth[v] = 0; dfs(v,u);
	ll ans = 2;
	for(int i=0;i<sz/2-1;i++){
		ans*=mx[i];
	}
	return ans;
}
int main() {
	read(n);
	for(int i=1;i<n;i++){
		read(u);read(v);
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1);
	int u = max_element(depth+1,depth+n+1)-depth;
	
	dfs(u);
	int v = max_element(depth+1,depth+n+1)-depth;
	vector<int> R;
	R.pb(v);
	while(v!=u){
		v = fa[v];
		R.pb(v);
	}
	sz = R.size();
	ll ans = 1e18;
	if(R.size()%2 == 1){
		int p = R[R.size()/2];
		ans = min(ans,calc1(p));
		sz+=1;
		for(auto ct:G[p]){
			ans = min(ans,calc2(p,ct));
		}
	}else{
		ans = calc2(R[R.size()/2],R[R.size()/2-1]);
	}
	cout<<(R.size()+1)/2<<' '<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)

int main(){
	int n,l;
	cin>>n>>l;
	vector<int>v(n);
	rep(i,n)cin>>v[i];
	
	int maxi = -1;
	int pos = -1;
	rep(i,n-1){
		if(v[i]+v[i+1]>maxi){
			maxi = v[i]+v[i+1];
			pos = i;
		}
	}
	
	if(maxi<l){
		cout<<"Impossible"<<endl;
		return 0;
	}
	else cout<<"Possible"<<endl;
	
	int c=0;
	while(1){
		if(c==pos)break;
		cout<<++c<<endl;
	}
	
	c=n-1;
	while(1){
		if(c==pos+1)break;
		cout<<c--<<endl;
	}
	cout<<pos+1<<endl;
}

Measured memory_bytes: 1152
#include<stdio.h>
int main()
{
	int h,n,a[100000];
	int i,m=0;
	scanf("%d %d",&h,&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
		m+=a[i];
	}
	if(h-m<=0){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 1996
s=input()
l=list(s)
N=l.count("N")
W=l.count("W")
S=l.count("S")
E=l.count("E")

if N*S!=0 and E*W!=0:
    print("Yes")
elif N*S==0 and E*W!=0:
    if N==0 and S==0:
        print("Yes")
    else:
        print("No")
elif E*W==0 and N*S!=0:
    if E==0 and W==0:
        print("Yes")
    else:
        print("No")
else:
    print("No")

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

int main()
{
  int n, m;
  cin >> n >> m;
  valarray<int> a(n);
  for (auto&& e : a)
    cin >> e;
  sort(begin(a), end(a), greater<>());
  int s = a.sum();
  cout << (a[m - 1] >= double(s) / (4 * m) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int main()
{
	int a,b;
	get2(a,b);
	if(a==1)a=14;if(b==1)b=14;
	if(a>b)puts("Alice");
	else if(a==b)puts("Draw");
	else puts("Bob");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n) for (int i=1; i < (int)(n); i++)
#define rrep(i, n) for (int i=((int)(n)-1); i>=0; i--)
#define rreps(i, n) for (int i=((int)(n)-1); i>0; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using lint = long long;
using p = pair<int, int>;
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; }

bool flag[110] = {false};

int main() {
  int N, K; cin >> N >> K;
  int d[110];
  int a[110][110];

  rep (i, K) {
    cin >> d[i];
    rep (j, d[i]) {
      cin >> a[i][j];
      a[i][j] --;
    }
  }

  rep (i, K){
    rep (j, d[i]) {
      flag[a[i][j]] = true;
    }
  }
  int ans = 0;
  rep (i, N) {
    if (flag[i] == false)
      ans ++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int cnt[55][26];

int main() {
  // 入力
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) cin >> s[i];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < s[i].size(); j++) {
      cnt[i][s[i][j]-'a']++;
    }
  }

  string ans = "";
  for (int i = 0; i < 26; i++) {
    int mini = 100;
    char c = 'a' + i;
    for (int j = 0; j < n; j++) {
      mini = min(mini, cnt[j][i]);
    }
    for (int j = 0; j < mini; j++) {
      ans += c;
    }
  }

  // 解答
  cout << ans << endl;

  return 0;
}


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

struct Graph
{
    int n;
    vector<vector<int>> g;
    
    Graph(){}
    
    Graph(int n) : n(n){
        g.resize(n);
    }
    
    void add_edge(int from, int to){
        g[from].push_back(to);
    }
};

struct SCC      //StronglyConnectedComponents
{
    int n;
    int k;
    vector<vector<int>> g, rg;
    vector<bool> used;
    vector<int> cmp;
    vector<int> vs;
    
    SCC(Graph &g) : g(g.g){
        n = g.n;
        rg.resize(n);
        for(int u = 0; u < n; u++){
            for(int v : g.g[u]){
                rg[v].push_back(u);
            }
        }
        used.resize(n);
        cmp.resize(n);
    }
    
    void dfs(int u){
        used[u] = true;
        for(int v : g[u]){
            if(!used[v]) dfs(v);
        }
        vs.push_back(u);
    }
    
    void rdfs(int u, int k){
        used[u] = true;
        cmp[u] = k;
        for(int v : rg[u]){
            if(!used[v]) rdfs(v, k);
        }
    }
    
    int decomposition(){
        fill(used.begin(), used.end(), false);
        for(int i = 0; i < n; i++){
            if(!used[i]) dfs(i);
        }
        fill(used.begin(), used.end(), false);
        k = 0;
        for(int i = n - 1; i >= 0; i--){
            if(!used[vs[i]]){
                rdfs(vs[i], k);
                k++;
            }
        }
        return k;
    }
    
    int decomposition(Graph &dag){
        k = decomposition();
        dag.n = k;
        dag.g.resize(k);
        map<pair<int, int>, bool> mp;
        for(int u = 0; u < n; u++){
            for(int v : g[u]){
                if(!mp[pair<int, int> (cmp[u], cmp[v])] && cmp[u] != cmp[v]){
                    mp[pair<int, int> (cmp[u], cmp[v])] = true;
                    dag.add_edge(cmp[u], cmp[v]);
                }
            }
        }
        return k;
    }
};

vector<int> v[500005];

int main()
{
    int n, m;
    cin >> n >> m;
    Graph g(n);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        g.add_edge(a, b);
    }
    SCC scc(g);
    int k = scc.decomposition();
    for(int i = 0; i < n; i++){
        v[scc.cmp[i]].push_back(i);
    }
    cout << k << endl;
    for(int i = 0; i < k; i++){
        cout << (int)v[i].size();
        for(int j : v[i]) cout << " " << j;
        cout << endl;
    }
}


Measured memory_bytes: 101172
"""
import string
al = string.ascii_lowercase

ord('A') =65
chr(65) ='A'
"""


def c2i(c): return ord(c) - ord('a')


s = input()
t = input()

chrList = [-1 for _ in range(26)]

flg = True
for i in range(len(s)):
    idx_s = c2i(s[i])
    idx_t = c2i(t[i])

    if chrList[idx_s] == -1:
        chrList[idx_s] = idx_t
    else:
        if chrList[idx_s] != idx_t:
            flg = False
            break

# 変換先が重複していないことを調べる
# 変換先のインデックスchrList[i]に該当するchkをTrueにしていく
chk = [False for _ in range(26)]
for i in range(26):
    if chrList[i] == -1:
        pass
    elif not chk[chrList[i]]:
        chk[chrList[i]] = True
    else:
        flg = False
        break

print('Yes' if flg else 'No')
# print(sorted(list(map(chr, list(map(lambda x: x + ord('a'), chrList))))))

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <set>
#include <iomanip>
#include <utility>
using namespace std;
#define ll long long

int main() {
	int N, K; cin >> N >> K;
	vector<int> V(N);
	for(int i=0; i<N; ++i) cin >> V[i];
	int ans=0;
	for(int l=0; l<=min(N, K); ++l){
	    for(int r=0; r<=min(N, K)-l; ++r){
	        vector<int> pq;
	        int now=0;
	        for(int i=0; i<l; ++i){
	            pq.push_back(V[i]);
	            now += V[i];
	        }
	        for(int i=0; i<r; ++i){
	            pq.push_back(V[N-1-i]);
	            now += V[N-1-i];
	        }
	        sort(pq.begin(), pq.end());
	        for(int i=0; i<l+r && i<K-(l+r); ++i){
	            if(pq[i]<0){
	                now -= pq[i];
	            }
	            else break;
	        }
	        ans=max(ans, now);
	    }
	}
	cout << ans << endl;
	return 0;
}


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

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


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


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define inf 1000000007
#define mod 1000000007
//#pragma GCC optimize(2)
//#define int long long
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,m,a[105];
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int sum=0;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(a[i]*4*m>=sum)
			cnt++;
	cout<<(cnt>=m?"Yes":"No")<<endl;
	return 0;
}


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

using namespace std;
typedef long long ll;

#define INF (long long)(10e9+7)
#define REP(i,n) for(ll i = 0; i < n; i++)
#define REP1(i,n) for(ll i = 1; i <= n; i++)

int main(void)
{
    int n;
    string s;
    int res = 0;
    cin >> n >> s;
    REP(i, s.size()-2) {
        if(s.substr(i,3) == "ABC") res ++;
    }
    cout << res << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
	int n; scanf("%d",&n);
	int cost[9999];
	rep(i,n-1) scanf("%d",cost+i);

	int dp[2][5001][2];
	rep(j,n/2+1) rep(k,2) dp[0][j][k]=INF;
	dp[0][1][0]=0;
	rep(i,n-1){
		int i1=i&1,i2=1-i1;
		rep(k,2) dp[i2][0][k]=INF;
		for(int j=1;j<=n/2;j++){
			dp[i2][j][0]=min(dp[i1][j-1][0],dp[i1][j-1][1]+cost[i]);
			dp[i2][j][1]=min(dp[i1][ j ][1],dp[i1][ j ][0]+cost[i]);
		}
	}
	printf("%d\n",min(dp[(n-1)&1][n/2][0],dp[(n-1)&1][n/2][1]));

	return 0;
}

Measured memory_bytes: 832
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as BS
main=do
 [n,m]<-map read.words<$>getLine
 a<-map (read.BS.unpack).BS.words<$>BS.getLine
 print(f m (S.fromList (zip a [1..n])))
  where f 0 s = sum(map fst (S.toList s))
        f m s = f (m-1) (S.insert((\(a,i)->((quot a 2),i))(S.findMax s))(S.deleteMax s))

Measured memory_bytes: 30076
main = do
    n <- getLine
    p <- getLine >>= return . map (read :: String -> Int) . words
    let (_,a) = solve $ reverse p
    putStrLn $ show a

solve :: [Int] -> (Int,Int) -- (min,ans)
solve (x:[]) = (x,1)
solve (x:xs)
    | x < y = (x,z+1)
    | otherwise = (y,z)
    where (y,z) = solve xs

Measured memory_bytes: 99708
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,i,sum=0; cin>>n;
    vector <int> a(n);
    for(i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i]-1;
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#define R(i, n) for(int i = 0;i < n;i++)
#define S(a) scanf("%d", &a)
#define S2(a, b) scanf("%d%d", &a, &b)
#define S3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define P(a) printf("%d", a)
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef pair<int, int> IR;

string S, T, U;
int A, B;

int main() {
	cin >> S >> T;
	S2(A, B);
	cin >> U;

	if (S.compare(U) == 0) A -= 1;
	else B -= 1;

	printf("%d %d", A, B);
}



Measured memory_bytes: 256
#!python3

# input
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))


def main():
    x = 0
    m = {0: 1}
    ans = 0
    for i in range(N):
        x = (x + A[i]) % M
        if x in m:
            ans += m[x]
            m[x] += 1
        else:
            m[x] = 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14224
/*
 */
#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

typedef pair<int, int> P;

// init

// input
int iN;
char cC; // 0 <= N <= 100,000
int iI; // 1 <= P <= 100
int iS; // 1 <= P <= 100
int iP; // 1 <= P <= 100

// manage

// ú»
void init() {
}

// üÍ
bool input() {
  scanf("%d", &iN);
  if (iN == 0)
    return false;
  return true;
}

// 
void manage() {
  int i;
  list<P> lis;
  list<P>::iterator it; // Ce[^
  P p;
  for (i = 0; i < iN; i++) {
    it = lis.begin();
/*
    while (it != lis.end()) { // listÌöÜÅ
      printf("(%d, %d) ", it->first, it->second); // vfðoÍ
      ++it; // Ce[^ðPÂißé
    }
    printf("\n"); // vfðoÍ
*/
    scanf(" %c", &cC);

    if (cC == 'W') {
      scanf("%d %d", &iI, &iS);
      it = lis.begin();
      while (it != lis.end()) { // listÌöÜÅ
        if (it->first == -1) {
          it->first = iI;
          if (iS >= it->second) {
            iS -= it->second;
          } else {
            int d = it->second - iS;
            it->second = iS;
            iS = 0;
            it++;
            lis.insert(it, P(-1, d));
          }
          if (iS == 0) break;
        }
        it++;
      }
      if (it == lis.end()) {
        lis.push_back(P(iI, iS));
      }
      continue;
    }

    if (cC == 'D') {
      scanf("%d", &iI);
      it = lis.begin();
      while (it != lis.end()) { // listÌöÜÅ
        if (it->first == iI) {
          it->first = -1;
        }
        it++;
      }

      continue;
    }

    if (cC == 'R') {
      scanf("%d", &iP);
      it = lis.begin();
      int sum = 0;
      while (it != lis.end()) { // listÌöÜÅ
        //printf("(%d, %d) %d %d %d\n", it->first, it->second, sum + it->second, iP, sum + it->second > iP); // vfðoÍ
        if (sum + it->second > iP)
          break;
        sum += it->second;
        it++;
      }
      if (it != lis.end()) {
        printf("%d\n", it->first);
      } else {
        printf("-1\n");
      }
      continue;
    }

  }

}

// oÍ
void output() {
  printf("\n");
}

// mizoSâ¤Ê
int main() {
  init(); // ú»
  while (1) {
    if (!input())
      break; // üÍ + I¹»è
    manage(); // 
    output(); // oÍ
  }
  return 0;
}

Measured memory_bytes: 1040
{-# LANGUAGE BangPatterns #-}
import Data.List
import Data.Functor

data Trump = Card Int Char
instance Show Trump where
  show (Card n c) = c:(show n)
instance Eq Trump where
  Card a _ == Card b _ = a == b
instance Ord Trump where
  Card a _ `compare` Card b _ = a `compare` b

toTrump :: [String] -> [Trump]
toTrump [] = []
toTrump ((a:as):ass) = (Card (read as) a):toTrump ass

isSameCard :: Trump -> Trump -> Bool
Card a x `isSameCard` Card b y = a == b && x == y

main :: IO ()
main = do
  _ <- getLine
  as <- toTrump . words <$> getLine :: IO [Trump]
  let (bubbly, n) = bubbleSort as
  let merged = sort as
  putStrLn . unwords . map show $ bubbly
  putStrLn (if show bubbly == show merged
            then "Stable"
            else "Not stable")
  let selection = selectionSort as
  putStrLn . unwords . map show $ selection
  putStrLn (if show selection == show merged
            then "Stable"
            else "Not stable")

bubbleSort :: (Ord a) => [a] -> ([a], Int)
bubbleSort [] = ([], 0)
bubbleSort as = cons' (x, i) $ bubbleSort $ xs
  where
    ((x:xs), i) = foldr bubble ([], 0) as

    bubble :: (Ord a) => a -> ([a], Int) -> ([a], Int)
    bubble x ([], i) = ([x], i)
    bubble x ((a:as), i)
      | a < x     = (a:x:as, i + 1)
      | otherwise = (x:a:as, i)

    cons' :: (Ord a) => (a, Int) -> ([a], Int) -> ([a], Int)
    cons' a b = let (x, i) = a
                    (xs, j) = b
                in (x:xs, i + j)

-- selectionSort :: (Ord a) => [a] -> [a]
selectionSort (a:b:[]) = if a > b then [b, a] else [a, b]
selectionSort (a:as)
  | a <= m = a:selectionSort as
  | a > m = m:selectionSort rep
  where
    m = minimum as
    rep = replaceFirst m a as

-- replaceFirst :: (Eq a) => a -> a -> [a] -> [a]
replaceFirst _ _ [] = []
replaceFirst old new (l:ls)
  | isSameCard old l = new:ls
  | otherwise = l:replaceFirst old new ls



Measured memory_bytes: 4116
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e16;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

ll p2[60];
ll memo[60];

ll solve(ll n, ll x){
    if(n == 0){
        if(x >= 1) return 1;
        else return 0;
    }
    if(memo[n] != -LINF && x == 4*p2[n]-3){
        return memo[n];
    }
    if(x <= 0) return 0;
    else if (n >= 1){
        ll anm = 4*p2[n-1]-3;
        if(x <= anm)return solve(n-1, x-1);
        if(x == anm+1){
            return memo[n-1] = solve(n-1, anm);
        }
        else if(x == anm+2) return solve(n-1, anm) + 1;
        else{
            ll ans = p2[n]-1 + 1 + solve(n-1, x-(anm+2));
            return ans;
        }
    }
    return 0;
}

int main(){
    ll N, X; cin >> N >> X;
    
    ll tmp = 1;
    REP(i, 60){
        p2[i] = tmp; tmp *= 2;
        memo[i] = -LINF;
    }
    ll ans = solve(N, X);
    cout << ans << endl;
    return 0;
}


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

int main(void){
    string t;
    cin >> t;
    string s = t;
    int count1 = 0;
    int count2 = 0;
    for (int i = 0; i < t.size(); i++){
        if(t[i]=='?' && t[i+1] == '?') {
            t[i] = 'P';
            t[i+1] = 'D';
        }
        if(t[i]=='?' && t[i+1] == 'D') {
            t[i] = 'P';
        }
        if(t[i]=='?' && t[i+1]=='P'){
            t[i] = 'D';
        }
        if(t[i]=='?')   t[i] = 'D';
        if(t[i]=='P' && t[i+1]=='?') t[i+1] = 'D';
    }
    for (int i = 0; i < t.size(); i++){
        cout << t[i];
    }
    
    cout << endl;
    
}

Measured memory_bytes: 3852
<?php
  list($n, $m, $R) = explode(" ", trim(fgets(STDIN)));

  $r = explode(" ", trim(fgets(STDIN)));

  $p = [];
  for ($i=1; $i<=$n; $i++){
    for ($j=1; $j<=$n; $j++){
      if($i == $j){
        $p[$i][$j] = 0;
      }else{
        $p[$i][$j] = PHP_INT_MAX;
      }
    }
  }

  for ($i=0; $i<$m; $i++) {
    list($a, $b, $c) = explode(" ", trim(fgets(STDIN)));
    if(!isset($p[$a])) $p[$a] = [];
    if(!isset($p[$b])) $p[$b] = [];
    $p[$a][$b] = intval($c);
    $p[$b][$a] = intval($c);
  }

  for($k=1; $k<=$n; $k++){
    for($i=1; $i<=$n; $i++){
      for($j=1; $j<=$n; $j++){
        $p[$i][$j] = min($p[$i][$j], $p[$i][$k]+$p[$j][$k]);
      }
    }
  }

  $arr = permutationAll(0, $R-1);

  $min = PHP_INT_MAX;
  for ($i=0; $i<count($arr); $i++) {
    $ptn = $arr[$i];
    $route = 0;
    for ($j=1; $j<strlen($ptn); $j++) {
      $route += $p[$r[$ptn[$j]]][$r[$ptn[$j-1]]];
//      echo $p[$r[$ptn[$j]]][$r[$ptn[$j-1]]]." ";
    }
//    echo $route." ".$ptn.PHP_EOL;
    $min = min($min, $route);
  }

  echo $min;

/**
   * 順列の組み合わせを返す
   * @param $n 数
   */
  function permutationAll($start, $end)
  {
    if($end < $start){
      return [];
    }
    $n=[];
    for($i=$start;$i<=$end;$i++){
      $n[$i]=true;
    }

    $arr = appendCount($n, "");

    return $arr;
  }

  function appendCount($n, $str){
    if(count($n)===1){
      return [$str.key($n)];
    }
    $arr = [];
    foreach($n as $key => $value){
      unset($n[$key]);
      $childs = appendCount($n, $str.$key);
      foreach($childs as $child){
        $arr[] = $child;
      }
      $n[$key]=true;
    }
    return $arr;
  }

Measured memory_bytes: 21864
#define ENABLE_DEBUG 1
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

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

    std::string s;
    std::cin >> s;
    std::sort(ALL(s));
    for (usize i=0; i<s.length(); i+=2) {
        if (s.length()%2==1 || s.at(i)!=s.at(i+1)) {
            std::cout << "No" << '\n';
            return 0;
        }
    }
    std::cout << "Yes" << '\n';
}


Measured memory_bytes: 256
import math
H, W, D = map(int, input().split())

array_len = math.ceil(H*W/D)

a_array = [[[0, 0] for _ in range(array_len)] for _ in range(D)]
for i in range(H):
    A = map(int, input().split())
    for j, a in enumerate(A):
        a = a - 1
        a_array[a % D][a//D][0] = i + 1
        a_array[a % D][a//D][1] = j + 1

# print(a_array)
sum_array = [[0] * array_len for _ in range(D)]
for i in range(D):
    s = 0
    for j in range(1, array_len):
        s += (abs(a_array[i][j][0]-a_array[i][j-1][0]) +
              abs(a_array[i][j][1]-a_array[i][j-1][1]))
        sum_array[i][j] = s

# print(sum_array)

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    d = (R-1) % D
    l_power = sum_array[d][(L-1-d)//D]
    r_power = sum_array[d][(R-1-d)//D]
    print(r_power-l_power)


Measured memory_bytes: 79068
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vii vector<ii>
#define li long int
#define ll long long
#define lli long long int
#define vlli vector<lli>
#define vll vector<ll>
#define vl vector<long>
#define ld long double
#define ulli unsigned long long int
 
using namespace std;

void solve() {
    int n, x, t;
    cin>>n>>x>>t;
    int tmp = x;
    int res = t;
    while(n > x) {
        x += tmp;
        res += t;
    }
    cout<<res;
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    solve();
}

Measured memory_bytes: 3624