akhauriyash/Code-Regression huggingface dataset:
#include <functional>
#include <sstream>
#include <math.h>
#include <vector>
#include <iostream>
#include <limits>

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=jp

using namespace std;

void parseInputs(istream &ist, int &outNumPacks, int &outNumTrucks, int &outSumWeights, vector<int> &outWeights);
int calculateEnoughBigSize(int numTrucks, int sum, const vector<int> &weights);
bool isGoodSize(int size, int numTrucks, const vector<int> &weights);
int doBinaryStep(int &inOutLow, int &inOutHigh, const function<bool(int)> &condition);

int main()
{
    int numPacks;
    int numTrucks;
    vector<int> weights;
    int sum;
    parseInputs(cin, numPacks, numTrucks, sum, weights);
    /*
    numPacks = 4;
    numTrucks = 2;
    weights = {1, 2, 2, 6};
    sum = 11;

    numPacks = 5;
    numTrucks = 3;
    weights = {8, 1, 7, 3, 9};
    sum = 8 + 1 + 7 + 3 + 9;
    */
    int tooSmall = sum / numTrucks - 1; // 載積量の下限 // falseの方にすること
    int enoughBig = calculateEnoughBigSize(numTrucks, sum, weights);
    function<bool(int)> condition = [numTrucks, &weights](int size) -> bool {
        return isGoodSize(size, numTrucks, weights);
    };
    while (doBinaryStep(tooSmall, enoughBig, condition) == numeric_limits<int>::lowest())
    {
    }
    cout << enoughBig << endl;
    return 0;
}

void parseInputs(istream &ist, int &outNumPacks, int &outNumTrucks,
                 int &outSumWeights, vector<int> &outWeights)
{
    ist >> outNumPacks >> outNumTrucks;
    outSumWeights = 0;
    for (int i = 0; i < outNumPacks; i++)
    {
        int w;
        ist >> w;
        outWeights.push_back(w);
        outSumWeights += w;
    }
}

int calculateEnoughBigSize(int numTrucks, int sum, const vector<int> &weights)
{
    float average = sum / numTrucks;
    int p = numeric_limits<int>::lowest();
    int tempP = 0;
    for (int w : weights)
    {
        tempP += w;
        if (tempP >= average)
        {
            p = max(p, tempP);
            tempP = 0;
        }
    }
    return max(p, tempP);
}

bool isGoodSize(int size, int numTrucks, const vector<int> &weights)
{
    int numLeftTrucks = numTrucks;
    int buffer = 0;
    for (int w : weights)
    {
        if (buffer + w > size)
        {
            numLeftTrucks--;
            if (numLeftTrucks <= 0)
            {
                return false;
            }
            if (size < w)
            {
                return false;
            }
            buffer = w;
        }
        else
        {
            buffer += w;
        }
    }
    return true;
}

// @returm 結果が得られたら結果(condition=trueとなる最小の値)、そうではないときはINT_NIN
int doBinaryStep(int &inOutLow, int &inOutHigh, const function<bool(int)> &condition)
{
    if (inOutHigh - inOutLow <= 1)
    {
        return inOutHigh;
    }
    int test = test = (inOutLow + inOutHigh) / 2;
    if (condition(test))
    {
        inOutHigh = test;
    }
    else
    {
        inOutLow = test;
    }
    return numeric_limits<int>::lowest();
}


Measured memory_bytes: 3564
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X, N = LI()
p = LI()

ans = mod
for i in range(100):
    if X - i not in p:
        ans = X - i
        break
    if X + i not in p:
        ans = X + i
        break

print(ans)
    

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

using namespace std;
using ll = long long int;
#define long ll

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

    ll h, w, n;
    cin >> h >> w >> n;

    vector<pair<ll,ll>> v(n);
    for(ll i=0; i<n; i++) {
        ll x, y;
        cin >> x >> y;
        x--, y--;
        v[i] = make_pair(x, y);
    }
    sort(v.begin(), v.end());

    ll r = h;
    {
        ll t = 0;
        for(ll i=0; i<n; i++) {
            ll x, y;
            tie(x, y) = v[i];
            if(x - y == t) t++;
            else if(x - y > t) {
                r = min(r, x);
            }
        }
    }

    cout << r << endl;

}


Measured memory_bytes: 3456
from collections import Counter

N = int(input())
a = [int(i) for i in input().split()]

def solve() :
    cnt = list(Counter(a).items())
    cnt.sort()
    
    if cnt[0][1] == 1 and cnt[-1][0] != 2 * cnt[0][0] :
        return 'Impossible'
    if cnt[0][1] == 2 and cnt[-1][0] != 2 * cnt[0][0] - 1 :
        return 'Impossible'
    if cnt[0][1] > 2 :
        return 'Impossible'

    for i in range(1, len(cnt)) :
        if cnt[i][0] != cnt[i-1][0] + 1 :
            return 'Impossible'
        if cnt[i][1] < 2 :
            return 'Impossible'
            
    return 'Possible'
    
print(solve())

Measured memory_bytes: 38384
#include <cstdio>
#include <iostream>

using namespace std;

int main() {

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

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

	int V[n];
	V[0] = A[0];
	int length = 1;
	for (int i = 1; i < n; ++i) {
		if (A[i] > V[length - 1]) {
			V[length++] = A[i];
		} else {
			int l = 0;
			int r = length;
			while (l < r) {
				int mid = (l + r) / 2;
				if (A[i] <= V[mid]) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			V[r] = A[i];
		}
	}
	cout << length << endl;

	return 0;
}

Measured memory_bytes: 3936
n, k = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(2 * k)]

d = []
a = []

for i in range(2 * k):
    if i % 2 == 0:
        d.append(ls[i])
    elif i % 2 == 1:
        a.append(ls[i])


cnt = [0] * n

for j in range(k):
    for ajd in a[j]:
        cnt[ajd - 1] += 1

print(cnt.count(0))

Measured memory_bytes: 9136
#include <iostream>
using namespace std;
char get(char t){
	string a = "iw()";
	string b = "iw)(";
	return b[a.find(t)];
}

int main(){
	string s;
	cin >> s;
	int a = 0;
	for(int i = 0 ; i <= (s.size()-1)/2 ; i++){
		if(s[s.size()-i-1] != get(s[i])){
			a++;
		}
	}
	cout << a << endl;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <unordered_map>
#include <cmath>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

ll mod_pow(ll x, ll n, const ll &p)
{
    ll ret = 1;
    while (n > 0)
    {
        if (n & 1)
        {
            (ret *= x) %= p;
        }
        (x *= x) %= p;
        n >>= 1;
    }
    return ret;
}

// 素因数分解のマップ
unordered_map<ll, ll> prime(ll n)
{
    unordered_map<ll, ll> m;
    for (size_t i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            m[i]++;
            n /= i;
        }
    }
    if (n != 1)
    {
        m[n]++;
    }
    return m;
}

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

    ll N;
    cin >> N;

    // prime factor
    vector<unordered_map<ll, ll>> primes(N);
    for (size_t i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        primes[i] = prime(a);
    }

    // lcm
    unordered_map<ll, ll> lcm_prime;
    for (auto &e : primes)
    {
        for (auto &p : e)
        {
            lcm_prime[p.first] = max(lcm_prime[p.first], p.second);
        }
    }

    ll ans = 0;
    for (auto &p : primes)
    {
        ll tmp = 1;
        for (auto &&e : lcm_prime)
        {
            if (p.count(e.first) > 0)
            {
                tmp *= mod_pow(e.first, e.second - p[e.first], MOD);
                tmp %= MOD;
            }
            else
            {
                tmp *= mod_pow(e.first, e.second, MOD);
                tmp %= MOD;
            }
        }
        ans += tmp;
    }
    cout << ans % MOD << endl;
}

Measured memory_bytes: 3328
// Justice will be served
// شهید حاج قاسم سلیمانی

#include <bits/stdc++.h>
using namespace std ;

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

#define PB push_back
#define F first
#define S second
#define _sz(x) (int)x.size()

#define debug(x) cerr << #x << " = " << x << endl

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

const int MAX_N = -1 ;
const int inf = 2e9 + 19 ;

int main() {
        ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
        string s ;
        cin >> s ;
        if (s == "Rainy")
                cout << "Sunny" ;
        else if (s == "Sunny")
                cout << "Cloudy" ;
        else if (s == "Cloudy")
                cout << "Rainy" ;
        return (0) ;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <numeric>

using namespace std;
using ll = long long;
const ll mod =  1000000007;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REP_FROM(i, j, n) for (ll i = (j); i < (n); ++i)
#define all(x) (x).begin(),(x).end()

ll power(ll base, ll exponent, ll module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ ll root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
ll inverse(ll x){ return power(x, mod - 2, mod);}
ll gcd(ll a, ll b) {if(a < b) gcd(b, a);ll r;while(r=a%b) {a=b;b=r;}return b;}
struct combination{ vector<ll> 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; } } ll C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };

vector<vector<ll>> dp;

combination table(2 * 100000 + 50);

signed main() {
  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  set<ll> a;
  REP(i, m) {
    ll x;
    cin >> x;
    a.insert(x);
  }
  vector<ll> dp(n+10);
  dp[0] = 1;
  REP(i, n) {
    dp[i] %= mod;
    if(a.find(i+1) == a.end()) {
      dp[i+1] += dp[i];
    }
    if(a.find(i+2) == a.end()) {
      dp[i+2] += dp[i];
    }
  }
  cout << dp[n] % mod << endl;
  return 0;
}


Measured memory_bytes: 8832
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

ll llmax(ll x, ll y)
{
    if (x > y)
        return x;
    else
        return y;
}

double dist(int i, int j)
{
    double ans;
    ans = sqrt(i * i + j * j);
    return ans;
}

int main()
{
    int N,M,C; cin >> N >> M >> C;
    vector<int> B(M);
    REP(i,M){
        cin >> B[i];
    }
    int cnt=0;
    int A[N][M]={0};
    REP(i,N){
        REP(j,M){
            cin >> A[i][j];
        }
    }
    REP(i,N){
        ll res=0;
        REP(j,M){
            res+=B[j]*A[i][j];
        }
        if(res+C>0) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

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

int main(){
  vector<char> a(4);
  for (int i = 0; i < 4; i++){
    cin >> a.at(i);
  }

  // for (int i = 0; i < 4; i++){
  //   cout << a[i] << endl;
  // }
  sort(a.begin(), a.end());
  if (a[0] == a[1] && a[2] == a[3] && a[1] != a[2]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main(){
    int s, w;
    cin >> s >> w;
    if(s>w){
        cout << "safe" << "\n";
    }else{
        cout << "unsafe" << "\n";
    }
    return 0;
}

Measured memory_bytes: 3592
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto T = RD;
	auto AB = new long[][](N, 2);
	foreach (i; 0..N)
	{
		AB[i] = [RD, RD];
	}
	AB.sort!"a[0] < b[0]";

	auto dp = new long[][](N+4000, T+4000);
	dp[0][0] = 0;
	foreach (i; 0..N)
	{
		foreach (key; 0..dp[i].length)
		{
			dp[i+1][key] = max(dp[i+1][key], dp[i][key]);
			if (key >= T) continue;
			auto t = key + AB[i][0];
			auto s = dp[i][key] + AB[i][1];
			dp[i+1][t] = max(dp[i+1][t], s);
		}
	}

	long ans;
	foreach (key; 0..dp[N].length)
	{
		ans = max(ans, dp[N][key]);
	}
	writeln(ans);
	stdout.flush();
	debug readln();
}

Measured memory_bytes: 394876
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
const int INF = 1001001001;
const ll LINF = 1e18;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)

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

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


int main(){
    ll N, W, mv = 0; cin >> N >> W; vl ws(N+1,0), vs(N+1,0);
    REP(i, N){
        cin >> ws[i+1] >> vs[i+1]; mv = max(mv, vs[i+1]+10);
    }
    const ll max_v = min(1010LL, mv);
    vvl dp(N+1, vl(max_v * N, LINF)); REP(i,N+1) dp[i][0] = 0; dp[1][vs[1]] = ws[1];
    FOR(i, 1, N+1){
        FOR(v, 1, max_v * N){
            dp[i][v] = min(dp[i][v], dp[i-1][v]);
            if(v >= vs[i]) dp[i][v] = min(dp[i][v], dp[i-1][v-vs[i]] + ws[i]);
        }
    }
    
    ll ret = 0;
    FOR(v, 1, max_v * N)
        if(dp[N][v] <= W) ret = max(ret, v);
    cout << ret << endstr;
    return 0;
}


Measured memory_bytes: 81024
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repm(i, a, b) for (ll i = (ll)(a); i > (ll)(b); i--)
#define all(v) v.begin(), v.end()
#define rall(x) (x).rbegin(), (x).rend()
#define pll pair<long long, long long>
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define vc vector<char>
#define vvc vector<vc>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<long long>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
template <class T>bool chmax(T &a, const T &b){if (a < b){a = b;return 1;}return 0;}
template <class T>bool chmin(T &a, const T &b){if (b < a){a = b;return 1;}return 0;}
//snippets:tmp,cl,cvl,cs,co,coy,con,cov,setp

int modPow(long long a, long long n, long long p) {
    if (n == 1) return a % p;
    if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
    long long t = modPow(a, n / 2, p);
    return (t * t) % p;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    cin >> n;
    string s;
    cin>>s;
    ll r=0;
    ll w=0;
    rep(i,s.size()){
        if(s[i]=='R')r++;
        else w++;
    }
    ll count=0;
    rep(i,r){
        if(s[i]=='W') count++;
    }
    cout<<count<<endl;
}

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

#define ll long long

#define fr(i,a,b) for (ll i = (a), _b = (b); i <= _b; i++)
#define frr(i,a,b) for (ll i = (a), _b = (b); i >= _b; i--)
#define rep(i,n) for (ll i = 0, _n = (n); i < _n; i++)
#define repr(i,n) for (ll i = n - 1; i >= 0; i--)
#define fill(ar,val) memset(ar, val, sizeof(ar))
#define fill0(ar) fill((ar), 0)
#define debug(x) cout<<#x<<": "<<x<<endl

#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<ii> vii;
typedef vector<int> vi;

#define INF 1000000000000000000
#define PI 3.14159265358979323846L

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll k, a , b;

    cin >> k >> a >> b;

    if(b-1<=a)
    {
    	cout << k+1 << endl;
    }
    else
    {
    	if(k>a)
    	{
    		k = k-a;
    		ll bis = b;
    		k--;	

    		if(k%2==0)
    		{
    			k = k/2;
    			bis = bis + (b-a)*k;
    		}
    		else
    		{
    			k = k/2;
    			bis = bis + (b-a)*k;
    			bis++;
    		}

    		cout << bis << endl;
    	}
    	else
    	{
    		cout << k+1 << endl;
    	}
    }
}


Measured memory_bytes: 256
n, total = map(int, input().split())

x = -1
y = -1
z = -1

for a in range(n+1):  #10000
    for b in range(n-a+1):  #5000
        c = n-a-b
        if total == 10000 * a + 5000 * b + 1000 * c:
            x, y, z = a, b, c
            break

print(x, y, z)


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
const int maxn = 200200;
long long p[maxn];
int main(){
	int n;
	cin >> n;
	for(int e = 0; e < n; e++){
		int x; cin >> x;
		p[e + 1] = p[e] + x;
	}
	map<long long, int> occ;
	long long res = 0;
	for(int e = 0; e <= n; e++){
		res += occ[p[e]];
		occ[p[e]]++;
	}
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 14336
#include "bits/stdc++.h"

#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++)

using namespace std;
const int INF = 1 << 30;


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

	vector<int> A(N);
	rep(i, N)cin >> A[i];

	unordered_map<int, int> mp;
	vector<int> roop;

	int town = 1;
	while (true) {
		if (mp[town] != 0)break;
		mp[town]++;
		roop.push_back(town);
		town = A[town - 1];
	}

	//rep(i, roop.size())cout << roop[i] << endl;

	int start = 0;
	rep(i, roop.size()) {
		if (roop[i] == town) {
			start = i + 1;
			break;
		}
	}
	if (K < roop.size())cout << roop[K];
	else {
		K = K - start + 1;
		int num = K % (roop.size() - start + 1);
		cout << roop[start - 1 + num];
	}
}

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<ll> t(n);
  for (int i = 0; i < n; i++) cin >> t[i];
  ll sum = 0;
  for (int i = 0; i < n; i++) sum += t[i];
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    ll j, x;
    cin >> j >> x;
    j--;
    cout << sum - t[j] + x << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import numpy as np
N=int(input())
a=np.array(list(map(int,input().split())))

def f(x):
    ret=0
    while(x!=0 and x%2==0):
        ret+=1
        x/=2
    return ret
  
ans=0
for i in a:
    ans+=f(i)
print(ans)

Measured memory_bytes: 13240
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

typedef complex<double> point;
typedef pair<point,point> pp;
typedef vector<point> VP;
#define x real()
#define y imag()
const point O{0,0};

typedef pair<int,double> T;
typedef pair<double,int> U;
class Graph{
	private:
	int V;
	vector<vector<T> > g;
	public:
	double DIJ(int s,int t){
		priority_queue<U> que;
		vd d(V,inf);
		d[s]=0;
		que.push({0,s});
		while(!que.empty()){
			U p=que.top();
			que.pop();
			int v=p.second;
			if(d[v]<-p.first) continue;
			for(int i=0;i<g[v].size();i++){
				int F=g[v][i].first;
				double S=g[v][i].second;
				if(d[F]>d[v]+S){
					d[F]=d[v]+S;
					que.push({-d[F],F});
				}
			}
		}
		return d[t];
	}
	Graph(int v){
		V=v;
		g=vector<vector<T> >(v);
	}
	void add_edge(int s,int t,double c){
		g[s].push_back({t,c});
		g[t].push_back({s,c});
	}
};

void Point_in(point& p){
	double A,B;
	cin>>A>>B;
	p={A,B};
}

bool If(pp a,pp b){
	point p1=a.first,p2=a.second,q1=b.first,q2=b.second;
	double c=(p1.x-p2.x)*(q1.y-p1.y)+(p1.y-p2.y)*(p1.x-q1.x);
	double d=(p1.x-p2.x)*(q2.y-p1.y)+(p1.y-p2.y)*(p1.x-q2.x);
	return c*d<0;
}

bool Inter(pp a,pp b){
	if(If(a,b)&&If(b,a)) return 1;
	return 0;
}

int n,m;
VP a,b;

double f(){
	Graph g(n);
	for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(!Inter({a[i],a[j]},{b[0],b[1]})){
		g.add_edge(i,j,abs(a[i]-a[j]));
	}
	return g.DIJ(0,1)+abs(b[0]-b[1]);
}

int main(){
	cin>>n>>m;
	a=VP(n);
	b=VP(m);
	for(int i=0;i<n;i++) Point_in(a[i]);
	for(int i=0;i<m;i++) Point_in(b[i]);
	double res=f();
	swap(n,m);
	swap(a,b);
	res=min(res,f());
	if(res>inf-eps) cout<<-1<<endl;
	else cout<<syosu(11)<<res<<endl;
}

Measured memory_bytes: 19760
adjacent = (
    (1, 3),       # 0
    (0, 2, 4),    # 1
    (1, 5),       # 2
    (0, 4, 6),    # 3
    (1, 3, 5, 7), # 4
    (2, 4, 8),    # 5
    (3, 7),       # 6
    (4, 6, 8),    # 7
    (5, 7)        # 8
)
 
GOAL = [1, 2, 3, 4, 5, 6, 7, 8, 0]
 
# Bidirectional search using breadth-first search
def solve(start):
    if start == GOAL:
        return 0
    # 0: forward, 1: backward
    generated_state = {tuple(start): 0, tuple(GOAL): 1}
    step = {tuple(start): 0, tuple(GOAL): 0}
    s = 0
    state1 = [(start, 0), (GOAL, 1)]
    while state1:
        state2 = state1[:]
        state1 = []
        s += 1
        for s2, d in state2:
            i = s2.index(0)
            for p in adjacent[i]:
                s1 = s2[:]
                s1[i], s1[p] = s1[p], 0
                key = tuple(s1)
                if key in generated_state:
                    if generated_state[key] != d:
                        return s + step[key]
                    continue
                state1.append((s1, d))
                generated_state[key] = d
                step[key] = s
 
import sys
 
start = list(map(int, sys.stdin.read().split()))
 
print(solve(start))


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back

const int maxm = 1000000000 + 7;


using namespace std;


int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int r;
	cin>>r;

	cout<<3*r*r<<endl;
}

Measured memory_bytes: 3564
#include <stdio.h>
#define MAX_N 30
#define NIL -1

typedef struct node_ {
    int parent;
    int left;
    int right;
} Node;

Node T[MAX_N];

void preorder(int u) {
    if (u == NIL) return;

    printf(" %d", u);
    preorder(T[u].left);
    preorder(T[u].right);
}

void inorder(int u) {
    if (u == NIL) return;

    inorder(T[u].left);
    printf(" %d", u);
    inorder(T[u].right);
}

void postorder(int u) {
    if (u == NIL) return;

    postorder(T[u].left);
    postorder(T[u].right);
    printf(" %d", u);
}

int main(void) {
    int i, n;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        T[i].parent = NIL;
        T[i].left = NIL;
        T[i].right = NIL;
    }

    for (i = 0; i < n; i++) {
        int id, left, right;
        scanf("%d %d %d", &id, &left, &right);
        T[id].left = left;
        T[id].right = right;
        if (left != NIL) T[left].parent = id;
        if (right != NIL) T[right].parent = id;
    }

    int r;
    for (i = 0; i < n; i++) {
        if (T[i].parent == NIL) r = i;
    }

    puts("Preorder");
    preorder(r); putchar('\n');
    puts("Inorder");
    inorder(r); putchar('\n');
    puts("Postorder");
    postorder(r); putchar('\n');

    return 0;
}

Measured memory_bytes: 616
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cctype>
#include<cstring>
#include<utility>
#include<cmath>
#include <string>
using namespace std;

int N, M, a[51], b[51], ans=0;
bool graph[51][51] = { false }, visited[51];

void dfs(int x) {
    visited[x] = true;
    for (int i = 0; i < N; i++) {
        if (graph[x][i] == false) continue;
        if (visited[i] == true) continue;
        dfs(i);
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        cin >> a[i] >> b[i];
        a[i]--, b[i]--;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
    }
    
    for (int i = 0; i < M; ++i) {
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
        for (int j = 0; j < N; ++j)visited[j] = false;
        dfs(0);
        bool connected = false;
        for (int j = 0; j < N; j++) {
            if (!visited[j]) connected = true;
        }
        if (connected) ans++;
        graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
    }

    cout << ans << endl;

    return 0;
}

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

 
int main() {
    string s,t;
    cin>>s>>t;

    vector<char> S(s.length());
    vector<char> T(t.length());

    rep(i,s.length())S[i]=s[i];
    rep(i,t.length())T[i]=t[i];

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

    if(T>S)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

}

//stringのままでsortはできた

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <memory.h>
#include <math.h>

#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define MIN(a, b) (((a) > (b)) ? (b) : (a))
#define SWAP(t, a, b) do{t c = a; a = b; b = c;}while(0)

int main (int argc, char **argv)
{
  int64_t k = 0;
  int64_t x = 0;
  int64_t i = 0;

  scanf("%lld %lld", &k, &x);

  for(i = MAX(x-k+1,-1000000); i <= MIN(x+k-1,1000000); i++)
  {
    printf("%lld ", i);
  }
  printf("\n");

  return 0;
}


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

class Program
{
    static void Main(string[] args)
    {
        var nk = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        var n = nk[0];
        var k = nk[1];
        var a = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();

        // 算出する楽器
        for (long i = k; i < n; i++)
        {
            if (a[i] > a[i - k]) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 47352
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

N = I()
if N >= 1000:
    print('ABD')
else:
    print('ABC')


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

using namespace std;

const int INF = 1e9;
int n, m, dp[21][50010], c[21];

int main(void) {
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> c[i];
    
    for (int i = 0; i < 50010; i++)
        dp[0][i] = INF;

    dp[0][0] = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= n; j++) {
            if (j < c[i]) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - c[i]] + 1);
        }
    
    cout << dp[m][n] << endl;

    return 0;
}


Measured memory_bytes: 7188
# -*- coding: utf-8 -*-
"""
Created on Thu Feb 28 16:53:54 2019

@author: またの
"""

N,M=map(int,input().split())
L = []
for i in range(N):
    L.append(list(map(int,input().split())))

K1=[]
K2=[]
K3=[]
K4=[]
K5=[]
K6=[]
K7=[]
K8=[]

C = [0,0,0,0,0,0,0,0]

for i in range(N):
    K1.append(L[i][0]+L[i][1]+L[i][2])
K1.sort()

for i in range(N):
    K2.append(L[i][0]-L[i][1]+L[i][2])
K2.sort()

for i in range(N):
    K3.append(L[i][0]+L[i][1]-L[i][2])
K3.sort()

for i in range(N):
    K4.append(-L[i][0]+L[i][1]+L[i][2])
K4.sort()

for i in range(N):
    K5.append(-L[i][0]+L[i][1]-L[i][2])
K5.sort()

for i in range(N):
    K6.append(L[i][0]-L[i][1]-L[i][2])
K6.sort()

for i in range(N):
    K7.append(-L[i][0]-L[i][1]+L[i][2])
K7.sort()

for i in range(N):
    K8.append(-L[i][0]-L[i][1]-L[i][2])
K8.sort()

for i in range(M):
    C[0] += K1[N-i-1]
    C[1] += K2[N-i-1]
    C[2] += K3[N-i-1]
    C[3] += K4[N-i-1]
    C[4] += K5[N-i-1]
    C[5] += K6[N-i-1]
    C[6] += K7[N-i-1]
    C[7] += K8[N-i-1]
    
for i in range(8):
    C[i] = abs(C[i])
print(max(C))


Measured memory_bytes: 3572
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

char s[500001];
int a[500001][27];
int b[20][500001];
set <int> se[500000];

bool in(int x, int y) {
    int i;
    
    for (i = 19; i >= 0; i--) {
        if (b[i][x] == -1 || b[i][x] > y) continue;
        
        if (b[i][x] == y) return true;
        
        x = b[i][x] + 1;
    }
    
    return false;
}

int main() {
    int n, q, c = 0, i, j;
    
    scanf("%s", s);
    
    n = strlen(s);
    
    for (i = 0; i <= n; i++) {
        for (j = 0; j < 27; j++) {
            a[i][j] = -1;
        }
    }
    
    for (i = n - 1; i >= 0; i--) {
        a[i][s[i] - 'a'] = i;
        
        for (j = s[i] - 'a'; j < 26; j++) {
            int x = a[i][j];
            
            if (a[x + 1][j] == -1) break;
            
            a[i][j + 1] = a[x + 1][j];
        }
        
        if (j == 26) {
            for (j = 0; j < s[i] - 'a'; j++) a[i][j] = a[a[i][26] + 1][j];
        }
    }
    
    for (i = 0; i < n; i++) b[0][i] = a[i][26];
    b[0][n] = -1;
    
    for (i = 1; i < 20; i++) {
        for (j = 0; j <= n; j++) {
            if (b[i - 1][j] == -1) {
                b[i][j] = -1;
            } else {
                b[i][j] = b[i - 1][b[i - 1][j] + 1];
            }
        }
    }
    
    scanf("%d", &q);
    
    for (i = 0; i < q; i++) {
        int l, r;
        
        scanf("%d %d", &l, &r);
        
        l--;
        r--;
        
        if (in(l, r)) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    
    return 0;
}


Measured memory_bytes: 116352
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ttl = sum(b)
for i in range(n-1):
    if a[i]+1 == a[i+1]:
        ttl += c[a[i]-1]
print(ttl)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
//const long long MOD = 998244353;
const long long INF_LL = 1e18+11; const int INF_int = 1e9+11;
#define ll long long
#define mp std::make_pair
#define rep(i,n) for(int i = 0;i<n;i++)
#define lrep(i,n) for(long long i = 0;i<n;i++)
#define All(a) a.begin(),a.end()
#define Debug_Output_ALL(a) for(auto x:a) cout << x << " ";cout << endl;
int main(){
    int a;
    cin >> a;
    if(a>=30) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3620
import java.util.Scanner;


class Main {

	public static void main(String[] args) {
	
		Scanner sc = new Scanner(System.in);
		
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		int x;
		int count = 0;
		
		for(x = a; x <= b; x++){
			
			if(c % x == 0){
				count++;
			}
			
		}
		
		System.out.println(count);
		
	}

}

Measured memory_bytes: 26240
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll INFL = 1e18;
const ll mod = 1e9 + 7;
 
int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}
 
ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

bool is_prime(long long N){
    if (N == 1) return false;
    for (long long i = 2;i * i <= N;i++){
        if (N % i == 0) return false;
    }
    return true;
}
 
ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}
 
double DegreeToRadian(double degree){
    return degree * M_PI / 180.0;
}
 
 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
 
 
///////////////////////////////////////////////////////////////////////////////////

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);

    for (int i = 0;i < n;i++){
        cin >> a[i];
    }
    long long rep = 1;
    long long sum = 0;
    long long even = 0, odd = 0;
    for (int i = 0;i < n;i++){
        sum += a[i];
        if (sum * rep <= 0){
            even += (abs(sum) + 1);
            sum = rep;
        }
        rep *= -1;
    }   
    rep = -1;
    sum = 0;
    for (int i = 0;i < n;i++){
        sum += a[i];
        if (sum * rep <= 0){
            odd += (abs(sum) + 1);
            sum = rep;
        }
        rep *= -1;
    }

    cout << min(even, odd) << endl;
}

Measured memory_bytes: 4020
#define _USE_MATH_DEFINES
#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <cmath>
#include <math.h>
#include <numeric>
#include <list>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <climits>
#include <set>
#include <memory.h>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <map>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int , P> PP;
typedef pair<int, string> Ps;
typedef vector<int> vec;
typedef vector<vec> mat;
const int INF = 1 << 29;
const double EPS = 1e-10;
const double PI = 3.1415926535897932384626433832795;
const int CLK = CLOCKS_PER_SEC;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
#define repD(i, n) for(int i = n; i >= 0; i--)

int cnt;
int field[100][100];
int check[100][100];
int res[100][100];
bool used[20];
int K[20];
int X, Y, n;

void solve(int y, int x){
	if(y == Y){
		bool ok = true;
		rep(i, Y)rep(j, X) if(check[i][j] == 0) ok = false;
		assert(ok);
		if(ok){
			cnt++;
			rep(i, Y)rep(j, X) res[i][j] = check[i][j];
		}
		
	}else{
		if(check[y][x] >= 0){
			if(x == X-1) solve(y+1, 0);
			else solve(y, x+1);
		}else{
			int dy = Y - y;
			int dx = X - x;
			bool ok;
			for(int i = 1; i <= dy; i++){
				for(int j = 1; j <= dx; j++){
					ok = true;
					int id = -1;
					rep(k, i){
						rep(l, j){
							if(check[y+k][x+l] >= 0) ok = false;
							if(field[y+k][x+l] > 0){
								if(!used[field[y+k][x+l]] && (id == -1 || field[y+k][x+l] == id)){
									id = field[y+k][x+l];
								}else ok = false;
							}
						}
					}
					if(!ok || id == -1 || K[id] != i * j) continue;
					rep(k,i)rep(l, j) check[y+k][x+l] = id;
					used[id] = true;
					solve(y,x);
					used[id] = false;
					rep(k,i)rep(l, j) check[y+k][x+l] = -1;
				}
			}
		}
	}
}



int main(){
	while(cin >> X >> Y >> n && (X || Y || n)){
	
		rep(i, n){
			int b;
			cin >> b;
			cin >> K[b];
		}
		
		rep(i, Y)rep(j, X){
			cin >> field[i][j];
		}
		memset(check, -1, sizeof(check));
		memset(used, false, sizeof(used));

		cnt = 0;
		solve(0, 0);
		if(cnt != 1) cout << "NA" << endl;
		else{
			bool f = false;
			rep(i, Y){
				rep(j,X){
					if(j != 0) cout << " ";
					cout << res[i][j];
					if(check[i][j] != -1) f = true;
				}
				cout << endl;
			}
			assert(!f);
		}
	}
	return 0;
}

Measured memory_bytes: 0
/* ****GT_18**** */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		ll i,j,k,l,m,n,a[200000];
		cin>>n;
		map<ll,ll> ma;
		ll t=1;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			ma[a[i]]++;
			if(a[i]!=0)
				t=0;
		}
		if(t)
		{
			cout<<"Yes";
			return 0;
		}
		if(n%3!=0)
		{
			cout<<"No";
			return 0;
		}
		ll ans=0;
		for(auto i:ma)
		{
			if(i.S*3!=n&&i.S*3!=2*n)
			{
				cout<<"No";
				return 0;
			}
			ans^=i.F;
			if(i.S*3==2*n)
				ans^=i.F;
		}
		if(ans==0)
		{
			cout<<"Yes";
			return 0;
		}
		cout<<"No";
		return 0;
	}
	return 0;
}	

Measured memory_bytes: 5760
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
long double lfabs(long double a)
{
   if(a < 0) a *= -1;
   return a;
}

int main()
{
   int i,j,k,l;
   long double x;
   int q;
   while(1) {
      cin >> q;
      if(q == -1) break;

      x = (long double)q/2;
      while(1) {
         x = x - (x*x*x - q) / (3*x*x) ;
         if( lfabs(x*x*x-q) < 0.00001*q ) break;
      }
      printf("%llf\n",x);
   }
   
   return 0;
}

Measured memory_bytes: 1188
#include <iostream>

using namespace std;

int main()
{
	int n;

	while (true)
	{
		cin >> n;

		if (n == 0) { break; }

		n = 1000 - n;

		cout << n / 500 + (n / 100) % 5 + (n / 50) % 2 + (n / 10) % 5 + (n / 5) % 2 + n % 5 << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
N = int(input())
a = - (10 ** 9 + 3)  # max(x + y)
b = 10 ** 9 + 3  # min(x + y)
c = - (10 ** 9 + 3)  # max(x - y)
d = 10 ** 9 + 3  # min(x - y)
for i in range(N):
    x, y = map(int, input().split())
    a = max(a, x + y)
    b = min(b, x + y)
    c = max(c, x - y)
    d = min(d, x - y)
ans = max([a - b, c - d])
print(ans)


Measured memory_bytes: 9128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(n); ++i)
typedef long long ll;
int main(){
  // 解説閲覧済み
  int a,b,x,y;
  scanf("%d %d %d %d", &a, &b, &x, &y);
  printf("%lf %d\n", (double)a*(double)b/2,2*x==a && 2*y==b);

}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n, t, s):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
        self.sizex = [1] * t + [0] * s
        self.sizey = [0] * t + [1] * s

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def sizeof(self, x):
        return self.sizex[self.find(x)] * self.sizey[self.find(x)]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.sizex[y] += self.sizex[x]
            self.sizey[y] += self.sizey[x]
        else:
            self.par[y] = x
            self.sizex[x] += self.sizex[y]
            self.sizey[x] += self.sizey[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
dx = coordinate_compression(x)
dy = coordinate_compression(y)
uf = UnionFind(len(dx) + len(dy), len(dx), len(dy))
for i in range(n):
    uf.unite(dx[x[i]], dy[y[i]] + len(dx))
s = set()
ans = 0
for i in range(len(dx)):
    p = uf.find(i)
    if p in s:
        continue
    ans += uf.sizeof(i)
    s.add(p)
print(ans - n)


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

using namespace std;

int main(int argc, char* argv[]){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string S, T; cin >> S >> T;

	int l = S.size();
	int notmatch = 0;
	for(int i=l-1; i>=0; i--){
		notmatch = 0;
		for(int j=0; j<l; j++){
			int pos = i+j;
			if(pos >= l) pos -=l;
			if(S[pos] != T[j]){
				notmatch = 1;
				break;
			}
		}
		if(notmatch == 0){
			break;
		}
	}
	if(notmatch == 1){
		printf("No\n");
	}
	else{
		printf("Yes\n");
	}
	return 0;
}

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

using namespace std;

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

#define int ll

const ll mod = 1e9 + 7;


main(){
	ll a,b,c;

	cin >> a >> b >> c;

	if(a+b<c && 4*a*b<(c-a-b)*(c-a-b)){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}


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

int gcd(int p, int q){
  if(p%q == 0) return q;
  return gcd(q, p%q);
}

int main (){
  int n;
  cin >> n;
  int ans = 0;
  int tmp;
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      tmp = gcd(i, j);
      for(int s = 1; s <= n; s++){
        ans += gcd(tmp, s);
      }
    }
  }
 
 
  cout << ans << endl;
}


Measured memory_bytes: 3640
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int n;
    R(n);
    VI AA(n);
    REP(i,n)R(AA[i]);
    sort(ALL(AA));
    double an=AA[0];
    REPP(i,1,n){
        an+=AA[i];
        an*=0.5;
    }
    W(an);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    Rectangle rectangle;
    Circle circle;
    try (Scanner scanner = new Scanner(System.in)) {
      rectangle = new Rectangle(scanner.nextInt(), scanner.nextInt());
      circle = new Circle(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
    }
    if (rectangle.isInclude(circle)) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}

class Rectangle implements Figure {
  final private int x;
  final private int y;

  Rectangle(int x, int y) {
    this.x = x;
    this.y = y;
  }

  boolean isInclude(Figure figure) {
    if (getTopY() < figure.getTopY()) {
      return false;
    }
    if (getBottomY() > figure.getBottomY()) {
      return false;
    }
    if (getLeftX() > figure.getLeftX()) {
      return false;
    }
    if (getRightX() < figure.getRightX()) {
      return false;
    }
    return true;
  }

  @Override
  public int getTopY() {
    return Math.max(0, y);
  }

  @Override
  public int getBottomY() {
    return Math.min(0, y);
  }

  @Override
  public int getLeftX() {
    return Math.min(0, x);
  }

  @Override
  public int getRightX() {
    return Math.max(0, x);
  }
}

interface Figure {
  int getTopY();
  int getBottomY();
  int getLeftX();
  int getRightX();
}

class Circle implements Figure {
  final private int x;
  final private int y;
  final private int r;

  Circle(int x, int y, int r) {
    this.x = x;
    this.y = y;
    this.r = r;
  }

  @Override
  public int getTopY() {
    return y + r;
  }

  @Override
  public int getBottomY() {
    return y - r;
  }

  @Override
  public int getLeftX() {
    return x - r;
  }

  @Override
  public int getRightX() {
    return x + r;
  }
}

Measured memory_bytes: 26440
a, b, c, d = map(int, input().split())
list_a_b = [a, b] 
list_c_d = [c, d]
max01, max02, min01, min02 = max(list_a_b), max(list_c_d), min(list_a_b), min(list_c_d)
print(max(max01 * max02, min01 * min02, max01 * min02, max02 * min01))

Measured memory_bytes: 9180