akhauriyash/Code-Regression huggingface dataset:
def min(a,b); a < b ? a : b; end
V = [6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]

N = gets.to_i
dp = Array.new(N + 1){|i| i}
V.each do |m|
  (m .. N).each do |i|
    dp[i] = min(dp[i - m] + 1, dp[i])
  end
end
puts dp[N]


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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

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

	vector<int> vec(3);
	for (auto& v : vec) {
		cin >> v;
	}

	sort(begin(vec), end(vec));

	int cnt = 0;
	while (vec[0] != vec[1] || vec[0] != vec[2] || vec[1] != vec[2]) {
		if (vec[0] + 2 <= vec[2]) {
			vec[0] += 2;
		} else if (vec[0] == vec[1]) {
			vec[0]++;
			vec[1]++;
		} else if ((vec[0] & 1) != (vec[1] & 1)) {
			vec[0]++;
			vec[2]++;
		} else {
			vec[0] += 2;
		}

		sort(begin(vec), end(vec));
		cnt++;
	}

	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 256
while True:
    h,w = map(int,input().split())
    if h == w == 0:
        break;
    for i in range(h):
        for j in range(w):
            if i % 2 == 0:
                if j % 2 == 0:
                    print("#",end="")
                else :
                    print(".",end="")
            else:
                if j % 2 == 0:
                    print(".",end="")
                else :
                    print("#",end="")
        print()
    print()

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

int n;
int a[200003];
int main()
{
	scanf("%d",&n);
	for(int i = 0;i < n;++i) scanf("%d",&a[i]);
	if(n == 1) {
		printf("1\n");
		return 0;
	}
	int l = 0, r = n;
	while(r-l>1) {
		int mid = (l+r)>>1;
		std::stack<std::pair<int,int> > s;
		bool ok = true;
		for(int i = 0;i < n;++i) {
			while(!s.empty() && s.top().first >= a[i]) s.pop();
			if(i == 0 || a[i] > a[i-1]) continue;
			int k = a[i]-1;
			while(!s.empty() && s.top().first == k && s.top().second == mid-1) {
				s.pop();
				--k;
			}
			if(k == -1) {
				ok = false;
				break;
			} else if(!s.empty() && s.top().first == k) {
				s.top().second++;
			} else {
				if(mid == 1) {
					ok = false;
					break;
				}
				s.push(std::make_pair(k,1));
			}
		}
		if(ok) {
			r = mid;
		} else {
			l = mid;
		}
	}
	printf("%d\n", r);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i <(n); i++)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using p = pair<int,int>;

int main(){
  int n;
  cin >> n;
  map<string,bool>a;
  rep(i,n){
    string s;
    cin >> s;
    if( a.count(s) ) continue;
    else a[s] = 1;
  }
  cout << a.size() << endl;
  return 0;
}


Measured memory_bytes: 19260
N,M = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(M)]
new=[]
inf  = [u for u in range(1,N+1)]
ref = 0
for i in range(M):
  x[i].insert(0,i)
x.sort(key=lambda y: y[2])
x.sort(key=lambda y: y[1])

for q in inf:
  count = 1
  for p in range(ref,M):
    if x[p][1]!=q:
      ref=p
      break
    new.append([x[p][0],x[p][1]*1000000+(count)])
    count += 1
new.sort()
for z in range(M):
  takahasi = "%012d" % new[z][1]
  print(takahasi)

Measured memory_bytes: 47280
#include <cstdio>
#include <string>

using namespace std;

char t[109];
string s[59];
int a[59];

int main() {
  int n;
  scanf("%d", &n);
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    scanf("%s%d", t, a + i);
    s[i] = string(t);
    ans += a[i];
  }
  scanf("%s", t);
  s[n] = t;
  for (int i = 0; i < n; ++i) {
    ans -= a[i];
    if (s[i] == s[n]) {
      printf("%d\n", ans);
    }
  }
}


Measured memory_bytes: 256
// You either die a hero, or you live long enough to see yourself become the villain.

/**
 *   author:  Blind_is_love
 *   created: 12.10.2019, 15:08
**/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;

template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE

#define endl "\n"
#define vll vector<int>
#define max_heap priority_queue<int>
#define min_heap priority_queue<int , vector<int>, greater<int> >
#define pb push_back
#define all(container) container.begin(), container.end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define printArr(name,from,to) for(int x = from; x < to; x++) cout << name[x] << " ";
#define fi first
#define se second
#define mp make_pair
#define prime1 304933
#define prime2 15486277 
#define mod2 179424691
#define int ll

typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

const ll MOD = 1000000007;
const ll MAX = 1e5+10;
const double PI = 3.1415926;
const ll INF = 1e18;
const double EPS = 1e-5;
int n;
int hgt[MAX];
int dp[MAX];
bool seen[MAX];

int solve(int i){

	if (i > n) return 1e12;
	if (i == n) return 0;

	if (seen[i]) return dp[i];
	seen[i] = true;
	int f1 = solve(i+1);
	int f2 = solve(i+2);
	return dp[i] = min( f1 + abs(hgt[i] - hgt[i+1]), f2 + abs(hgt[i] - hgt[i+2]));
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	clock_t t1, t2;
	t1 = clock();
	cin >> n;
	for(int i = 1 ; i < n+1; ++i){
		cin >> hgt[i];
	}
	cout << solve(1) << endl;
	t2 = clock(); cerr << "time taken: " << (t2-t1)/(long double)CLOCKS_PER_SEC << endl;
	return 0;
}

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

int main() {
	int n, a, b;
	cin >> n >> a >> b;

	if ((b - a) % 2 == 1 && n == 4) cout << "Draw" << endl;
	else if ((b - a) % 2 == 0) cout << "Alice" << endl;
	else cout << "Borys" << endl;

	return 0;
}

Measured memory_bytes: 3640
/*
      author : Nishikawa
      created: 07.08.2020 17:54:25
*/

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

class Sieve{
public:
    vector<pair<ll,int>> pf(ll n){
        vector<pair<ll,int>> res;
        for(ll i=2; i*i<=n; i++){
            int x=0;
            while(n%i==0){
                n/=i;
                ++x;
            }
            res.emplace_back(i,x);
        }
        if(n!=1) res.emplace_back(n,1);
        return res;
    }
};

int main(){
    ll n;
    cin >> n;
    Sieve s;
    int ans = 0;
    auto fs = s.pf(n);
    for(auto a : fs){
        int x = a.second;
        int b = 1;
        while(b <= x){
            x -= b;
            b++; 
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 19712
import heapq
n,m=map(int,input().split())
a=[]
for i in input().split():
    heapq.heappush(a, -int(i))

for _ in range(m):
    x=-heapq.heappop(a)//2
    
    heapq.heappush(a, -x)

print(-sum(a))

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

int main() {
  long long N , i=0;
  cin >> N ;
  if(N == 0) return 0;
  vector<char> name(26);
  vector<char> na;
  char m ;
  for( m='a'; m<='z' ; ++m){
    name.at(i) = m;
    i++ ;
  }
  int s,j=0;
  while( N > 26){
    s = N % 26 ;
    if(s > 0) na.push_back(name.at(s-1)) ;
    else{
      na.push_back(name.at(25)) ;
      N-- ;
    }
    j++;
    N = N / 26 ;
  }
  if(N > 0) na.push_back(name.at(N-1)) ;
  else na.push_back(name.at(25));
    
  reverse(na.begin(), na.end());
  for(int k=0; k < na.size() ; k++){
    cout << na.at(k);
  }
  return 0 ;
}


Measured memory_bytes: 3616
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        if (a > b) {
            System.out.println(0);
        } else if (n == 1) {
            System.out.println(a == b ? 1 : 0);
        } else {
            System.out.println((n-2) * (b-a) + 1);
        }
    }
}


Measured memory_bytes: 21844
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# a=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# a=[int(input()) for _ in range (n)]  #リスト入力  改行でa1 ... anのとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#

a, b, c = map(int, input().split())

if len(set([a, b, c])) == 2:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 38256
import sys
from itertools import starmap
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
def cross(a, b):
    return a.real * b.imag - a.imag * b.real
def dot(a, b):
    return a.real * b.real + a.imag * b.imag
def norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(p1, p2, p3, p4):
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and
			ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)
def intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
p0, p1 = starmap(complex, zip(*[map(int, input().split())] * 2))
n = int(readline())
for _ in [0] * n:
    res = ccw(p0, p1, complex(*map(float, readline().split())))
    if res == COUNTER_CLOCKWISE: print("COUNTER_CLOCKWISE")
    elif res == CLOCKWISE: print("CLOCKWISE")
    elif res == ONLINE_BACK: print("ONLINE_BACK")
    elif res == ONLINE_FRONT: print("ONLINE_FRONT")
    else: print("ON_SEGMENT")

Measured memory_bytes: 8024
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
    int a, b; cin >> a >> b;
    ostringstream oss;
    if (a < b) swap(a, b);

    for (int i = 0; i < a; ++i) oss << b;

    cout << oss.str() << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int i,j,d,k,n1,n2,n3,temp;
 int l[3];

int rt()
{
//入力
cin >> n1 >> n2 >> n3;
while(n1 < 1 or n1 > 1000 or n2 < 1 or n2 >1000 or n3 < 1 or n3 > 1000){
cin >> n1 >> n2 >> n3;
}
if(n1 >= 1 and n1 <= 1000 and n2 >= 1 and n2 <=1000 and n3 >= 1 and n3 <= 1000){
       l[0]=n1;
       l[1]=n2;
       l[2]=n3;
        for (i = 0; i < 2; i++) {
        for (j = 2; j > i; j--) {
            if (l[j - 1] > l[j]) {  
                temp = l[j];  
                l[j] = l[j - 1];
                l[j - 1] = temp;
            }
        }
    }
 }
    if(l[2]*l[2] == (l[1]*l[1]+l[0]*l[0])){
    cout << "YES\n";
    }else{
    cout << "NO\n";
    }
}



int main(){

   cin >> d;
   while(d < 1 or d > 1000){
       cin >> d;
   }

for(k=0;k<d;k++){
    rt();
}

    return 0;
}

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

ans=0
cnt=0
for i in range(1,N+1):
    if i%2==0:
        pass
    else:
        for j in range(1,N+1):
            if i%j==0:
                cnt+=1
        if cnt==8:
            ans+=1
            cnt=0
        else:
            cnt=0
        #print(ans,i)
print(ans)

Measured memory_bytes: 3060
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>

const int mod = 1e9 + 7;
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	vector<int> dp(k + 1, 0);
	for (int i = 0; i <= a[1]; i++) {
		dp[i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		auto sum = dp;
		for (int j = 1; j <= k; j++) {
			sum[j] += sum[j - 1];
			sum[j] %= mod;
		}
		vector<int> tdp(k + 1, 0);
		for (int j = 0; j <= k; j++) {
			int av = sum[j];
			int minus = (j - a[i] <= 0 ? 0 : sum[j - a[i] - 1]);
			tdp[j] = (av - minus + mod) % mod;
		}
		dp = tdp;
	}
	cout << dp[k] << "\n";
}



Measured memory_bytes: 2668
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define test ll tx; cin>>tx; while(tx--)
typedef long long int ll;
int main() {
    FIO;
    //test
    {
        ll n,m,x,i,j,ans=mod,u,v,k;
        cin>>n>>m>>x;
        ll dp[n][m+1];
        for(i=0;i<n;i++){
            for(j=0;j<=m;j++){
                cin>>dp[i][j];
            }
        }
        ll a[n];
        for(i=1;i<=n;i++){
            for(j=0;j<n;j++){
                a[j]=0;
            }
            for(j=n-1;j>=n-i;j--){
                a[j]=1;
            }
        do{
            u=0; v=0;
            ll b[m];
            for(j=0;j<m;j++){
                b[j]=0;
            }
            for(j=0;j<n;j++){
                if(a[j]==1){
                    u+=dp[j][0];
                for(k=1;k<=m;k++){
                    b[k-1]+=dp[j][k];
                }
            }
            }
            if(*min_element(b,b+m)>=x){
                ans=min(ans,u);
            }
        }
        while(next_permutation(a,a+n));
        }
        if(ans==mod){
            ans=-1;
        }
        cout<<ans<<endl;
    }
	return 0;
}


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

int main(){

	int n;

	while (cin >> n && n != 0){

		int kind[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

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

			int k;
			cin >> k;
			kind[k]++;
		}

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

			if (kind[i] != 0){

				for (int j = 0; j < kind[i]; j++){
					cout << '*';
				}
			}

			else cout << '-';

			cout << endl;
		}
	}
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

const int K_MAX = 1e5+5;
bool reached[K_MAX];

int solve(){
  int K;cin >> K;
  deque<PII> dq(1,PII(1,1));
  reached[1] = true;
  int n,count,val1,val2;
  while(!dq.empty()){
    //cout << dq.front().first SP dq.front().second << endl;
    n = dq.front().first;
    count = dq.front().second;
    if(n == 0) return count;
    reached[n] = true;
    val1 = (n+1)%K;
    val2 = (n*10)%K;
    dq.pop_front();
    if(!reached[val1]) dq.push_back(PII(val1,count+1));
    if(!reached[val2]) dq.push_front(PII(val2,count));
  }
  return 0;
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cout << solve() << endl;
  return 0;
}




Measured memory_bytes: 896
n = int(input())
c = [0] * (n + 1)

for i in range(1, n + 1):
    c[i] = int(input())
    
lc = [0] * (2 * 10**5 + 1)
dp = [0] * (n + 1)
dp[1] = 1
lc[c[1]] = 1

for i in range(2, n + 1):
    if lc[c[i]] == i - 1:
        dp[i] = dp[i - 1]
    else:
        dp[i] = dp[i - 1] + dp[lc[c[i]]]
    lc[c[i]] = i
    
print(dp[n] % (10**9 + 7))

Measured memory_bytes: 761972
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

int main() {
    int H, W;
    cin >> H >> W;
    auto mp = make_v(H, W, ' ');
    REP(i, 0, H) {
        REP(j, 0, W) {
            cin >> mp[i][j];
        }
    }
    vector<bool> isPrintH(H, false), isPrintW(W, false);
    REP(i, 0, H) {
        REP(j, 0, W) {
            isPrintH[i] = isPrintH[i] | (mp[i][j] == '#');
            isPrintW[j] = isPrintW[j] | (mp[i][j] == '#');
        }
    }
    REP(i, 0, H) {
        if (!isPrintH[i]) continue;
        REP(j, 0, W) {
            if (!isPrintW[j]) continue;
            cout << mp[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
data = readlines
nmc = data[0].split(" ")
nmc.map!{|x| x.to_i}
b = data[1].split(" ").map{|x| x.to_i}
a = data[2..-1]
ok = 0
nmc[0].times{|i|
  aa = a[i].split(" ").map{|x| x.to_i}
  sum = 0
  nmc[1].times{|j| sum += aa[j]*b[j]}
  if ((sum + nmc[2]) > 0)
    ok += 1
  end
  }
puts ok

Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;

int main() {
  ll n;
  cin >> n;
  vec a(n-1);
  vec s(n-1);
  vec f(n-1);
  for(ll i=0;i<n-1;i++) {
    cin >> a[i] >> s[i] >> f[i];
  }
  for(ll i=0;i<n-1;i++) {
    ll t=0;
    for(ll j=i;j<n-1;j++) {
      t=(t+f[j]-1)/f[j]*f[j];
      if(t<s[j]) {
        t=s[j];
      }
      t+=a[j];
    }
    cout << t << endl;
  }
  cout << 0 << endl;
}

Measured memory_bytes: 256
object Main {
       def main(args: Array[String]) = {
           var in = new java.util.Scanner(System.in)
           var arr = new Array[Int](10)
           for(i<-0 until 10) {
                    arr(i) = in.nextInt 
           }
           arr = arr.sorted.reverse
           for(i<-0 to 2) {
                    println(arr(i))
           }
       }
}

Measured memory_bytes: 45140
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

//typedef pair<int,int> P;

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

	printf("ABC%d\n",n);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
    int x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
    return x*f;
}
inline ll readll(){
    ll x;
    char c;
    int f=1;
    while((c=getchar())!='-' && (c>'9' || c<'0'));
    if(c=='-') f=-1,c=getchar();
    x=c^'0';
    while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
    return x*f;
}
const int maxn=1000+10;
struct point{
	ll x,y;
}a[maxn];
char mp[4]={'L','R','D','U'};
int b;
void work(int times,ll x,ll y){
	ll u=(1ll<<times);
	if(y>=u) putchar('U'),y-=u;
	else if(y<=-u) putchar('D'),y+=u;
	else if(x>=u) putchar('R'),x-=u;
	else if(x<=-u) putchar('L'),x+=u;
	else{
		if(abs(x)>abs(y)){
			if(x<0) putchar('L'),x+=u;
			else putchar('R'),x-=u;
		}
		else{
			if(y<0) putchar('D'),y+=u;
			else putchar('U'),y-=u;
		}
	}
	if(times!=0) work(times-1,x,y);
}
int main(){
	int n=read();
	REP(i,1,n) a[i].x=read(),a[i].y=read();
	b=(a[1].x+a[1].y+(ll)2e9)%2;
	bool flag=1;
	REP(i,2,n) if((a[i].x+a[i].y+(ll)2e9)%2!=b) flag=0;
	if(!flag) return printf("-1\n"),0;
	printf("%d\n",32-b);
	DREP(i,30,0) printf("%lld ",(1ll<<(ll)i));
	if(!b){
		printf("%d ",1);
		REP(i,1,n) a[i].x+=1;
	}
	putchar('\n');
	REP(i,1,n){
		work(30,a[i].x,a[i].y);
		if(!b) printf("L");
		putchar('\n');
	}
    return 0;
}

Measured memory_bytes: 256
N,M=map(int,input().split())
xyz=[]
for i in range(N):
    xyz.append(list(map(int,input().split())))
coefs=[[1,1,1],[1,1,-1],[1,-1,1],[1,-1,-1]
       ,[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
ans=[]

for ix,iy,iz in coefs:
    xyz_ = [sum([ix*l[0],iy*l[1],iz*l[2]]) for l in xyz]
    ans.append(sum(sorted(xyz_,reverse=True)[:M]))
print(max(ans))

Measured memory_bytes: 3316
#include<bits//stdc++.h>
using namespace std;
int main(){
  int n,m,k;string s,t;vector<int> v;
  cin >> n;
  for(int i = 1;i < 110;i++){
    if(1000 * i >= n){
      cout << 1000*i - n << endl;
      return 0 ;
    }
  }
}

Measured memory_bytes: 3624
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
#from fractions import gcd
#from math import gcd
import sys
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = float('inf')


n = I()
D = LI()
D.sort()
a = D[int(n/2)-1]
b = D[int(n/2)]
print(b-a)

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

// #define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(0);
#define rep(i,a,n) for(int i=a;i<n;i++)
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define UMP(x,y) unordered_map<x,y>
#define MP(x,y) map<x,y>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define inf 1e18
#define endl "\n"
#define coutd(n) cout << fixed << setprecision(n)
#define watch(x) cout<<#x<<" = "<<x<<endl;
typedef double db;
typedef long double ld;	
const int mod = 1000000007;

using namespace std;

int32_t main(){
    fast
		
	int n,m;
	cin>>n>>m;
	int h[n];
	rep(i,0,n)
		cin>>h[i];
	UMP(int,int) mapping;
	
	int count = 0;
	rep(i,0,m){
		int a,b;
		cin>>a>>b;
		if(h[a-1] > h[b-1]){
			if(mapping[a-1] != -1)
				mapping[a-1]++;
			mapping[b-1] = -1;
		}
		else if(h[a-1] == h[b-1]){
        	mapping[a-1] = -1;
          	mapping[b-1] = -1;
        }
        else{
			mapping[a-1] = -1;
			if(mapping[b-1] != -1)
				mapping[b-1]++;
		}
	}

	rep(i,0,n){
		if(mapping[i]!=-1)
			count++;
	}
  	cout<<count;
	
    return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()
#define endl "\n"

using ll = long long;
using P = pair<int,int>;
using mp =  map<int,int>;

const int MOD = 1e9 + 7;

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

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

    if(h == 1 || w == 1){
        cout << 1 << endl;
    }else{
        ll ans = (h * w + 1) / 2;
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int 
#define mod 1000000007
#define se second
#define fi first
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971
#define MAX 9223372036854775807
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	cout<<fixed<<setprecision(10);
	ll n,m;
	cin>>n>>m;
	ll arr[n+1],brr[n+1]={0};
	for(int a=1;a<=n;a++)
	cin>>arr[a];
	while(m--)
	{
		ll x,y;
		cin>>x>>y;
		if(arr[x]>arr[y])
		brr[y]=1;
		else if(arr[x]<arr[y])
		brr[x]=1;
		else
		brr[x]=brr[y]=1;
	}
	ll ans=0;
	for(int a=1;a<=n;a++)
	{
		if(brr[a]==0)
		ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 5216
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
const int NIL = -1;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
struct Point {
	int x, y;
	int id;
	Point() {}
	Point(int x, int y, int id = -1) :x(x), y(y), id(id) {}
	bool operator<(const Point &p) {
		return id < p.id;
	}
};
ostream &operator<<(ostream &os, Point &p) {
	os << p.id;
	return os;
}
bool lessX(const Point &p1, const Point &p2) {
	return (p1.x == p2.x) ? (p1.y < p2.y) : (p1.x < p2.x);
}
bool lessY(const Point &p1, const Point &p2) {
	return (p1.y == p2.y) ? (p1.x < p2.x) : (p1.y < p2.y);
}
struct KDTree {
	struct Node {
		int index, l, r;
		Node() {}
		Node(int index, int l, int r) :index(index), l(l), r(r) {}
	};
	vector<Node>nodes; vector<Point>points, ret;
	int n, root, nn;
	KDTree(const vector<Point>&p) :points(p), n(p.size()), nn(0) {
		nodes.resize(n);
		root = makeKDTree(0, n, true);
	}
	int makeKDTree(int l, int r, bool is_x_base) {
		if (!(l < r))return NIL;
		int mid = (l + r) / 2, t = nn++;
		vector<Point>::iterator first = points.begin() + l,
			nth = points.begin() + mid, last = points.begin() + r;
		if (is_x_base)nth_element(first, nth, last, lessX);
		else nth_element(first, nth, last, lessY);
		nodes[t] = Node(mid, makeKDTree(l, mid, !is_x_base), makeKDTree(mid + 1, r, !is_x_base));
		return t;
	}
	bool inrange(const Point&z, const Point&p1, const Point&p2) {
		return p1.x <= z.x&&z.x <= p2.x&&p1.y <= z.y&&z.y <= p2.y;
	}
	vector<Point> find(Point&s, Point&t) {
		ret.clear();
		return find(root, true, s, t);
	}
	vector<Point> find(int v, bool is_x_base, const Point&s, const Point&t) {
		Point u = points[nodes[v].index];
		Node node = nodes[v];
		if (inrange(u, s, t))ret.emplace_back(u);
		if (is_x_base) {
			if (node.l != NIL && s.x <= u.x)find(node.l, !is_x_base, s, t);
			if (node.r != NIL && u.x <= t.x)find(node.r, !is_x_base, s, t);
		}
		else {
			if (node.l != NIL && s.y <= u.y)find(node.l, !is_x_base, s, t);
			if (node.r != NIL && u.y <= t.y)find(node.r, !is_x_base, s, t);
		}
		return ret;
	}
};
signed main() {
	int N; scanf("%d", &N);
	vector<Point>p;
	rep(i, 0, N) {
		int x, y; scanf("%d%d", &x, &y);
		p.emplace_back(Point(x, y, i));
	}
	KDTree tree(p);
	int Q; scanf("%d", &Q);
	rep(i, 0, Q) {
		int sx, tx, sy, ty; scanf("%d%d%d%d", &sx, &tx, &sy, &ty);
		auto s = Point(sx, sy), t = Point(tx, ty);
		auto ret = tree.find(s,t);
		sort(all(ret));
		rep(j, 0, ret.size())printf("%d\n", ret[j].id);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 20064
import sys

input = sys.stdin.readline
L, R = map(int, input().split())
a = []
if L == 2019 or R == 2019 or (L<2019 and R >= 2019):
    print(0)
    exit()
elif L < 2019 and R < 2019:
    for i in range(L, R+1):
        for j in range(i+1, R+1):
            a.append((i*j)%2019)
    print(min(a))
    exit()
else:
    for i in range(L, min(L+2019, R+1)):
        for j in range(i+1, min(L+2019, R+1)):
            a.append((i*j)%2019)
    print(min(a))
    exit()


Measured memory_bytes: 75460
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e17 // 4倍しても(4回足しても)long longを溢れない
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

ll addsolve(ll a) { return (a + 1) / 2 % 2; }
ll solve(ll a) {
  if (a % 2 == 1) return addsolve(a);
  else return addsolve(a + 1) ^ (a + 1);
}

int main() {
  ll a,b;
  cin >> a >> b;

  cout << (solve(b) ^ solve(a-1)) << endl;
}


Measured memory_bytes: 256
# coding: utf-8
# Here your code !
N, M = map(int, input().split())

A = []
b = []

for _ in range(N):
    A.append([int(i) for i in input().split()])
    
for _ in range(M):
    b.append(int(input()))
    
for i in range(N):
    print(sum([A[i][j] * b[j] for j in range(M)]))

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
typedef pair<int,int>P;
typedef pair<int,P>P2;
#define F first
#define S second
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int lcm(int a,int b){
	return a*b/__gcd(a,b);
}

signed main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;

	int A=(b/c+b/d)-(b/(lcm(c,d)));
	int B=((a-1)/c+(a-1)/d)-((a-1)/(lcm(c,d)));

	//cout<<A<<endl;
	//cout<<B<<endl;

	cout<<((b-a+1)-A)+B<<endl;
}


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

int main(){
  int n, k;
  cin >> n >> k;
  int a[n+1]; //a[i]は数字iがa[i]こ存在することを表す
  for(int i=0; i<n+1; i++) a[i]=0;
  for(int i=0; i<n; i++){
    int buf; cin >> buf; //入力読み込み
    a[buf]++; //読み込んだ数のカウントをインクリメント
  }
  sort(a, a+n+1);
  int ans=0;
  for(int i=0; i<n+1-k; i++){
    ans += a[i];
  }

  cout << ans << endl;

  return 0;

}


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

const int64_t mod107 = 1000000007;

int64_t mpow(int64_t a, int64_t p)
{
  if (p == 0) return 1;
  if (p % 2 == 0) {
    int64_t t = mpow(a, p / 2);
    return t * t % mod107;
  } else {
    int64_t t = mpow(a, p - 1);
    return a * t % mod107;
  }
}

int64_t mcomb(int64_t n, int64_t k)
{
  if (k > n - k) return mcomb(n, n - k);
  int64_t numer = 1;
  int64_t denom = 1;
  for (int i = 0; i < k; i++) {
    numer *= n - i;
    numer %= mod107;
    denom *= i + 1;
    denom %= mod107;
  }
  return numer * mpow(denom, mod107 - 2) % mod107;
}

int main()
{
  int64_t n, a, b;
  cin >> n >> a >> b;
  int64_t ans = mpow(2, n) - 1;
  ans -= mcomb(n, a);
  if (ans < 0) ans += mod107;
  ans -= mcomb(n, b);
  if (ans < 0) ans += mod107;
  ans %= mod107;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using ull = unsigned long long;
#define rep(i, n) for (int i = 0; i < n; i++)

int main(){
  string S;
  cin >> S;
  char s = S[S.size() - 1];
  if (s == '3') cout << "bon";
  else if(s == '0' || s == '1' || s == '6' || s == '8') cout << "pon";
  else cout << "hon";
  cout << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int h,w,a,b;
  cin>>h>>w>>a>>b;
  int ans = h*w;
  int sh = h - (h%a);
  int sw = w - (w%b);
  ans -= sh*sw;
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 3104
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

int prime_count[101];


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

	for (int i = 1; i <= n; i++){
		int tmp = i;
		for (int j = 2; ; j++){
			while (tmp%j == 0){
				tmp /= j;
				prime_count[j]++;
			}
			if (tmp == 1) break;
		}
	}
	
	int ans = 0;
	
	for (int i = 2; i <= n; i++){
		for (int j = i+1; j <= n; j++){
			for (int k = j+1; k <= n; k++){
				if (prime_count[i] >= 4 && prime_count[j] >= 4 && prime_count[k] >= 2){
					ans++;
				}
				if (prime_count[i] >= 4 && prime_count[j] >= 2 && prime_count[k] >= 4){
					ans++;
				}
				if (prime_count[i] >= 2 && prime_count[j] >= 4 && prime_count[k] >= 4){
					ans++;
				}	
			}
		}
	}

	for (int i = 2; i <= n; i++){
		for (int j = i+1; j <= n; j++){
			if (prime_count[i] >= 14 && prime_count[j] >= 4){
				ans++;
			}
			if (prime_count[i] >= 4 && prime_count[j] >= 14){
				ans++;
			}
			if (prime_count[i] >= 24 && prime_count[j] >= 2){
				ans++;
			}
			if (prime_count[i] >= 14 && prime_count[j] >= 24){
				ans++;
			}
		}
	}

	for (int i = 2; i <= n; i++){
		if (prime_count[i] >= 74) ans++;
	}
	cout << ans << endl;
 	return 0;
 }


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

int main(void){
    int n;
    cin >> n;
    int a[n];
    for (size_t i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    bitset<32> t;
    for (size_t i = 0; i < n; i++)
    {
        t|=a[i];
    }
    int ans=0;
    while (t[0]==0)
    {
        t>>=1;
        ans++;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
w,l=0,[0]*n
for i in range(m):
    p,s=input().split()
    p=int(p)-1
    if s=='AC':
        w+=l[p]*(l[p]>=0)
        l[p]=-1
    else:
        l[p]+=(l[p]>=0)
print(l.count(-1),w)

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    vi x(5);
    int ans;
    for(int i=0;i<5;i++){
        cin>>x[i];
        if(x[i]==0)ans=i+1;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3620
n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]

dp = [0]*(n+2)
dp[0] = 1
broken = 0
for i in range(n):
    if broken < len(a) and i == a[broken]:
        broken += 1
    else:
        dp[i+1] = (dp[i+1] + dp[i]) % (10e8+7)
        dp[i+2] = (dp[i+2] + dp[i]) % (10e8+7)
print(int(dp[-2]))


Measured memory_bytes: 8212
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	int h;
	cin>>h;
	if(h>=30)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

//do smth instead of nothing and stay organized
//long long
//array bounds
//special cases
//binary search

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll MOD = 1e9+7;
const static ll INF = 1e14;


ll N;
vector<ll> A;
ll DP[3005][3005];
bool grid[3005][3005];

ll rec(int i, int j, int cnt){
    if(grid[i][j]) return DP[i][j];
    
    if(i == j-1) {
        if(cnt == 0) DP[i][j] = max(A[i], A[j]) - min(A[i], A[j]);
        else DP[i][j] = min(A[i], A[j]) - max(A[i], A[j]);
        grid[i][j] = true;
        return DP[i][j];
    }
    if(i < j && j-1 >= 0) rec(i, j-1, (cnt+1)%2);
    if(i < j && i+1 < N) rec(i+1, j, (cnt+1)%2);
    if(cnt == 0) DP[i][j] = max(DP[i][j-1]+A[j], DP[i+1][j]+A[i]);
    else DP[i][j] = min(DP[i][j-1]-A[j], DP[i+1][j]-A[i]);
    grid[i][j] = true;
    return DP[i][j];
}



int main() {
    cin >> N;
    A.resize(N);
    for(int i = 0; i < N; i++) cin >> A[i];
    memset(DP, 0, sizeof(DP));
    memset(grid, false, sizeof(grid));
    cout << rec(0, N-1, 0) << endl;
}

Measured memory_bytes: 79872
dir = [(-1,0),(0,1),(1,0),(0,-1)]
while True:
    N = int(input())
    if N == 0: break
    sq = [(0,0)]
    for i in range(1,N):
        n,d = map(int,input().split())
        dx,dy = dir[d]
        sq.append((sq[n][0]+dx, sq[n][1]+dy))
    maxx = maxy = minx = miny = 0
    for x,y in sq:
       maxx = max(maxx,x)
       maxy = max(maxy,y)
       minx = min(minx,x)
       miny = min(miny,y)
    w = maxx - minx + 1
    h = maxy - miny + 1
    print('{0} {1}'.format(w,h))

Measured memory_bytes: 5620
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
int a[100000];
int main(){
	ll ans=1,mod=1e9+7;
	int N,T;
	cin>>N>>T;
	rep(i,N) cin>>a[i];
	sort(a,a+N);
	rep(i,N){
		int id=lower_bound(a,a+N,a[i]-T)-a;
		ans*=(i-id+1);
		ans%=mod;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1560
#include <stdio.h>
int selectionsort(int *,int);
void swap(int *,int *);
int main(){

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

  count=selectionsort(A,n);
  
  for(j=0;j<n;j++){
    if(j==n-1)printf("%d\n",A[j]);
    else printf("%d ",A[j]);
  }
  printf("%d\n",count);

  return 0;
}
int selectionsort(int a[],int n){
  int i,j,min,flag,count=0;
  for(i=0;i<n;i++){
    min=i;
    for(j=i;j<n;j++){
      if(a[j]<a[min]){
	min=j;
      }
    }
    if(i!=min){
    swap(&a[i],&a[min]);
    count++;
    }
  }
  return count;
}

void swap(int *p,int *q)
{
  int tmp;

  tmp=*p;
  *p=*q;
  *q=tmp;
  
}



Measured memory_bytes: 2084
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define Repr(i, n, a) for (int i = (n); i >= (a); i--)
#define rep(i, n) Rep(i, 0, n)
#define repr(i, n) Repr(i, n, 0)
#define all(a) a.begin(), a.end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;

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

    int a,b;
    cin >> a >> b;
    cout << max(a, b) + (a > b ? max(a - 1, b) : max(a, b - 1)) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define long int64_t
	
	char arr[25][25];
	bool vis[25][25];
	int dist[25][25];
	int h,w;
	int ans = 0;


	void bfs(int x,int y)
	{
		if(arr[x][y] == '#')
		{
			return;
		}
		queue<pair<int,int> >q;
		q.push({x,y});
		vis[x][y] = 1;
		while(!q.empty())
		{
			pair<int,int> k = q.front();
			q.pop();

			vector<pair<int,int>> v;
			x = k.first;
			y = k.second;

			v.push_back({x+1,y});
			v.push_back({x-1,y});
			v.push_back({x,y+1});
			v.push_back({x,y-1});

			for(auto &i:v)
			{
				int a = i.first;
				int b = i.second;

				if(a < 1 or a > h or b < 1 or b > w)
				{
					continue;
				}
				if(arr[a][b] == '#')
				{
					continue;
				}
				if(!vis[a][b])
				{
					vis[a][b] = true;
					q.push({a,b});
					dist[a][b] = dist[x][y] + 1;
					ans = max(ans,dist[a][b]);
				}
			}

		}
	}


int main()
{
 	




 	    cin >> h >> w;

 	    for(int i = 1; i <= h; i++)
 	    {
 	    	for(int j = 1; j <= w; j++)
 	    	{
 	    		cin >> arr[i][j];
 	    	}
 	    }


 	    bfs(3,1);


 	    int answer = 0;

 	    for(int i = 1; i <=h; i++)
 	    {
 	    	for(int j = 1; j <= w; j++)
 	    	{
 	    		bfs(i,j);
 	    		answer = max(ans,answer);
 	    		ans = 0;

 	    		for(int xx = 1; xx <= h; xx++)
 	    		{
 	    			for(int yy = 1; yy <= w; yy++)
 	    			{
 	    				vis[xx][yy] = false;
 	    				dist[xx][yy] = 0;
 	    			}
 	    		}
 	    	}	
 	    }


 	    cout << answer << endl;

    return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(ll i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

template <typename T>
bool chmax(T &a, const T& b) {
    if (a < b) {
      a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T& b) {
    if (a > b) {
      a = b;
      return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    ll MX=0;
    vl A(N);
    rep(i,N){
        cin >> A[i];
        chmax(MX,A[i]);
    }
    ll ans=0;
    while(MX>=N){
        ll res=0;
        vl d(N);
        rep(i,N){
            res+=A[i]/N;
            d[i]=A[i]/N;
            A[i]%=N;
        }
        rep(i,N){
            A[i]+=res-d[i];
        }
        MX=0;
        rep(i,N){
            chmax(MX,A[i]);
        }
        ans+=res;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3620
N, M = map(int, input().split())
List = [list(map(int, input().split()))+[_] for _ in range(M)]


List = sorted(List, key=lambda x:(x[0], x[1]))

idx = List[0][0]
id_lst = []
n = 0
for i in range(M):
    if idx==List[i][0]:
        n+=1
        id_lst.append([format(idx, '06')+format(n, '06'), List[i][2]])
    else:
        idx = List[i][0]
        n=1
        id_lst.append([format(idx, '06')+format(n, '06'), List[i][2]])
        
id_lst = sorted(id_lst, key=lambda x:x[1])

for j in range(M):
    print(id_lst[j][0])

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

ll A[100100];
int main(){
    int N;
    cin >> N;
    REP(i,N){
        ll a;
        cin >> a;
        A[i] = a;
    }

    ll tmp = 0;
    REP(i,N){
        if(i % 2)
            tmp -= A[i];
        else
            tmp += A[i];
    }

    vector<ll> x(N);
    x[0] = tmp/2;
    for(int i = 1; i < N; i++){
        x[i] = A[i-1] - x[i-1];
    }

    REP(i,N){
        printf("%lld ", x[i]*2);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 2816