akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<math.h>
#include<stdio.h>
using namespace std;
#define inf 1<<21
struct cell{
  double x,y,z,r;
};
double dis(cell a,cell b){
  double o=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-(a.r+b.r);
  if(o<=0) return 0;
  return o;
}
int main(){
  int n;
  cin >> n;
  while(n!=0){
    int i,j,k;
    vector<cell> cells;
    cell c;
    for(i=0;i<n;i++){
      cin >> c.x >> c.y >> c.z >> c.r;
      cells.push_back(c);
    }
    
    double cost[100][100]={{}};
    for(i=0;i<n;i++){
      for(j=i;j<n;j++){
	if(i==j) cost[i][j]=inf;
	else{
	  cost[i][j]=dis(cells[i],cells[j]);
	  cost[j][i]=cost[i][j];
	}
      }
    }
    
    int color[100]={},p[100]={};
    double d[100]={};
    for(i=0;i<n;i++){
      color[i]=0;
      d[i]=inf;
      p[i]=-1;
    }
    double sum=0,minv;
    int u;
    d[0]=0;
    while(1){
      minv=inf;
      u=-1;
      for(i=0;i<n;i++){
	if(minv>d[i]&&color[i]!=2){
	  u=i;
	  minv=d[i];
	}
      }
      if(u==-1) break;
      color[u]=2;
      for(i=0;i<n;i++){
	if(color[i]!=2&&u!=i){
	  if(d[i]>cost[u][i]){
	    d[i]=cost[u][i];
	    p[i]=u;
	    color[i]=1;
	  }
	}
      }
      
    }
    for(i=0;i<n;i++){
      if(p[i]!=-1) sum+=cost[i][p[i]];
    }
    
    printf("%.3f\n",sum);
    
    cin >> n;
  }
  return 0;
}



Measured memory_bytes: 3384
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

const int MAXN=1e5+10;

int N;
pair<int,int> elements[MAXN];//value index
int BIT[MAXN];

int len(int i){
    return i&(-i);
}

int query(int prefixIndex){
    if (prefixIndex<1) return 0;

    return max(query(prefixIndex-len(prefixIndex)),BIT[prefixIndex]);
}

void updateTo(int i,int val){
    if (i>N) return;
    BIT[i]=max(BIT[i],val);
    updateTo(i+len(i),val);
}

int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int temp;
        scanf("%d",&temp);
        elements[i].first=temp;
        elements[i].second=i;
    }

    sort(elements+1,elements+N+1);

    int cur=1;
    while(cur<=N){
        int head=cur;
        vector<int> newvalues;
        while(cur<=N&&elements[cur].first==elements[head].first) cur++;

        for(int index=head;index<cur;index++){
            int pre=elements[index].second-1;
            int temp=query(pre);
            newvalues.push_back(temp+1);
        }

        for(int index=cur-1;index>=head;index--){
            updateTo(elements[index].second,newvalues.back());
            newvalues.pop_back();
        }
    }

    printf("%d\n",query(N));

    return 0;
}


Measured memory_bytes: 4112
//#define DEBUGGING  // Enables DEBUG macro.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
#define REP(i, n) for (int i = 0; (i64)(i) < (i64)(n); ++i)

#ifndef DEBUGGING
#define DEBUG(...)
#else
template <typename T>
void _debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void _debug(T value, Ts... args) {
  std::cerr << value << ", ";
  _debug(args...);
}
#define DEBUG(...)                     \
  do {                                 \
    cerr << " (L" << __LINE__ << ") "; \
    cerr << #__VA_ARGS__ << ": ";      \
    _debug(__VA_ARGS__);               \
    cerr << endl;                      \
  } while (0)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, Q;
  cin >> N >> Q;
  vector<i64> A(N);  // sorted
  for (auto& x : A) cin >> x;

  // rcum[i] = sum of A[i] and its right, inclusive.
  vector<i64> rcum(N + 1);
  REP(i, N) { rcum[N - 1 - i] = rcum[N - i] + A[N - 1 - i]; }

  // lhcum[i] = sum of A[i-2] and its left.
  vector<i64> lhcum(N + 2);
  for (int i = 2; i < N + 2; ++i) {
    lhcum[i] = lhcum[i - 2] + A[i - 2];
  }

  auto solve = [&](const i64 X) -> i64 {
    auto closest_it = lower_bound(A.begin(), A.end(), X);
    if (closest_it == A.end()) {
      return lhcum[N + 1];
    }
    int closest_i = closest_it - A.begin();
    if (closest_i > 0 && A[closest_i] - X >= X - A[closest_i - 1]) {
      --closest_i;
      --closest_it;
    }
    if (closest_i == N - 1) {
      return lhcum[N + 1];
    }
    DEBUG(closest_i, A[closest_i]);

    int ok = closest_i, ng = N - 1;
    while (ng - ok > 1) {
      int m = (ng + ok) / 2;
      i64 delta = abs(A[m] - X);
      int lb = lower_bound(A.begin(), A.end(), X - delta) - A.begin();
      bool b = m - lb + 1 > N - 1 - m;
      DEBUG(m, A[m], lb, A[lb], b);
      if (m - lb + 1 > N - 1 - m) {
        // m is too big
        ng = m;
      } else {
        ok = m;
      }
    }
    return rcum[ng] + lhcum[ok - (N - ng) + 2];

    // int olb = lower_bound(A.begin(), A.end(), X - abs(A[ok] - X)) -
    // A.begin(); DEBUG(ok, ng, olb, rcum[ng], lhcum[olb + 1]); if (ng - olb ==
    // N - ng) {
    //   return rcum[ng] + lhcum[olb + 1];
    // } else {
    //   N-ng -
    //     (N-ng) - (ng-olb)
    //   assert(ng - olb == N - ng - 1);
    //   return rcum[ng] + lhcum[olb];
    // }
  };

  REP(i, Q) {
    i64 X;
    DEBUG(i);
    cin >> X;
    cout << solve(X) << '\n';
  }
}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll INF = 1LL << 30;

int main(void){
    int N,K; cin >> N >> K;
    string S; cin >> S;
    
    int score = 0;
    for(int i = 0; i < N-1; i++){
        if(S[i] == S[i+1]) score++;
    }
    
    int ans = min(score+2*K, N-1);
    cout << ans << "\n";
}


Measured memory_bytes: 512
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        long W = Long.parseLong(sc.next());
        Map<Long, List<Long>> map = new TreeMap<>();
        long w = Long.parseLong(sc.next());
        long basew = w;
        for (int i = (int)w; i <= w + 3; i++) {
            List<Long> base = new ArrayList<>();
            map.put((long)i, base);
        }
        long v = Long.parseLong(sc.next());
        map.get(w).add(v);
        for (int i = 1; i < N; i++) {
            w = Integer.parseInt(sc.next());
            v = Long.parseLong(sc.next());
            map.get(w).add(v);
        }
        int[] listsize = new int[map.size()];
        int ii = 0;
        for (Long key : map.keySet()) {
            listsize[ii] = map.get(key).size() + 1;
            ii++;
        }
        for (Map.Entry<Long, List<Long>> list : map.entrySet()) {
            Collections.sort(list.getValue(), Comparator.reverseOrder());
            long sum = 0;
            List<Long> sumList = new ArrayList<>();
            for (long l : list.getValue()) {
                sum += l;
                sumList.add(sum);
            }
            sumList.add(0, 0L);
            map.put(list.getKey(), sumList);
        }
        long ans = 0;
        for (int i = 0; i < listsize[0]; i++) {
            for (int j = 0; j < listsize[1]; j++) {
                for (int k = 0; k < listsize[2]; k++) {
                    for (int l = 0; l < listsize[3]; l++) {
                        long sumw = basew * i + (basew + 1) * j + (basew + 2) * k + (basew + 3) * l;
                        if (sumw <= W) {
                            long sum1 = map.get(basew).get(i);
                            long sum2 = map.get(basew + 1).get(j);
                            long sum3 = map.get(basew + 2).get(k);
                            long sum4 = map.get(basew + 3).get(l);
                            long sumv = sum1 + sum2 + sum3 + sum4;
                            ans = Math.max(ans, sumv);
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 22996
#include <stdio.h>

int def(int n, int count){
    int i,j,a[4],l,s,k;

    if(n==6174){
        return count;
    }else{

        a[3]=n/1000;
        a[2]=(n/100)%10;
        a[1]=(n/10)%10;
        a[0]=n%10;

        for(i=0;i<3;i++){
            for(j=0;j<3-i;j++){
                if(a[j]<a[j+1]){
                    k=a[j];
                    a[j]=a[j+1];
                    a[j+1]=k;
                }
            }
        }

        l=a[0]*1000 + a[1]*100 + a[2]*10 + a[3];
        s=a[3]*1000 + a[2]*100 + a[1]*10 + a[0];

        return def(l-s, count + 1);
    }
}

int main(){
    int num,ans;
    while(scanf("%d",&num),num){
        if(num%1111==0){
            printf("NA\n");
        }else{
            printf("%d\n", def(num, 0));
        }
    }

    return 0;
}

Measured memory_bytes: 608
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,i,sum = 0,m,l,k;
    map<long long int,long long int>mp;
    vector<long long int>v,v1;
    set<long long int>s;
    set<long long int>::iterator it;
    cin>>n;
    for(i = 0;i < n;i++)
    {
        cin>>m;

        mp[m-1]++;
        mp[m+1]++;
        mp[m]++;
    s.insert(m-1);
        s.insert(m+1);
        s.insert(m);

    }
    for(it = s.begin();it !=s.end();it++ )
        v.push_back(*it);
    for(i = 0;i < v.size();i++)
        v1.push_back(mp[v[i]]);
    sort(v1.begin(),v1.end());

    cout<<v1[v1.size()-1]<<endl;
    return 0;
}


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

using namespace std;

#define fi first
#define se second
#define eb emplace_back
#define mt make_tuple
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

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

const ll INF=LLONG_MAX;
const int mxn = 1e6+5;
bool prime[mxn];
vi primes;
vector<pll>factors;

void seive(){
	memset(prime,1,sizeof(prime));
	prime[0]=prime[1]=0;
	for(int i=2; i<mxn; i++){
		if(prime[i]){
			primes.eb(i);
			for(int j=2; j*i<mxn; j++){
				prime[i*j]=0;
			}
		}
	}
}

void fact(ll n){
	for(int p:primes){
		if(n%p==0){
			int cnt = 1;
			n /= p;
			while(n%p==0){
				cnt++;
				n /= p;
			}
			factors.eb((ll)p,(ll)cnt);
		}
	}
	if(n>1){
		factors.eb((ll)n,1LL);
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	seive();
	ll dp[60];
	dp[0]=0LL;
	for(int i=1; i<60; i++){
		dp[i]=dp[i-1]+i;
	}
	ll n;
	cin >> n;
	fact(n);
	ll ans = 0;
	for(pll x:factors){
		ll cnt = x.se;
		auto ptr = lower_bound(dp,dp+60,cnt)-begin(dp);
		if(cnt<dp[ptr])ptr--;
		ans += ptr;
	}
	cout << ans << endl;
}
	
// READ & UNDERSTAND
// ll, int overflow, array bounds, memset(0)
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN


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

int main() 
{
    int a, b;
    cin >> a >> b;
    if (a == b) {
        cout << 2*a << endl;
        return 0;
    }

    int x = max(a,b);
    int ans = 2*x -1;
    cout << ans << endl;
    return 0;
}


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

int main() {
  string S;
  int sum=0;
  cin >> S;

  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) == '1') {
      sum++;
    }
  }

  cout << sum << endl;

  }

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

using namespace std;

#define REP(i,m) for(int i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000001
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main() {
  int r, c;
  cin >> r >> c;
  string s[r];
  REP(i, r) cin >> s[i];
  int dx[4] = {0, 0, -1, 1};
  int dy[4] = {1, -1, 0, 0};
  REP(i, r){
    REP(j, c){
      if(s[i][j] == '#'){
        bool x = false;
        REP(k, 4){
          int nx = i + dx[k];
          int ny = j + dy[k];
          x |= (0 <= nx && nx < r && 0 <= ny && ny <= c && s[nx][ny] == '#');
        }
        if(!x){
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stdio.h>
#include <stdlib.h>

using namespace std;
//DP用
template<class T> inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
const long long INF = 1LL << 60;

long long lcm(long long x, long long y){
    if(x<y) swap(x,y);
    long long r = x%y , xy = x*y;
    while(r!=0){
        x = y;
        y = r;
        r = x%y;
    }
    return xy / y;
}

int main() {
    long long a,b;
    int c,d;
    cin >> a >> b >> c >> d;
    long long g = lcm(c,d);
    long long count = (b/c-(a-1)/c) + (b/d-(a-1)/d) - (b/g-(a-1)/g);
    cout << (b-a+1)-count;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <deque>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
typedef pair<int, int> P;

int main() {
  int n, m; cin >> n >> m;
  vector<int> a(n);
  priority_queue<P> que;
  rep(i, n) {
    cin >> a[i];
    que.push(P(a[i], 1));
  }
  rep(i, m) {
    int b, c; cin >> b >> c;
    que.push(P(c, b));
  }

  ll ans = 0;
  rep(i, n) {
    P p = que.top(); que.pop();
    ans += p.first;
    if(p.second>1) {
      p.second--;
      que.push(p);
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2804
#include <stdio.h>

int main(void) {
  int a, b, sum;
  int digit;

  while (scanf("%d %d", &a, &b) != EOF) {
    sum = a + b;
    digit = 0;

    while (sum != 0) {
      sum /= 10;
      digit++;
    }

    printf("%d\n", digit);
  }

  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long int> vp, vn, vz;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        if (t > 0) {
            vp.push_back(t);
        } else if (t < 0) {
            vn.push_back(t);
        } else {
            vz.push_back(t);
        }
    }
    if (vp.size() + vn.size() < k) {
        cout << 0 << endl;
        return 0;
    }
    int cn = vn.size(), cp = vp.size();
    long long int res = 1;
    const int mod = 1e9 + 7;
    bool flag;
    int kk = 0;
    kk += cn / 2 * 2;
    kk = min(kk, k / 2 * 2);
    if (kk + cp >= k) flag = true;
    else flag = false;

    if (!flag) {
        if (vz.size() > 0) {
            cout << 0 << endl;
            return 0;
        }
        for (int i = 0; i < vn.size(); i++) vn[i] *= -1;
        sort(vp.begin(), vp.end());
        sort(vn.begin(), vn.end());
        int i1 = 0, i2 = 1;
        if (k % 2 == 1) {
            res = vn[0];
            k -= 1;
        } else {
            res = vn[0] * vp[0] % mod;
            i1 = 1;
            k -= 2;
        }
        k /= 2;
        priority_queue<long long int, vector<long long int>, greater<long long int>> pq;
        for (int i = i1; i + 1 < vp.size(); i += 2) {
            pq.push(vp[i] * vp[i + 1]);
        }
        for (int i = i2; i + 1 < vn.size(); i += 2) {
            pq.push(vn[i] * vn[i + 1]);
        }
        for (int i = 0; i < k; i++) {
            res = res * (pq.top() % mod) % mod;
            pq.pop();
        }
        res %= mod;
        res *= -1;
        res = (res + mod) % mod;
        cout << res << endl;
        return 0;
    }
    priority_queue<long long int> pq;
    sort(vn.begin(), vn.end());
    for (int i = 0; i + 1 < cn; i += 2) {
        pq.push(vn[i] * vn[i + 1]);
    }
    sort(vp.begin(), vp.end(), greater<long long int>());
    for (int i = k % 2; i + 1 < cp; i += 2) {
        pq.push(vp[i] * vp[i + 1]);
    }
    if (k % 2 == 1) {
        res = vp[0];
    }
    k /= 2;
    for (int i = 0; i < k; i++) {
        res = res * (pq.top() % mod) % mod;
        pq.pop();
    }
    cout << res << endl;
}


Measured memory_bytes: 6572
def bellman_ford(s):
    '''
    始点sから各頂点への最短距離を求める (重み付き有向グラフ)
    '''
    dist = [float('inf')] * v
    dist[s] = 0
    neg = [False] * v

    for i in range(v-1):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
    
    for i in range(v):
        for p, q, cost in edge:
            if dist[p] != float('inf') and dist[q] > dist[p] + cost:
                dist[q] = dist[p] + cost
                neg[q] = True
            if neg[p]:
                neg[q] = True

    if neg[v-1]:
        return False
    else:
        return -dist[v-1]


v, e = map(int, input().split())

edge = []
for _ in range(e):
    s, t, d = map(int, input().split())
    edge.append([s-1, t-1, -d])

res = bellman_ford(0)

if not res:
    print('inf')
else:
    print(res)

Measured memory_bytes: 70976
import math


def solve():
    n = read()
    result = think(n)
    write(result)


def read():
    return read_int(1)[0]


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n):
    """
    >>> think(10)
    5
    >>> think(50)
    13
    >>> think(10000000019)
    10000000018
    """

    if is_prime(n):
        return n - 1  # from (1, 1) to (1, n) is the least. so distance is (n - 1)
    ceil = int(math.ceil(math.sqrt(n)))
    for a in range(ceil, -1, -1):
        if n % a == 0:
            b = n // a
            return (a - 1) + (b - 1)  # from (1, 1) to (a, b) is the least. so distance is (a - 1) + (b - 1)


def write(result):
    print(result)


def is_prime(n):
    """
    >>> is_prime(0)
    False
    >>> is_prime(1)
    False
    >>> is_prime(2)
    True
    >>> is_prime(3)
    True
    >>> is_prime(4)
    False
    >>> is_prime(5)
    True
    >>> is_prime(6)
    False
    >>> is_prime(7)
    True
    >>> is_prime(8)
    False
    >>> is_prime(9)
    False
    >>> is_prime(10)
    False
    >>> is_prime(11)
    True
    >>> is_prime(12)
    False
    >>> is_prime(13)
    True
    >>> is_prime(14)
    False
    >>> is_prime(15)
    False
    >>> is_prime(16)
    False
    >>> is_prime(17)
    True
    >>> is_prime(18)
    False
    >>> is_prime(19)
    True
    >>> is_prime(20)
    False
    >>> is_prime(23)
    True
    >>> is_prime(25)
    False
    >>> is_prime(29)
    True
    >>> is_prime(30)
    False
    >>> is_prime(31)
    True
    """

    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False

    ceil = int(math.ceil(math.sqrt(n))) + 1
    for x in range(3, ceil, 2):
        if n == x:
            return True
        else:
            if n % x == 0:
                return False
    return True


if __name__ == '__main__':
    # import doctest
    # doctest.testmod()
    solve()

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

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

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int l, n; cin>>l>>n;
    int sum = 0;
    for(int i=0; i<n; i++){
        int x, w; cin>>x>>w;
        sum += x * w;
    }

    if(sum != 0){
        cout << 1 << endl;
        cout << - sum / abs(sum) << " " << abs(sum) << endl;
    }
    else{
        cout << 0 << endl;
    }
}


Measured memory_bytes: 3104
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define mod 1000000007
#define mod1 998244353
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define inf 1e18
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define rep1(i,a,n) for(ll i=a;i<=(long long)n;++i)
#define rep2(i,n,a) for(ll i=n;i>(long long)a;--i)
#define rep3(i,n,a) for(ll i=n;i>=(long long)a;--i)
#define repi(i,a,n) for(int i=a;i<=(int)n;++i)
#define repl(i,a,n) for(int i=a;i<(int)n;++i)
#define PI 3.141592653589793238510
#define en '\n'
#define MAX 100005
#define less_time ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug cout<<"HERE"<<en;
#define setbits(x)  __builtin_popcountll(x)
#define zrobits(x)  __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vi vc<int>
#define mii unordered_map<int,int>
#define pql priority_queue<int>
#define pqs priority_queue<int,vi,greater<int>>
#define vll vector<long long>
#define pll pair<long long,long long>
#define pl pair<int,int>
#define eb emplace_back
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace std::chrono;
int main(){
    less_time;
    ll n,W,V=0;
    cin>>n>>W;
    ll wt[n+5]={0};
    ll val[n+5]={0};
    rep1(i,1,n)
    cin>>wt[i]>>val[i],V+=val[i];
    ll dp[n+5][V+5];
    rep1(i,0,n+1)
      rep1(j,0,V+1)
        dp[i][j]=1e18+5;
    rep1(i,1,n)
    dp[i][0]=0;
    dp[1][val[1]]=wt[1];
    rep1(i,2,n)
    {
      rep1(v,1,V)
      {
        if(val[i]<=v)
         dp[i][v]=min(wt[i]+dp[i-1][v-val[i]],dp[i-1][v]);
        else
         dp[i][v]=dp[i-1][v];
      }
    }
    ll max_=-inf;
    rep1(i,1,V)
    {
      if(dp[n][i]<=W)
      max_=i;
    }
    cout<<max_;
return 0;
}


Measured memory_bytes: 80512
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class D
{
	public static void Main() => (new Solver()).Solve();
}


public class Solver
{
	public void Solve()
	{
		int N = GetInt();
		int M = GetInt();
		var adj = Enumerable.Range(0, N).Select(_ => new List<int>()).ToArray();
		for(int i = 0; i < N - 1 + M; i++)
		{
			int A = GetInt() - 1;
			int B = GetInt() - 1;
			adj[A].Add(B);
		}

		var tpl = tplSort(adj);
		int[] p = new int[N];
		for(int i = 0; i < N; i++)
		{
			int v = tpl[i];
			foreach(int u in adj[v])
				p[u] = v + 1;		
		}

		Console.WriteLine(string.Join("\n", p.Select(x => x.ToString()).ToArray()));
	}

	private List<int> tplSort(List<int>[] adj)
	{
		int N = adj.Length;
		int[] deg = new int[N];
		for(int v = 0; v < N; v++)
		{
			foreach(int u in adj[v])
				deg[u]++;
		}

		var res = new List<int>();
		var queue = new Queue<int>();
		for(int v = 0; v < N; v++)
			if(deg[v] == 0)
				queue.Enqueue(v);
		
		while(queue.Count > 0)
		{
			int v = queue.Dequeue();
			res.Add(v);
			foreach(int u in adj[v])
			{
				deg[u]--;
				if(deg[u] == 0)
					queue.Enqueue(u);
			}
		}

		return res;
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray();
	public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray();
	public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray();
	public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray();
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

inline bool is_prime(i32 n) {
  if (n < 2) {
    return 0;
  }
  for (i32 i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

void solve() {
  while (true) {
    int a, d, n; cin >> a >> d >> n;
    if (a == 0) return;
    int cnt = 0, ans;
    for (int i = 0;;i++) {
      int x = a + d * i;
      if (is_prime(x)) {
        cnt++;
        if (cnt == n) { ans = x; break; }
      }
    }
    cout << ans << '\n';
  }
}



Measured memory_bytes: 3124
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct A
{
    int id;
    int num;
}alist[100005];

bool cmp(A x, A y)
{
    return x.num < y.num;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        scanf("%d", &alist[i].num);
        alist[i].id = i + 1;
    }
    sort(alist, alist+n, cmp);
    for(int i = 0; i < n - 1; ++i)
        printf("%d ", alist[i].id);
    printf("%d\n", alist[n-1].id);
    return 0;
}


Measured memory_bytes: 1536
module AOJ_Volume0031;

import std.stdio,std.string,std.conv,std.math,std.algorithm,std.container;

int main()
{
	int[] value;
	value.length = 10;
	auto v = Array!int();

	foreach(i;0..10)
	{
		value[i] = pow(2,i);
	}

	sort!("a > b")(value);

	string s;
	while((s = readln.chomp).length != 0)
	{
		int w = s.to!int;
		v.clear();
		foreach(i;0..10)
		{
			if(value[i] <= w)
			{
				w -= value[i];
				v.insertBack(value[i]);
			}

		}

		for(size_t i = v.length-1; i>= 0;i--)
		{
			if(i == 0)
			{
				writeln(v[i]);
				break;
			}
			else
			{
				write(v[i]," ");
			}
		}
	}
	return 0;
}

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

testimony_list = [[] for _ in range(N)]
for i in range(N):
    Ai = int(input())
    for j in range(Ai):
        x, y = map(int, input().split(' '))
        testimony_list[i].append((x, y))

def judge(bit):
    for i in range(N):
        if not (bit & (1<<i)):
            continue
        for x, y in testimony_list[i]:
            if y == 1 and not (bit & (1<<(x-1))):
                return False
            if y == 0 and (bit & 1<<(x-1)):
                return False
    return True

max_num = 0
for bit in range(1<<N):
    res = judge(bit)
    if res == True:
        num = 0
        for i in bin(bit)[2:][::-1]:
            if int(i) == 1:
                num += 1
        max_num = max(max_num, num)
print(max_num)

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std ;

int h[1000] ;
int n ;
int res ;

int main ()
{
	int i ;
	scanf("%d",&n);
	for ( i=1 ; i<=n ; i++ ) scanf("%d",h+i);
	res=1 ;
	for ( i=2 ; i<=n ; i++ ) 
	{
		if ( h[i]>=h[i-1] ) res++;
		h[i]=max(h[i],h[i-1]);
	}
	printf("%d\n",res);
	return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <string>
#include <climits>
#include <algorithm>
    
typedef long long int ll;
    
using namespace std;
ll a,b,c,n,m,x,q,qn,aa[100000],bb[10000][10000];
bool ra,rb,rc[100000];
vector<ll> va,vb;
string sta,stb;
    
#define CE cout<<endl
#define C cout<<
#define E <<endl

int main(){
    cin>>sta>>stb;
    b=0;
    for(int i=0;i<sta.size();i++){
        b+=(sta[i]!=stb[i]);
    }
    C b E;
}

Measured memory_bytes: 3840
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = println(solve(new Scanner(System.in)))

  def solve(in: String): String = {
    println("-" * 80)
    val start = System.currentTimeMillis
    val result = solve(new Scanner(in))
    val end = System.currentTimeMillis
    println("%d ms.".format(end - start))
    result
  }

  def solve(sc: Scanner): String = {
    val N = sc.nextInt
    val A = Array.fill(N)(sc.nextInt)

    var ans = 0L
    var sum = 0
    var r = 0
    for (l <- 0 until N) {
      if (r <= l) {
        r = l
        sum = 0
      }
      ans += r - l
      while (r < N && sum + A(r) == (sum ^ A(r))) {
        sum += A(r)
        r += 1
        ans += 1
      }
      sum -= A(l)
    }
    ans.toString
  }
}


Measured memory_bytes: 70956
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define pb push_back
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
#define umap unordered_map
#define all(x) x.begin(), x.end()
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x%M;
    while (y > 0) {
        if (y & 1)
            res = (res*x)%M ;
        y = y>>1;
        x = (x*x)%M ;
    }
    return res%M;
}
void print(vector<vll>& A){
    lli n = A.size();
    loop(i, 0, n){
        loop(j, 0, n)
            cout<<A[i][j]<<" ";
        cout<<"\n";
    }
    cout<<"\n\n";
}
vector<vll> multiply(vector<vll>& A, vector<vll>& B){
    lli n = A.size();
    vector<vll> res(n, vll(n, 0));
    loop(i, 0, n){
        loop(j, 0, n){
            lli temp = 0;
            loop(k, 0, n){
                temp += (A[i][k] * B[k][j])%M;
                temp = temp%M;
            }
            res[i][j] = temp;
        }
    }
    // print(A);
    // print(B);
    // print(res);
    // cout<<"\n\n\n";
    return res;
}
lli solve(){
    lli n, k;
    cin>>n>>k;
    vector<vll> A(n, vll(n));
    loop(i, 0, n){
        loop(j, 0, n)
            cin>>A[i][j];
    }
    vector<vll> res(n, vll(n, 0));
    loop(i, 0, n)
        res[i][i] = 1;
    while(k > 0){
        // cout<<k<<" ";
        if(k%2 == 1){
            res = multiply(res, A);
        }
        k = k / 2;
        A = multiply(A, A);
    }
    lli ans = 0;
    loop(i, 0, n){
        loop(j, 0, n){
            ans += res[i][j];
            ans %= M;
        }
    }
    cout<<ans<<"\n";
    return 0;
}
int main(){
    fastio;
    lli t;
	// cin>>t;
    t = 1;
    while(t>0){ 
        t--;
        solve();
    }
}

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

const int MAX_N = 101;

bool know[MAX_N][MAX_N];
int leaked[MAX_N];

void sovle(int N) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            know[i][j] = false;
        }
    }
    int M, p;
    for (int i = 1; i <= N; i++) {
        cin >> M;
        for (int j = 0; j < M; j++) {
            cin >> p;
            know[i][p] = true;
        }
    }
    int K;
    cin >> K;
    for (int i = 0; i < K; i++) {
        cin >> leaked[i];
    }
    vector<int> ans;
    for (int i = 1; i <= N; i++) {
        bool is_ok = true;
        for (int j = 0; j < K; j++) {
            if (!know[i][leaked[j]]) {
                is_ok = false;
                break;
            }
        }
        if (is_ok) ans.push_back(i);
    }
    if (ans.size() == 1) cout << ans[0] << endl;
    else cout << -1 << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while (true) {
        cin >> N;
        if (N == 0) break;
        sovle(N);
    }
    return 0;
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
 
int main() {
  int n,x,y;
  cin >> n >> x >> y;
  vector<int> vec(n-1,0);
  int sizea = -1;
  int sizeb = -1;
  int size = -1;
  rep(i,n) {
    rep(j,n){
      if (i >= j) continue;
      else if (x >= i+1) { 
        sizea = x-i-1;
        }
      else {
        sizea = i+1-x;
      }
      if (i >= j) continue;
      else if (y >= j+1) {
        sizeb = y-j-1;
      }
      else {
        sizeb = j+1-y;
      }
        size = sizea+sizeb+1;
    if (i >= j) continue;
     else if(size > j-i) {
       vec.at(j-i-1)++;
     }
      else {
        vec.at(size-1)++;
      }
    }
  }
 rep(i,n-1) {
   cout << vec.at(i) << endl;
 }
    }

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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

bool used[10];
int n, m;
vector<int> g[50];

int main(void)
{
  vector<int> data;
  cin >> n >> m;
  REP(i, m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  int ans = 0;
  for(int i=0; i<n; ++i) data.push_back(i);
  do {
    if(data[0] != 0) continue;
    bool ff = true;
    for(int i=0; i<n-1; ++i) {
      bool flag = false;
      for(int j: g[data[i]]) {
        if(j == data[i+1]) {
          flag = true;
        }
      }
      if(!flag) ff = false;
    }
    if(ff) ans++;
  } while(next_permutation(data.begin(), data.end()));

  cout << ans << endl;

  return 0;
}


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

int main()
{
	unsigned int n;
	cin >> n;
	unsigned int buy = 0;
	vector<long long int> price(n);
	long long int max_profit = numeric_limits<long long int>::lowest()+1;
	cin >> price[0];
	for (int t = 1; t < n; ++t) {
		cin >> price[t];
		if ((price[t] - price[buy]) > max_profit) {
			max_profit = price[t] - price[buy];
		}
		if (price[t] < price[buy]) {
			buy = t;
		}
	}
	cout << max_profit << endl;
	return 0;
}


Measured memory_bytes: 4328
using System;

namespace abc151A
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string A = Console.ReadLine();
            switch (A)
            {
                case "a":
                    Console.WriteLine("b");
                    break;
                case "b":
                    Console.WriteLine("c");
                    break;
                case "c":
                    Console.WriteLine("d");
                    break;
                case "d":
                    Console.WriteLine("e");
                    break;
                case "e":
                    Console.WriteLine("f");
                    break;
                case "f":
                    Console.WriteLine("g");
                    break;
                case "g":
                    Console.WriteLine("h");
                    break;
                case "h":
                    Console.WriteLine("i");
                    break;
                case "i":
                    Console.WriteLine("j");
                    break;
                case "j":
                    Console.WriteLine("k");
                    break;
                case "k":
                    Console.WriteLine("l");
                    break;
                case "l":
                    Console.WriteLine("m");
                    break;
                case "m":
                    Console.WriteLine("n");
                    break;
                case "n":
                    Console.WriteLine("o");
                    break;
                case "o":
                    Console.WriteLine("p");
                    break;
                case "p":
                    Console.WriteLine("q");
                    break;
                case "q":
                    Console.WriteLine("r");
                    break;
                case "r":
                    Console.WriteLine("s");
                    break;
                case "s":
                    Console.WriteLine("t");
                    break;
                case "t":
                    Console.WriteLine("u");
                    break;
                case "u":
                    Console.WriteLine("v");
                    break;
                case "v":
                    Console.WriteLine("w");
                    break;
                case "w":
                    Console.WriteLine("x");
                    break;
                case "x":
                    Console.WriteLine("y");
                    break;
                case "y":
                    Console.WriteLine("z");
                    break;
            }
        }
    }
}


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

typedef long long int ll;
typedef long double ld;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD (ll)(1e9 + 7)
#define vi vector<int>
#define vii vector<vector<int> >
#define vl vector<ll>
#define vll vector<vector<ll> >
#define vc(T, nm) vector<T> nm
#define pb push_back
#define popb pop_back
#define si set<int>
#define sl set<ll>
#define F first
#define S second
#define pii pair<int, int>
#define mp make_pair
#define ins insert
#define ers erase
#define endl "\n"
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define adr(a, b) ((a % MOD) + (b % MOD)) % MOD
#define FORA(x, s, e, inc) for(ll x = s; x != e; x += inc)
#define ROFA(x, s, e, inc) for(ll x = s; x != e; x -= inc)
#define FOR(x, s, e) FORA(x, s, e, 1)
#define ROF(x, s, e) ROFA(x, s, e, 1)
#define loop(x, n) FOR(x, 0, n)
#define rd1(t, a) 					t a; cin >> a;
#define rd2(t, a, b) 				rd1(t, a); rd1(t, b); 
#define rd3(t, a, b, c) 			rd2(t, a, b); rd1(t, c);
#define rd4(t, a, b, c, d) 			rd3(t, a, b, c); rd1(t, d);
#define rd5(t, a, b, c, d, e) 		rd4(t, a, b, c, d); rd1(t, e);
#define rd6(t, a, b, c, d, e, f) 	rd5(t, a, b, c, d, e); rd1(t, f);
#define rdA(t, nm, len)				t nm[len]; loop(i, len) {cin >> nm[i];}
#ifdef DEBUG
	#define deb(v) cout << endl << #v << ": " << v << endl
	#define db1(v) cout << endl << #v << ": " << "[ "; for(auto x: v) {cout << x << " ";}; cout << "]" << endl;
	#define db2(v) cout << endl << #v << ": " << endl; for(auto r: v) {cout << "[ "; for(auto x: r) {cout << x << " ";}; cout << "]" << endl;};
	#define dbl cout << "-------------------------------" << endl
#else
	#define deb(v)
	#define db1(v)
	#define db2(v)
	#define dbl
#endif



void solve() {
    // rd1(ll, n);
	rd2(ll, n, k);
	vl A(n);
	FOR(i, 0, n)
	    cin >> A[i];
	    
    int DP[100004];
    memset(DP, 0, sizeof(DP));
    DP[0] = 0;
    DP[1] = abs(A[0] - A[1]);
    
    for(ll i = 2; i < n; i++) {
        int can_jump_from_last = min(k, i);
        int c = INT_MAX;
        for(int j = 1; j <= can_jump_from_last; j++) {
            int lc = abs(A[i - j] - A[i]) + DP[i - j];
            c = min(c, lc);
        }
        DP[i] = c;
    }
    
    cout << DP[n - 1] << endl;
	
}

int main() {
	
	fastio;

//  	rd1(ll, t);
	ll t = 1;

    while(t--) {
        solve();
    }
    
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cmath>
#include <queue>

using namespace std;

string str[10] = {
	"0111111",
	"0000110",
	"1011011",
	"1001111",
	"1100110",
	"1101101",
	"1111101",
	"0100111",
	"1111111",
	"1101111"
};

int main(){
	
	int n;
	
	while(true){
		
		cin >> n;
		
		if(n == -1){
			break;
		}
		
		string cur_num = "0000000";
		
		for(int i = 0; i < n; i++){
			int num;
			cin >> num;
			
			for(int j = 0; j < 7; j++){
				if(cur_num[j] != str[num][j]){
					cout << "1";
				}else{
					cout << "0";
				}
			}
			cout << endl;
			cur_num = str[num];
		}
		
		
		
	}
	
	return 0;
}

Measured memory_bytes: 3156
#include <stdio.h>
int main(void)
{
    int a,b;
    
    scanf("%d",&a);
    scanf("%d",&b);
    
    if(a<b){
        printf("a < b\n");
    }else if(a>b){
        printf("a > b\n");
    }else{
        printf("a == b\n");
    }
    return 0;
}



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

int main(){
  int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
  int tmp_x,tmp_y;
  tmp_x=x2-x1;
  tmp_y=y2-y1;
  //cout <<tmp_x<<' '<<tmp_y<<endl;;
  cout <<x2-tmp_y<<' '<<y2+tmp_x<<' ';
  cout <<x1-tmp_y<<' '<<y1+tmp_x<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define sort(a) sort((a).begin(),(a).end())
#define rev(a) reverse((a).begin(),(a).end())
using db = double;
using namespace std;
typedef long long ll;


int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  vector<int> c(n);
  rep(i,n) {
    cin >> v[i];
  }
  rep(i,n) {
    cin >> c[i];
  }
  int ans = 0;
  rep(i,n) {
    ans += max(0,v[i] - c[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
/*{{{*/
#define HOME
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define F first
#define S second

template<class T> void _R(T &_x) { cin >> _x; }
void _R(int &_x) { scanf("%d", &_x); }
void _R(int64_t &_x) { scanf("%" SCNd64, &_x); }
void _R(double &_x) { scanf("%lf", &_x); }
void _R(char &_x) { scanf(" %c", &_x); }
void _R(char *_x) { scanf("%s", _x); }
template<class T, class U> void _R(pair<T, U> &_x) {_R(_x.F); _R(_x.S);}
void R() {}
template<class T, class... U> void R(T &_head, U &... _tail) { _R(_head); R(_tail...); }

template<class T> void _W(const T &_x) { cout << _x; }
void _W(const int &_x) { printf("%d", _x); }
void _W(const int64_t &_x) { printf("%" PRId64, _x); }
void _W(const double &_x) { printf("%.16f", _x); }
void _W(const char &_x) { putchar(_x); }
void _W(const char *_x) { printf("%s", _x); }
template<class T, class U> void _W(const pair<T, U> &_x) {_W(_x.F); putchar(' '); _W(_x.S);}
template<class T> void _W(const vector<T> &_x) { for (auto i = _x.begin(); i != _x.end(); _W(*i++)) if (i != _x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &_head, const U &... _tail) { _W(_head); putchar(sizeof...(_tail) ? ' ' : '\n'); W(_tail...); }

template<class T, class... U> void DB(const T &_head, const U &... _tail) {
#ifdef HOME
    W('#', _head, _tail...);
#endif
}

#define REP(i,a,b) for (int i = (a); i <= (b); ++i)
#define REPD(i,a,b) for (int i = (a); i >= (b); --i)
#define FORI(i,n) REP(i,1,n)
#define FOR(i,n) REP(i,0,int(n)-1)
#define ITER(i,t) for (auto i = t.begin(); i != t.end(); ++i)

#define SZ(x) int((x).size())
#define ALL(x) (x).begin(), (x).end()
#define UNIQUE(x) {sort(ALL(x)); (x).erase(unique(ALL(x)), (x).end());}

#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define MS(X, v) memset((X), (v), sizeof((X)))

template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef int64_t ll;

inline int LG (const unsigned int &_x) { return 32-__builtin_clz(_x); } // floor: LG(x), ceil: LG(x-1)+1
/*}}}*/

const int K = 100000+10;

int k;
ll a[K]; //, small[K], big[K];

int main(){
    R(k);
    FOR(i, k) R(a[i]);

    if(a[k-1] != 2){ W("-1"); return 0; }

    int pos = 1;
    ll small = 2, big = 3;
    REPD(i, k-2, 0){
        // small += ms, big -= ...
        ll ms = small % a[i], mb = big % a[i];
        ms = ms ? a[i]-ms : 0;
        if((small+ms) > big) pos = -1;
        small += ms, big = big-mb+a[i]-1;
        if(pos != 1) break;
    }

    if(pos == 1) W(small, big);
    else W("-1");

    return 0;
}


Measured memory_bytes: 1024