akhauriyash/Code-Regression huggingface dataset:
d, g = map(int, input().split())
point = []
for i in range(d):
    p, c = map(int, input().split())
    point.append([p, c])

def f(g, i):
    
    if i == -1:
        return 10000000
    n = min(g // ((i + 1) * 100), point[i][0])
    s = n * (i + 1) * 100
    if n == point[i][0]:
        s += point[i][1]
    if s < g:
        n += f(g - s, i - 1)
    return min(n, f(g, i - 1))
print(f(g, d-1))

Measured memory_bytes: 3064
tbl=[[i for i in range(1,14)] for _ in range(4)]
n=int(input())
for _ in range(n):
    a,b=input().split()
    b=int(b)
    if a=="S":
        tbl[0].remove(b)
    if a=="H":
        tbl[1].remove(b)
    if a=="C":
        tbl[2].remove(b)
    if a=="D":
        tbl[3].remove(b)
for i in range(4):
    for j in tbl[i]:
        print("SHCD"[i],j)


Measured memory_bytes: 5604
n,m=map(int,input().split())
h=list(map(int,input().split()))

f=[True]*n

for i in range(m):
  ai,bi=map(int,input().split())
  ai-=1
  bi-=1
  if h[ai]==h[bi]:
    f[ai]=False
    f[bi]=False
  elif h[ai]>h[bi]:
    f[bi]=False
  elif h[ai]<h[bi]:
    f[ai]=False

print(sum(f))
    

Measured memory_bytes: 84660
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long ;
int main(){
    int n;
    cin >> n;
    if(n==1){
        cout << "Hello World"<<endl;
    }
    else{
        int a,b;
        cin >> a >> b;
        cout << a+b << endl;
    }
    return 0;
}

Measured memory_bytes: 3604
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

N=intput()
xy=[]
for _ in range(N):
    xy.append(lint())
xy.sort()
if N==1:
    print(1)
    exit()
C=counter()
for i in range(N):
    for j in range(i+1,N):
        C.add((xy[j][0]-xy[i][0],xy[j][1]-xy[i][1]))
print(N-max(list(C.values())))

Measured memory_bytes: 74596
package main

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

type IO struct {
	scanner *bufio.Scanner
	writer  *bufio.Writer
}

func NewIO() (*IO, func()) {
	io := &IO{
		scanner: newScanner(),
		writer:  newWriter(),
	}
	return io, func() { io.writer.Flush() }
}

func newScanner() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Buffer(make([]byte, 1000005), 1000005)
	s.Split(bufio.ScanWords)
	return s
}

func newWriter() *bufio.Writer {
	return bufio.NewWriter(os.Stdout)
}

func (io *IO) ScanString() string {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Text()
}

func (io *IO) ScanStrings(n int) []string {
	strs := make([]string, n)
	for i := 0; i < n; i++ {
		strs[i] = io.ScanString()
	}
	return strs
}

func (io *IO) ScanInt() int {
	return int(io.ScanInt64())
}

func (io *IO) ScanInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = io.ScanInt()
	}
	return ints
}

func (io *IO) Scan2DInts(x, y int) [][]int {
	ints := make([][]int, y)
	for i := 0; i < y; i++ {
		ints[i] = io.ScanInts(x)
	}
	return ints
}

func (io *IO) ScanInt64() int64 {
	i, err := strconv.ParseInt(io.ScanString(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *IO) ScanFloat64() float64 {
	i, _ := strconv.ParseFloat(io.ScanString(), 64)
	return i
}

func (io *IO) ScanFloat64s(n int) []float64 {
	floats := make([]float64, n)
	for i := 0; i < n; i++ {
		floats[i] = io.ScanFloat64()
	}
	return floats
}

func (io *IO) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func main() {
	io, flush := NewIO()
	defer flush()
	n, a, b := io.ScanInt(), io.ScanInt(), io.ScanInt()
	var extra int
	if mod := n % (a + b); mod != 0 {
		if a < mod {
			extra = a
		} else {
			extra = mod
		}
	}
	io.Println(n/(a+b)*a + extra)
}


Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;

ll x;
ll fpow(ll a,ll b){
    ll res=1;
    while(b) {
        if (b & 1) res = res * a;
        b >>= 1;
        a = a * a;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>x;
    for(ll i=-1000;i<=1000;++i){
        for(ll j=-1000;j<=1000;++j){
            if(fpow(i,5)-fpow(j,5)==x){
                printf("%lld %lld\n",i,j);
                return 0;
            }
        }
    }


    return 0;
}

Measured memory_bytes: 3768
#include <cstdio>
#include <iostream>
#include <algorithm>
#define maxn 10005
int a[maxn];
int b[maxn];
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		b[a[i]]++;
		//cout<<b[a[i]]<<" ";
	}
	int cnt=0;
	for(int i=0;i<maxn;i++){
		if(b[i]>0){
			cnt++;
		}
	}
	cout<<cnt<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
namespace FAST_IO
{
	template<typename T> void read(T &a)
	{
		a=0;
		int f=1;
		char c=getchar();
		while(!isdigit(c))
		{
			if(c=='-')
			{
				f=-1;
			}
			c=getchar();
		}
		while(isdigit(c))
		{
			a=a*10+c-'0';
			c=getchar();
		}
		a=a*f;
	}
	template <typename T> void write(T a)
	{
		if(a<0)
		{
			a=-a;
			putchar('-');
		}
		if(a>9)
		{
			write(a/10);
		}
		putchar(a%10+'0');
	}
	template <typename T> void writeln(T a)
	{
		write(a);
		puts("");
	}
}
int n,m,x,a[101],l,r;
int main()
{
	cin>>n>>m>>x;
	for(int i=1;i<=m;i++)
	{
		int tmp;
		cin>>tmp;
		a[tmp]=true;
	}
	for(int i=x;i>=0;i--)
	{
		if(a[i])
		{
			l++;
		}
	}
	for(int i=x;i<=n;i++)
	{
		if(a[i])
		{
			r++;
		}
	}
	cout<<min(l,r);
}

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

int main()
{
  int n;
  cin>>n;
  vector<int> v(n),m;
  for(auto &i:v) cin>>i;
  m=v;
  sort(m.begin(),m.end());
  int c=0;
  for(int i=0;i<n;i++) if(v[i]!=m[i]) c++;
  if(c<=2)
    cout<<"YES\n";
  else
    cout<<"NO\n";
  
  
  return 0;
}

Measured memory_bytes: 256
import sys
import queue

H,W = map(int,input().split())
white = 0
maze = []
for y in range(H):
	li = list(input())
	white += li.count('.')
	maze.append(li)

def check(x,y,n):
	if 0 <= x < W and 0 <= y < H:
		if x == W-1 and y == H-1:
			print (white - n - 1)
			sys.exit()
		elif maze[y][x] == '.':
			maze[y][x] = n
			q.put([x-1,y,n+1])
			q.put([x+1,y,n+1])
			q.put([x,y-1,n+1])
			q.put([x,y+1,n+1])
		else:
			return
	else:
		return

q = queue.Queue()
q.put([0,0,0])
while not q.empty():
	x,y,n = q.get()
	check(x,y,n)

print(-1)


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

int main() {
	int n, m;
	cin >> n >> m;
	int h[n+1];
	for (int i = 1; i <= n; ++i)
	{
		cin >> h[i];
	}
	vector<bool> ok(n+1,true);
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		if(h[a] >= h[b])
		{
			ok[b] = false;
		}
		if (h[a] <= h[b])
		{
			ok[a] = false;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		if(ok[i]) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3952
import std.stdio;
void main() {
	float w;
	while ("%f\n".readf(&w))
		writeln(w <= 48.00 ? "light fly"
			: w <= 51.00 ? "fly"
			: w <= 54.00 ? "bantam"
			: w <= 57.00 ? "feather"
			: w <= 60.00 ? "light"
			: w <= 64.00 ? "light welter"
			: w <= 69.00 ? "welter"
			: w <= 75.00 ? "light middle"
			: w <= 81.00 ? "middle"
			: w <= 91.00 ? "light heavy"
			: "heavy");
}

Measured memory_bytes: 2444
N=int(input())
name=[input()[0] for _ in range(N)]
m,a,r,c,h=name.count("M"),name.count("A"),name.count("R"),name.count("C"),name.count("H")
print(m*a*(r+c+h)+m*r*(c+h)+m*c*h+a*r*(c+h)+a*c*h+r*c*h)

Measured memory_bytes: 3864
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 300005

int N;
vector<ll> V[NUM];

int main(){

	scanf("%d",&N);

	int tmp_num;
	ll tmp;

	for(int loop = 0; loop < N; loop++){

		scanf("%d",&tmp_num);

		for(int i = 0; i < tmp_num; i++){

			scanf("%lld",&tmp);
			V[loop].push_back(tmp);
		}
	}

	ll ans = 0;
	priority_queue<ll> Q;

	for(int i = N-1; i >= 0; i--){

		for(int k = 0; k < V[i].size(); k++){
			Q.push(V[i][k]);
		}

		ans += Q.top();
		Q.pop();
	}

	printf("%lld\n",ans);

	return 0;
}



Measured memory_bytes: 19568
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	int n;
	float o=0;
	cin>>n;
	for (int i=1;i<=n;i++){
		if(i%2) o++;
	}
	cout<<o/n<<endl;
}

Measured memory_bytes: 256
import collections
N,Q=map(int,input().split())
lc=[[] for i in range(N)]#二重リストで木を表現
for i in range(N-1):
    a,b=map(int,input().split())
    lc[a-1].append(b-1)
    lc[b-1].append(a-1)
lv=[0 for i in range(N)]#値のリスト
for i in range(Q):
    p,x=map(int,input().split())
    lv[p-1]+=x
lf=[0 for i in range(N)]#訪れたかどうか
#d=collections.deque([0])
#lp=[0]
lp=collections.deque([0])
lf[0]=1
#for i in range(N):
while len(lp)>0:
    #p=lp[-1]
    p=lp.pop()
    for c in lc[p]:
        if lf[c]==0:
            lv[c]+=lv[p]
            lf[c]=1
            lp.append(c)
for i in range(N-1):
    print(lv[i],end=" ")
print(lv[N-1])


Measured memory_bytes: 52972
from bisect import bisect_left, bisect_right

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))

    Ls.sort()

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            k = bisect_left(Ls, Ls[i]+Ls[j]) - 1
            ans += k-j

    print(ans)


solve()


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


int main(){

  long long int N;

  scanf("%lld",&N);

  /*
  int A[N];
  int i;
  for(i=0;i<N;i++){
   scanf("%d",A[i]);
   }
  */
  long long int f,t;

  f = N/500;
  t = (N-f*500)/5;

  printf("%lld",f*1000+t*5);







 return(0);
 }


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n;
	string s;
	cin>>n>>s;
	s='-'+s;
	vector<int>r(1,0),g(1,0);
	vector<bool>B(s.size()+1,false);
	for(int i=1;i<s.size();++i){
		if(s.at(i)=='R'){
			r.emplace_back(i);
		}
	}
	for(int i=1;i<s.size();++i){
		if(s.at(i)=='G'){
			g.emplace_back(i);
		}
	}
	int b=0;
	for(int i=1;i<s.size();++i){
		if(s.at(i)=='B'){
			++b;
			B.at(i)=true;
		}
	}
	uint64_t ans=0;
	for(int i=1;i<r.size();++i){
		for(int j=1;j<g.size();++j){
			int minnum=min(r.at(i),g.at(j)),
			mxnum=max(r.at(i),g.at(j));
			
			int sa=abs(r.at(i)-g.at(j));

			int bl=minnum-sa, bm=(r.at(i)+g.at(j))/2,
			bh=mxnum+sa;
			ans+=b;
			if(bl>=0&&B.at(bl))--ans;
			if(B.at(bm)&&mxnum-bm==bm-minnum)--ans;
			if(bh<s.size()&&B.at(bh))--ans;
		}
	}
	cout<<ans<<"\n"s;
}

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

int main(){
  string S,T;
  cin>>S;
  cin>>T;
  
  int count=0;
  for(int i=0;i<3;i++){
    if(S.at(i)==T.at(i)){
      count++;
    }
  }
  cout <<count<<endl;
  
  return 0;
}

  


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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

struct Edge {
  int l;
  int r;
  int64 c;
};

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

  int n, m;
  cin >> n >> m;
  vector<vector<Edge>> v_to_edges(n);
  for (int i = 0; i < m; i++) {
    int l;
    int r;
    int64 c;
    cin >> l >> r >> c;
    l--;
    r--;
    Edge e({l, r, c});
    v_to_edges[l].push_back(e);
  }

  multiset<int64> s;
  constexpr int64 INF = 1E18;
  vector<int64> dp(n, INF);
  vector<vector<int64>> v_to_ends(n);
  dp[0] = 0;
  for (const auto& e : v_to_edges[0]) {
    s.insert(e.c);
    v_to_ends[e.r].push_back(e.c);
  }

  for (int v = 1; v < n; v++) {
    if (!s.empty()) {
      dp[v] = *s.begin();
    }
    if (dp[v] == INF) continue;
    for (int64 x : v_to_ends[v]) {
      s.erase(s.find(x));
    }
    for (const auto& e : v_to_edges[v]) {
      s.insert(dp[v] + e.c);
      v_to_ends[e.r].push_back(dp[v] + e.c);
    }
  }

  if (dp[n - 1] == INF) {
    cout << -1 << endl;
  } else {
    cout << dp[n - 1] << endl;
  }
}

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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pf printf
#define sc scanf
#define sf(n) scanf("%d",&n)
#define sff(n1,n2) scanf("%d %d",&n1,&n2)
#define sfff(n1,n2,n3) scanf("%d %d %d",&n1,&n2,&n3)
#define sl(n) scanf("%lld",&n)
#define sll(n1,n2) scanf("%lld %lld",&n1,&n2)
#define slll(n1,n2,n3) scanf("%lld %lld %lld",&n1,&n2,&n3)
#define rep0(i,n) for(i=0;i<n;i++)
#define rep(i,n) for(i=1;i<=n;i++)
#define reps(i,a,n) for(i=a;i<=n;i++)
#define nl puts("");
#define pb push_back
#define MOD 1000000007
#define fi first
#define se second
#define N 100005
#define mem(ara,n) memset(ara,n,sizeof(ara))
#define memb(ara) memset(ara,false,sizeof(ara))
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define sz(x) x.size()
#define pi pair<int,int>
#define pii pair<pair<int,int>,pair<int,int> >
#define line puts("-------");
#define db(x) cout<<#x<<" :: "<<x<<"\n";
#define dbb(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define fr freopen("input.txt","r",stdin);
#define fw freopen("output.txt","w",stdout);
typedef long long int ll;
using namespace std;
int main()
{
    ll n,i;
    sl(n);
    if(n==0)
    {
        puts("0");
        return 0;
    }
    vector<int>ans;
    while(n!=0)
    {
        if(n%2==0)
        {
            ans.pb(0);
            n/=-2;
        }
        else if(n<0)
        {
            ans.pb(1);
            n/=-2;
            n++;
        }
        else
        {
            ans.pb(1);
            n/=-2;
        }
    }
    for(i=ans.size()-1;i>=0;i--)
        pf("%d",ans[i]);
}


Measured memory_bytes: 256
#def gcd(a, b):
#    while b:
#        a, b = b, a % b
#    return a
#
#def lcm(a, b):
#    return a * b // gcd (a, b)

import fractions
from functools import reduce
def lcm_base(x, y):
    r = (x * y) // fractions.gcd(x, y)
    if r > 2*M:
        return 0
    return r

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


N,M = map(int, input().split())
xs = list(map(int, input().split()))
b = None
for x in xs:
    for i in range(30):
        if x%(2**i):
            break
    if b!=None:
        if b!=i:
            b = -1
            break
    b = i
if b==-1:
    print(0)
else:
    r = lcm_list(xs)
    if r//2 > M:
        print(0)
    elif r == 0:
        print(0)
    else:
        print((M-r//2)//r+1)


Measured memory_bytes: 89708
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define pb push_back
#define mp make_pair
const int mod=1e9+7;

void solve()
{
  string str;
  cin>>str;
  if(str[2]==str[3] && str[4]==str[5])
  cout<<"Yes";
  else
  cout<<"No";
}

int main()
{
  fastio
  solve();
}


Measured memory_bytes: 256
using System;

namespace CSharp
{
    class Program
    {
        static void Main()
        {
            var S = Console.ReadLine();

            if (S[2] == S[3] && S[4] == S[5])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 11092
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}

int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};

int f(int x){
  int r=0;
  int a=x/10,b=x%10,k=10;
  while(b!=x){
    r=max(a*b,r);
    b+=(k*(a%10));
    a/=10;k*=10;
  }
  return r;
}

int main(){
  int i,q,n,r;
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&n);
    r=0;
    while(n>=10){
      n=f(n);
      r++;
    }
    printf("%d\n",r);
  }
  return 0;
}



Measured memory_bytes: 2112
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(){
  int A,B;
  cin >> A >> B;
  if(A+B<24)  cout << A+B << endl;
  else  cout << A+B-24 << endl;
  
  return 0;
}


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

int main() {
  char c;
  cin >> c;
  // ここにプログラムを追記
    if(c == 'a' || c=='i' || c=='u' || c=='e' || c=='o')
      cout << "vowel" << endl;
    else
      cout << "consonant" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 100100;
ll a[N];
int n;
ll b[N], c[N];

void update(int v) {
	bool ch = false;
	if (v > 0) {
		ll x = 2 * c[v - 1] - a[v];
		if (x < c[v]) {
			c[v] = x;
			ch = true;
		}
	}
	if (v < n) {
		ll x = a[v + 1] + c[v + 1];
		if (x < c[v]) {
			c[v] = x;
			ch = true;
		}
	}
	if (ch) {
		if (v > 0) update(v - 1);
		if (v < n) update(v + 1);
	}
}

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 0; i <= n; i++)
		scanf("%lld", &a[i]);

	if (n == 0) {
		if (a[0] == 1) {
			printf("1\n");
		} else {
			printf("-1\n");
		}
		return 0;
	}
	if (a[0] != 0) {
		printf("-1\n");
		return 0;
	}
	b[n] = c[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		b[i] = (a[i + 1] + b[i + 1] + 1) / 2;
		c[i] = a[i + 1] + c[i + 1];
		assert(b[i] <= c[i]);
	}
	for (int i = 0; i <= n && i <= 60; i++) {
		c[i] = min(c[i], (1LL << i) - a[i]);
	}
	for (int i = 0; i <= n; i++)
		update(i);
	for (int i = n; i >= 0; i--) {
		if (c[i] < b[i]) {
			printf("-1\n");
			return 0;
		}
	}

//	for (int i = 0; i <= n; i++)
//		eprintf("%lld %lld %lld\n", a[i], b[i], c[i]);

	ll ans = 0;
	for (int i = 0; i <= n; i++)
		ans += a[i] + c[i];
	printf("%lld\n", ans);

	return 0;
}


Measured memory_bytes: 5600
#include<bits/stdc++.h>    
using namespace std;
#define ll long long 
#define pi pair<int,int>
#define pb push_back
#define inf 1e16
#define mod 1000000007
#define en '\n'
int pw(int a, int b){
	int ans = 1;
	while(b){
		if(b&1)ans = (ans*a)%mod;
		a = (a*a)%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n;cin>>n;
	ll arr[n];
	bool ref[n+1];memset(ref,0,sizeof ref);
	for(int i = 0 ; i < n ; i ++ ){
		cin>>arr[i];
		if(arr[i]==1)ref[arr[i]]=true;
		else {
			if(ref[arr[i]-1])ref[arr[i]]=true;
		}
	}
	ll mx = 0 ;
	for(int i = 1 ; i <= n ; i ++ )mx=(ref[i]?i:mx);
	if(mx==0){
		cout<<-1<<en;
		return 0;
	}
	cout<<n-mx<<en;
	return 0 ; 
}



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

#define INIT_CAP 1000

typedef struct Cell {
    int data;
    struct Cell* next;
} Cell;

typedef struct LinkedList {
    struct Cell* tail;
    struct Cell* head;
} LinkedList;

Cell* newCell (int x) {
    Cell* cell = malloc(sizeof(Cell));
    cell->data = x;
    cell->next = NULL;
    return cell;
}

void freeCell (Cell* cell) {
    free(cell);
}

void l_init(LinkedList *l) {
    l->tail = NULL;
    l->head = NULL;
}

void l_reset(LinkedList *l) {
    l_init(l);
}

void l_append(LinkedList *l, int x) {
    if (l->head == NULL) {
        l->tail = newCell(x);
        l->head = l->tail;
        return;
    }
    
    l->head->next = newCell(x);
    l->head = l->head->next;
}

void insert(LinkedList *l, int x) {
    l_append(l, x);
}

void dump(LinkedList *l) {
    Cell *cell = l->tail;
    if (cell == NULL) {
        printf("\n");
        return;
    }
    
    int space = 0;
    while (cell != NULL) {
        if (space) printf(" ");
        printf("%d", cell->data);
        cell = cell->next;
        space = 1;
    }
    printf("\n");
}

void splice(LinkedList *s, LinkedList *t) {
    if (s->head == NULL) return;
    
    if (t->head == NULL) {
        t->head = s->head;
        t->tail = s->tail;
    }
    else {
        t->head->next = s->tail;
    }
    
    t->head = s->head;
    
    l_reset(s);
}

void test () {
    LinkedList s, t;
    l_init(&s);l_init(&t);
    
    insert(&s, 10);
    insert(&s, 0);
    insert(&s, -10);
    dump(&s);
    dump(&s);
    insert(&t, 200);
    insert(&t, -2000);
    insert(&t, -20);
    splice(&s, &t);
    dump(&s);
    dump(&t);
}

int main(void){
    //test();return 0;
    int n, q, query, t, x;
    char arr[20];
    FILE *fp;
    fp = stdin;
    fgets(arr, 20, fp);
    sscanf(arr, "%d %d", &n, &q);
    
    LinkedList V[n];
    for (int i=0; i<n; i++) {
        LinkedList v;
        l_init(&v);
        V[i] = v;
    }
    
    while (q--) {
        fgets(arr, 20, fp);
        sscanf(arr, "%d %d %d", &query, &t, &x);
        switch (query) {
            case 0:
                insert(&V[t], x);
                break;
            case 1:
                dump(&V[t]);
                break;
            case 2:
                splice(&V[t], &V[x]);
                break;
            default:
                printf("Invalid query: %d", query);
                exit(1);
        }
    }
}



Measured memory_bytes: 17348
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k,a,b,ans,l,r,sl,sr;
int main()
{
	cin>>k>>a>>b;
	if(a>=b||k<=a||b==a+1){cout<<k+1<<endl;return 0;}
	ans=a,k-=a-1;
	if(k%2)k--,ans++;
	ans+=k/2*(b-a);
	cout<<ans<<endl;
}

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

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };
int mp[2048][2048];
int main(){
    int w,h,n;
    while(cin>>w>>h && w){
        cin>>n;
        int pos[1000][4];
        vector<int> x_comp,y_comp;

        for(int i=0;i<n;i++){
            cin>>pos[i][0]>>pos[i][1]>>pos[i][2]>>pos[i][3];
            for(int j=-1;j<=1;j++){
                int tmp1=pos[i][0]+j;int tmp2=pos[i][2]+j;
                if(tmp1>=0 && tmp1<w) x_comp.push_back(tmp1);
                if(tmp2>=0 && tmp2<w) x_comp.push_back(tmp2);
                tmp1=pos[i][1]+j;tmp2=pos[i][3]+j;
                if(tmp1>=0 && tmp1<h) y_comp.push_back(tmp1);
                if(tmp2>=0 && tmp2<h) y_comp.push_back(tmp2);
            }
        }
        sort(x_comp.begin(),x_comp.end());
        x_comp.erase(unique(x_comp.begin(),x_comp.end()),x_comp.end());
        sort(y_comp.begin(),y_comp.end());
        y_comp.erase(unique(y_comp.begin(),y_comp.end()),y_comp.end());

        w = x_comp.size();
        h = y_comp.size();

        for(int i=0;i<n;i++){
            pos[i][0] =distance(x_comp.begin(),lower_bound(x_comp.begin(),x_comp.end(),pos[i][0]));
            pos[i][2] =distance(x_comp.begin(),lower_bound(x_comp.begin(),x_comp.end(),pos[i][2]));
            pos[i][1] =distance(y_comp.begin(),lower_bound(y_comp.begin(),y_comp.end(),pos[i][1]));
            pos[i][3] =distance(y_comp.begin(),lower_bound(y_comp.begin(),y_comp.end(),pos[i][3]));
        }

        memset(mp,0,sizeof(mp));
        for(int i=0;i<n;i++){
            for(int j=pos[i][1];j<pos[i][3];j++){
                for(int k=pos[i][0];k<pos[i][2];k++) mp[j][k] = 1;
            }
        }

        int ans = 0;
        for(int i=0;i<h;++i){
            for(int j=0;j<w;++j){
                if(!mp[i][j]){
                    ++ans;
                    queue<pair<int,int> > q;
                    q.push(pair<int,int>(i,j));
                    mp[i][j]=1;
                    while(!q.empty()){
                        pair<int,int> pos=q.front();q.pop();
                        for(int k=0;k<4;++k){
                            int tx=pos.second+dx[k];
                            int ty=pos.first+dy[k];
                            if(tx>=0&&tx<w&&ty>=0&&ty<h&&!mp[ty][tx]){
                                q.push(pair<int,int>(ty,tx));
                                mp[ty][tx]=1;
                            }
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)


bool evenStr(string s){
  forll(i, 0, s.size() / 2){
	if(s[i] != s[i + s.size()/2])
	  return false;
  }
  return true;
}


int main()
{
  string s;
  cin >> s;
  ll k = s.size() / 2;
  forll(i, 0, k){
	s.pop_back();
	s.pop_back();
	if (evenStr(s))
	  break;
  }
  cout << s.size() << endl;	
}


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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N; cin >> N;
	string str; cin >> str;
	set<int> R,W;
	forn(i,0,N){
		if(str[i] == 'R')R.insert(i);
		else W.insert(i);
	}
	int res = min(R.size(),W.size());
	int tmp = 0;
	forn(i,0,N){
		if(R.count(i)){
			R.erase(i);
			res = min(res,tmp+(int)R.size());
			//cout << i << ' ' << tmp << ' ' << R.size() << '\n';
		}else{
			if(R.empty()){
				tmp++;
				res = min(res,tmp);
				//cout << i << ' ' << tmp << ' ' << R.size() << '\n';
			}else{
				tmp++;
				auto it = R.rbegin();
				R.erase(*it);
				res = min(res,tmp+(int)R.size());
				//cout << i << ' ' << tmp << ' ' << R.size() << '\n';
			
			}
		}
	}
	cout << res << '\n';
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;


class UnionFind {
public:
    //親の番号を格納する。親だった場合は-(その集合のサイズ)
    vector<int> Parent;
    //つくるときはParentの値をすべて-1にする
    //こうするとすべてバラバラになる
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//親をとってきたい
    }
    //AとBをくっつける
    bool connect(int A, int B){
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if(A == B) {
            //すでにくっついてるからくっつけない
            return false;
        }
        //大きい方（A）に小さいほう（B）をくっつけたい。
        //大小が逆だったらひっくり返しちゃう。
        if(size(A)<size(B)) swap(A,B);

        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;

        return true;
    } 
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin>>n>>m;
    vector<int> x(m), y(m), z(m);
    REP(i,m) cin>>x[i]>>y[i]>>z[i];
    UnionFind U(n);
    vector<bool> bo(n,false);
    REP(i,m){
        U.connect(x[i]-1 , y[i]-1);
    }
    REP(i,n){
        bo[U.root(i)] = true;
    }
    int cnt = 0;
    REP(i,n){
        if(bo[i]==true) cnt++;
    }
    print(cnt);
    return 0;
}

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

class Mainclass 
{
    static void Main()
    {
        int[] A = new int[] {1,3,5,7,8,10,12};
        int[] B = new int[] {4,6,9,11};
        int[] z = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
        if (A.Contains(z[0]) && A.Contains(z[1]))
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine(B.Contains(z[0]) && B.Contains(z[1])?"Yes":"No");
        }
    }
}

Measured memory_bytes: 27740
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 100000007;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
int main() {
	int n, m, s, g1, g2;
	while (cin >> n >> m >> s >> g1 >> g2, n) {
		s--; g1--; g2--;
		int d[100][100];
		rep(i, 100) {
			rep(j, 100) {
				d[i][j] = (int)MOD;
				if (i == j)d[i][j] = 0;
			}
		}
		rep(i, m) {
			int x, y, z; cin >> x >> y >> z; x--; y--;
			d[x][y] = min(d[x][y], z);
		}
		rep(k, n) {
			rep(i, n) {
				rep(j, n) {
					d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
				}
			}
		}
		int mi = (int)MOD;
		rep(i, n) {
			mi = min(mi, d[s][i] + d[i][g1] + d[i][g2]);
		}
		cout << mi << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <cmath>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;
#define INF 1000000007
#define ll long long
#define rep(i_, start, end) for(ll i_=(ll)start; i_<(ll)end; i_++)
#define print(a) cout << a << endl;
#define printarray(a, len) rep(ii,0,len) cout << a[ii] << " ";
#define printarray2(aa, len) rep(ij,0,len) printarray(aa[ij], aa[ij].size()); print("");

vector<ll> tree[100001];
ll length[100001];

void dfs(ll cur, ll pre, ll len){
  ll now = len;
  for(ll i=0; i<tree[cur].size(); i+=2){
    ll x = tree[cur][i];
    if (x != pre){
      len += tree[cur][i+1];
      length[x] += len;
      dfs(x, cur, len);
    }
    len = now;
  }
}

int main(){
  ll n, u, v, w;
  cin >> n;
  ll color[100001];
  rep(i, 0, n-1){
    cin >> u >> v >> w;
    tree[u].push_back(v);
    tree[u].push_back(w);
    tree[v].push_back(u);
    tree[v].push_back(w);
  }
  /*
  rep(i, 1, n+1){
    rep(j, 0, tree[i].size()){
      cout << tree[i][j] << " ";
    }
    print("");
  }
  */
  dfs(1, -1, 0);
  /*
  rep(i, 1, n+1){
    cout << length[i] << " ";
  }
  */
  rep(i, 1, n+1){
    if (length[i] % 2 == 0){
      print(0);
    }else{
      print(1);
    }
  }
  
  return 0;
}

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

int main(){
  ll a,b,c;
  cin >> a >> b >> c;
  string ans = "No";
  if(c-a-b >0 && (c-b-a)*(c-b-a) > 4*a*b) ans = "Yes";
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let n: usize = parse!(it);
    let a: Vec<i64> = parse!(it, n);
    let mut positive = true;
    let mut retall = std::i64::MAX;
    for &positive in &[true, false] {
        let mut positive = positive;
        let mut ret = 0;
        let mut cur = 0;
        for i in 0..a.len() {
            let di = if positive && a[i] + cur < 1 {
                1 - cur - a[i]
            } else if !positive && a[i] + cur > -1 {
                -1 - cur - a[i]
            } else {
                0
            };
            ret += di.abs();
            cur += a[i] + di;
            positive = !positive;
        }
        retall = std::cmp::min(ret, retall);
    }

    println!("{}", retall);
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 6396
#include<stdio.h>
int main()
{
  int n,s,i,k,t,max,min;
  while(1){
    max=0;
    min=500;
  scanf("%d",&n);
  if(n==0)break;
  for(i=1;i<=n;i++){
    t=0;
    for(k=0;k<5;k++){
      scanf("%d",&s);
      t=t+s;
    }
    if(t>max)max=t;
    if(t<min)min=t;
  }
  printf("%d %d\n",max,min);
  }
  return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	lint N;
	cin >> N;

	lint h = 0;
	for (lint Ncopy = N; Ncopy != 0; Ncopy /= 10)
	{
		h += Ncopy % 10;
	}

	if (N % h == 0)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}

	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}

Measured memory_bytes: 256
/*****************************
*  Author :: Prasanna Kumar  *
*****************************/

/***********************************
* Unus pro omnibus, omnes pro uno  *
***********************************/
#include<bits/stdc++.h>
using namespace std;

// #define __AnAkLuSmOs freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define __AcHiLlEs ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define i_64 long long

void solve() {
    int res, x;
    for (int i = 0; i < 5; i++) {
        cin >> x;
        if (x == 0) res = i + 1;
    }
    cout << res << "\n";
}

signed main() {
    // #ifndef ONLINE_JUDGE 
    //     __AnAkLuSmOs    
    // #endif

    __AcHiLlEs

    i_64 t(1);
    // cin >> t;
    for (i_64 i = 1; i <= t; /*cout << "Case " << i << ": ",*/ solve(), i++);
    return 0;
}
    

Measured memory_bytes: 3592
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;

namespace C_test_For_Atcorder
{

    public static class Extensions
    {
        public static string Reverse(this string sourse){
            char[] chrAry = sourse.ToCharArray();
            Array.Reverse(chrAry);
            return new string(chrAry);
        }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }


        public void Solve(ConsoleInput cin)
        {
            var A = cin.ReadInt;
            var B = cin.ReadInt;
            var C = cin.ReadInt;
            var D = cin.ReadInt;
            Console.WriteLine(Min(A,B)+Min(C,D));
            return;

        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue inputStream;

        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return (string)inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return (string)inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
    }

}


Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#include<string>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn=1e5+4;
int main(){
    int n;
    while(cin>>n){
    	int dep=1;
    	while(dep*10<=n)
    		dep*=10;
    	while(n){
    		int t=n/dep;
    		if(t==9)
    			t=1;
    		else if(t==1)
    			t=9;
    		cout<<t;
    		n%=dep;
    		dep/=10;
		}
		cout<<endl;
	}
}

Measured memory_bytes: 256
import java.io.*;

public class Main{
	public static void main(String[] atgs){
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		try{
			String line = reader.readLine();
			int num = Integer.parseInt(line);
			System.out.println(num * num * num);
		}catch(IOException e){
			System.out.println(e);
		}catch(NumberFormatException e){
			System.out.println("入力できる型はInt型に限ります");
		}
	}
}


Measured memory_bytes: 24296
#include<stdio.h>
#include<algorithm>
#include<bitset>
std::bitset<25010001>f;
struct P{int x,y;P(){}P(int x,int y):x(x),y(y){}}a[3000];
int G(P x){return x.x*5001+x.y;}
int F(P x)
{
	return x.x>=0&&x.y>=0&&x.x<5001&&x.y<5001&&f[G(x)];
}
int E(P p,P d)
{
	if(F(p)&&F(P(p.x+d.x,p.y+d.y)))
		return d.x*d.x+d.y*d.y;
	return 0;}
int main()
{
	int n,i,j,r;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)scanf("%d%d",&a[i].x,&a[i].y),f[G(a[i])]=1;
		for(r=i=0;i<n;++i)for(j=i+1;j<n;++j)
		{
			P d(a[j].x-a[i].x,a[j].y-a[i].y);
			r=std::max(r,E(P(a[i].x-d.y,a[i].y+d.x),d));
			r=std::max(r,E(P(a[i].x+d.y,a[i].y-d.x),d));
		}
		printf("%d\n",r);
		f.reset();
	}
	return 0;
}

Measured memory_bytes: 3840
#include <iostream>
    #include <vector>
    #include <set>
    #include <algorithm>
    #include <bits/stdc++.h>
    #define rep(i,n) for (int i = 0; i < (n); ++i)
    using namespace std;
    typedef long long ll;
    typedef pair<int,int> P;
     
    int main(){
        int n,k,q;
        cin >> n>>k>>q;
      vector<int> v(n);
      rep(i,n){
      	v[i]=k;
      }
      int a;
      rep(i,q){
      cin >>a;
        v[a-1]++;
      }
      rep(i,n){
      	v[i]-=q;
      }
      rep(i,n){
     //   cout << v[i] <<endl;
      if(v[i]>0){
      	cout << "Yes"<<endl;
      }else{
      cout << "No" <<endl;
      }
      }
    }

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

#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    map<string,int> mp;
    int n;
    cin >> n;
    int m  = 0;
    rep(i,0,n){
        string tmp;
        cin >> tmp;
        auto itr = mp.find(tmp);
        if(itr != mp.end()){
            mp[tmp]++;
            m = max(m,mp[tmp]);
        }else{
            mp[tmp] = 1;
            m = max(m,mp[tmp]);
        }
    }
    vector<string> ans;
     for(auto itr = mp.begin(); itr != mp.end(); ++itr){
         if(itr->second == m) ans.push_back(itr->first);
     }
     sort(all(ans));
     rep(i,0,ans.size()){
         cout << ans[i] << endl;
     }
}

Measured memory_bytes: 26224
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x , a , b;
    cin  >> x >> a >> b;
    cout << ( x - a ) % b;
}


Measured memory_bytes: 3580
#include<iostream>
#include<vector>

int n,m,count=0;
std::vector<std::vector<char> >v;

void dfs(int x,int y,char c){
	v[y][x]=0;
	if(y-1>=0 && v[y-1][x]==c)dfs(x,y-1,c);
	if(y+1<=n-1 && v[y+1][x]==c)dfs(x,y+1,c);
	if(x-1>=0 && v[y][x-1]==c)dfs(x-1,y,c);
	if(x+1<=m-1 && v[y][x+1]==c)dfs(x+1,y,c);
}

int main(){
	std::cin>>n>>m;
	while(!(n==0&&m==0)){
		count=0,v.clear();
		for(int i=0;i<n;i++){
			v.push_back(std::vector<char>());
			for(int j=0;j<m;j++){
				char a;
				std::cin>>a;
				v[i].push_back(a);
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(v[i][j]!=0)dfs(j,i,v[i][j]),count++;
			}
		}
		std::cout<<count<<std::endl;
		std::cin>>n>>m;
	}
	return 0;
}

Measured memory_bytes: 1704
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true) {
            String s = sc.next();
            if(s.length() == 1 && s.charAt(0) == '0') break;
            int sum = 0;
            for(int i = 0; i < s.length(); i++) {
                int x = s.charAt(i) - 48;
                sum += x;
            }
            System.out.println(sum);
        }
    }
}


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

int main() {
  int sx,sy,tx,ty;
  cin>>sx>>sy>>tx>>ty;
  for(int i=0;i<ty-sy;i++){
    cout<<"U";
    }
  for(int i=0;i<tx-sx;i++){
    cout<<"R";
    }
  for(int i=0;i<ty-sy;i++){
    cout<<"D";
    }
  for(int i=0;i<tx-sx;i++){
    cout<<"L";
    }
  cout<<"L";
  for(int i=0;i<ty-sy+1;i++){
    cout<<"U";
    }
  for(int i=0;i<tx-sx+1;i++){
    cout<<"R";
    }
  cout<<"D";
  cout<<"R";
  for(int i=0;i<ty-sy+1;i++){
    cout<<"D";
    }
  for(int i=0;i<tx-sx+1;i++){
    cout<<"L";
    }
  cout<<"U"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string str;
int main()
{
    cin>>str;
    for(int i=0;i<3;i++)
        if(str[i]=='7')
        {
            printf("Yes\n");
            return 0;
        }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[10], c[10];
bool check(int x){
    vector<int>xs;
    if(x==0) 
	xs.push_back(0);
    	else{
    		while(x) {
            	xs.push_back(x%10);
        			x/=10;
        		}
    		}
    	if (xs.size()!=n) 
			return false;
    	for (int i=0;i<m;i++) {
        	if (xs[n-s[i]]!=c[i]) 
				return false;
    		}
    	return true;
	}
int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++) 
	cin>>s[i]>>c[i];
    for(int i=0;i<1000;i++) {
        if(check(i)) {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"-1"<<endl;
    return 0;
}

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

void travelFar(int index,vector<vector<int>> &edges, vector<ll int> &maxTravel){

    if(maxTravel[index-1] != -1){
        return;
    }

    ll int maxDist = 0;


    // Loop thr direct connections of i vertex
    for (int i = 0; i < edges[index-1].size(); i++)
    {
        //cout << index << "-" << maxTravel[edges[index-1][i] - 1] << endl;
        if(maxTravel[edges[index-1][i] - 1] == -1){
            travelFar(edges[index-1][i], edges, maxTravel);
        }
        maxDist = max(maxDist, 1+maxTravel[edges[index-1][i] - 1]);
    }
    maxTravel[index-1] = maxDist;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<int> tempv;
    vector<vector<int>> edges(n, tempv);

    int xi, yi;
    for (int i = 0; i < m; i++)
    {
        cin >> xi >> yi;
        edges[xi-1].emplace_back(yi);
    }

    vector<ll int> maxTravel(n,-1);
    for (int i = 0; i < n; i++)
    {
        if(maxTravel[i] == -1){
            travelFar(i+1, edges, maxTravel);
        }
    }
    
    cout << *max_element(maxTravel.begin(), maxTravel.end());
    cout << endl;
}

Measured memory_bytes: 9984
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pre = 0
ans = 0
for i, a in enumerate(A):
    if i == N:
        ans += min(pre, a)
        break
    if a <= pre:
        ans += a
        pre = B[i]
    elif pre < a < pre + B[i]:
        ans += a
        pre = B[i]+pre - a
    else:
        ans += pre + B[i]
        pre = 0

print(ans)

Measured memory_bytes: 19116