akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <bitset>

#define INF 1000000000
#define Inf 1000000000000000000
#define mp make_pair
#define pb push_back
#define EPS 1e-9

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

ll k, a[100010];

int main() {
    
    scanf("%lld", &k);

    for(int i = 0; i < k; ++i) scanf("%lld", &a[i]);
    
    if (a[k - 1] != 2) {
        printf("-1\n");
        return 0;
    }

    ll lo = 2, hi = 3;

    for(int i = k - 2; i >= 0; --i) {
        ll x = ((lo + a[i] - 1) / a[i]) * a[i];
        ll y = (hi / a[i]) * a[i] + a[i] - 1; 
        if (x > hi) {
            printf("-1\n");
            return 0;
        }
        lo = x;
        hi = y;
    }

    printf("%lld %lld\n", lo, hi);

    return 0;
}

Measured memory_bytes: 1024
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var N = Sarray()[0];
            var dct = new SortedDictionary<string, long>(StringComparer.OrdinalIgnoreCase);
            var max = 1L;
            for (var i = 0; i < N; ++i)
            {
                var str = ReadLine();
                if (dct.ContainsKey(str))
                {
                    ++dct[str];
                    max = Max(dct[str], max);
                }
                else
                    dct[str] = 1;
            }
            var strb = new StringBuilder((int)N * 11);
            foreach (var s in dct)
                if (max == s.Value)
                    strb.Append(s.Key + "\n");
            WriteLine(strb);
            Out.Flush();
        }
    }
}

Measured memory_bytes: 50880
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int N;
  string S;
  int K;
  cin >> N;
  cin >> S;
  cin >> K;
  for(int i=0;i<10;i++)
  {
    if(S[i]!=S[K-1])
    {
      S[i] = '*';
    }
  }
  cout << S << endl;
  return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
use std::cmp::min;
use std::usize;
use std::collections::HashSet;

const INF: i32 = 1000000007;

struct Graph {
    node: Vec<Vec<i32>>,
}

impl Graph {
    fn new(node: usize) -> Graph {
        Graph { node: vec![vec![INF; node]; node] }
    }

    fn add_edge(&mut self, start_node: usize, end_node: usize, edge_cost: i32) -> () {
        self.node[start_node][end_node] = edge_cost;
        self.node[end_node][start_node] = edge_cost;
    }
    fn floyd_warshall(&mut self) -> Vec<Vec<i32>> {
        let mut node = self.node.clone();
        let i = self.node[0].len();
        for relay_node in 0..i {
            for start_node in 0..i {
                for end_node in 0..i {
                    self.node[start_node][end_node] = min(self.node[start_node][end_node], self.node[start_node][relay_node] + self.node[relay_node][end_node]);
                }
            }
        }
        return node;
    }
}

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

fn readc() -> char {
    let s: String = read();
    return s.chars().nth(0).unwrap();
}

fn read_vec<T: FromStr>(n: usize) -> Vec<T> {
    return (0..n).map(|_| read()).collect();
}

fn main() {
    let n: usize = read();
    let m: usize = read();

    let mut g = Graph::new(n+1);
    for i in 0..m {
        let a: usize = read();
        let b: usize = read();
        let c: i32 = read();
        g.add_edge(a, b, c);
    }

    let node = g.floyd_warshall();
    let mut ans = 0;
    for i in 1..n+1 {
        for j in 1..n+1 {
            if i == j {
                continue;
            }
            // println!("{} {} {} {}", i, j, node[i][j], g.node[i][j]);
            if node[i][j] != INF && node[i][j] != g.node[i][j] {
                ans += 1;
            }
        }
    }
    println!("{}", ans / 2);
}


Measured memory_bytes: 4352
import sys
from statistics import median_low
inputs = sys.stdin.readlines()

n = int(inputs[0])
A = list(map(int, inputs[1].split()))

B = list(map(lambda x: x[1]-x[0], enumerate(A, 1)))
b = median_low(B)
C = list(map(lambda x: abs(x-b), B))
print(sum(C))

Measured memory_bytes: 30760
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,s;
  cin>>n>>s;
  vector<int> a(n);
  for(int i=0;i<n;i++)
    cin>>a.at(i);
  int p=998244353;
  vector<vector<int>> c(s+1,vector<int>(n+1,0));
  c[0][0]=1;
  for(int i=0;i<=s;i++)
    for(int j=1;j<=n;j++)
      c[i][j]=(c[i][j-1]*2%p+(j>0&&a.at(j-1)<=i?c[i-a.at(j-1)][j-1]:0))%p;
  cout<<c[s][n]<<endl;
}

Measured memory_bytes: 38552
#include <stdio.h>

void calc() {
    int h1, h2;
    int m1, m2;
    int s1, s2;

    scanf("%d %d %d %d %d %d", &h1, &m1, &s1, &h2, &m2, &s2);

    s1 += h1 * 3600;
    s1 += m1 * 60;

    s2 += h2 * 3600;
    s2 += m2 * 60;

    s2 -= s1;
    h2 = s2 / 3600;
    m2 = (s2 % 3600)/60;
    s2 %= 60;

    printf("%d %d %d\n", h2, m2, s2);
}


int main() {
    int i;

    for (i=0;i<3;i++) calc();
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vs = vector<string>;
#define  rep(i,n) for(ll i = 0; i < (n); ++i)
#define  red(i,n) for(ll i = (n)-1; i >= 0; --i)
#define  all(a)   begin(a),end(a)
#define  pb(a)    push_back(a)
#define  yn       cout<<"Yes\n"; else cout<<"No\n";
inline ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
const int INF=1000000009;
const ll LINF = 1e18;


int main()
{
    int n,k;
    cin>>n>>k;
    char a[11];
    rep(i,k) cin>>a[i];
    string s;
    for(;;n++){
        s=to_string(n);
        bool f=1;
        rep(i,k) if(s.find(a[i])!=string::npos) {f=0; break;}
        if(f)cout<<n<<endl,exit(0);
    }    
    return 0;
}


Measured memory_bytes: 256
// 問題の URL を書いておく
// https://atcoder.jp/contests/abc167/tasks/abc167_a

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <numeric>
using namespace std;

//#define ENABLE_PRINT

template<typename T>
T Input()
{
    T v;
    cin >> v;
    return v;
}

template<typename T>
vector<T> InputVector(int n)
{
    vector<T> v(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    return v;
}

template<typename T>
void InputArray(T* begin, int n)
{
    for(int i = 0; i < n; ++i)
    {
        cin >> begin[i];
    }
}

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

bool check(string s, string t)
{
    if(s.size() + 1 != t.size())
    {
        return false;
    }
    return t.substr(0, s.size()) == s;
}

int main(int argc, const char* argv[])
{
    auto s = Input<string>();
    auto t = Input<string>();

    cout << (check(s, t) ? "Yes" : "No") << endl;
    return 0;
}


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

using namespace std;

char s[30];

int main(){
	scanf("%s",s+1);
	if (strlen(s+1)>=4){
		if (s[1]=='Y' && s[2]=='A' && s[3]=='K' && s[4]=='I')
			puts("Yes");
		else puts("No");
	}
	else puts("No");
	
	return 0;
}
			

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int sqrt_n = 317;
struct SqrtDecomposition {
	int n, bucket_size;
	vector<int> data;
	vector<int> bucket;
	SqrtDecomposition(int n, int val = 0) :n(n) {
		assert(n);
		bucket_size = 1 + (n - 1) / sqrt_n;
		data.assign(bucket_size * sqrt_n, val);
		bucket.assign(bucket_size, val);
	}
	void update(int x, int y) {
		int k = x / sqrt_n;
		data[x] = y;
		int mini = y;
		for (int i = k * sqrt_n; i < (k + 1) * sqrt_n; i++) {
			chmin(mini, data[i]);
		}
		bucket[k] = mini;
	}
	int get_min(int l, int r) {
		int ret = data[l];
		for (int k = 0; k < bucket_size; k++) {
			int bl = k * sqrt_n, br = (k + 1) * sqrt_n;
			if (r <= bl || br <= l)
				continue;
			if (l <= bl && br <= r) {
				chmin(ret, bucket[k]);
			}
			else {
				for (int i = max(l, bl); i < min(r, br); i++) {
					chmin(ret, data[i]);
				}
			}
		}
		return ret;
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, q; cin >> n >> q;
	SqrtDecomposition sd(n, INT_MAX);
	rep(i, 0, q) {
		int com, x, y; cin >> com >> x >> y;
		if (com == 0) {
			sd.update(x, y);
		}
		else {
			cout << sd.get_min(x, y + 1) << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3252
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main(void){
    ll n; ll a; ll b;
    cin >> n >> a >> b;
    ll ans;
    if ((b-a) % 2 == 0){
        ans = (b-a) / 2;
    } else {
        if (n-b < a-1){
            ans = n - b + 1;
            a = a + n - b + 1;
            b = n;
            ans += (b-a) / 2;
        } else {
            ans = a - 1 + 1;
            b = b - a;
            a = 1;
            ans += (b-a) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <utility>
#include <algorithm>

typedef std::pair<int, int> pi;

int maxi(int a, int b) {
  return a > b ? a : b;
}

int main(void) {
  int n, i, j, h, w;
  scanf("%d%d%d", &w, &h, &n);
  pi p[n];
  int max[w];
  for(i = 0; i < w; ++i) max[i] = 0;
  for(i = 0; i < n; ++i) scanf("%d%d", &p[i].first, &p[i].second);
  for(i = n - 1; i >= 0; --i) {
    if(!p[i].first) continue;
    if(max[p[i].first - 1] < p[i].second) max[p[i].first - 1] = p[i].second;
  }
  /*for(i = 0; i < w; ++i) printf("%d ", max[i]);
  printf("\n");*/
  for(i = w - 2; i >= 0; --i) max[i] = maxi(max[i + 1], max[i]);
  /*for(i = 0; i < w; ++i) printf("%d ", max[i]);
  printf("\n");*/
  int ans = 999999999;
  for(i = 0; i < w; ++i) {
    if(ans > i + max[i]) ans = i + max[i];
  }
  printf("%d\n", ans);
  return 0;
}


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

int N;
string S[300];


int main(){
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  long long ans = 0;
  for(int A = 0; A < N; A++){
    bool flag = true;
    for(int i = 0; i < N; i++){
      for(int j = i+1; j < N; j++){
	if(S[(i-A+N) % N][j] != S[(j-A+N)%N][i]){
	  flag = false;
	  break;
	}
      }
      if(flag == false){
	break;
      }
    }
    if(flag == true){
      ans += N;
    }
  }
  cout << ans << endl;
}


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

#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define repi(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define uniqueV(x)          \
  sort(x.begin(), x.end()); \
  x.erase(unique(x.begin(), x.end()), x.end());
#define debug(x) cerr << #x << ": " << x << '\n'
#define debug2(x, y) cerr << "(" << #x << ", " << #y << ") = " \
                          << "(" << x << ", " << y << ")" << '\n'

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

const long long INF = 3e18 + 12;
const int inf = 1e9;

// ----------------------------------------------

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

  int n;
  cin >> n;
  string s;
  cin >> s;

  ll r, g, b;
  r = 0;
  g = 0;
  b = 0;

  rep(i, n) {
    if (s[i] == 'R') {
      r++;
    } else if (s[i] == 'G') {
      g++;
    } else {
      b++;
    }
  }

  ll ans = r * g * b;

  rep(i, n) {
    repi(j, i + 1, n) {
      if ((i + j) % 2 == 0) {
        ll k = (i + j) / 2;
        if (s[i] != s[j] && s[j] != s[k] && s[k] != s[i]) {
          ans--;
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3668
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x)
{
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=2e5+10,M=4010,L=2001;
const int mod=1e9+7;
inline void add(int &x,int y) { x+=y; if(x>=mod) x-=mod; }
inline void dec(int &x,int y) { x-=y; if(x<0) x+=mod; }
int Pow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=res*(ll)x%mod;
		x=x*(ll)x%mod,y>>=1;
	}
	return res;
}
int fac[M<<1],inv[M<<1];
void predo(int n) {
	fac[0]=1; for(int i=1;i<=n;++i) fac[i]=fac[i-1]*(ll)i%mod;
	inv[n]=Pow(fac[n],mod-2); for(int i=n;i>=1;--i) inv[i-1]=inv[i]*(ll)i%mod;
}
int C(int n,int m) { return fac[n]*(ll)inv[m]%mod*inv[n-m]%mod; }
int f[M][M];
int A[N],B[N],n;
int main() {
	rd(n);
	for(int i=1;i<=n;++i) {
		rd(A[i]),rd(B[i]);
		f[L-A[i]][L-B[i]]++;
	}
	for(int i=0;i<=L*2;++i)
		for(int j=0;j<=L*2;++j) {
			if(i) add(f[i][j],f[i-1][j]);
			if(j) add(f[i][j],f[i][j-1]);
		}
	predo(8000);
	int ans=0;
	for(int i=1;i<=n;++i) {
		add(ans,f[L+A[i]][L+B[i]]);
		dec(ans,C(2*(A[i]+B[i]),2*A[i]));
	}
	ans=ans*(ll)((mod+1)/2)%mod;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 64640
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  long n;
  scanf("%ld", &n);
  if (n%2 == 1) {
    printf("0\n");
    return 0;
  }
  long ans = n/10;
  n /= 10;
  while (n != 0) {
    ans += n/5;
    n /= 5;
  }
  printf("%ld\n", ans);
  return 0;
}


Measured memory_bytes: 128
first_input = list(map(int, input().split()))
number = first_input[0]
steps = first_input[1]

scaffolds = list(map(int, input().split()))

start_cost = scaffolds[0]

costs = []

for i in range(number):
    next_step = i
    next_scaffold = scaffolds[next_step]
    target_cost = -1
    for j in range(steps):
        
        last_step = next_step - (j + 1)
        if -1 < last_step:
            cost = abs(scaffolds[next_step] - scaffolds[last_step]) + costs[last_step]
            if target_cost == -1 or cost < target_cost:
                target_cost = cost

    if 0 < target_cost:
        next_cost = target_cost
    else:
        next_cost = scaffolds[next_step]

    
    costs.append(next_cost)

print(costs[number - 1] - start_cost)

Measured memory_bytes: 57824
#include <iostream>
#include <algorithm>
#include <limits>

#define MAX_ELEMENTS 400

using namespace std;

// I have to create a binary tree where each inner node has the value of its two sons, I want to minimize the value of the root.

long long dp[MAX_ELEMENTS][MAX_ELEMENTS]; // The weight of having to combine all elements between interval i and j. It has to be continuous since the slimes don't change positions
long long slimes[MAX_ELEMENTS]; // The slimes themselves
long long inf = 1e18L + 5;

long long arraySum(int L, int R)
{
    long long ans = 0;
    for(int i = L; i <= R; i++)
        ans += slimes[i];
    return ans;
}

int main()
{
    int nSlimes;
    long long slimeValue;
    cin >> nSlimes;
    for(int i = 0; i < nSlimes; i++)
    {
        cin >> slimeValue;
        slimes[i] = slimeValue;
    }
    for(int i = nSlimes - 1; i >= 0; i--)
    {
        for(int j = i; j < nSlimes; j++)
        {
            if(i == j)
                dp[i][j] = 0; // The cost to combine a slime to itself is none
            else
            {
                dp[i][j] = inf;
                for(int k = i; k < j;  k++)
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + arraySum(i,j));
            }
        }
    }
    cout << dp[0][nSlimes-1];
}

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

int main(){
  char a,b;
  cin >> a >> b;
  if( a == 'H' ){
    if( b == 'H' ){
      cout << 'H' << endl;
    }else{
      cout << 'D' << endl;
    }
  }else{
    if( b == 'H' ){
      cout << 'D' << endl;
    }else{
      cout << 'H' << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
// setprecision(n)
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
int main() {
    ll w,h,x,y;
    cin >> w >> h >> x >> y;
    if (2*x == w && 2*y ==h) {
        cout << setprecision(20) << (double)(w * h) / 2 << ' ' << 1 << endl;
    } else {
        cout << setprecision(20) << (double)(w * h) / 2 << ' ' << 0 << endl;
    }
}

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

int main(){
    double n, m, d;
    cin >> n >> m >> d;
    
    double exp = 1;
    if(d != 0 && n > 2 * d) exp = 2 * (n-d) / n;

    exp = exp / n * (m-1);
    cout << fixed << setprecision(10) << exp << endl;
    return 0;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<lint>;
const lint MOD = 1e9 + 7;
inline lint emod(lint x, lint p = MOD) {
  return (x % p + p) % p;
}

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  lint n; cin >> n;
  lint m = n - 2;
  VL inv(n + 1, 1);
  for (int i = 2; i <= n; i++) {
    inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
  }
  VL fac(n + 1, 1);
  for (int i = 2; i <= n; i++) {
    fac[i] = fac[i - 1] * i % MOD;
  }
  VL ifac(n + 1, 1);
  for (int i = 2; i <= n; i++) {
    ifac[i] = ifac[i - 1] * inv[i] % MOD;
  }
  lint k = (n + 1) / 2;
  lint res = fac[k] * fac[k - 1] % MOD * ifac[2 * k - n] % MOD * k % MOD;
  while (k < n) {
    k++;
    lint b = fac[k] * fac[k - 1] % MOD * ifac[2 * k - n] % MOD;
    lint a = fac[k - 1] * fac[k - 2] % MOD * ifac[2 * (k - 1) - n] % MOD;
    res = (res + (b - a) * k % MOD ) % MOD;
  }
  cout << emod(res) << '\n';
  return 0;
}

Measured memory_bytes: 23680
import collections
S = list(input())
s = collections.deque(S)
Q = int(input())
mode = 1
for _ in range(Q):
    tmp = tuple(input().split())
    if len(tmp) == 1:
        mode = 1 ^ mode
    else:
        t, f, c = tmp
        f = int(f)
        f -= 1
        if mode ^ f:
            s.appendleft(c)
        else:
            s.append(c)
if mode:
    print("".join(list(s)))
else:
    print("".join(list(s)[::-1]))


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

signed main(void)
{
	int n, ans;
	cin >> n;
	ans = (n + 1) * n / 2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

int main(void){
	//エラトステネスで1~10^5までの素数を求めておく
	int p[100010]={};//0が素数
	reg(i,2,317){
		if(p[i]!=0)continue;
		reg(j,2,100010){
			if(i*j>100000)break;
			p[i*j]=1;
		}
	}
	//次にそれらの素数の中でN+1/2が素数であるものを抜き出す
	int sum[100010]={};
	reg(i,3,100000){//ただし2は含めない
		sum[i]=sum[i-1];
		if(p[i]==0 && p[(i+1)/2]==0)sum[i]++;
	}
	int Q,l,r;
	scanf("%d",&Q);
	rep(i,Q){
		scanf("%d%d",&l,&r);
		printf("%d\n",sum[r]-sum[l-1]);
	}
	return 0;
}

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

using namespace std;

int main()
{
    int a,b,c;
    cin >> a>>b>>c;
    int ans= b/a;
    if(ans>c)
    {
        cout << c;
    }
    else
    {
        cout << ans;
    }
    return 0;
}


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

int H, W, h, w;
int main(){
    cin >> H >> W >> h >> w;
    if(H % h == 0 && W % w == 0){
        cout << "No" << endl;
        return 0;
    }else if(H % h != 0){
        cout << "Yes" << endl;
        // i % h == 0 => s[i] = - (i/h)
        // otherwise => s[H-h+1, ..., H] = 1; s[i] = (H - i) / h + 1
        int a[500] = {}, s[501] = {};
        for(int i = 0; i <= H; i++){
            if(i % h){
                s[i] = (H - i) / h + 1;
            }else{
                s[i] = - (i/h);
            }
        }
        for(int i = 0; i < H; i++){
            a[i] = s[i+1] - s[i];
        }
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(j){
                    cout << " ";
                }
                cout << a[i];
            }
            cout << endl;
        }
    }else{
        cout << "Yes" << endl;
        int s[501] = {}, a[500] = {};
        for(int j = 0; j <= W; j++){
            if(j % w){
                s[j] = (W - j) / w + 1;
            }else{
                s[j] = - (j / w);
            }
        }
        for(int j = 0; j < W; j++){
            a[j] = s[j+1] - s[j];
        }
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                if(j){
                    cout << " ";
                }
                cout << a[j];
            }
            cout << endl;
        }
    }
    
}


Measured memory_bytes: 1408
/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

//{{{ FAST IO AND SOME FUNCTIONS
const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define ra read_alpha()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline char read_alpha() { char c = ge; while(!isalpha(c) && c != EOF) c = ge; return c; }
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T> inline void chkmin(T&a, T b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
//}}}

inline int SG(int x, int k) {
	if(x < k) return 0;
	if(x % k == 0) return x / k;
	int t = x / k, p = k * t;
	int tim = (x - p - 1) / (t + 1) + 1;
	return SG(x - tim * (t + 1), k);
}

int main() {
#ifdef LOCAL
	FILE("");
#endif
	int Xor = 0, n = ri;
	for(int i = 1; i <= n; i++) {
		int x = ri, k = ri;
		Xor ^= SG(x, k);
	} puts(Xor ? "Takahashi" : "Aoki");
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
long long int MOD = 1000000000 + 7;
using ll = long long;


int main() {
	ll N;
	string s;
	string t;
	cin >> N;
	cin >> s >> t;
	for (ll i = 0; i < N; ++i) {
		cout << s.at(i) << t.at(i);
	}
	cout << endl;

}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 205, INF = 10000;

class Edge {
public:
  int nxt, to, cap;
} e[1000005];

int head[MAX_N], cnt, iter[MAX_N], level[MAX_N];
void addedge(int u, int v, int cap) {
  e[++cnt] = (Edge){head[u], v, cap}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u, 0}, head[v] = cnt;
}

void add_biedge(int u, int v, int cap) {
  e[++cnt] = (Edge){head[u], v, cap}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u, cap}, head[v] = cnt;
}

void bfs(int s) {
  static int q[MAX_N];
  memset(level, -1, sizeof level);
  memcpy(iter, head, sizeof iter);
  
  int l = 1, r = 1;
  q[1] = s, level[s] = 0;

  while (l <= r) {
    int u = q[l++];
    for (int i = head[u]; i; i = e[i].nxt)
      if (e[i].cap > 0 && level[e[i].to] == -1) {
	level[e[i].to] = level[u] + 1;
	q[++r] = e[i].to;
      }
  }
}

#define rev(x) (x & 1 ? x + 1 : x - 1)

int dfs(int u, int t, int f) {
  if (u == t) return f;
  for (int &i = iter[u]; i; i = e[i].nxt)
    if (e[i].cap > 0 && level[e[i].to] > level[u]) {
      int d = dfs(e[i].to, t, min(f, e[i].cap));
      if (d > 0) {
	e[i].cap -= d;
	e[rev(i)].cap += d;
	return d;
      }
    }
  return 0;
}

int dinic(int s, int t) {
  int flow = 0;
  while (true) {
    bfs(s);
    if (level[t] == -1) return flow;
    static int f;
    while ((f = dfs(s, t, INF)) > 0) flow += f; 
  }
}


int H, W;
char mp[MAX_N];

int main() {
  scanf("%d%d", &H, &W);

  int S = H + W + 1, T = S + 1;
  for (int i = 1; i <= H; ++i) {
    scanf("%s", mp + 1);
    for (int j = 1; j <= W; ++j)
      if (mp[j] == 'o') {
	add_biedge(i, j + H, 1);
      } else if (mp[j] == 'S') {
	add_biedge(i, j + H, INF);
	addedge(S, i, INF);
	addedge(S, j + H, INF);
      } else if (mp[j] == 'T') {
	add_biedge(i, j + H, INF);
	addedge(i, T, INF);
	addedge(j + H, T, INF);
      }
  }

  int res = dinic(S, T);

  printf("%d\n", res < INF ? res : -1);
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 5;


int main() {
	int H, n;
	cin >> H >> n;
	// Similar to creating an array dp[h+1] but this one is better
	vector<int> dp(H + 1, INF); //dp[h]
	// dp[x] - minimum total cost to get value x
	dp[0] = 0;
	while(n--){
		int value, cost;
		cin >> value >> cost;
		for(int i = 0; i <= H; i++){ // O(N*H)
			// dp[i] -> dp[i+value]
			int j = min(H, i + value);
			dp[j] = min(dp[j], dp[i] + cost);
		}
	}
	cout << dp[H] << endl;
}

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

const int NMAX = 3010;

int n, a[NMAX];
long res = 0;

int main(){
	cin >> n;
	for (int i=1; i<=n; ++i) {
		cin >> a[i];
		res += a[i]-1;
	}

	cout << res;
	return 0;
}

Measured memory_bytes: 256
a = raw_input()
a = a.split()
for i in range(0,len(a)):
    a[i] = int(a[i])
b = sorted(a)
for i in range(0,len(a)):
    if(a[i] != b[i] or (i != (len(a) - 1) and a[i] == a[i+1])):
        print 'No'
        break
if(i == len(a)-1):
    print 'Yes'


Measured memory_bytes: 4648
#include <stdio.h>
int main(){
    int a,b,c,d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    while(a>0 && c>0){
        c=c-b;
        if(c<=0){
            printf("Yes");
            break;
        }
        a=a-d;
        if(a<=0){
            printf("No");
            break;
        }
    }
}

Measured memory_bytes: 1736
taste = 0
hoge = []
N, L = gets.chomp.split.map(&:to_i)
for i in 1..N
    taste += (i + L - 1)
    hoge.push(taste)
end

if hoge[0].to_i >= 0
    puts hoge[N-1].to_i - hoge[0].to_i
elsif hoge[N-1].to_i < 0
    puts hoge[N-2].to_i
else
    puts taste
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
	int dx=tx-sx,dy=ty-sy;

	rep(i,dx) cout<<'R';
	rep(i,dy) cout<<'U';
	cout<<'L';
	rep(i,dy-1) cout<<'D';
	rep(i,dx-1) cout<<'L';
	cout<<"DL";
	rep(i,dy+1) cout<<'U';
	rep(i,dx+1) cout<<'R';
	cout<<"DR";
	rep(i,dy+1) cout<<'D';
	rep(i,dx+1) cout<<'L';
	cout<<"U"<<"\n";
}

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


int main() {
    int n,k;
    cin >> n >> k;
    int i=1;
    while(1){
        i++;
        n /= k;
        if(n == 1){
            cout << i << endl;
            break;
        }else if (n == 0)
        {
            cout << i-1 << endl;
            break;
        }
        
    }
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

int main()
{
	int a[3];
	int ans=0x3fffffff;
	for (int i=0; i<3; ++i) scanf("%d", &a[i]);
	for (int i=0; i<3; ++i)
		for (int j=0; j<3; ++j)
			for (int k=0; k<3; ++k)
				if (i!=j && i!=k && j!=k)
					ans=min(ans, abs(a[i]-a[j])+abs(a[j]-a[k]));
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		String str = br.readLine();

		int l = 0;
		int r = n + 2;

		String[] subRights = new String[n];
		for(int i = 0; i < n; i++){
			subRights[i] = str.substring(i);
		}

		while(r - l > 1){
			int mid = (l + r)/2;

			boolean hit = false;
			for(int i = 0; i <= n - 2*mid; i++){
				String subLeft = str.substring(i, i + mid);
				char[] leftArray = subLeft.toCharArray();
				char[] rightArray = subRights[i + mid].toCharArray();
//				String subRight = str.substring(i + mid);

//				if(subRight.contains(subLeft)){
//				if(subRights[i + mid].contains(subLeft)){
				if(RKSearcher.indexOf(leftArray, rightArray) >= 0){
//				if(BMSearcher.indexOf(rightArray, leftArray) >= 0){
					hit = true;
					break;
				}
			}

			if(hit){
				l = mid;
			}
			else {
				r = mid;
			}
		}

		System.out.println(l);
	}

}

class RKSearcher {
	private static final long q = 10000000007L;
	private static final int d = 64;

	public static int indexOf(char[] str1, char[] str2){
		int M = str1.length;
		int N = str2.length;
		long dM = 1;
		long h1 = 0;
		long h2 = 0;

		//?????????????????°???????????????equals???????????°??????
		if(M == N){
			if(new String(str1).equals(new String(str2))){
				return 0;
			}
			else {
				return -1;
			}
		}

		else if (M > N){
			return -1;
		}

		for(int i = 1; i < M ; i++){
			dM = (d*dM)%q;
		}

		for(int i = 0; i < M; i++){
			h1 = (h1*d + index(str1[i])) % q;
			h2 = (h2*d + index(str2[i])) % q;
		}
		int i;
		for(i = 0; h1 != h2 ;i++){
			//System.out.println("i = "+i+" h1 "+h1+" h2 "+h2);
			h2 = (h2 + d*q - index(str2[i])*dM) % q;
			if(i+M >= N){
				return -1;
			}
			h2 = (h2*d + index(str2[i+M])) % q;
			if (i > N-M){
				return -1;
			}
		}
		return i;
	}

	private static int index(char c){
		//return c - '0' + 1;
		//??°??????0~9
		if(c >=  '0' && c <= '9'){
			return c - '0';
		}
		//?°??????????10~35
		else if (c >= 'a' && c <= 'z'){
			return c - 'a' + 10;
		}
		//??§?????????36~61
		else if (c >= 'A' && c <= 'Z'){
			return c - 'A' + 36;
		}
		else {
			return -1;
		}
	}
}



Measured memory_bytes: 120568
def resolve():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = list(input())
 
    score = {'r':  P, 's': R, 'p': S}
 
    ans = 0
    for i in range(K):
        ans += score[T[i]]
 
    for i in range(K, N):
        if T[i-K] == T[i]:
            T[i] = ' '
            continue
        ans += score[T[i]]
 
    print(ans)
 
if __name__ == "__main__":
    resolve()

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

using namespace std;

typedef vector<int> vii;
typedef long long ll;

int main(){

	int n;
	cin >> n;
	vii times;
	ll total_time = 0;
	while(n--){
		int t;
		cin >> t;
		total_time+=t;
		times.push_back(t);
	}
	int m;
	cin >> m;
	for(int i=0;i<m;++i){
		int p, x;
		cin >> p >> x;
		cout << total_time-times[p-1]+x<< endl;
	}

	return 0;
}

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

int main(){
  int A,B,K;
  cin >> A >> B >> K;
  if( K * 2 <= B - A){
    for(int i = A; i <  A + K;i++){
    cout << i << endl;
    }
    for(int j = B - K  + 1;j < B + 1;j++){
    cout <<j << endl;
    }
  }
  else {
    for(int i = A;i < B + 1;i++){
      cout << i << endl;
    }
  }
}

Measured memory_bytes: 384
import itertools

n = int(input())

li = [3,5,7]
ans = 0
for i in range(1,11):
    for elm in itertools.product(li,repeat=i):
        if not(7 in elm) or not(5 in elm) or not(3 in elm):
            continue
        ttl = 0
        for j in range(len(elm)):
            ttl += elm[j]*(10**j)
        if ttl<=n:
            #print(ttl)
            ans += 1  

print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int n;
inline void addedge(int a,int b){printf("%d %d\n",a,b);}
int main()
{
	scanf("%d",&n);
	int vvv=1;
	while(vvv<n) vvv<<=1;
	if(vvv==n) return puts("No"),0;
	puts("Yes");
	for(int i=3;i<=n;i+=2)
	{
		addedge(1,i-1);addedge(i-1,i);
		addedge(1,n+i);addedge(n+i,n+i-1);
	}
	addedge(3,1+n);
	if(n%2==0)
	{
		int va=1;
		while((n&va)==0) va<<=1;
		addedge(n,va);
		addedge(n+n,(va^n^1)+n);
	}
}

Measured memory_bytes: 3820
n,k = map(int,input().split())
x = [int(i) for i in input().split()]
ans = 10**9
for i in range(n-k+1):
    tmp = abs(x[i] - x[i+k-1])
    ans = min(ans, tmp + abs(x[i]), tmp + abs(x[i+k-1]))
print(ans)
    

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
int S[505],T[505];
unsigned long long U[505],V[505];
unsigned long long A[505][505];
int B[505][505];
int R[505][2];
int C[505][2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	FOR(i,N) cin>>T[i];
	FOR(i,N) cin>>U[i];
	FOR(i,N) cin>>V[i];
	
	FOR(r,64) {
		MINUS(B);
		ZERO(R);
		ZERO(C);
		FOR(i,N) {
			if(S[i]==1 && (U[i]&1)==0) {
				FOR(j,N) {
					if(B[i][j]==1)return _P("-1\n");
					B[i][j]=0;
				}
			}
			if(S[i]==0 && (U[i]&1)==1) {
				FOR(j,N) {
					if(B[i][j]==0)return _P("-1\n");
					B[i][j]=1;
				}
			}
			
			if(T[i]==1 && (V[i]&1)==0) {
				FOR(j,N) {
					if(B[j][i]==1) return _P("-1\n");
					B[j][i]=0;
				}
			}
			if(T[i]==0 && (V[i]&1)==1) {
				FOR(j,N) {
					if(B[j][i]==0) return _P("-1\n");
					B[j][i]=1;
				}
			}
		}
		
		
		FOR(y,N) FOR(x,N) {
			if((U[y]&1)==(V[x]&1)) B[y][x]=U[y]&1;
			if(B[y][x]==-1) B[y][x]=0;
			R[y][B[y][x]]++;
			C[x][B[y][x]]++;
		}
		
			
		FOR(y,N) if(S[y]==1&&(U[y]&1)==1) {
			if(R[y][1]) continue;
			FOR(x,N) if(T[x]==0&&(V[x]&1)==0&&C[x][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(x==N) return _P("-1\n");
		}
		FOR(x,N) if(T[x]==1&&(V[x]&1)==1) {
			if(C[x][1]) continue;
			FOR(y,N) if(S[y]==0&&(U[y]&1)==0&&R[y][0]>1) {
				B[y][x]=1;
				R[y][0]--;
				C[x][0]--;
				R[y][1]++;
				C[x][1]++;
				break;
			}
			if(y==N) return _P("-1\n");
		}
		FOR(y,N) {
			if(S[y]==0&&(U[y]&1)==1&&R[y][1]!=N) return _P("-1\n");
			if(S[y]==0&&(U[y]&1)==0&&R[y][1]==N) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==1&&R[y][1]==0) return _P("-1\n");
			if(S[y]==1&&(U[y]&1)==0&&R[y][1]!=0) return _P("-1\n");
		}
		FOR(x,N) {
			if(T[x]==0&&(V[x]&1)==1&&C[x][1]!=N) return _P("-1\n");
			if(T[x]==0&&(V[x]&1)==0&&C[x][1]==N) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==1&&C[x][1]==0) return _P("-1\n");
			if(T[x]==1&&(V[x]&1)==0&&C[x][1]!=0) return _P("-1\n");
		}
		
		FOR(y,N) FOR(x,N) if(B[y][x]) A[y][x]|=1ULL<<r;
		FOR(j,N) U[j]>>=1,V[j]>>=1;
	}
	
	
	
	FOR(y,N) {
		FOR(x,N) cout<<A[y][x]<<" ";
		cout<<endl;
	}
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 8608
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

vector<long long> P(55),ALL(55);

long long calc(long long N,long long X) {
  if(N == 0) {
    if(X <= 0) return 0;
    else return 1;
  }else if(X == 0) return 0;
  else if(1 < X && X < ALL.at(N-1)+2) return calc(N-1,X-1);
  else if(X == ALL.at(N-1)+2) return P.at(N-1)+1;
  else if(ALL.at(N-1)+2 < X && X < 2*ALL.at(N-1)+3) return P.at(N-1)+1+calc(N-1,X-2-ALL.at(N-1));
  else if(X == 2*ALL.at(N-1)+3) return 2*P.at(N-1)+1;
}

int main() {

  long long N,X;
  cin >> N >> X;

  
  P.at(0) = 1; ALL.at(0) = 1;
  for(int i = 1;i <= N;i++) {
    P.at(i) = 2*P.at(i-1) + 1;
    ALL.at(i) = 2*ALL.at(i-1) + 3;
  }

  long long ans = calc(N,X);
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> a[200010];
multiset<pair<int, int>> st;
int ans[200010], b[200010];
void dfs(int x, int pa){
	auto tmp=st.lower_bound(mk(b[x], -1));
	--tmp;
	int xx=(tmp->sc)+1;
	vector<pair<int, int> >v;
	auto store_it=mk(b[x], xx);
	ans[x]=max(xx, (*--st.end()).sc);
	++tmp;
	while(1){
		if(tmp==st.end()){
			break;
		}
		if(xx>=(tmp->sc)){
			auto it1=tmp;
			++it1;
			v.push_back(*tmp);
			st.erase(tmp);
			tmp=it1;
		}
		else{
			break;
		}
	}
	tmp=st.insert(mk(b[x], xx));
	for(auto it:a[x]){
		if(it==pa){
			continue;
		}
		dfs(it, x);
	}
	st.erase(st.find(store_it));
	for(auto it:v){
		st.insert(it);
	}
}
int main(){
    int n;
    while(cin>>n){
        for(int i=1; i<=n; ++i){
        	scanf("%d", b+i);
        }
        int x, y;
        for(int i=0; i<n-1; ++i){
            scanf("%d%d",&x, &y);
            a[x].push_back(y);
            a[y].push_back(x);
        }
        st.insert(mk(-1, 0));
        dfs(1, -1);
        for(int i=1; i<=n; ++i){
        	printf("%d\n",ans[i]);
        }
    }
  return 0;
}




Measured memory_bytes: 47844
package main

import "fmt"

func main () {
	var n int
	fmt.Scan(&n)
  
	switch lower_digit := n%10; lower_digit {
    case 2,4,5,7,9: fmt.Print("hon")
    case 0,1,6,8: fmt.Print("pon")
    case 3: fmt.Print("bon")
    }
}

Measured memory_bytes: 1752
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

using std::string;
using std::vector;
using std::set;
using std::map;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

typedef boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>> cpp_dec_float_1000;

constexpr char CRLF = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }

void solve(void)
{
  int n; cin >> n;
  cout << ((n + 1) / 2) * (n / 2) << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main() {
	char id_bef[11];
	char id_aft[12];

	scanf("%s", id_bef);
	scanf("%s", id_aft);

	for (int i = 0;; i++) {
		if (id_bef[i] != id_aft[i]) {
			if (id_bef[i] == '\0')
				printf("Yes");
			else
				printf("No");
			break;
		}
	}

	return 0;
}

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

int main(){
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll r,g,b;
  r = count(s.begin(),s.end(),'R');
  g = count(s.begin(),s.end(),'G');
  b = count(s.begin(),s.end(),'B');
  ll ans = r*g*b;
  for(ll i=0;i<=n-3;i++){
    for(ll j=i+1;j<=n-2;j++){
      if( 2*j-i >= n ) continue;
      if( s.at(i) != s.at(j) && s.at(i) != s.at(2*j-i) && s.at(j) != s.at(2*j-i) ){
        ans--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int N,W;
int w[210] = {};
ll dp[210][10010] = {};
const ll inf = 1e9+7;
int main(){
    cin >> N >> W;
    for(int i=1;i<=N;i++) cin >> w[i];
    sort(w+1,w+N+1,greater<int>());
    dp[0][0] = 1;
    ll ans = 0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<=W;j++){
            (dp[i][j] += dp[i-1][j])%=inf;
            if(j+w[i]<=W) (dp[i][j+w[i]] += dp[i-1][j])%=inf;
        }
    }
    int sum = 0;
    for(int i=N;i>=1;i--){
        for(int j=max(W-sum-w[i]+1,0);j<=W-sum;j++) (ans += dp[i-1][j])%=inf;
        sum += w[i];
    }
    if(sum<=W) ans++;
    cout << ans << endl;
}




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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

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; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 N, C; cin >> N >> C;
    vector<i64> CX(N + 1, 0);
    vector<i64> V(N);
    REP(i, N) cin >> CX[i + 1] >> V[i];

    vector<i64> CV(N + 1, 0);
    REP(i, N) CV[i + 1] = CV[i] + V[i];

    vector<i64> dp(N + 1, 0);
    REP(i, N) {
        chmax(dp[i + 1], dp[i]);
        chmax(dp[i + 1], (CV[N] - CV[N - i - 1]) - (C - CX[N - i]));
    }

    i64 maxv = 0;

    REP(l, N) {
        i64 v = CV[l + 1] - CX[l + 1];
        chmax(maxv, v);
        v -= CX[l + 1];
        chmax(maxv, v + dp[N - (l + 1)]);
    }

    REP(i, N + 1) dp[i] = 0;
    REP(i, N) {
        chmax(dp[i + 1], dp[i]);
        chmax(dp[i + 1], CV[i + 1] - CX[i + 1]);
    }
    REP(r, N) {
        i64 v = (CV[N] - CV[N - r - 1]) - (C - CX[N - r]);
        chmax(maxv, v);
        v -= C - CX[N - r];
        chmax(maxv, v + dp[N - (r + 1)]);
    }

    cout << maxv << endl;

    return 0;
}

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

string alphabet = "abcdefghijklmnopqrstuvwxyz";

int main(){
	int n;
	cin >> n;
	vector<map<char,int>> mp(n);
	rep(i,n){
		string s;
		cin >> s;
		rep(j,s.size()){
			mp[i][s[j]]++;
		}
	}
	
	string ans;
	
	rep(j,26){
		int count = mp[0][alphabet[j]];
		rep(i,n){
			count = min(count, mp[i][alphabet[j]]);
		}
		if(count > 0){
			rep(i,count){
				ans += alphabet[j];
			}
		}
	}
	
	cout << ans << endl;
    return 0;
}



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

#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
#define INF 1e12
typedef long long ll;
using namespace std;


int main()
{
	int N, T;
	cin >> N >> T;
	vector<int> t(N);
	rep(i, N)cin >> t[i];
	vector<int> t_act(N);
	rep(i, N-1)
	{
		if (t[i + 1] - t[i] >= T) t_act[i] = T;
		else t_act[i] = t[i + 1] - t[i];
	}
	t_act[N - 1] = T;
	ll ans = 0;
	rep(i, N)
	{
		ans += t_act[i];
	}
	co(ans);
	return 0;
}

Measured memory_bytes: 1792