akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string s;
    int n, k;
    cin >> n >> k >> s;
    string t = s;
    reverse(be(t));
    s += t;
    string u = s.substr(0, n);
    for(int i=1;i<=n;i++) u = min(u, s.substr(i, n));
    int x = 1;
    while(x < u.length() && u[0] == u[x]) x++;
    int y = x;
    k--;
    if(k > 17) y = n;
    else y <<= k;
    string ans = "";
    while(ans.length() < n && y > 0) y--, ans += u[0];
    ans += u.substr(x, n - ans.length());
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
import numpy as np
A, B, H, M = map(int, input().split())
a = 30 * (H + M / 60)
b = 360 * (M / 60)
r = abs(a - b)
deg_ = min(r, 360 - r)
ans_ = A ** 2 + B ** 2 - 2 * A * B * np.cos(deg_ * np.pi / 180)
print("{:.021f}".format(np.sqrt(ans_)))

Measured memory_bytes: 27128
#!/usr/bin/env python3
#最終上体がわかれば回数fin*3 - (a+b+c) //2
a =list(map(int,input().split()))
a.sort()
# maxがfinにならないのは、a[0]-1[1]が奇数の時
if (a[1] -a[0])%2 == 0:
    print((a[-1]*3-sum(a))//2)
else:
    print((a[-1]*3+3-sum(a))//2)
"""
x = a[-1]-a[1]
y = a[1] -a[0]
def dist(n):
    if n % 2 == 0: return n//2
    else: return n//2+2
print(min(2*x+y,dist(y)+x,dist(x+y)+dist(x)))"""

Measured memory_bytes: 38384
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int n;
    cin >> n;
    ll h;
    cin >> h;
    ll a[n], b[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    ll maxA = *max_element(a, a + n);
    sort(b, b + n, greater<ll>());
    ll ans = 0;
    for (ll i : b) {
        if (i >= maxA) {
            h -= i;
            ans++;
        } else
            break;
        if (h <= 0) break;
    }
    if (h > 0) {
        if (h % maxA) {
            ans += h / maxA + 1;
        } else {
            ans += h / maxA;
        }
    }
    OUT(ans);
}


Measured memory_bytes: 1792
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def comb(a,b):
        res = 1
        for i in range(b):
            res *= n-i
            res %= mod
            res *= pow(i+1,mod-2,mod)
            res %= mod
        return res
    n,a,b = LI()
    ans = pow(2,n,mod)-1
    ans -= comb(n,a)+comb(n,b)
    ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 39536
using System;
using System.Linq;

namespace AtCodr.ABC123.A
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            Console.ReadLine();
            Console.ReadLine();
            Console.ReadLine();
            var e = int.Parse(Console.ReadLine());
            var k = int.Parse(Console.ReadLine());
            Console.WriteLine(e - a > k ? ":(" : "Yay!");
        }
    }
}


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

#define rep(i, n) REP(i, 0, n)
#define REP(i,k,n) for(int i = k; i < n; i++)
#define mmax(start, end) *max_element(start, end)
#define mmin(start, end) *min_element(start, end)
#define argmax max_element
#define argmin min_element
#define ALL(x) (x).begin(), (x).end()

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

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy8[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

template<class T = ll> T in() {
    T _in;
    cin >> _in;
    return _in;
}

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

    ll N;
    cin >> N;

    ll ans = 1;
    REP(i, 2, 33000) {
      if(N < i*i)
        break;

      ans = i*i;
    }

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


Measured memory_bytes: 256
<?php

while (($line = trim(fgets(STDIN))) !== '0 0 0') {
    sscanf($line, '%d %d %d', $d, $w, $h);
    fscanf(STDIN, '%d', $n);
    $m = sqrt(pow($w, 2) + pow($h, 2)) / 2;
    for ($i = 0; $i < $n; $i++) {
        fscanf(STDIN, '%d', $r);
        echo $r > $m ? "OK\n" : "NA\n";
    }
}

Measured memory_bytes: 6564
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_solve
{
    class Program
    {
        public const ulong mod = 1000000007;

        static void Main(string[] args)

        {
            var lr = Input3();
            long L = lr[0];
            long R = Math.Min(lr[1],L+4038);
            long ans = 2018;
            for(long i = L; i <=R; i++)
            {
                for(long j = i + 1; j <= R; j++)
                {
                    long x = i * j % 2019;
                    ans = Math.Min(ans, x);
                }
            }
            
            

           
            
            Console.WriteLine(ans);
                
                





        }

       
        static public long Input()
        {
            return long.Parse(Console.ReadLine());
        }

        static public string[] Input2()
        {
            return Console.ReadLine().Split();
        }

        static public long[] Input3()
        {
            string[] data = Console.ReadLine().Split();
            long[] res = new long[data.LongLength];
            for(long i = 0; i < data.LongLength; i++)
            {
                res[i] = long.Parse(data[i]);
            }
            return res;
        }
        public static long Choose(long n, long a)
        {
            long x = 1;
            long y = 1;
            for (long i = 0; i < a; i++)
            {
                x *= n - i;
                y *= i + 1;
            }
            return x / y;
        }

        public static long Gcd(long a, long b)
        {
            long x = Math.Max(a, b);
            long y = Math.Min(a, b);
            if (x % y == 0) return y;
            else return Gcd(y, x % y);
        }

        
       
    }
}


Measured memory_bytes: 11092
a,b,c,x = 4.times.map { gets.to_i }
cnt = 0

(0..a).each do |i|
    (0..b).each do |j|
        (0..c).each do |k|
            if i * 500 + j * 100 + k * 50 == x
                cnt += 1
            end
        end
    end
end
p cnt

Measured memory_bytes: 1916
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// Hello World
func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Scan()
	num, _ := strconv.Atoi(sc.Text())
	fmt.Println(num * num * num)
}



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

def isOK(n,w):
    if 4*n*w-N*w-N*n==0:
        return False
    if N*n*w%(4*n*w-N*w-N*n)==0:
        h=N*n*w//(4*n*w-N*w-N*n)
        if 0<h:
            return h
    return False

for i in range(1,3501):
    for j in range(1,3501):
        if isOK(i,j):
            print(i,j,isOK(i,j))
            exit()


Measured memory_bytes: 69664
import std.stdio : writeln;

void main() {
    int n,a,b;
    scan(n,a,b);

    long ans;

    foreach (i ; 1 .. n + 1) {
        int d = digitSum(i);
        
        if (a <= d && d <= b) {
            ans += i;
        }
    }

    writeln(ans);
}

int digitSum(int x) {
    return x > 0 ? digitSum(x / 10) + x % 10 : 0;
}




void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.array : split;
    import std.conv  : to;
    import std.range.primitives;

    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) {
    cin >> a.at(i);
  }
  map<int, int> a_map;
  rep(i, n) {
    if (a_map.count(a.at(i))) {
      a_map.at(a.at(i))++;
    }
    else {
      a_map[a.at(i)] = 1;
    }
  }
  int sum = 0;
  if (a_map.size() <= k) {
    cout << 0 << endl;
  }
  else {
    vector<int> num(a_map.size());
    int counta = 0;
    rep(i, n + 1) {
      if (a_map.count(i)) {
        num.at(counta) = a_map.at(i);
        counta++;
      }
    }
    sort(num.begin(), num.end());
    for (int i = 0; i < num.size() - k; i++) {
      sum += num.at(i);
    }
    cout << sum << endl;
  }
}


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

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

	long long int sum = 0;
	vector<int> T(N);

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

	int M;
	cin >> M;
	vector<int> ans(M);

	for (int i = 0; i < M; ++i){
		int P, X;
		cin >> P >> X;
		ans[i] = sum + X - T[P - 1];
	}

	for (int i = 0; i < M; ++i){
		cout << ans[i] << endl;
	}
	return 0;
}

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

int main() {
  int p,q,r,min;
  int pq,pr,qr;

  cin >> p >> q >> r;

  pq=p+q;
  pr=p+r;
  qr=q+r;

  if (pq <= pr) {
    min = pq;
  } else {
    min = pr;
  }
  if (qr <= min) {
    min = qr;
  }

  printf("%d", min);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <functional>
#include <iostream>
#define ALL(v) v.begin(), v.end()
#define MAX 510000
#define rrep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define dcout cout<<fixed<<setprecision(15);

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

constexpr int MOD = 1e9 + 7;
constexpr ll inf = 1LL << 60;

//lcm//
ll gcd(ll x, ll y) {
	if (x == 0) return y;
	return gcd(y%x, x);
}
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

//a^n mod p//
ll modpow(ll a, ll n, ll p) {
  if (n == 1) return a % p;
  if (n % 2 == 1) return (a * modpow(a, n - 1, p)) % p;
  ll t = modpow(a, n / 2, p);
  return (t * t) % p;
}

//inversemod//
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//Cmonp//
ll fac[MAX], finv[MAX], inv[MAX];
// 
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 
ll COM(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

//LARGE n
ll com(ll n,ll m){
    if(n<m || n<=0 ||m<0){
		return 0;
	}
	if( m==0 || n==m){
		return 1;
	}
	ll k=1;
	for(ll i=1;i<=m;i++){
       k*=(n-i+1); 
	   k%=MOD;
	   k*=modinv(i,MOD);
	   k%=MOD;
	}
	return k;
}

//radP
ll rad(ll u, ll p){
ll cnt=0;
	while(u%p==0){
		u/=p;
		cnt++;
	}
	return cnt;
}


////////////////////////////////////////////////////////////////////

int main(){
ll a,b,c,k;
cin>>a>>b>>c>>k;
ll val;
if(a>=k)val=k;
if(a<k &&a+b>=k)val=a;
if(a+b<k)val=a-(k-a-b);

cout<<val<<endl;
return 0;


}





Measured memory_bytes: 3624
#include<stdio.h>

#define MAX_NUM 200001

int main(void){

    int N,P[MAX_NUM],i,lowest,ans = 0;

    scanf("%d",&N);
    for(i = 0;i < N;i++){
        scanf("%d",&P[i]);
    }

    lowest = P[0];
    for(i = 0;i < N;i++){
        if(P[i] <= lowest){
            ans++;
            lowest = P[i];
        }
    }

    printf("%d\n",ans);
    return 0;
}

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

#define ll long long
#define F first
#define S second
#define ii pair < int , int >
#define ever (;;)

int x;

int main()
{
    cin>>x;

    if( x >= 400 && x <= 599 )
    {
        cout<<8<<endl;
        return 0;
    }
    if( x >= 600 && x <= 799 )
    {
        cout<<7<<endl;
        return 0;
    }
    if( x >= 800 && x <= 999 )
    {
        cout<<6<<endl;
        return 0;
    }
    if( x >= 1000 && x <= 1199 )
    {
        cout<<5<<endl;
        return 0;
    }
    if( x >= 1200 && x <= 1399 )
    {
        cout<<4<<endl;
        return 0;
    }
    if( x >= 1400 && x <= 1599 )
    {
        cout<<3<<endl;
        return 0;
    }
    if( x >= 1600 && x <= 1799 )
    {
        cout<<2<<endl;
        return 0;
    }
    if( x >= 1800 && x <= 1999 )
    {
        cout<<1<<endl;
        return 0;
    }
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (;;) {
        int n, m; cin >> n >> m;
        if (n == 0) break;
        vi t(m), s(m), d(m);
        REP(i, m) {
            cin >> t[i] >> s[i] >> d[i];
            --s[i], --d[i];
        }
        vi ord(m); iota(ALL(ord),0);
        sort(ALL(ord), [&](int i,int j){return t[i] < t[j];});

        vi infected(n);
        infected[0] = 1;
        for (int id : ord) {
            infected[d[id]] |= infected[s[id]];
        }

        cout << accumulate(ALL(infected), 0) << endl;
    }

    return 0;
}



Measured memory_bytes: 3288
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	char ch;
	while (scanf("%c", &ch) != EOF) {
		if (ch >= 'a' && ch <= 'z') {
			printf("%c\n", 'a');
		} else if (ch >= 'A' && ch <= 'Z') {
			printf("%c\n", 'A');
		} else {
		}
	}
	return (0);
}


Measured memory_bytes: 1664
#include<cstdio>
#include<algorithm>
using namespace std;
int n, D[101000], w[110], K;
int main() {
	int i, j, k;
	scanf("%d%d", &n,&K);
	for (i = 1; i <= n; i++)scanf("%d", &w[i]);
	for (i = 1; i <= K; i++) {
		for (j = 1; j <= n; j++) {
			if (i >= w[j] && !D[i - w[j]]) {
				D[i] = 1;
				break;
			}
		}
	}
	if (D[K])puts("First");
	else puts("Second");
}

Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
#include <numeric>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
//#define MOD 998244353
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=350;
//↑templete
int main(){
	int N, K;
	cin>>N>>K;
	vll H;
	for(int i=0;i<N;i++){
		int h;
		cin>>h;
		H.pb(h);
	}
	static ll DP[SIZE][SIZE][SIZE]={};
	for(int i=1;i<SIZE;i++){
		for(int j=0;j<SIZE;j++){
			for(int k=0;k<SIZE;k++){
				DP[i][j][k]=INFLL;
			}
		}
	}
	if(N==K){
		cout<<0<<endl;
		return 0;
	}

	DP[0][0][0]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<=K;j++){
			for(int k=-1;k<i;k++){
				if(k==-1){
					if(j!=i)
						continue;

					DP[i+1][j][i]=min(DP[i+1][j][i], H[i]);
				}
				else{
					if(H[i]<=H[k]){
						DP[i+1][j][i]=min(DP[i+1][j][i], DP[i][j][k]);
						DP[i+1][j+1][k]=min(DP[i+1][j+1][k], DP[i][j][k]);
					}
					else{
						DP[i+1][j][i]=min(DP[i+1][j][i], DP[i][j][k]+(H[i]-H[k]));
						DP[i+1][j+1][k]=min(DP[i+1][j+1][k], DP[i][j][k]);
					}
				}
			}
		}
	}

	ll ans=INFLL;
	for(int j=0;j<=K;j++)
		for(int k=0;k<=N;k++)
			ans=min(ans, DP[N][j][k]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 334336
n,m = map(int,input().split())
aa = list(map(int, input().split()))
aa.sort()
bc_list = [list(map(int, input().split())) for i in range(m)]
bc_list = sorted(bc_list, key=lambda x:x[1])

p = 0
for bc in bc_list[::-1]:
    for i in range(bc[0]):
        if aa[p] < bc[1]:
            aa[p] = bc[1]
            p += 1
            if p > len(aa) - 1:
                break
        else:
            break
    else:
        continue
    break

print(sum(aa))

Measured memory_bytes: 33736
using System;
using System.Collections.Generic;
using System.Linq;

class MainClass
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        var P = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int ans = 0;
        int min = int.MaxValue;
        for (int i = 0; i < N; i++)
        {
            if (P[i] <= min)
            {
                ans++;
                min = P[i];
            }

        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 43064
n = int(input())

stone_list = [ int(input()) for i in range(2**n) ]


for k in range(n,0,-1):
    next_stone_list = []
    for i in range(2**(k-1)):
        if stone_list[2*i] == stone_list[2*i+1]:
            next_stone_list.append(stone_list[2*i])
        else:
            next_stone_list.append(abs(stone_list[2*i] - stone_list[2*i+1]))
    stone_list = next_stone_list
print(*next_stone_list)


Measured memory_bytes: 71644
#include <iostream>

using namespace std;

int nrd[10000005] , n;

long long ans;

int main() 
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        nrd[i] = 1;
    for(int i = 2 ; i <= n ; i++)
          {
              ++nrd[i];
              for(int j = 2 * i ; j <= n ; j += i)
                    ++nrd[j];
          }
    for(int i = 1 ; i <= n ; i++)
        ans += 1LL * i * nrd[i];
    cout << ans << "\n";
    return 0;
}

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

using namespace std;

#define FOR(i, j, k) for(int i = j; i <= k; i++)
#define ROF(i, j, k) for(int i = j; i >= k; i--)
#define PB push_back
#define MEM(n, val) memset((n), val, sizeof(n))
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F first
#define S second
#define MP make_pair
#define LL long long
#define MOD 998244353
#define MX 200010
#define INFL 1000000000000000000LL
#define INF 1000000000

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;

int n;

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);tt
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    FastIO;
    cin >> n;
    int go;
    for(go = 1000; go < n; go += 1000) {
    }
    cout << go - n << "\n";

    return 0;
}
/**
*/


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
#include <algorithm>
using namespace std;

void numpush(int A[], int N){
  char lett[N] ;
  for(int j=0;j<N;j++){
    lett[j] = 96 + A[j]  ;
    cout << lett[j] ;
  }
  cout << endl ;
  return ;
}

int nextlet(int A[], int N){
  int checker ;
  for(int i=N-1;i>0;i--){
    checker = 0 ;
    for(int j=i-1;j>=0;j--){
      if(A[j] >= A[i]) checker = 1 ; 
    }
    if(checker){
      A[i]++ ;
      for(int j=i+1;j<N;j++){
        A[j] = 1 ;
      }
      return 1 ;
    }
  }
  return 0 ;
}

int main(){
  int N, box = 2, numbox, count = 0, ans = 1, check;
  cin >> N ;
  int A[N] ;
  for(int i=0;i<N;i++){
    A[i] = 1 ;
  }
  numpush(A,N) ;
  while(nextlet(A,N)){
    numpush(A,N) ;
  }
  return 0 ;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
	int n;
	cin >> n;
	vi a(n);
	rep(i, n) {
		cin >> a[i];
		a[i]--;
	}
	int cnt = 0;
	rep(i, n-1) {
		if(a[i] == i) {
			swap(a[i], a[i+1]);
			cnt++;
		}
	}
	if(a.back() == n-1) cnt++;
	cout << cnt << endl;
	return 0;
}

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

const int MOD = 1000000007;
const int INF = 1e9;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n, i##_len=(n); i>=0; i--)
#define FOR(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)

//最大公約数 
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

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

int main(){
int N;
cin >> N;
vector<string>s(N);
REP(i, N) {
  cin >> s.at(i);
  sort(all(s.at(i)));
}
sort(all(s));
ll ans = 0;
ll tmp = 0;
ll tmp2 = 0;
for(int i = 0; i < N - 1; i++){ 
   if(s.at(i) == s.at(i + 1)){
     tmp += 1;
     tmp2 += tmp; 
   }else{
     ans += tmp2;
     tmp2 = 0;
     tmp = 0;
   } 

if(i == N - 2) ans += tmp2;
}
print(ans);
}


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

using namespace std;
const int N=112345;

char s[N];

int main()
{
    scanf("%s",s);
    int len=strlen(s);
    set<char>S;
    for(int i=0;i<=len-1;i++)
        S.insert(s[i]);
    if(S.size()>2)
    {
        if(s[0]==s[len-1])
        {
            if ((len - 3) % 2 == 0)printf("Second\n");
            else printf("First\n");
        }
        else {
            if ((len - 2) % 2 == 0)printf("Second\n");
            else printf("First\n");
        }
    }
    else if(S.size()==2)
    {
        printf("Second\n");
    }
    else if(S.size()==1)
    {
        printf("Second\n");
    }
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdint>
#include <vector>
 
using namespace std;
typedef long long ll;


ll ans,mx,mn,sum;
int main(){
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	sort(a,a+n);
	for(int i=0; i<n; i++){
		if(a[i]!=a[i+1]){
			sum++;
			if(sum%2!=0) ans++;
			sum=0;
		}
		else sum++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9+7;

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




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



int n;
cin>>n;
vector<double>v(n+1,0.0);
cout<<setprecision(15)<<fixed;
for(int i=1;i<=n;i++)cin>>v[i];

vector<vector<double>>dp(n+5,vector<double>(n+5,0.0));

dp[0][0]=1;

for(int i=1;i<=n;i++)
{
  for(int j=0;j<=i;j++)
  {
   
     if(j-1>=0)
     {
       dp[i][j]+=(v[i])*dp[i-1][j-1]; 
     }
     if(i-1>=j)
     dp[i][j]+=(1.0-v[i])*dp[i-1][j];
    //  cout<<dp[i][j]<<" ";
  }
  // cout<<"\n";
}

double ans=0.0;


for(int i=n/2+1;i<=n;i++)
{
  ans+=dp[n][i];

}
cout<<ans<<"\n";



}

Measured memory_bytes: 70912
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
  private void solve(Scanner in, PrintWriter out) {
    int N = in.nextInt();
    int[] primes = getPrimes(N + 1);

    TreeMap<Integer, Integer> count = new TreeMap<>();
    for (int n = 1; n <= N; n++) {
      int x = n;
      for (int prime : primes) {
        while (x % prime == 0) {
          Integer c = count.get(prime);
          if (c == null)
            count.put(prime, 1);
          else
            count.put(prime, c + 1);
          x /= prime;
        }
        if (x == 1) break;
      }
    }

    int MOD = (int) (1e9 + 7);
    long ans = 1;
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      ans *= (entry.getValue() + 1);
      ans %= MOD;
    }
    out.println(ans);
  }

  public static int[] getPrimes(int N) {
    ArrayList<Integer> primes = new ArrayList<>();
    boolean[] isComposite = new boolean[N + 1];
    primes.add(2);
    for (int i = 3; i <= N; i += 2)
      if (!isComposite[i]) {
        primes.add(i);
        for (int j = i * 2; j <= N; j += i) {
          isComposite[j] = true;
        }
      }
    int[] array = new int[primes.size()];
    for (int i = 0; i < primes.size(); i++) {
      array[i] = primes.get(i);
    }
    return array;
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);
    new Main().solve(in, out);
    in.close();
    out.close();
  }
}


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

int main(){
    int N, K, C;
    cin >> N >> K >> C;
    string S;
    cin >> S;

    vector<int> L1, L2;
    int stock = 1e9;
    for(int i=0; i<N; i++){
        if(S[i] == 'o' && stock >= C){
            L1.push_back(i);
            stock = 0;
        }else{
            stock++;
        }
        if(L1.size() == K) break;
    }
    stock = 1e9;
    for(int i=N-1; i>=0; i--){
        if(S[i] == 'o' && stock >= C){
            L2.push_back(i);
            stock = 0;
        }else{
            stock++;
        }
        if(L2.size() == K) break;
    }

    reverse(L2.begin(), L2.end());
    for(int i=0; i<K; i++) if(L1[i] == L2[i]) cout << L1[i]+1 << endl;
    return 0;
}


Measured memory_bytes: 3448
from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
L = []
for i in range(n):
    a, b = map(int, input().split())
    L.append([a, b])
L.sort()

tot = 0
i = 0
while True:
    if m == 0:
        break
    a, b = L[i]
    if m <= b:
        tot += a*m
        m = 0
    else:
        m -= b
        tot += a*b
    i += 1

print(tot)

Measured memory_bytes: 20072
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
length = len(A)
R_down = [0]*length
L_down = [0]*length

for i in range(n):
    count = 0
    for j in range(i, n):
        if A[i] > A[j]:
            count += 1

    R_down[i] = count

for i in range(n):
    count = 0
    for j in range(i, -1, -1):
        if A[i] > A[j]:
            count += 1

    L_down[i] = count

R = sum(R_down)*k*(k+1)//2
L = sum(L_down)*(k-1)*k//2
ans = (R + L) % mod
print(int(ans))


Measured memory_bytes: 3188
S = input()
T = input()

len_s = len(S)
len_t = len(T)

match = -1

for i in range((len_s - len_t), -1, -1):
    for j in range(len_t):
        if T[j] != S[i+j] and S[i+j] != "?":
            break

        if j == len_t-1:
            match = i

    if match != -1:
        break

if match == -1:
    print("UNRESTORABLE")
    exit()

list_s = list(S)

for i in range(match, match+len_t):
    list_s[i] = T[i - match]

list_s = [x if x != "?" else "a" for x in list_s]

print("".join(list_s))


Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <set>
#include <numeric>
using namespace std;
typedef long long ll;

int main(){
int n;cin>>n;
ll x;cin>>x;
vector<int> v(n);
for(ll i=0;i<n;i++)cin>>v[i];
ll yay=accumulate(v.begin(),v.end(),0LL);
int m=*min_element(v.begin(),v.end());
cout<<n+(x-yay)/m;
}

Measured memory_bytes: 256
from collections import defaultdict
N, M = map(int,input().rstrip().split())
d = defaultdict(lambda: 0)
for _ in range(N):
    A, B = map(int,input().rstrip().split())
    d[A] += B
ans=0
for k in sorted(d.keys()):
    if d[k]<=M:
        ans += k*d[k]
    else:
        ans += k*M
    M -= d[k]
    if M<=0:break
print(ans)

Measured memory_bytes: 22276
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;ll W;cin>>n>>W;
    vll v(n),w(n);rep(i,n)cin>>v[i]>>w[i];
    if(n==1){
        if(w[0]<=W)cout<<v[0]<<endl;
        else cout<<0<<endl;
        return 0;
    }
    int k=n/2;
    vector<pair<ll,ll>> a,b,c;
    ll sumw,sumv;
    rep(i,(1<<k)){
        bitset<25> tmp(i);
        sumw=(ll)0;sumv=(ll)0;
        rep(j,k){
            if(tmp[j]){
                sumw+=w[j];
                sumv+=v[j];
            }
        }
        a.push_back(mp(sumw,sumv));
    }
    rep(i,(1<<n-k)){
        bitset<25> tmp(i);
        sumw=(ll)0;sumv=(ll)0;
        rep2(j,k,n){
            if(tmp[j-k]){
                sumw+=w[j];
                sumv+=v[j];
            }
        }
        c.push_back(mp(sumw,sumv));
    }
    sort(all(a));sort(all(c));
    ll tmp=(ll)0;
    rep(i,c.size()){
        if(i<c.size()-1&&c[i].first==c[i+1].first)continue;
        else if(c[i].second>tmp){
            b.push_back(c[i]);
            tmp=c[i].second;
        }
    }
    int l,r,m;ll ans=0;
    rep(i,a.size()){
        l=-1;r=b.size();
        while(r-l>1){
            m=(l+r)/2;
            if(a[i].first+b[m].first>W)r=m;
            else l=m;
        }
        if(l==-1)break;
        ans=max(ans,a[i].second+b[l].second);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 43708
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define VS vector<string>
#define ll long long int
int main(void) {
    int a;
    bool p[10];
    int w[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
    while(cin >> a) {
        REP(i,10) p[i] = false;
        for(int i=9;i>=0;i--) {
            if(a-w[i] >= 0) {
                p[i] = true;
                a = a-w[i];
            } else {
                p[i] = false;
            }
        }
        int k;
        REP(i,10) {
            if(p[i]) k = i;
        }
        REP(i,10) {
            if(p[i]) {                                                                               
                cout << w[i];
                if(i != k) cout << " ";
            }

            if(i == k) cout << endl;
        }
    }
}

Measured memory_bytes: 3012
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<numeric>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)
#define INF 1000000000
#define MOD 1000000007
typedef  long long ll;
using namespace std;

ll conv(ll n,ll r){
    if(r == 0 || n==r){
        return 1;
    }
    return conv(n-1,r)+conv(n-1,r-1);
}

int a[15][29];

void solve(void){
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a,b) << endl;

}


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



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    long long a, b;
    cin >> a >> b;
    
    if(a <= 0 && b >= 0) {
        cout << "Zero" << endl;
    }
    else {
        if(a <= 0) {
            if(b <= 0) {
                int tmp = (b - a) % 2;
                if(tmp == 0) {
                    cout << "Negative" << endl;
                }
                else {
                    cout << "Positive" << endl;
                }
            }
            else {
                int tmp = a % 2;
                if(tmp == 0) {
                    cout << "Positive" << endl;
                }
                else {
                    cout << "Negative" << endl;
                }
            }
        }
        else {
            cout << "Positive" << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

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

Measured memory_bytes: 256
public class Main {


  private static void solve() {
    int R = ni();
    int G = ni();
    int B = ni();
    
    int n = ni();
    
    int ret = 0;
    for (int r = 0; r * R <= n; r ++) {
      for (int g = 0; r * R + g * G <= n; g ++) {
        int last = n - (r * R + g * G);
        
        if (last % B == 0) {
          ret ++;
        }
      }
    }
    System.out.println(ret);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


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

#define watch(x) cout << (#x) << " = " << x << endl;
#define mkp make_pair
#define mkt make_tuple
#define pb push_back
#define ll long long
#define ld long double

using namespace std;

int n, dp[100010][3], h[100010][3];

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

	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			scanf("%d", &h[i][j]);
		}
	}

	dp[1][0] = h[1][0];
	dp[1][1] = h[1][1];
	dp[1][2] = h[1][2];

	for(int i = 2; i <= n; i++){
		for(int j = 0; j < 3; j++){
			dp[i][j] = h[i][j];
			for(int k = 0; k < 3; k++){
				if(j == k) continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + h[i][j]);
			}
		}
	}

	printf("%d\n", max(dp[n][0], max(dp[n][1], dp[n][2])));

	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)n; i++)
int main()
{
  int n;
  cin >> n;
  vector<int > a(n), b(n), c(n);
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];
  REP(i, n - 1) cin >> c[i];
  int ans = 0;
  ans = b[a[0] - 1];
  int ind_b = a[0] - 1;
  // cout << ans << endl;
  for(int i = 1; i < n; i ++){
    ans += b[a[i] - 1];
    if(a[i - 1] == a[i] - 1){
      ans += c[a[i - 1] - 1];
    }
    // cout << ans << endl;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, a[500][500];

int main() {
	cin >> N;
	for (int i = 1; i <= 11; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int k = j + 1; k < N; ++k) {
				if (a[j][k] == 0 && (j&(1 << i - 1)) != (k&(1 << i - 1))) {
					a[j][k] = i;
				}
			}
		}
	}
	for (int i = 0; i < N; ++i) {
		for (int j = i + 1; j < N; ++j) {
			cout << a[i][j];
			if (j != N - 1)cout << sp;
		}
		cout << endl;
	}
}

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

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

signed main() {
	ll n, result = INF;
  ll p[5005], q[5005];
  cin >> n;
  rep(i, n) cin >> p[i];
  rep(i, p[0] + 1) {
    rep(j, n) q[j] = p[j];
    q[0] -= i;
    ll sum = i;
    rep(j, n - 1) {
      if(q[j] > 0) {
        q[j + 1] -= q[j];
        sum += q[j] * 2;
        q[j] = 0;
      }
    }
    if(q[n - 1] > 0) sum += q[n - 1];
    result = min(result, sum);
  }
  cout << result << endl;
	return 0;
}


Measured memory_bytes: 3220
#include<iostream>
using namespace std;
int bubbleSort(int* A, int N){ 
    int flag,v,j,k=0;
    flag = 1;
    while(flag==1){
        flag = 0;
        for(j=N-1;j>0;j--){
           if(A[j] < A[j-1]){
               v=A[j];
               A[j]=A[j-1];
               A[j-1]=v;
               flag = 1;
               k+=1; 
            }
        }
        
    }
    return k;
}
int main(){
    int N,i,k;
    int A[1000];
    cin>>N;
    for(i=0;i<N;i++){
        cin>>A[i];
    }
    k=bubbleSort(A,N);
    for(i=0;i<N-1;i++){
        cout<<A[i]<<" ";
    }
    cout<<A[N-1]<<endl;
    cout<<k<<endl;
    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int a[maxn];
int main(int argc, char const *argv[])
{
	int n;
	cin>>n;
	if(n==1||n==0)
	{
		cout<<n<<endl;
		return 0;
	}
	int k=0;
	while(n)
	{
		int m=n;
		a[k++]=abs(n)%2;
		n/=-2;
		if(m<0&&abs(m)%2)
			n++;
	}	
	for(int i=k-1;i>=0;i--)
		cout<<a[i];
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define ll long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repeat(i,s,n) for(int (i)=s; (i)<(n); (i)++)
#define revrep(i,n) for(int (i)=(n)-1;i>=0; i--)

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(std::numeric_limits<float>::max_digits10);
  cout<<fixed;
  int h,w,n;
  cin>>h>>w>>n;
  int x = max(h,w);
  cout << (n+x-1)/x << endl;
  return 0;
}


Measured memory_bytes: 256
//  zukonit14 - Kunal Raut

#include<bits/stdc++.h>
using namespace std;
#define ll                  long long
#define int                 long long
#define ld                  long double
#define pb                  push_back
#define mp                  make_pair
#define fi                  first
#define se                  second
#define mod                 1000000007
#define pi                  3.1415926535
#define MAXN                2*100000+10
#define MAX2N               1*1000+10
const   ll INF              = 1e18;
#define all(v)              v.begin(), v.end()
#define allr(v)             v.rbegin(), v.rend()
#define ms(s, n)            memset(s, n, sizeof(s))
#define prec(n)             fixed<<setprecision(n)
#define forci(p,n)          for(ll i=p;i<(ll)n;i++)
#define forcj(p,n)          for(ll j=p;j<(ll)n;j++)
#define bolt                ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a)             __builtin_popcountll(a)
#define djokovic            freopen("input00.txt", "r", stdin);freopen("output00.txt", "w", stdout);
clock_t time_p              = clock();
void rtime()                {time_p = clock() - time_p; cout << "\nTime Taken : " << fixed << (float)(time_p) / CLOCKS_PER_SEC << "s\n";}
ll gcd(ll a, ll b)          {if (b == 0) return a;    return gcd(b, a % b);}
ll lcm(ll a, ll b)          {return (a / gcd(a, b) * b);}
ll expo(ll x, ll y)         {ll res = 1; x = x % mod; while (y > 0) {if (y & 1)res = (1ll * res * x) % mod; y = y >> 1; x = (1ll * x * x) % mod;} return res % mod;}
ll inv_mod(ll q, ll m = mod)   {return (expo(q, m - 2) % m);}
ll ncr(ll n, ll r)          {ll res = 1; if (r > n - r)r = n - r; for (ll i = 0; i < r; i++) {  res *= n - i;  res /= i + 1; } return res;}
ll max(ll a, ll b)          {return (a > b) ? a : b;}
bool prime(ll n)            {ll i; for (i = 2; i <= sqrt(n); i++) {if (n % i == 0)return false;} return true;}
//https://www.youtube.com/watch?v=WTJSt4wP2ME

ll rr[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll cc[] = {1, 1, 0, -1, -1, -1, 0, 1};
ll n, m, k, x, q, w[MAXN], v[MAXN], c[MAXN], best;
ll dp[100005];
void solve()
{
    ll n, ww; cin >> n >> ww;
    for (ll i = 1; i <= n; i++)
    {
        ll v, w; cin >> w >> v;
        for (ll j = ww; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    //for (ll i = 1; i <= ww; i++)   cout << dp[i] << " ";
    //cout << "\n";
    cout << dp[ww];
}
signed main()
{
    bolt;
#ifndef ONLINE_JUDGE
    djokovic;
#endif
    ll t;
    t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    //rtime();
}




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

    vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
    int ans = 0;
    for(int i=n-1; i > -1; i--){
        for(int j=n-1; j > -1; j--){
            if(s.at(i) == s.at(j)){
                dp[i][j] = dp[i + 1][j + 1] + 1;
            }else{
                dp[i][j] = 0;
            }
            if(i < j){
                int now = min(j-i, dp[i][j]);
                ans = max(ans, now);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 100224
function Main(arg) {
 
    var A = arg.split(" ")[0]-0;
    var B = arg.split(" ")[1]-0;
 
    var ans = 0;

    if (A - 2 * B > 0) {
        console.log(A - 2 * B);
    }
    else {
        console.log(0);
    }


    return;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21956
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node {
  int p;
  int l;
  int r;
};

struct Node T[MAX];
int n;

void preParse(int u){
  if(u == NIL) return;
  printf(" %d", u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u){
  if(u == NIL)return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);
}

void postParse(int u){
  if(u == NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d", u);
}
int main(){
  int i;
  int v,l,r, root;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    T[i].p = NIL;
  }

  for(i=0; i<n; i++){
    scanf("%d %d %d", &v, &l, &r);
    T[v].l = l;
    T[v].r = r;
    if(l != NIL) T[l].p = v;
    if(r != NIL) T[r].p = v;
  }

  for(i=0; i<n; i++){
    if(T[i].p == NIL) root = i;
  }
  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");
  
  return 0;
}
  



Measured memory_bytes: 2056
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <utility>
using namespace std;

int main()
{
    double w, h, x, y, xk, yk, ansx, ansy, ans;
    cin >> w >> h >> x >> y;

    cout << double(w) * double(h) / 2 << " ";

    if(w == x + x && h == y + y){
        cout << 1;
    }
    else{
        cout << 0;
    }
    
    return 0;
}

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

int main( )
{
    string s, t1, t2;
    int l;
    cin >> l;
    cin >> s;
    t1 = s.substr(0, l / 2);
    t2 = s.substr(l / 2, l - (l / 2));
    if (t1 == t2)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#define int long long
using namespace std;
signed main() {
	int n, k, x[114514]; cin >> n >> k;
	for (int i = 0; i < n; i++)cin >> x[i];
	int ans = (abs(x[0]) + abs(x[n - 1])) * 2 + 1;
	for (int i = 0; i < n - k + 1; i++) {
		int p = i + k - 1;
		if (x[i] * x[p] > 0)ans = min(ans, max(abs(x[i]), abs(x[p])));
		else ans = min(ans, min(abs(x[i]) * 2 + x[p], abs(x[i]) + x[p] * 2));
	}
	cout << ans << endl;
}

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

int main() {
    int a, b, c; cin >> a >> b >> c;
    rep(i, 1, 101) {
        if (a * i % b == c) {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

N=int(input())+2
C="R"+input().strip()+"W"

W=[0]*(N+1)
R=[0]*(N+1)

for i in range(N):
    if C[i]=="W":
        W[i]=W[i-1]+1
    else:
        W[i]=W[i-1]

for i in range(N-1,-1,-1):
    if C[i]=="R":
        R[i]=R[i+1]+1
    else:
        R[i]=R[i+1]

ANS=1<<30
for i in range(N-1):
    ANS=min(ANS,max(W[i],R[i+1]))

print(ANS)



Measured memory_bytes: 18624