akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{fastout, input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize, k: usize,
        mut a: [i64; n],
    }
    let m = 1000000007i64;
    let mod_product = |acc: i64, &value: &i64| {
        (acc * value).rem_euclid(m)
    };

    if k == n || k % 2 == 1 && a.iter().all(|v| *v <= 0) {
        a.sort_by_key(|v| -*v);
        let ans = a.iter().take(k).fold(1, mod_product);
        println!("{}", ans);
        return;
    }

    a.sort_by_key(|v| Reverse(v.abs()));
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for i in 0..n {
        if a[i] >= 0 {
            plus.push(a[i]);
        } else {
            minus.push(a[i]);
        }
    }

    let mut ppos = 0;
    let mut mpos = 0;
    let mut vals = Vec::new();
    let mut retry = false;
    while vals.len() < k {
        if vals.len() < k - 1 && ppos + 1< plus.len() && mpos + 1 < minus.len() {
            if plus[ppos] * plus[ppos+1] < minus[mpos] * minus[mpos+1] {
                vals.push(minus[mpos]);
                vals.push(minus[mpos+1]);
                mpos += 2;
            } else {
                vals.push(plus[ppos]);
                ppos += 1;
            }
        } else if vals.len() < k - 1 && mpos + 1 < minus.len() {
            vals.push(minus[mpos]);
            vals.push(minus[mpos+1]);
            mpos += 2;
        } else if ppos < plus.len() {
            vals.push(plus[ppos]);
            ppos += 1;
        } else {
            retry = true;
            break;
        }
    }
    let ans = if !retry {
        vals.iter().fold(1, mod_product)
    } else {
        panic!()
    };
    println!("{}", ans);
}


Measured memory_bytes: 9800
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def main():
    x = int(input())

    sosuu_list = []
    for i in range(2, int(x ** 0.5) + 1):
        flg = 1
        for ele in sosuu_list:
            if i % ele == 0:
                flg = 0
                break
        if flg:
            sosuu_list.append(i)

    while 1:
        flg = 0
        for ele in sosuu_list:
            if x % ele == 0:
                flg = 1
                break
        if flg:
            x += 1
        else:
            break

    print(x)


if __name__ == '__main__':
    main()



Measured memory_bytes: 63212
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    int ans=0 , n=s.length();
    rep(i,0,n){
        if(s[i]-'0'!=i%2) ans++;
    }
    int res=0;
    rep(i,0,n){
        if(s[i]-'0'!=(i+1)%2) res++;
    }
    cout << min(ans,res)<<"\n";
}

Measured memory_bytes: 512
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)

int main()
{

  int MAX = 100010;
  vector<int> is_prime(MAX, 1);
  is_prime[0] = 0;
  is_prime[1] = 0;
  for (int i = 2;i<MAX;i++){
    if(!is_prime[i])continue;
    for (int j = i * 2; j < MAX;j+=i)is_prime[j]=0;
  }

  vector<int> a(MAX, 0);
  for (int i = 0;i<MAX;i++){
    if(i%2==0)continue;
    if(is_prime[i]&&is_prime[(i+1)/2])a[i]=1;
  }

  vector<int> s(MAX + 1, 0);
  for (int i = 0;i<MAX;i++)s[i+1]=s[i]+a[i];

  int q;
  cin >> q;
  for (int i = 0;i<q;i++){
    int l, r;
    cin >> l >> r;
    cout << s[r + 1] - s[l] << endl;
  }

  return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define fs first
#define se second
#define pb push_back
using namespace std;

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

const int maxn=2e3+5;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll num[maxn];
int main(){
	int n,x,y;
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int dis=j-i;
			dis=min(dis,abs(x-i)+abs(j-y)+1);
			num[dis]++;
		}
	}
	for(int i=1;i<n;i++){
		printf("%lld\n",num[i]);
	}
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0138

"""
import sys
from sys import stdin
from operator import itemgetter
input = stdin.readline

def solve(data):
    data.sort(key=itemgetter(1))
    top2 = data[:2]
    others = data[2:]
    return top2, others         #  ??????2?????¨????????\??????id??¨?????????????????????


def main(args):
    others_results = []
    for _ in range(3):
        round_results = []
        for _ in range(8):
            id, time = input().split()
            round_results.append([int(id), float(time)])
        top2, others = solve(round_results)
        others_results.extend(others)

        # ????????????2???????????±
        for id, time in top2:
            print('{} {}'.format(id, time))

    # ????????????3?????\?????????????????????2???????????±
    top2, others = solve(others_results)
    for id, time in top2:
        print('{} {}'.format(id, time))


if __name__ == '__main__':
    main(sys.argv[1:])

Measured memory_bytes: 7752
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n = get_int()
    a = get_int()
    b = get_int()
    c = get_int()
    d = get_int()
    e = get_int()
    m = min(a, b, c, d, e)
    print(5 + (n + m - 1) // m - 1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


Measured memory_bytes: 5336
n=int(input())
ans=0
for i in range(1,n+1):
    count=0
    if(i%2==1):
        for j in range(1,i+1):
            if(i%j==0):
                count+=1
            else:
                continue
        if(count==8):
            ans+=1
        else:
            continue
    else:
        continue
print(ans)

Measured memory_bytes: 3060
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

signed main(){
    int n;
    cin >> n;
    rep(i, n){
        int a, b;
        cin >> a >> b;
        if(a > b){
            swap(a, b);
        }

        if(b - a <= 1){
            cout << a * 2 - 2 << endl;
            continue;
        }

        int left = 1;
        int right = 1e9;
        while(right - left > 1){
            int mid = left + (right - left) / 2;
            if(mid * mid < a * b){
                left = mid;
            }else{
                right = mid;
            }
        }
        if(left * (left + 1) >= a * b){
            cout << left * 2 - 2 << endl;
            continue;
        }

        cout << left * 2 - 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool used[200];
int main()
{
    int n,d;
    cin>>n>>d;
    int ind=d+1,ans=0;
    while(ind<=n)
    {
        ans++;
        for(int i=ind;i>0 && i>=ind-d;i--)
            used[i]=true;
        for(int i=ind;i<=n && i<=ind+d;i++)
            used[i]=true;
        ind+=2*d+1;
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i]==false)
        {
            ans++;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
#define inf 1000000000
using namespace std;
int n;
ll sum,mn,a;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();sum=0;mn=inf;
    for(int i=1;i<=n;i++){
        a=read();sum+=a;
        if(a%10!=0)mn=min(mn,a);
    }
    if(sum%10==0){
        if(mn==inf)sum=0;else sum-=mn;
    }
    printf("%lld\n",sum);
    return 0;
}


Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;

int main(){
    int K,N,a,b,max=0,val;
    cin>>K>>N;
    vector<int> vec(N);
    for(int i=0;i<N;i++){
        cin>>vec.at(i);
    }
    a=vec.at(N-1)-vec.at(0);
    for(int i=0;i<(N-1);i++){
        val=vec.at(i+1)-vec.at(i);
        if(val>max)max=val;
    }
    b=K-max;
    if(a<=b){
        cout<<a<<endl;
    }else{
        cout<<b<<endl;
    }
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
   int i, j, k,a;
for (a=1 ;a<300;a++) {
        int n,x,y=0;
   scanf("%d",&n);
   scanf("%d",&x);
   if(n==0&&x==0)break;
for ( i=1 ;i<n;i++) {
   for ( j=i+1;j<n;j++) {
       for ( k=j+1;k<=n;k++){
   if(i+j+k==x){
       y=y+1;
     }
       }
   }
}
       printf("%d\n",y);
}
}



Measured memory_bytes: 2680
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct point
{
	ll x;
	ll y;
}p[N];
bool cmp(point a,point b)
{
	return atan2(a.x,a.y)<atan2(b.x,b.y);
}
int main()
{
	int n;	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&p[i].x,&p[i].y);
	int nx[N];
	for(int i=1;i<=n;i++)
		nx[i]=i+1; nx[n]=1;
	sort(p+1,p+1+n,cmp);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		ll x=p[i].x;
		ll y=p[i].y;
		ans=max(ans,x*x+y*y);
		for(int j=nx[i];j!=i;j=nx[j])
		{
			x=x+p[j].x;
			y=y+p[j].y;
			ans=max(ans,x*x+y*y);
		} 
	}
	printf("%.10lf\n",sqrt(ans));
	return 0;
} 

Measured memory_bytes: 768
#include<algorithm>
#include <iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<string>
using namespace std;
int main() {

	int k;
	cin >> k;

	int w, i;
	w = 0;
	for (i = 2; i <= k; i++) {
		w += i / 2;
	}


	cout <<w<< endl;


	return 0;
}

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

using namespace std;

typedef long long ll;

int main() {
  string s; cin >> s;
  int ans = 0;
  int n = s.length();
  for(int i = 0; i < n / 2; i++) {
    if(s[i] != s[n - i - 1]) ans++;
  }
  cout << ans << '\n';
}



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

using namespace std;

int main() {
    int t,m,n,a,b,c,d;
    a=b=c=d=0,t=3;
    while(t--){
     cin>>m>>n;
     if(m==1)
      a++;
     else if(m==2)
      b++;
     else if(m==3)
      c++;
     else
      d++;
     if(n==1)
      a++;
     else if(n==2)
      b++;
     else if(n==3)
      c++;
     else
      d++;
    }
    if(a==3 || b==3 || c==3 || d==3)
     cout<<"NO"<<endl;
    else
    cout<<"YES"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define flash ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define all(v) (v).begin(),(v).end() 
#define endl "\n"
#define int long long int
#define ll long long
#define ld long double
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<bool> vb;
const int mod = 1000000007;
const int N=200005;
const int inf=1e18;
vector<vector<int>>adj(N);

bool isprime(int n){for(int i=2;i*i<=n;++i){if(n%i==0){return false;}}return true;}
int factorial(int n){return (n==1 || n==0) ? 1:n*factorial(n-1);} 
int gcd(int a,int b){if (a==0)return b;return gcd(b%a,a);}
int lcm(int a,int b){return (a/gcd(a,b)*b);}
int max(int a,int b){int sol=a>b?a:b;return sol;}
int min(int a,int b){int sol=a<b?a:b;return sol;} 

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


signed main(){
    flash;
    fun();
    int t=1;
    //cin>>t;
    while(t--){
        int n;
        cin>>n;
        int cnt=0;
        while(n>1){
            n/=2;
            cnt++;
        }
        cout<<pow(2,cnt);
    }
    return 0;
}

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

void printList(int num[], int n){
	for (int i = 0; i < n; i++){
		cout << num[i];
		if (i != n-1) cout << ' ';
	}
	cout << endl;
}

void insertSort(int num[], int n){
	int tmp;
	int j;
	for (int i = 1; i < n; i++){
		tmp = num[i];
		j = i - 1;
		while (j >= 0 && num[j] > tmp){
			num[j+1] = num[j];
			j--;
		}
		num[j+1] = tmp;
		printList(num, n);
	}
}

int main(){
	int n[100];
	int limit;
	cin >> limit;
	for (int i = 0; i < limit; i++){
		cin >> n[i];
	}
	printList(n, limit);
	insertSort(n, limit);
//	printList(n, limit);
	return 0;
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using  namespace std;
#define ll long long
int main()
{
  	ll n;
  	cin>>n;
  	ll a[n];
  	ll i;
  	for(i=0;i<n;i++)
    {
      	cin>>a[i];
    }
  	ll x=a[0];
  	for(i=1;i<n;i++)
    {
      	x=x^a[i];
    }
  	if(x==0) cout<<"Yes\n";
  	else cout<<"No\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i, s, n) for (int i = s; i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define MOD 1000000007
using namespace std;
using ll = long long;

int main() {
    int N; cin >> N;
    vector<int> A(N), B(N);
    REP(i, 0, N) cin >> A[i] >> B[i];

    sort(ALL(A));
    sort(ALL(B));

    if (N % 2 == 1) {
        cout << B[N / 2] - A[N / 2] + 1 << endl;
    } else {
        ll a = (A[N / 2] + A[N / 2 - 1]);
        ll b = (B[N / 2] + B[N / 2 - 1]);
        cout << b - a + 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;
int main(){
string S;
  cin>>S;
  
  int min=642;
  
  
  for(int i=0;i<S.size()-2;i++){
    int X=(S.at(i)-'0')*100+(S.at(i+1)-'0')*10+(S.at(i+2)-'0')-753;
    if(X>0&&min>X){
      min=X;
    }
    else if(X<0&&min>-X){
      min=-X;
    }
    else if(X==0){
     min=0;
    }
  }
  cout<<min<<endl;
}

  
    

 


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
#include <numeric>
#include <list>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
#define show(a, n) rep(i,n) {cout<<a[i]<<' ';} cout<<endl
#define show2(a, n, m) rep(i, n) { rep(j, m) {cout << a[i][j] << ' ';} cout << endl;} 
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef long double ld;

const int INF = 1 << 30;
const long long INFL = 1LL << 60;
const int MOD = 1000000007;
const int MAX = 100000;
const int N = 100010;

struct mint {
	ll x;
	mint(ll x=0):x((x%MOD+MOD)%MOD){}
	mint operator-() const { return mint(-x);}
	mint& operator+=(const mint a) {if ((x+=a.x)>=MOD) x-=MOD; return *this;}
	mint& operator-=(const mint a) {if ((x+=MOD-a.x)>=MOD) x-=MOD; return *this;}
	mint& operator*=(const mint a) {(x*=a.x)%=MOD; return *this;}
	mint operator+(const mint a) const {mint res(*this); return res+=a;}
	mint operator-(const mint a) const {mint res(*this); return res-=a;}
	mint operator*(const mint a) const {mint res(*this); return res*=a;}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
 		return a;
	}

	// for prime mod
	mint inv() const { return pow(MOD-2);}
	mint& operator/=(const mint a) { return (*this) *= a.inv();}
	mint operator/(const mint a) const {mint res(*this); return res/=a;}
};

vector<vi> g;
vi par, cnt;

void set_par(int node) {
	for(auto i: g[node]) {
		if(par[i] != -1) continue;
		par[i] = node;
		set_par(i);
	}
}

int set_cnt(int node) {
	cnt[node] = 1;
	for(auto i: g[node]) {
		if(i == par[node]) continue;
		cnt[node] += set_cnt(i);
	}
	return cnt[node];
}

int main() {
//	cout << fixed << setprecision(15);
	int n;
	cin >> n;
	g = vector<vi>(n);
	rep(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	par = vi(n, -1);
	par[0] = 0;
	set_par(0);

	cnt = vi(n);
	set_cnt(0);

	mint ans;
	mint b(2);
	b = b.pow(n - 1);
	rep(i, n) {
		mint tmp = b;
		tmp -= 1;	// all white
		for(auto j: g[i]) {
			if(j == par[i]) continue;
			tmp -= mint(2).pow(cnt[j]) - 1;	// subtree without parent
		}
		tmp -= mint(2).pow(cnt[0] - cnt[i]) - 1;	// subtree with parent
		ans += tmp;
	}
	b *= 2;
	ans /= b;
	cout << ans.x << endl;
}


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

int main() {
    long long a, b, c, res = 0, sum;
    cin >> a >> b >> c;
    while (!(a == b && b == c)) {
        if (a%2 || b%2 || c%2) {
            cout << res << '\n';
            return 0;
        }
        sum = (a+b+c)/2;
        a += sum-3*a/2;
        b += sum-3*b/2;
        c += sum-3*c/2;
        res++;
    }
    if (a%2 || b%2 || c%2) {
        cout << 0 << '\n';
    } else {
        cout << -1 << '\n';
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const ll MOD = (ll) 998244353;
const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

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

bool is_prime_or_one(ll a) {
    if (a == 1) return true;
    for (ll i = 2; i <= sqrt(a + 1); ++i) {
        if (a % i == 0) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20) << setiosflags(ios::fixed);
    ll a, b;
    cin >> a >> b;
    set<ll> div;
    for (ll i = 1; i <= max(sqrt(a + 1), sqrt(b + 1)); ++i) {
        if (a % i == 0) {
            if (b % i == 0) div.insert(i);
            if (b % (a / i) == 0) div.insert(a / i);
        }
    }

    int cnt = 0;

    for (auto d : div) {
        if (is_prime_or_one(d)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 512
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        s: Chars,
    }

    let mut ans: Vec<char> = Vec::new();
    for i in 0..s.len() {
        if s[i]=='0' {
            ans.push('0');
        } else if s[i]=='1' {
            ans.push('1');
        } else {
            ans.pop();
        }
    }
    for i in 0..ans.len() {
        print!("{}", ans[i]);
    }
    print!("\n");
}


Measured memory_bytes: 2160
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define maxn 2147483640
using namespace std;
int dp[420][420];
int a[50], b[50], c[50];
int main()
{
    int n, ma, mb, i, j, k;
    int ans;
    scanf("%d%d%d", &n, &ma, &mb);
    for(i = 1; i <= n; ++i)
    {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(i = 1; i <= n; ++i)
    {
        for(j = 410; j >= 0; --j)
        {
            if(j - a[i] < 0) break;
            for(k = 410; k >= 0; --k)
            {
                if(k - b[i] < 0) break;
                if(dp[j - a[i]][k - b[i]] == -1) continue;
                if(dp[j][k] == -1)
                {
                    dp[j][k] = c[i] + dp[j - a[i]][k - b[i]];
                }else
                {
                    dp[j][k] = min(dp[j - a[i]][k - b[i]] + c[i], dp[j][k]);
                }
            }
        }
    }
    ans = maxn;
    for(i = 1; i <= 400; ++i)
    {
        if(i * mb % ma != 0) continue;
        j = i * mb / ma;
        if(j > 400 || dp[i][j] == -1) continue;
        ans = min(ans, dp[i][j]);
    }
    if(ans == maxn)
    {
        printf("-1\n");
    }else
    {
        printf("%d\n", ans);
    }
    return 0;
}


Measured memory_bytes: 896
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		
		int list[] = new int[5];
		
		for(int i = 0;i < 5;i++) {
			list[i] = sc.nextInt();
		}
		Arrays.sort(list);

		for (int i = list.length; i > 1; i--) {
			System.out.print(list[i - 1] + " ");
		}
		System.out.println(list[0]);

	}

}

Measured memory_bytes: 26348
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define PI 3.14159265358979323846
using namespace std;

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    int max = (b / k) * k;
    if (a <= max) {
        cout << "OK" << endl;
    }
    else {
        cout << "NG" << endl;
    }
}

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

vector<pair<ll,int>> factorize(ll n){
    vector<pair<ll,int>> res;
    for(ll i=2; i*i <=n;i++){
        if(n%i)continue;
        res.emplace_back(i,0);
        while(n % i == 0){
            n /= i;
            res.back().second++;
        }
    }
    if(n != 1)res.emplace_back(n,1);
    return res;
}
int main(){
    ll A,B;
    cin >> A >> B;
    ll C = __gcd(A,B);
    auto v = factorize(C);
    cout << v.size() + 1 << endl;
}


Measured memory_bytes: 256
n = int(input())
h = [int(i) for i in input().split()]
c = 0
max = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        c+= 1 
    else:
        if max < c:
            max = c
        c = 0
if max < c:
    max = c
print(max)        

Measured memory_bytes: 14224
def get_num(n, x):
    ans = 0
    for n3 in xrange(min(n, x - 3), (x + 2) / 3, -1):
        for n2 in xrange(min(n3 - 1, x - n3 - 1), (x - n3 + 1) / 2 - 1, -1):
            for n1 in xrange(min(n2 - 1, x - n3 - n2), 0, -1):
                if n3 == x - n1 - n2:
                    ans += 1
                    break
    return ans


data = []
while True:
    [n, x] = [int(m) for m in raw_input().split()]
    if [n, x] == [0, 0]:
        break
    if x < 3:
        # print(0)
        data.append(0)
    else:
        # print(get_num(n, x))
        data.append(get_num(n, x))
for n in data:
    print(n)

Measured memory_bytes: 6356
import java.io.*;
import java.util.*;

class Main{

    static final int M = 1000000007;
    static final int N_MAX = 200000;
    long[]  fact;
    Scanner sc;

    void compute(int N, int H){
        int[] word = new int[N];
        boolean[] invalid = new boolean[N];

        for ( int i = 0; i < N; i++ ) word[i] = i;
        int s, t;
        for ( int i = 0; i < H; i++ ){
            s = sc.nextInt();
            t = sc.nextInt();
            s--; t--; // to 0 origin
            int tmp = word[s];
            word[s] = word[t];
            word[t] = tmp;
        }

        for ( int i = 0; i < N; i++ ) if ( word[i] != i ) invalid[i] = true;

        long ans = 0;
        ArrayList<Integer> deleted = new ArrayList<Integer>();
        ArrayList<Integer> inserted = new ArrayList<Integer>();

        for ( int i = 0; i < N; i++ ){
            long unable = Math.min(word[i], i);
            for ( int j = 0; j < deleted.size(); j++ )
                if ( deleted.get(j) < word[i] ) unable--;
            for ( int j = 0; j < inserted.size(); j++ )
                if ( inserted.get(j) < word[i] ) unable++;

            ans += ((word[i] - unable) * fact[N-i-1])%M;
            ans %= M;

            if ( invalid[i] ){
                deleted.add(i);
                inserted.add(word[i]);
            }
        }

        System.out.println(ans);
    }
 void solve(){
        fact = new long[N_MAX+1];
        fact[0] = 1;
        for ( int i = 1; i <= N_MAX; i++ ) fact[i] = (fact[i-1]*i)%M;
        sc = new Scanner(System.in);

        int N, H;
        while(true){
            N = sc.nextInt();
            if ( N == 0 ) break;
            H = sc.nextInt();
            compute(N, H);
        }
    }

    public static void main(String[] arfv){
        new Main().solve();
    }
}




Measured memory_bytes: 69944
n = int(input())
s = list(input())
ans = [i * 0 for i in range(100)]
if n == 2:
    ans.clear()
    if s[0] == s[1]:
        ans.append(1)
    else:
        ans.append(0)
else:
    for i in range(0,n-1):
        tmp1 = list(set(s[:i]))
        tmp2 = list(set(s[i:]))
        for j in range(len(tmp1)):
            if tmp1[j] in tmp2:
                ans[i] += 1
print(max(ans))


Measured memory_bytes: 3064
import numpy as np

N = int(input())
A = list(map(int, input().split()))


for i in range(len(A)):
    A[i] -= (i + 1)

np_A = np.array(A)
b = -np.median(np_A)

np_A += b.astype("i")
res = np.abs(np_A).sum()
print(res)

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

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

    int a, b;
    cin >> a >> b;
    if(a <= 9 and b <= 9){
        cout << a * b << endl;
    }else{
        cout << -1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 101
#define WHITE -1
#define GRAY -2
#define BLACK -3

int G[MAX][MAX],d[MAX],f[MAX],color[MAX];
int n,k[MAX],u,v,time;
void DFSvisit(int u){
  int i;

  color[u] = GRAY;
  time++;
  d[u] = time;


  for(i=1; i<=k[u]; i++){
    // printf("u = %d %d now -> %d\n",uu,k[uu],vv);
    if(color[G[u][i]] == WHITE) {
      //printf("%d\n",G[uu][i]);
      DFSvisit(G[u][i]);
    }
  }
  //printf("%d finished!\n",u);
  color[u] = BLACK;
  f[u] = ++time;
  //printf("f = %d\n",f[u]);
}


void DFS(){

  for(u=1; u<=n; u++){
    color[u] = WHITE;
  }
  time = 0;
  for(u=1; u<=n; u++){
 
    if(color[u]==WHITE) {
      // printf("u = %d\n",u);
      DFSvisit(u);
    }
  }
}


int main(){
  int i,j;

  scanf("%d",&n);

  for(i=1; i<=n; i++){
    scanf("%d%d",&u,&k[i]);
    for(j=1; j<=k[i]; j++){
      scanf("%d",&G[i][j]);
    }
  } 
  DFS();

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

Measured memory_bytes: 636
/*
 * author: Tran Minh Khoa
 * Ho Chi Minh University of Science
 */

#include <bits/stdc++.h>

using namespace std;

const int inf = 1 << 31;
const long long INF = 1LL << 61;

const int MOD = 1000000007;
const int N = 123456;
const int M = 1010;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) (int) a.size()
#define all(a) a.begin(), a.end()
#define sqr(x) (x) * (x)

#define REP(i, a, b) for (int i = (a); i < (b); i++)
#define REPN(i, a, b) for (int i = (a); i <= (b); i++)
#define DEBUG(x) cerr << #x << " = " << x << '\n';
#define PR(x, a, b) { cerr << #x << " = "; REP(i, a, b) cerr << x[i] << ' '; cerr << '\n'; }
                 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
  cout.precision(10); 
  cout << fixed;
#ifdef KM777
  freopen("in", "r", stdin);
#endif
  int n;
  cin >> n;
  vector<int> a(3 * n + 1);
  for (int i = 1; i <= 3 * n; i++) {
    cin >> a[i];
  }
  vector<long long> fl(3 * n + 1), fr(3 * n + 1);
  priority_queue<int> Q;
  long long sum = 0;
  for (int i = 1; i <= 3 * n; i++) {
    if (sz(Q) == n) {
      if (a[i] > -Q.top()) {
        sum = sum + Q.top() + a[i];
        Q.pop();
        Q.push(-a[i]);
      }
    } else {
      sum += a[i];
      Q.push(-a[i]);
    }
    fl[i] = sum;
  }
  sum = 0;
  while (!Q.empty()) Q.pop();
  for (int i = 3 * n; i >= 1; i--) {
    if (sz(Q) == n) {
      if (a[i] < Q.top()) {
        sum = sum - Q.top() + a[i];
        Q.pop();
        Q.push(a[i]);
      } 
    } else {
      sum += a[i];
      Q.push(a[i]);
    }
    fr[i] = sum;
  }
  long long result = -INF;
  for (int k = n; k <= 2 * n; k++) {
    result = max(result, fl[k] - fr[k + 1]);
  }
  cout << result << '\n';
#ifdef KM777
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

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

int h,A1[500001];

int left(int i){ return i*2;}
int right(int i) { return i*2+1;}

void maxHeapify(int i){
    int largest;
    int l = left(i);
    int r = right(i);
    if(l<=h && A1[l]>A1[i])
        largest = l;
    else
        largest = i;
    if(r<=h && A1[r]>A1[largest])
        largest = r;
    
    if(largest!=i){
        int tmp = A1[i];
        A1[i] = A1[largest];
        A1[largest] = tmp;
        maxHeapify(largest);
        //swap(A1[i],A1[largest]);
        maxHeapify(largest);
    }
}

int main(){
    cin >> h;
    
    for(int i=1; i<=h; i++){
        cin >> A1[i];
    }
    for(int i=h/2; i>=1; i--){
        maxHeapify(i);
    }
    
    for(int i=1; i<=h; i++){
        cout << " " << A1[i];
    }
    cout << endl;
}

Measured memory_bytes: 4936
#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(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h,w; cin>>h>>w;
  vector<string> s(h+2);
  rep(i,h){
    string S; cin>>S;
    s.at(i+1)=' '+S+' ';
  }
  rep(i,h){
    rep(j,w){
      if(s[i+1][j+1]=='.'){
        int cnt=0;
        rep(k,3)rep(l,3) if(s[i+k][j+l]=='#') cnt++;
        s.at(i+1).at(j+1)=char(cnt+'0');
      }
    }
  }
  rep(i,h){
    s.at(i+1)=s.at(i+1).erase(w+1);
    cout<<s.at(i+1).substr(1)<<endl;
  } 
} 

Measured memory_bytes: 256
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

// https://atcoder.jp/contests/abc157/tasks/abc157_c
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();

		boolean flag = true;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < M; i++) {
			int s = sc.nextInt();
			int c = sc.nextInt();
			if (map.containsKey(s)) {
				if (map.get(s) != c) {
					flag = false;
				}
			} else {
				if (s == 1 && c == 0 && N >= 2) {
					flag = false;
				} else {
					map.put(s, c);
				}
			}
		}
		sc.close();

		Integer[] ans = { -1, -1, -1 };
		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			ans[entry.getKey() - 1] = entry.getValue();
		}

		if (flag) {
			for (int i = 0; i < N; i++) {
				if (ans[i] >= 0) {
					System.out.print(ans[i]);
				} else {
					if (i == 0) {
						if (N == 1) {
							System.out.print("0");
						} else {
							System.out.print("1");
						}
					} else {
						System.out.print("0");
					}
				}
			}
			System.out.println();

		} else {
			System.out.println(-1);
		}





		//		int sum = 0;
		//		if(flag) {
		//	        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {//[9]
		//				if(N==3) {
		//					if(entry.getKey()==1)sum = sum + 100*entry.getValue();
		//					if(entry.getKey()==2)sum = sum + 10*entry.getValue();
		//					if(entry.getKey()==3)sum = sum + 1*entry.getValue();
		//				}else if(N==2) {
		//					if(entry.getKey()==1)sum = sum + 10*entry.getValue();
		//					if(entry.getKey()==2)sum = sum + 1*entry.getValue();
		//					if(entry.getKey()==3)sum = sum + 0*entry.getValue();
		//				}else {
		//					if(entry.getKey()==1)sum = sum + 1*entry.getValue();
		//					if(entry.getKey()==2)sum = sum + 0*entry.getValue();
		//					if(entry.getKey()==3)sum = sum + 0*entry.getValue();
		//				}
		////	        	sum = sum + entry.getKey()*entry.getValue();
		//	            System.out.println("キー：" + entry.getKey() + " 値：" + entry.getValue());//[10]
		//	        }
		//		}else {
		//			sum = -1;
		//		}
		//		System.out.println(sum);
	}
}

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

int main(){
    int n, k;
    std::cin >> n >> k;
    std::vector<int> v;
    for(int i = 0; i < n; i++){
        int x;
        std::cin >> x;
        v.push_back(x);
    }
    
    auto calcDistance = [](int left, int right){
        int first, last;
        if(std::abs(left) < std::abs(right)){
            first = left;
            last = right;
        }else{
            first = right;
            last = left;
        }
        return std::abs(first) + std::abs(last - first);
    };
    
    int ans = calcDistance(v[0], v[k - 1]);
    for(int i = 1; i < n - k + 1; i++){
        if(i + k < n - 1 && v[i + k] <= 0){
            continue;
        }else if(i - 1 >= 0 && v[i - 1] >= 0){
            continue;
        }
        int d = calcDistance(v[i], v[i + k - 1]);
        if(d < ans){
            ans = d;
        }
    }
    
    std::cout << ans << std::endl;
    
    return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
#define P pair<int,ll>
using namespace std;
typedef long long ll;
const int maxx=1e5+10;
struct S{
    int id; ll val;
    bool operator < (const S &a) const{
        return val<a.val;
    }
};
S a[maxx];
set<int> aset;
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i].val);
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=n;i;i--){
        ll l1=0,l2=0,r1=0,r2=0;
        aset.insert(a[i].id);
        auto it = aset.find(a[i].id);
        auto ik=it;
        ik++;
        if(ik==aset.end()){
            r1=n-a[i].id+1;
        }else{
            r1=(*ik)-a[i].id;
            ik++;
            if(ik==aset.end()){
                ik--;
                r2=n-(*ik)+1;
            }else{
                r2=*ik;
                ik--;
                r2-=*ik;
            }
        }
        ik=it;
        if(ik==aset.begin()){
            l1=a[i].id;
        }else{
            ik--;
            l1=a[i].id-(*ik);
            if(ik==aset.begin()){
                l2=(*ik);
            }else{
                l2=(*ik);
                ik--;
                l2-=(*ik);
            }
        }
        ans+=(l1*r2+l2*r1)*a[i].val;
        //cout<<ans<<endl;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 6528
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(int argc, const char * argv[]) {
    
    long long n;
    
    scanf("%lld",&n);
    int ans = 1000;
    for(long long i = 1;i*i<=n;i++){
        
        if(n%i == 0){
            
            long long a = i;
            long long b = n/i;
            int tmpA = 0;
            int tmpB = 0;
            
            while(a>0){
                tmpA++;
                a/=10;
            }
            
            while(b>0){
                tmpB++;
                b/=10;
            }
            if(ans > max(tmpA,tmpB)){
                ans = max(tmpA,tmpB);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int bubblesort(vector<int>&a,int n)
{
    int swaps =0;
    for(int i=0;i<n;i++ )
    {
        int mini =i;
    for(int j=i+1;j<n;j++)
    {
        if(a[j]<a[mini])
        mini =j;
    }
    {
        if(mini != i)
   {        swap(a[i],a[mini]);
        swaps++;
    }}
    }
    return swaps;
    
}
int main()
{
    int n;
    cin>>n;
    vector<int> arr;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        arr.push_back(x);
        
    }
    int swaps;
    swaps=bubblesort(arr,n);
    cout<<arr[0];
    for(int i=1;i<n;i++)
    cout<<" "<<arr[i];
    cout<<endl;
    cout<<swaps<<endl;
}

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

if T in S:
    print(S.replace('?', 'a'))
    exit()

SL = len(S)
TL = len(T)

for i in range(SL-TL, -1, -1):
    S2 = S[i:i+TL]
    for j in range(TL):
        if S2[j] == T[j] or S2[j] == '?':
            continue
        else:
            break
    else:
        answer = S[:i] + T + S[i+TL:]
        print(answer.replace('?', 'a'))
        exit()
print('UNRESTORABLE')


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

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48);
    c = getchar();
  }
  return f ? -x : x;
}

int main() {
  int x = rd();
  printf("%d\n", 1 - x);
	return 0;
}


Measured memory_bytes: 3760
import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
  public static void main(String[] args) {
    FastScanner sc = new FastScanner();
    PrintWriter out = new PrintWriter(System.out);

    long x = sc.nextLong();
    long y = sc.nextLong();

    long count = 0;
    for (long i = x; i <= y;) {
      i *= 2;
      count++; 
    }

    out.println(count);
    out.flush();
  }

}

class FastScanner {
  private final InputStream in = System.in;
  private final byte[] buffer = new byte[1024];
  private int ptr = 0;
  private int buflen = 0;
  private boolean hasNextByte() {
    if (ptr < buflen) return true;
    else {
      ptr = 0;
      try {
        buflen = in.read(buffer);
      } catch (IOException e) {
        e.printStackTrace();
      }
      if (buflen <= 0)
        return false;
    }
    return true;
  }

  private byte readByte() {
    if (hasNextByte()) return buffer[ptr++];
    return -1;
  }

  private boolean isPrintableChar(byte c) {
    return '!' <= c && c <= '~';
  }

  private void skipUnprintable() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
  }

  public boolean hasNext() {
    skipUnprintable();
    return hasNextByte();
  }

  public String next() {
    if (!hasNext()) throw new NoSuchElementException();
    StringBuilder sb = new StringBuilder();
    byte b = readByte();
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b);
      b = readByte();
    }
    return sb.toString();
  }

  public int nextInt() {
    if (!hasNext()) throw new NoSuchElementException();
    int n = 0;
    boolean minus = false;
    byte b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b)
      throw new NumberFormatException();
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }

  public int[] nextIntArray(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = nextInt();
    }
    return a;
  }

  public long nextLong() {
    if (!hasNext()) throw new NoSuchElementException();
    long n = 0;
    boolean minus = false;
    byte b = readByte();
    if (b == '-') {
      minus = true;
      b = readByte();
    }
    if (b < '0' || '9' < b) throw new NumberFormatException();
    while (true) {
      if ('0' <= b && b <= '9') {
        n *= 10;
        n += b - '0';
      } else if (b == -1 || !isPrintableChar(b)) {
        return minus ? -n : n;
      } else {
        throw new NumberFormatException();
      }
      b = readByte();
    }
  }

  public long[] nextLongArray(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
      a[i] = nextInt();
    }
    return a;
  }

}

Measured memory_bytes: 21204
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;

int D;
vector<LL> c(26);
vector<vector<LL>> s;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

LL solve(const vector<LL>& t) {
  LL ans = 0;
  vector<LL> last(26, 0);
  for (int d = 1; d <= D; ++d) {
    int i = d - 1;
    int j = t[i];
    last[j] = d;
    ans += s[i][j];
    for (int k = 0; k < 26; ++k) {
      ans -= c[k] * (d - last[k]);
    }
  }
  return ans;
}

int main() {
  cin >> D;
  cin >> c;
  s.resize(D, vector<LL>(26, 0));
  for (int i = 0; i < D; ++i) cin >> s[i];

  vector<LL> t(D);
  for (int d  =  0; d < D; ++d) t[d] = rand() % 26;

  LL prev = solve(t);
  int d = 0;
  for (int i = 0; i < 100; ++i) {
    auto best_t = t;
    for (int j = 0; j < 26; ++j) {
      t[i % D] = j;
      LL score = solve(t);
      if (score > prev) {
        prev = score;
        best_t = t;
      }
    }
    t = best_t;
  }

  for (int x : t) cout << x + 1 << endl;
}


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


class Main {


   public static void main(String args[]) throws IOException{

	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


	   String[] string =  br.readLine().split(" ");
	   int n = Integer.parseInt( string[0] );
	   int k = Integer.parseInt( string[1] );
       int[] W = new int[n];
       int Wmax , Wsum;
       int answer;

       for(int i = 0; i < n; i++ ){
    	   W[i] = Integer.parseInt( br.readLine() );
       }


       int i;
       for(i = 0, Wmax = W[i] , Wsum = 0; i < n; i++ ){

           if( Wmax < W[i] ){
        	   Wmax = W[i];
           }
           Wsum += W[i];
       }



       answer =  binarysearch(W, Wmax,  Wsum, k , n);

       System.out.println(answer);
   }




   public static int binarysearch(int[] W, int left, int right, int truck_number , int n){

    int ans = 0;
    int mid = ( right+left )/2;
    int truck_n;
    int sum = 0;

       while(left <= right ){
    	   truck_n = truck_number;
    	   mid = ( right+left )/2;
           sum = 0;
           //ans = 0;

    	   for(int i = 0; i < n; i++){
    		   sum += W[i];
    		   if(mid < sum ){
    			   sum = W[i];
    			   truck_n--;
    		   }

    	   }

    	   if(truck_n>0){
			   right = mid-1;
			   ans = mid;
		   }else{
			   left = mid+1;
		   }

    	  // System.out.println(left + " "+ mid+ " "+right+" "+truck_n+" ans="+ans);

       }

       return ans;
   }
}

Measured memory_bytes: 35124
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 31) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int m;
int t[] = { 500,100,50,10 };
int cnt[4];
bool f = 1;

vector<int> solve(int num) {
	vector<int> res(4);
	rep(i, 4) {
		while (num >= t[i]) {
			res[3 - i]++;
			num -= t[i];
		}
	}
	return res;
}

int main() {
	while (cin >> m&&m) {
		rep(i, 4) {
			int num;
			cin >> num;
			cnt[i] = num;
		}
		int ans[4] = {};
		ll sum = INF;
		rep(i, cnt[0] + 1) {
			rep(j, cnt[1] + 1) {
				rep(k, cnt[2] + 1) {
					rep(l, cnt[3] + 1) {
						int mm = 10 * i + 50 * j + 100 * k + 500 * l;
						int num = cnt[0] - i + cnt[1] - j + cnt[2] - k + cnt[3] - l;
						if (mm >= m) {
							vector<int> vi = solve(mm - m);
							num += accumulate(ALL(vi), 0);
							if (sum > num) {
								ans[0] = i;
								ans[1] = j;
								ans[2] = k;
								ans[3] = l;
								sum = num;
							}
						}
					}
				}
			}
		}
		if (!f)cout << endl;
		f = 0;
		rep(i, 4) {
			if (ans[i])cout << t[3 - i] << " " << ans[i] << endl;
		}
	}
}

Measured memory_bytes: 3080