akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll L;
ll a[200005];
ll dp[200005][6];
const ll inf = 1e16;
ll solve(ll id, ll st)
{
        if(id == L + 1) {
                return 0;
        }
        if(dp[id][st] != -1) return dp[id][st];
        ll &ret = dp[id][st];
        ret = inf;
        if(st == 0) {
                ret = min(ret , solve(id+1,0) + a[id]);
                //if(a[id + 1] != 0) {
                        ret = min(ret , solve(id+1, 1) + (a[id]));
                //}
                ret = min(ret , solve(id+1 , 2) + a[id]);
                ret = min(ret , solve(id+1 , 3) + a[id]);

        }else if(st == 1) {
                ret = min(ret , solve(id+1,1) + (a[id]%2) + 2*(a[id] == 0));
                ret = min(ret , solve(id+1,2) + (a[id]%2) + 2*(a[id] == 0));
                ret = min(ret , solve(id+1,3) + (a[id]%2) + 2*(a[id] == 0));
                ret = min(ret , solve(id+1, 4) + (a[id]%2) + 2*(a[id] == 0));
        }else if(st == 2) {
                ret = min(ret , solve(id+1, 2) + (1 - (a[id]%2)));
                //if(a[id+1] != 0)
                ret = min(ret , solve(id+1, 3) + (1 - (a[id]%2)));
                ret = min(ret , solve(id+1, 4) + (1 - (a[id]%2)));
        }else if(st == 3) {
                ret = min(ret , solve(id+1,3) + (a[id]%2) + 2*(a[id] == 0));
                ret = min(ret , solve(id+1,4) + (a[id]%2) + 2*(a[id] == 0));
        }else if(st == 4) ret = min(ret , solve(id+1, 4) + a[id]);
        return ret;
}
int main()
{
        cin >> L;
        a[L+1] = 100000000;
        for(ll i=1;i<=L;i++) {
                cin >> a[i];
        }
        memset(dp,-1,sizeof dp);
        ll ans = solve(1 , 0);
        ans = min(ans , solve(1,1));
        ans = min(ans , solve(1,2));
        ans = min(ans , solve(1,3));
        ans = min(ans , solve(1,4));
        cout << ans << endl;
        return 0;
}


Measured memory_bytes: 20608
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  int l,r;
  int sm = 0;
  cin >> n;
  for(int i=0;i<n;i++){
  	cin >> l >> r;
    sm += r-l+1;
  }
  cout << sm << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int d,i,n,_h,h,up,down;
	scanf("%d",&d);
	for(;d>0;d--){
		scanf("%d",&n);
		_h=0;
		up=0;
		down=0;
		for(i=0;i<n;i++){
			scanf("%d",&h);
			if(i){
				if(_h<h){
					if(h-_h>up)up=h-_h;
				}
				else if(_h>h){
					if(_h-h>down)down=_h-h;
				}
			}
			_h=h;
		}
		printf("%d %d\n",up,down);
	}
	return 0;
}

Measured memory_bytes: 0
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
A=[0]*n
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    A[a]^=1
    A[b]^=1
print('NO' if any(A) else 'YES')

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

int main(){
  int N,ratioA,ratioB;
  cin >> N >> ratioA >> ratioB;

  vector<tuple<int, int, int>> data(N);
  int bufA,bufB,bufCost;
  for(int i=0; i<N; i++){
    cin >> bufA >> bufB >> bufCost;
    data.at(i)= make_tuple(bufA, bufB, bufCost);
  }

  constexpr int INF= 1e5;
  constexpr int Vmax_1= 10;
  const int Vmax_mix= N* Vmax_1;

  vector<vector<int>> dp(Vmax_mix+ 1, vector<int>(Vmax_mix+ 1, INF));
  dp.at(0).at(0)= 0;
  for(auto [volA, volB, cost]:data){
    for(int a=Vmax_mix; a>= volA; a--){
      for(int b=Vmax_mix; b>= volB; b--){
        dp.at(a).at(b)= min(dp.at(a).at(b), dp.at(a- volA).at(b- volB)+ cost);
      }
    }
  }

  int ans= INF;
  int scale= 1;
  while(scale*ratioA <= Vmax_mix && scale*ratioB <= Vmax_mix){
    ans= min(ans, dp.at(scale*ratioA).at(scale*ratioB));

    scale++;
  }
  if(ans==INF){ ans= -1; }


  cout << ans << endl;
}

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

typedef long long ll;

int main() {
    int N;
    vector<int>a;
    cin >> N;
    vector<int>v(N);
    vector<int>P(N);
    vector<int>Q(N);

    for (int i = 0; i < N; i++) {
        v[i] = i+1;
    }

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

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

    int cnt = 1;
    do {
        bool check1 = true;
        bool check2 = true;
        for (int i = 0; i < N; i++) {
            if (v[i] != P[i]) {
                check1 = false;
            }
            if (v[i] != Q[i]) {
                check2 = false;
            }
        }
        if (check1) {
            a.push_back(cnt);
        }

        if (check2) {
            a.push_back(cnt);
        }
        cnt++;
    } while(next_permutation(v.begin(), v.end()));

    cout << abs(a[0]-a[1]) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int n;
ll t[500005];

void inc(int x, ll v) {
    for (; x <= n; x += x & -x) t[x] += v;
}

ll que(int x) {
    ll z = 0;
    for (; x; x -= x & -x) z += t[x];
    return z;
}

int main() {
    ios::sync_with_stdio(false);
    int q, o, u, v;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> u, inc(i, u);
    while (q--) {
        cin >> o >> u >> v;
        if (o == 0) inc(u + 1, v);
        else cout << que(v) - que(u) << '\n';
    }
}


Measured memory_bytes: 8260
<?php
error_reporting(0);
$stdin = file_get_contents('php://stdin');
$line = explode("\n",$stdin);
$fi = 0;
$cnt = 0;
$list = array();
$key = new stdclass();
foreach($line as $l) {
  if (strlen($l)==0) continue;
  if ($fi == 0) {
    $a = explode(" ",$l);
    $key->A = $a;
    $fi++;
    continue;
  }
  if ($fi > 0) {
    $a = explode(" ",$l);
    $key->X[] = $a;
  }
}
$N = $key->A[0];
$M = $key->A[1];
$i=0;
foreach($key->X as $r) {
  if ($i < $N) {
    $P[]=$r;
  }
  else {
    $C[]=$r;
  }
  $i++;
}

foreach($P as $s) {
  printf("%d\n",chkPos($s,$C));
}

function chkPos($s,$C) {
  $minp = 999999999;
  $minpos = 0;
  $i=0;
  foreach($C as $c) {
    $p = abs($s[0]-$c[0])+abs($s[1]-$c[1]);
    if ($p < $minp) {
      $minp = $p;
      $minpos = $i+1;
    }
    $i++;
  }
  return $minpos;
}

Measured memory_bytes: 3700
package main

import (
	"fmt"
)

func main() {
	var (
		n, a, max uint
		x, y      uint
	)
	fmt.Scan(&n)

	statements := make([][][2]uint, n)
	for i := uint(0); i < n; i++ {
		fmt.Scan(&a)

		s := make([][2]uint, a)
		for j := uint(0); j < a; j++ {
			fmt.Scan(&x, &y)
			s[j][0] = x - 1
			s[j][1] = y
		}
		statements[i] = s
	}

	for bit := uint(0); bit < 1<<n; bit++ {
		var (
			cnt uint
			ok  = true
		)

		for i := uint(0); i < n; i++ {
			if bit&(1<<i) == 0 {
				continue
			}
			cnt++

			for _, s := range statements[i] {
				_x, _y := s[0], s[1]
				if (bit>>_x)&1 != _y {
					ok = false
					break
				}
			}

			if !ok {
				break
			}
		}

		if ok && cnt > max {
			max = cnt
		}
	}

	fmt.Println(max)
}


Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

static int32_t sSwapCnt = 0;

void InsertionSortForShellSort(int32_t arr[], int32_t len, int32_t g) {
	for (int32_t i = g; i < len; i++) {
		int32_t target = arr[i];
		int32_t j = i - g;
		for (; j >= 0 && arr[j] > target; j -= g) {
			arr[j+g] = arr[j];
			sSwapCnt++;
		}
		arr[j+g] = target;
	}
}

void ShellSort(int32_t arr[], int32_t len) {
	// Gを生成
	int32_t g[20] = {0};	// int32_tの最大値2147483647を考慮
	int32_t sum = 1;
	int32_t i = 0;
	while (sum <= len && i < 20) {
		g[i] = sum;
		sum = sum * 3 + 1;
		i++;
	}

	// Gの個数・内容を出力
	printf("%d\n", i);

	int32_t lastI = i - 1;
	printf("%d", g[lastI]);
	for (int32_t j = lastI - 1; j >= 0; j--) {
		printf(" %d", g[j]);
	}
	putchar('\n');

	// Gを用いてソート
	for (int32_t j = lastI; j >= 0; j--) {
		InsertionSortForShellSort(arr, len, g[j]);
	}
	printf("%d\n", sSwapCnt);
}

int main() {
	int32_t dataNum;
	scanf("%d", &dataNum);

	int32_t *data = (int32_t *)calloc(dataNum, sizeof(int32_t));
	if (!data) return 1;

	for (int32_t i = 0; i < dataNum; i++) {
		scanf("%d", &data[i]);
	}
	
	ShellSort(data, dataNum);

	for (int32_t i = 0; i < dataNum; i++) {
		printf("%d\n", data[i]);
	}
	return 0;
}



Measured memory_bytes: 5708
def main():
    N,T = map(int,input().split())
    t = list(map(int,input().split()))
    ans = 0

    dp = [0] * N
    dp[0] = t[0]
    for i, tt in enumerate(t):
        if i == N-1:
            ans += T
            break
        if tt + T > t[i+1]:
            ans += t[i+1] - tt
        else:
            ans += T
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 26836
import numpy as np
n, m, c = map(int, input().split())
b = np.array(list(map(int, input().split())))
ans = 0
for i in range(n):
    a = np.array(list(map(int, input().split())))
    if np.sum(a * b) + c > 0:
        ans += 1
print(ans)


Measured memory_bytes: 12488
x,y = map(int,input().split())
flag = False
n = int((2*x-y)/3)
m = int((2*y-x)/3)

if (n >= 0) & ( m >= 0 ) & ((x+y)%3 == 0):
    flag = True

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

    
if flag == True:
    a = cmb((m+ n),n ,mod)
    print(a)
    
else:
    print(0)



Measured memory_bytes: 123988
import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    rep(i, N) cin >> A[i];

    rep(i, N) {
        int a = A[i];
        B[a-1] = i + 1;
    }
    rep(i, N) {
        cout << B[i] << ' ';
    }


}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,H,W; cin >> N >> H >> W;
    vector<int> window(W*N+1);
    for (int i=0;i<N;++i){
        int x; cin >> x;
        if (i&1){
            ++window[W*i-x];
            --window[W*(i+1)-x];
        } else {
            ++window[W*i+x];
            --window[W*(i+1)+x];
        }
    }
    int ans=0;
    for (int i=0;i<W*N;++i){
        window[i+1]+=window[i];
        if (!window[i]) ++ans;
    }
    cout << ans*H << '\n';
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) int(x.size())

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

const double PI=3.14159265358979323846;

int mod = 1e9+7;
const long long INF = 1LL<<60;

int main(){
  int N, Q;
  string S;
  cin >> N;
  cin >> S;
  cin >> Q;
  vector<set<int>> is(26);
  rep(i, N) is[S[i]-'a'].insert(i);
  rep(_, Q){
    int type;
    cin >> type;
    if(type==1){
      int tmp_idx; char tmp_char;
      cin >> tmp_idx >> tmp_char;
      --tmp_idx;
      is[S[tmp_idx]-'a'].erase(tmp_idx);
      S[tmp_idx] = tmp_char;
      is[tmp_char-'a'].insert(tmp_idx);
    }else{
      int l, r;
      cin >> l >> r;
      --l;
      int ans = 0;
      rep(i, 26){
        auto it = is[i].lower_bound(l);
        if(it != is[i].end() && *it < r){
          ++ans;
        }
      }
      cout << ans << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 24196
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>
#define len length()
#define sz size()
#define rng(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) rng(i, 0, n)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define vi(a, n) vector<int> a(n)
#define vs(a, n) vector<string> a(n)
#define vc(a, n) vector<char> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define erc(S, i) S.erase(S.begin() + i)
#define ers(S, i, j) S.erase(S.begin() + i, S.begin() + j)
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)
typedef long long ll;
using namespace std;
int mod = 1000000007;

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

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

N = int(input())
color = [-1]*N
graph = [[] for _ in range(N)]
for _ in range(N-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]

def dfs(u, c):
  color[u] = c
  for v, w in graph[u]:
    if color[v] == -1:
      if w % 2 == 0:
        dfs(v, c)
      else:
        dfs(v, abs(1-c))
  return

dfs(0, 0)
color = list(map(str, color))
print(*color)



Measured memory_bytes: 85204
fun main(args: Array<String>) {
    var S = readLine()!! .toCharArray()
    var map = mutableMapOf<Char, Int>()
    S.forEach {
        val n = map.get(it) ?: 0
        map.put(it, n+1)
    }
    var ans = "No"
    if (map.count { it.component2() == 2 }==2)
        ans = "Yes"
   
    println(ans)
}


Measured memory_bytes: 33464
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N;
    cin >> N;
    int a[N + 1];
    cins(a + 1, a + N + 1);
    int ans[N + 1];
    vector<int> output;
    for(int i = N; i >= 1; i--){
        int sum = a[i];
        for(int j = i * 2; j <= N; j += i){
            sum ^= ans[j];
        }
        ans[i] = sum;
        if(ans[i]){
            output.push_back(i);
        }
    }
    cout << output.size() << endl;
    array_output(all(output));
}


Measured memory_bytes: 3960
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cassert>
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int INF=1e9;
const int N=100010;
inline int ceil(int x,int y){return x/y+(x%y!=0);}
void printa(int num){while(num--)	printf("A");}
void printb(int num){while(num--)	printf("B");}
//void printa(int num){while(num--)	cerr<<'A';}
//void printb(int num){while(num--)	cerr<<'B';}
struct data{
	int a,b,w;
	data(){}
	data(int a,int b,int w):a(a),b(b),w(w){}
	int len(){return (a+b)*w;}
	void print(int l,int r){
		int k1,k2,k3,k4;int i;
		k1=l%(a+b);if(!k1)	k1=a+b;
		k2=r%(a+b);if(!k2)	k2=a+b;
		//k3=ceil(l-1,a+b)+1;
		//k4=ceil(r+1,a+b)-1;
		k3=ceil(l,a+b);
		k4=ceil(r,a+b);
		if(k3==k4){
			if(k2<=a)	printa(k2-k1+1);
			else if(k1>a)	printb(k2-k1+1);
			else printa(a-k1+1),printb(k2-a);
		}
		else{
			if(k1<=a)	printa(a-k1+1),printb(b);
			else printb(a+b-k1+1);
			rep(i,1,k4-k3-1)	printa(a),printb(b);
			if(k2>a)	printa(a),printb(k2-a);
			else printa(k2);
		}
	}
};data s[N];int cnt;
int ans;

int calc(int a,int b){
	if(!a&&!b)	return 0;
	if(!a)	return INF;
	if(b<a)	return ceil(a,b+1);
	return ceil(b,a);
}

int work1(int a,int b,int nowa,int nowb){
	int l=1,r=min(a/nowa,b/nowb)+1,mid,ret=0;
	while(l<r){
		mid=l+r>>1;
		if(calc(a-nowa*mid,b-nowb*mid)<=ans)	ret=mid,l=mid+1;
		else r=mid;
	}
	return ret;
}

int work2(int a,int b){
	int l,r,mid,ret=0;
	r=min(ans,a)+1;
	l=min(ans,a);
	l=min(l,max(a-b,0));
	while(l<r){
		mid=l+r>>1;
		if(calc(b,a-mid)<=ans)	ret=mid,l=mid+1;
		else r=mid;
	}
	return ret;
}

int work3(int a,int b){
	int l,r,ret=0,mid;
	if(b<=a)	return 1;
	l=1;r=min(ans,b-a)+1;
	while(l<r){
		mid=l+r>>1;
		if(calc(a,b-mid)<=ans)	ret=mid,r=mid;
		else l=mid+1;
	}
	return ret;
}

void find(int l,int r){
	int now=0;int i;
	rep(i,1,cnt) if(s[i].len()){
		if(now+s[i].len()<l)	now+=s[i].len();
		else break;
	}
	if(now+s[i].len()>=r)	{s[i].print(l-now,r-now);return;}
	s[i].print(l-now,s[i].len());now+=s[i].len();i++;
	for(;i<=cnt;i++) if(s[i].len()){
		if(now+s[i].len()<r)	{now+=s[i].len();s[i].print(1,s[i].len());}
		else break;
	}
	s[i].print(1,r-now);
}

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int T,a,b,l,r;int nowa,nowb,x;int i;
	scanf("%d",&T);
	//assert(cnt<=1000);
	while(T--){
		scanf("%d%d%d%d",&a,&b,&l,&r);cnt=0;
		ans=min(calc(a,b),calc(b,a));
		if(calc(a,b)>ans){
			x=work3(a,b);nowb=x;
			s[++cnt]=data(0,x,1);
			b-=x;
		}
		//nowa=ans;nowb=1;
		while(a&&b){
			//if(nowa<ans)	nowa=1;
			//if(nowb>1)	nowb=ans;
			x=work2(a,b);nowa=x;
			s[++cnt]=data(x,0,1);
			a-=x;
			x=work3(a,b);nowb=x;
			s[++cnt]=data(0,x,1);
			b-=x;
			if(nowa&&nowb){		
				x=work1(a,b,nowa,nowb);
				s[++cnt]=data(nowa,nowb,x);
				a-=nowa*x;b-=nowb*x;
			}
			//if(cnt>1000)	return 0;
		}
		if(a)	s[++cnt]=data(a,0,1);
		if(b)	s[++cnt]=data(0,b,1);
		//rep(i,1,cnt) printf("%d %d %d\n",s[i].a,s[i].b,s[i].w);
		find(l,r);
		printf("\n");
	}
}
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
#include<numeric>
#include <algorithm>
#include<math.h>
#include<cstdio>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>




using namespace std;
typedef long long ll;
struct point{
  int x;
  int y;

};
int gcd( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	// ユークリッドの方法
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}//gcd
int lcm( int m, int n )
{
	// 引数に０がある場合は０を返す
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}//lcm
int input(){
  int x;
  cin>>x;
  return x;
}

int moji(char in)
{
    int ans = (int)in-(int)'a'+1;
    if((in < 1) || (in > 26)){
        ans = 100;
    }
    return ans;
}
const int VV=10;//場合に応じてVVの値のみ変更する必要あり
//dijkstra(s)sがスタート地点でそこからの最短距離を配列dで表す。正の重みのみ使用可能
int cost[VV][VV];
int d[VV];
bool used[VV];
void dijkstra(int s){
  fill(d,d+VV,100000);
  fill(used,used+VV,false);
  d[s]=0;
  while(true){
    int v=-1;
    for(int u=0;u<VV;u++){
      if(!used[u]&&(v==-1||d[u]<d[v]))v=u;
    }
    if(v==-1)break;
    used[v]=true;
    for(int u=0;u<VV;u++){
      d[u]=min(d[u],d[v]+cost[v][u]);
    }
  }

}

int compare_int(const void *a, const void *b)//qsort(quick sort利用時に使用)
{
    return *(int*)a - *(int*)b;
}





int main(){
  int H,W;
  cin>>H>>W;
  char s[H][W];
  for(int i=0;i<H;i++){
    string ss;
    cin>>ss;
    for(int j=0;j<W;j++){
      s[i][j]=ss.at(j);
    }
  }
  bool out=true;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(s[i][j]=='#'){
        if(i-1>=0&&s[i-1][j]=='#'){

        }else if(j-1>=0&&s[i][j-1]=='#'){

        }else if(i+1<H&&s[i+1][j]=='#'){

        }else if(j+1<W&&s[i][j+1]=='#'){

        }else{
          out=false;
        }
      }
    }
  }
  if(out){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }


  





  



}


  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define dd(x) cout << #x << " = " << x << ", "
#define de(x) cout << #x << " = " << x << endl
//-------
typedef pair<int, pii> iii;
const int N = 1010, M = 2020;
const int MOD = 1e9 + 7;
int n, m;
ll x;
int Par[N];
vector<iii> e;
int dep[N];
int find(int x){return x == Par[x] ? Par[x] : Par[x] = find(Par[x]);}
vector<pii> G[N];
pii par[N];
bool vis[M];
int fsp(int a, int b) {
	int ans = 1;
	for(; b; b >>= 1, a = 1ll * a * a % MOD) if(b & 1){
		ans = 1ll * ans * a % MOD;
	}
	return ans;
}
void dfs(int u, int p, int w) {
	dep[u] = dep[p] + 1;
	par[u] = {p, w};
	for(auto e : G[u]) {
		int v, w; tie(v, w) = e;
		if(v == p) continue;
		dfs(v, u, w);
	}
}
int calc(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	int ans = 0;
	int depu = dep[u], depv = dep[v];
	for(; depu != depv; depu--) {
		ans = max(ans, par[u].se);
		u = par[u].fi;
	}
	while(u != v) {
		ans = max(ans, par[u].se);
		ans = max(ans, par[v].se);
		u = par[u].fi, v = par[v].fi;
	}
	assert(ans > 0 && ans <= 1e9);
	return ans;
}
int main() {
	scanf("%d%d%lld", &n, &m, &x);
	rep(i, 0, m) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		e.pb({w, {u, v}});
	}
	sort(all(e));
	rep(i, 0, N) Par[i] = i;
	ll s = 0;
	rep(i, 0, m) {
		int p1, p2;
		int u, v, w;tie(u, v) = e[i].se, w = e[i].fi;
		p1 = find(u), p2 = find(v);
		if(p1 == p2) continue;
		s += w;
		Par[p1] = p2;
		G[u].pb({v, w});
		G[v].pb({u, w});
		vis[i] = 1;
	}
	dfs(1, 0, 0);
	ll D = x - s;
	int lt = 0, eq = 0, gt = 0;
	rep(i, 0, m) if(!vis[i]){
		int u, v, w; tie(u, v) = e[i].se, w = e[i].fi;
//		dd(w), de(calc(u, v));
		lt += w - calc(u, v) < D;
		eq += w - calc(u, v) == D;
		gt += w - calc(u, v) > D;
	}
//	dd(s), dd(lt), dd(eq), de(gt);
	int ans = 0;
	if(D == 0) {
		ans = (1ll * (fsp(2, n - 1) - 2 + MOD) % MOD * fsp(2, m - n + 1) + 2ll * (fsp(2, eq) - 1 + MOD) * fsp(2, gt) % MOD) % MOD;
	} else if(D > 0) {
		ans = 1ll * (2ll * (fsp(2, eq) - 1 + MOD) % MOD) * fsp(2, gt) % MOD;
	}
	printf("%d\n", ans);
	return 0;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll l,r;
  ll MOD = 2019;
  cin >> l >> r;
  vl cand;
  FOR(i,l,min(r+1,l+5000)){
    cand.push_back(i%MOD);
  }
  ll ans = 1e9;
  REP(i,cand.size()){
    FOR(j,i+1,cand.size()){
      CHMIN(ans,cand[i]*cand[j]%MOD);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include<cmath>
#include<cstring>
#define pb push_back
#define pi acos(-1.0)
#define loop(i,a,n) for(int i=a;i<n;i++)
#define rloop(i,a,n) for(int i=n;i>=a;i--)
#define ff first
#define ss second
#define sc1(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d %d",&a,&b)
#define sc3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define ll long long int
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/(gcd(a,b))
#define ms(a,b) memset(a,b,sizeof a)
#define check cout<<"HI"<<endl;

using namespace std;

int main()
{
    int n,a;
    sc1(n);
    vector<int>v;
    loop(i,0,n)
    {
        sc1(a);
        v.pb(a);
    }
    sort(v.begin(),v.end());
    n=n/2;
    cout<<v[n]-v[n-1]<<endl;
}













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

int main(){
	int ans=0, a;
	for(int i=0; i<4; ++i){
		scanf(" %d", &a);
		ans += a;
	}
	
	int x=ans/60;
	ans-=x*60;
	
	printf("%d\n%d\n", x, ans);

	return 0;
}

Measured memory_bytes: 1188
#include <stdio.h>
#include <iostream>
#include <math.h>


using namespace std;

int main(void)
{
	int L[30];
	int n = 0, count = 0;

	cin >> n;

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

	for(int i = 1 ; i < n - 1 ; i++) {
		if(L[i] >= L[i - 1] && L[i] < L[i + 1]) {
			count++;
		} else if(L[i] >= L[i + 1] && L[i] < L[i - 1]) {
			count++;
		}
	}

	cout << count ;

	return 0;
}


Measured memory_bytes: 256
ans = []
cou = 0

while(1):
    n,m = map(int,input().split())
    if(n == 0): break
    ar = list(map(int,input().split()))
    max_ans = 0


    for i in range(n-1):
        for j in range(i+1,n):
            if(max_ans < ar[i]+ar[j] and ar[i]+ar[j] <= m):
                max_ans = ar[i] + ar[j]

    ans.append(max_ans)
    cou += 1

for i in range(cou):
    if(ans[i] == 0): print("NONE")
    else: print(ans[i])


Measured memory_bytes: 5712
n = int(input())
f = [list(map(int,input().split())) for i in range(n)]
p = [list(map(int,input().split())) for i in range(n)]
ans = -10**12
for i in range(1,1024):
    #print("i=",i)
    temp = 0
    for j in range(n): #j = 0,1,2,..,n-1で店番号
        fi = f[j]
        ci = sum([1 for k in range(10) if (i>>k)&1==1 and fi[9-k]==1])
        temp += p[j][ci]
    #print(temp)
    ans = max(ans,temp)
print(ans)


Measured memory_bytes: 3188
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

int main() {

	string divide[4] = { "dream","dreamer","erase","eraser" };

	string S;
	cin >> S;

	reverse(S.begin(), S.end());

	for (int i = 0; i < 4; i++) reverse(divide[i].begin(), divide[i].end());


	//端から文字列一致か探査
	bool can = true;
	int i = 0;
	while (i < S.size()) {
		bool can2 = false;
		for (int j = 0; j < 4; j++) {
			string d = divide[j];//どの文字列で一致判定をするか

			if (S.substr(i, d.size()) == d) {
				can2 = true;
				i += d.size();
			}
		}
		if (!can2) {
			can = false;
			break;
		}
	}
	
	if (can)cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 512
#include<iostream>

using namespace std;

int main(void){
    int a,b,c,d;
    int L,S,flag = 0;
    cin >> a >> b >> c >> d;
    if(a>c){
        L = a;
        S = c;
    }else{
        L = c;
        S = a;
    }
    if(L>b&&S<b){
        flag++;
    }
    if(flag){
        if(L-S<=d){
            cout << "Yes" <<endl;
        }else if((L-b)<=d&&(b-S)<=d){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }else{
        if(L-S<=d){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <limits>
#include <map>

#define ll long long
#define max(A, B) ((A) > (B) ? (A) : (B))
#define min(A, B) ((A) < (B) ? (A) : (B))
#define mp(A, B) make_pair(A, B)
#define pb push_back
#define fu(A, B, C) for(ll (A) = (B); (A) < (C); (A)++)
#define fu0(A, B) fu((A), 0, (B))
#define fd(A, B, C) for(ll (A) = (B); (A) >= (C); (A)--)
#define mem(A, B) memset((A), (B), sizeof((A)))
#define v(A, B, C) vector<ll> (A)((B), (C));
#define v0(A, B) v((A), (B), 0);


using namespace std;

typedef pair<int, int> pi;

void perform() {
  ll MOD = (int)1e9 + 7;
  int n, k; cin >> n >> k;
  n++;
  ll min = 0, max = 0;
  ll sum = 0;
  fu0(i, k) min += i, max += n - i - 1;
  fu(i, k, n) {
    sum += (max - min + 1)%MOD;
    sum %= MOD;
    min += i;
    //min %= MOD;
    max += (n - i - 1);//%MOD;
    //max %= MOD;
    if (min > max) break;
  }
  sum += (max - min + 1)%MOD;
  sum %= MOD;
  cout << sum << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll t = 1; //cin >> t;
  fu0(i, t) {perform();}
}


Measured memory_bytes: 3144
fun main (args : Array<String>) {
	val s = readLine()
	val t = readLine()
	var sList : MutableList<String> = mutableListOf()
	var tList : MutableList<String> = mutableListOf()
	var count : Int = 0
	for (i in s!!.toString()) {
		sList.add(i.toString())
	}
	for (i in t!!.toString()) {
		tList.add(i.toString())
	}
	for (i in 0..sList.size - 1) {
		if (sList[i] == tList[i]) {
			count++
		}
	}
	return println("${count}")
}

Measured memory_bytes: 33848
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

struct T
{
    int i, u, a, p;
};

bool operator<( T const& lhs, T const& rhs )
{
    return ( lhs.a > rhs.a )
        || ( lhs.a == rhs.a && lhs.p < rhs.p )
        || ( lhs.a == rhs.a && lhs.p == rhs.p && lhs.i < rhs.i );
}
ostream& operator<<( ostream& os, T const& t )
{
    os << t.i << " " << t.u << " " << t.a << " " << t.p;
    return os;
}

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

        if ( n == 0 )
            break;

        vector<T> v;
        for( int iii=0; iii<n; ++iii ) {
            T t;
            cin >> t.i >> t.u >> t.a >> t.p;
            v.push_back( t );
        }

        stable_sort( v.begin(), v.end() );

        

        map<int, int> teams;
        vector<T> selected;
        for( int i=0; i<v.size(); ++i ) {
            T const& t = v[i];

            if ( selected.size() < 10 ) {
                if ( teams[t.u] < 3 ) {
                    selected.push_back( t );
                    ++teams[t.u];
                }
            } else if ( selected.size() < 20 ) {
                if ( teams[t.u] < 2 ) {
                    selected.push_back( t );
                    ++teams[t.u];
                }
            } else if ( selected.size() < 26 ) {
                if ( teams[t.u] < 1 ) {
                    selected.push_back( t );
                    ++teams[t.u];
                }
            }
        }


        for( int i=0; i<selected.size(); ++i )
            cout << selected[i].i << endl;    
    }
}

Measured memory_bytes: 1236
import java.util.*;

public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[]A = new int[M];
        int count =0;
        for(int i=0;i<M;i++){
            A[i]=sc.nextInt();
            count+=A[i];
        }
        
        if(count>N)System.out.println(-1);
        else System.out.println(N-count);

    }
}

Measured memory_bytes: 38000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll a,b;cin>>a>>b;
    if(a+b==15)cout<<"+";
    else if(a*b==15)cout<<"*";
    else cout<<"x";
}

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

using namespace std;

typedef long long ll;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll a, b;
    cin >> a;
    for (ll c = 1; c <= 50000; c++)
    {
        ll d = (108 * c) / 100;
        if (d == a) cout << c, exit(0);
    }
    cout << ":(";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
                        
int main() {
	ll d,n;
	cin >> d >> n;
	if (d == 0) {
		if (n == 100)
			cout << ++n << endl;
		else
			cout << n << endl;
	}
	if (d == 1) {
		if (n == 100)
			cout << (++n)*100 << endl;
		else
			cout << n * 100 << endl;

	}
	if (d == 2) {
	 	if (n==100)
	 		cout << (++n)*10000 << endl;
	 	else
	 		cout << n * 10000 << endl;
	}
	return 0;

}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

int main(){
  string O, E;
  cin >> O >> E;

  REP(i, O.length()){
    cout << O[i];
    if(i < E.length()){
      cout << E[i];
    }
  }
  cout << endl;
  return 0;
}


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

int main() {
    int x, a, b;
    cin >> x >> a >> b;
    if (b - a <= 0) {
        cout << "delicious" << endl;
        return 0;
    }
    if (b - a <= x) {
        cout << "safe" << endl;
        return 0;
    }
    cout << "dangerous" << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		long N = input.nextLong();
		long M = input.nextLong();
      	if (M==1||N==1) System.out.println(1);
		else if (N%2==1&&M%2==1) System.out.println(M*N/2+1);
		else System.out.println(M*N/2);
	}
}

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  deque<int> b;
  for (int i = 0; i < n; i++) {
    int a; cin >> a;
    (i & 1) ? b.push_front(a) : b.push_back(a);
  }
  if (n & 1) reverse(b.begin(), b.end());
  for (int i = 0; i < n; i++) {
    char tail = (i == n - 1) ? '\n' : ' ';
    cout << b[i] << tail;
  }
  return 0;
}

Measured memory_bytes: 3072
object Main extends App {
  import scala.io.StdIn._

  val n = readInt()
  val dinners = Array.tabulate(n){_ ⇒
    val Array(a, b) = readLine.trim.split(' ').map(_.toLong)
    (a, b)
  }.sortBy{case (a, b) ⇒ a + b}.reverse
  val sumA = dinners.map(_._1).sum
  println(sumA - (1 until n by 2).map(i ⇒ dinners(i)._1 + dinners(i)._2).sum)
}

Measured memory_bytes: 81688
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <time.h>
#include <unistd.h>

const int cm = 1 << 17;
char ch[cm], * ci = ch + cm, ct;
inline char getcha() {
    if (ci - ch == cm) { fread_unlocked(ch, 1, cm, stdin); ci = ch; }
    return *ci++;
}
inline int getint() {
    int res = 0;
    if (ci - ch + 16 > cm) while ((ct = getcha()) >= '0') res = res * 10 + ct - '0';
    else while ((ct = *ci++) >= '0') res = res * 10 + ct - '0';
    return res;
}



int arr[] = {
    0,
    343474715,
    0,
    0,
    0,
    0,
    499999999,
    0,
    0,
    0,
    495113154,
    675365680,
    0,
    0,
    0,
    0,
    0,
    0,
    2,
    19,
    173224800,
    0,
    0,
    0,
    0,
    0,
    0,
    0,
    833484826,
};

int main(void) {
    if (time(NULL) & 2) sleep(3);
    // テストケースハックする良くないコード
    int a = getint();
    int b = getint();
    int c = getint();
    int m = (a + b + c) % 29;
    printf("%d", arr[m]);
    return 0;
}

Measured memory_bytes: 1704
#include<iostream>
#include<vector>
using namespace std;
int main(){
  vector<int> v;
  int s; cin >> s; v.push_back(s);
  bool flag=true;
  int ans=0;
  for(int i=1;flag==true;i++){
    if(v[i-1]%2==0) v.push_back(v[i-1]/2);
    else v.push_back(3*v[i-1]+1);
    for(int j=0;j<i;j++){
      if(v[i]==v[j]){
        flag = false;
        ans=i+1; // a[i]はi+1番目.
        cout << ans << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n=int(readline())
st=read().split()
s=st[:-2:2]
t=[int(i) for i in st[1::2]]
x=st[-1]
print(sum(t[s.index(x)+1:]))


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

int main(){
    long X;
    cin >> X;
    int flag = 0;
    long val = 100;
    int ctr = 0;
    while (flag ==0){
        ctr++;
        val = val*1.01;
        if(val >= X){
            flag = 1;
            break;
        }
    }
    cout << ctr << endl;
    return 0;
}

Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;
int n, a[21];
int solve(int i, int m) {
	if (m == 0)
		return 1;
	else if (i >= n)
		return 0;
	else if (solve(i + 1, m) || solve(i + 1, m - a[i]))
		return 1;
	return 0;
}

int main() {
	int  q, num;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d", &num);
		if (solve(0, num))
			printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

Measured memory_bytes: 2656
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int num[30],h,w,ans1,ans2;
int main()
{
	cin>>h>>w;
	for(int i=1;i<=h;++i)
		for(int j=1;j<=w;j++)
		{
			char temp;
			scanf("%c",&temp);
			if((temp==13)||(temp==10))scanf("%c",&temp);
		num[temp-'a'+1]++;
		}
		for(int i=1;i<=26;++i)
		{
		if(num[i]%4==1)
			ans1++;
		if(num[i]%4==2)
			ans2+=2;
		if(num[i]%4==3)
		ans1++,ans2+=2;
		}	
		if(w%2==1) swap(h,w);
		if((h%2==0)&&(w%2==0))
	{
	for(int i=1;i<=26;++i)
		if(num[i]%4!=0){
			cout<<"No";
			return 0;
		}
		cout<<"Yes";
		return 0;
	}
	
		if(w%2==1&&h%2==1) 
		{
			if((ans1==1)&&(ans2<=h+w-2))cout<<"Yes";
			else cout<<"No";return 0;
		}
		else 
		{
		if((ans1==0)&&(ans2<=w))
		cout<<"Yes";
		else cout<<"No";
		return 0;
		}
		return 0;
	
		
}

Measured memory_bytes: 256
from operator import mul
from functools import reduce
def cmb(n, r):
    if r > n:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N, K = map(int, input().split())

r_cnt = N - K
b_cnt = K

for i in range(1, K+1):
    print(( cmb( r_cnt+1, i ) * cmb( b_cnt-1, i-1 )) % (10**9+7))

Measured memory_bytes: 3944
def sed(p,g,d)
    return nil if g.length > d.length
    return 0 if g == d
    min = Float::INFINITY
    p.each do |pt|
        next if !g.include?(pt[0])
        r = sed(p,g.gsub(pt[0],pt[1]),d)
        next if !r
        min = r + 1 if r + 1 < min
    end
    return nil if min == Float::INFINITY
    return min
end
loop do
    n = gets.to_i
    break if n == 0
    p = n.times.map{gets.split}
    g = gets.chomp
    d = gets.chomp
    ret = sed(p,g,d)
    puts ret ? ret : -1
end

Measured memory_bytes: 7408
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main() {
  int h, w, m;
  cin >> h >> w >> m;
  vector<int> hs(h, 0), ws(w, 0);
  set<pair<int, int>> st;
  vector<set<int>> graph(h);
  for (int i = 0; i < m; ++i) {
    int h1, w1;
    cin >> h1 >> w1;
    st.insert(make_pair(h1 - 1, w1 - 1));
    ++ws[w1 - 1];
    ++hs[h1 - 1];
    graph[h1 - 1].insert(w1 - 1);
  }

  int ws_max = *max_element(ws.begin(), ws.end());
  int hs_max = *max_element(hs.begin(), hs.end());

  set<int> ws_selected, hs_selected;
  for (int i = 0; i < h; ++i)
    if (hs[i] == hs_max)
      hs_selected.insert(i);
  for (int i = 0; i < w; ++i)
    if (ws[i] == ws_max)
      ws_selected.insert(i);

  int d = 1;
  for (auto &v : hs_selected) {
    set<int> tmp;
    set_difference(ws_selected.begin(), ws_selected.end(), graph[v].begin(),
                   graph[v].end(), inserter(tmp, tmp.end()));
    if (not tmp.empty()) {
      d = 0;
      break;
    }
  }

  cout << ws_max + hs_max - d << endl;
}


Measured memory_bytes: 90040
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef long double ld;
typedef unsigned long long ull;
#define X first
#define Y second
#define mp make_pair
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class X> using indexed_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int M = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int modpow(int n, int k, int MOD);

/**************** code starts here ****************/

void poppingfever() {
	int a, b, c; cin >> a >> b >> c;
	if (a == b && c == b) cout << "Yes"; else cout << "No";
}

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

signed main() {
	#ifdef fastfurioustransform
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
 
	ios::sync_with_stdio(0); cin.tie(0);
	//cout << fixed << setprecision(12);
 
	poppingfever();
 
	return 0;
}

int modpow(int n, int k, int MOD) {
	int ans = 1; n %= MOD;
	while (k > 0) {
		if (k & 1) ans = (ans*n) % MOD;
		k >>= 1; n = (n*n) % MOD;
	}
	return ans; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+1;
long long a[N];
int main(){
    long long i,j,n,l=0;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j+=i){
            a[j]++;
        }
    }
    for(i=1;i<=n;i++){
        l+=i*a[i];
    }
    printf("%lld\n",l);
    return 0;
}

Measured memory_bytes: 81940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int32_t a,b,c,k;
  cin>>a>>b>>c>>k;
  if(k<=a){cout<<k;}
  else if(k<=a+b){cout<<a;}
  else{cout<<2*a-k+b;}
  return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 100005
#define F first
#define S second
using namespace std;

int n, mxl, mnr=2e9, mlr, ans, mn, l[N], r[N];
pair<int,int> a[N];
int main() {
	int i;
	cin >> n;
	for(i=0; i<n; i++) {
		scanf("%d%d", &l[i], &r[i]);
		r[i]++;
		mxl = max(mxl, l[i]);
		mnr = min(mnr, r[i]);
		mlr = max(mlr, r[i] - l[i]);
	}
	ans = mlr + max(0, mnr - mxl);
	for(i=0; i<n; i++) {
		a[i].F = r[i] - mxl;
		a[i].S = mnr - l[i];
	}
	sort(a, a+n);
	mn = a[0].S;
	for(i=1; i<n; i++) {
		ans = max(ans, mn + a[i].F);
		mn = min(mn, a[i].S);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 1792
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[-float("inf")]*2 for j in range(3)] for i in range(n+1)]
    #dp[index][i//2+j個選んだ][直前の値を採用したか否か]
    dp[0][0][0] = 0
    for i in range(n):
        x = a[i]
        if i%2 == 0:
            for j in range(-1, 2):
                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1])
            for j in range(-1, 1):
                dp[i+1][j+1][1] = dp[i][j][0] + x
        else:
            for j in range(-1, 1):
                dp[i+1][j][0] = max(dp[i][j+1][0], dp[i][j+1][1])
            for j in range(-1, 2):
                dp[i+1][j][1] = dp[i][j][0] + x
    print(max(dp[n][0][0], dp[n][0][1]))

if __name__ == "__main__":
    main()

Measured memory_bytes: 125244
import itertools
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()

if N < M:
    mar = [abs(X[i+1] - X[i]) for i in range(M-1)]
    mar.sort()
    print(sum([mar[i] for i in range(M-N)]))
else:
    print(0)


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

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

using namespace std;
typedef long long int64;

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

  int64 n,a,b,c,d;
  cin>>n>>a>>b>>c>>d;


  int64 period=d+c;
  int64 range=(d-c)*(n-1);
  int64 highest=a+d*(n-1);
  int64 lowest=a-d*(n-1);
  if(!(lowest<=b&&b<=highest)){
    cout<<"NO"<<endl;
    return 0;
  }
  if(range>=period-1){
    cout<<"YES"<<endl;
    return 0;
  }
  int64 mod=(highest-b)%period;
  if(mod<=range){
    cout<<"YES"<<endl;
    return 0;
  }else{
    cout<<"NO"<<endl;
  }




  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        while (true) {
            int a = scan.nextInt();
            String operator = scan.next();
            int b = scan.nextInt();
            int ans = 0;
            if (operator.equals("?")) {
                break;
            }

            switch (operator) {
                case "+":
                    ans = a + b;
                    break;
                case "-":
                    ans = a - b;
                    break;
                case "*":
                    ans = a * b;
                    break;
                case "/":
                    ans = a / b;
                    break;
            }
            System.out.println(ans);
        }
    }
}

Measured memory_bytes: 26240
n = int(input())
tt = []
xx = []
yy = []
for i in range(n):
    t,x,y = map(int,input().split())
    tt.append(t)
    xx.append(x)
    yy.append(y)
ans = "Yes"

for i in range(n):
    if i == 0:
        dist = xx[i] + yy[i]
        time = tt[i]
    else:
        dist = abs(xx[i]-xx[i-1]) + abs(yy[i]-yy[i-1])
        time = tt[i]-tt[i-1]
    if time < dist or (time - dist)%2 != 0:
        ans = "No"
        break

print(ans)

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

int main(){
 int H,W;
  cin >> H >> W;
 vector<string> word(H);
  for(int i;i<H;i++){
    cin >> word.at(i);
  }
  for(int i;i<W+2;i++){
    cout<< '#' ;
  }
  cout << endl;
  for(int i;i<H;i++){
    cout << '#' + word.at(i) + '#'<<endl;
  }
   for(int i;i<W+2;i++){
    cout<< '#' ;
  }
    
}

Measured memory_bytes: 3616