akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>

using namespace std;

typedef long long ll;

int a[100];

int GCD(int a, int b) {
  if (a == 0) return b;
  return GCD(b % a, a);
}

bool Check(int n) {
  int g = a[0];
  for (int i = 0; i < n; ++i) g = GCD(g, a[i]);
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (a[i] == a[j]) return false;
  if (g != 1) return false;
  int sum = accumulate(a, a + n, 0);
  for (int i = 0; i < n; ++i) {
    if (GCD(a[i], sum - a[i]) == 1) return false;
  }
  return true;
}

void Solve(int at, int n, int cap) {
  if (at == n && Check(n)) {
    for (int i = 0; i < n; ++i) {
      if (i) cout << " ";
      cout << a[i];
    }
    cout << endl;
    exit(0);
  }

  if (at == n) return;

  for (int i = 2; i <= cap; ++i) {
    a[at] = i;
    Solve(at + 1, n, cap);
  }
}

int main()
{
  vector<int> a;
  for (int i = 1; i < 30001; ++i) {
    if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0) a.push_back(i);
  }
  int n;
  cin >> n;

  for (;;) {
    random_shuffle(a.begin(), a.end());
    int g = a[0];
    int sum = accumulate(a.begin(), a.begin() + n, 0);
//    for (int i = 0; i < n; ++i) {
//      printf("%d%d%d ", a[i] % 2, a[i] % 3, a[i] % 5);
//    }
//    cout << endl;
    bool ok = true;
    for (int i = 0; i < n; ++i) {
      g = GCD(g, a[i]);
      if (GCD(sum, a[i]) == 1) ok = false;
    }
    if (g != 1) continue;
    if (!ok) continue;
    for (int i = 0; i < n; ++i) {
      if (i) cout << " ";
      cout << a[i];
    }
    cout << endl;
    return 0;
  }

  return 0;


  Solve(0, n, 20);
  return 0;
  for (int i = 0; i < n - 2; ++i) cout << "2 ";
  cout << "3 ";
  if (n % 3 == 2) {
    cout << "3\n";
    return 0;
  }
  cout << (n - 1) * 10 + 5 << endl;
  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main( )
{
	int n;
	cin>>n;
	cout<<a[n-1];	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define lli long long int
#define rep(i,a,n) for(int i = a; i>n; i--)
#define reps(i,a,n) for(int i = a; i < n; i++)
#define s(n) cin >> n
#define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
#define rsz(x,n) x.clear(); x.resize(n)
#define rrsz(x,a,n) x.clear(); x.resize(n,a)
#define wt while(true)
#define all(x) x.begin(),x.end()
#define pb push_back
#define ls(x) ((2*(x)) + 1)
#define rs(x) ((ls(x)) + 1)
#define md(a,b) (((a) + (b))/2)
#define INF (1e9 + 7)
using namespace std;
lli sum(lli c[],lli a,lli b){
     lli x=0;
     reps(i,a,b+1)
     x+=c[i];
     return x;
}
int main()
{
    lli n;
    s(n);
    lli a[n+1];
    reps(i,0,n)
    s(a[i+1]);
    vector<vector<lli>>dp(n+1,vector<lli>(n+1,0)) ;
    rep(l,n,0)
    {
        reps(r,l,n+1)
        {
         if(l==r)dp[l][r]=0;
         else
         { lli temp=1e18;
            reps(i,l,r)
         {
             temp=min(temp,dp[l][i]+dp[i+1][r]+sum(a,l,r));
         }
         dp[l][r]=temp;
         }
        }
    }
    cout<<dp[1][n];
    return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll a,b,c; cin>>a>>b>>c;
  if(a+b>=c) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
}

Measured memory_bytes: 3644
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[8] ={1,0,-1,0,1,-1,1,-1};
ll dy[8] ={0,1,0,-1,1,-1,-1,1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};



 
void solve(){
    ll n,m;
    ll a[100],b[100];
    ll c[100],d[100];
    cin>>n>>m;
    rep(i,n) cin>>a[i]>>b[i];
    rep(i,m) cin>>c[i]>>d[i];
    rep(i,n){
        ll ans=-1;
        ll sum=LLINF;
        rep(j,m){
            if(chmin(sum,abs(a[i]-c[j])+abs(b[i]-d[j]))) ans=j;
        }
        cout<<ans+1<<endl;
    }

}
 
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
     
    ll Q=1;
    // cin>>Q;
    rep(_,Q){
 
        solve();
 
    }
   
 
 
    return 0;
}

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

using namespace std;

int n;
int num[100100];

int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n;i++) {
        int a;
        scanf("%d",&a);
        num[a]++;
    }
    int cnt = 0;
    for (i=0;i<=100000;i++) {
        if (!num[i]) continue;
        cnt += num[i]-1;
    }
    printf("%d\n",n-(cnt+1)/2*2);

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
long long n, arr[200005],bsr1,idxbsr,bsr2;
long long t,a,b,c;
int main(){
	cin>>n;
	for(int i =1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i =1;i<=n;i++){
		if(arr[i]>=bsr1){
			bsr1=arr[i];
			idxbsr = i;
		}
	}
	for(int i =1;i<=n;i++){
		if(arr[i]>=bsr2&&i!=idxbsr){
			bsr2=arr[i];
		}
	}
	for(int i =1;i<=n;i++){
		if(i==idxbsr)cout<<bsr2<<endl;
		else cout<<bsr1<<endl;
	}
}

Measured memory_bytes: 3200
#include <stdio.h>
#include <stdlib.h>
  
typedef struct node{
    int p;
    int left;
    int right;
} Node;
  
int searchHight(int);
  
Node *node;
  
int main(){
      
    int n,i,id,depth,tmpP,deg,nowNode,sibling;
  
    scanf("%d", &n);
  
    node = malloc(sizeof(Node)*n);
  
    for (i = 0; i < n; ++i){
        node[i].p = -1;
    }
  
    for (i = 0; i < n; ++i){
        scanf("%d",&id);
        scanf("%d%d",&node[id].left,&node[id].right);
        node[node[id].left].p = id;
        node[node[id].right].p = id;
    }
  
    nowNode = 0;
    while(1){
        if (node[nowNode].left != -1 && node[nowNode].right != -1)
        {
            break;
        } else if (node[nowNode].left == -1)
        {
            nowNode = node[nowNode].right;
        } else {
            nowNode = node[nowNode].left;
        }
    }
  
    for (i = 0; i < n; ++i){
          
        tmpP = node[i].p;
        if (tmpP == -1) sibling = -1;
        else if(node[tmpP].left == i) sibling = node[tmpP].right;
        else sibling = node[tmpP].left;

        depth = 0;
        while(tmpP != -1){
            tmpP = node[tmpP].p;
            depth++;
        }
  

        deg = 0;
        if (node[i].left != -1) deg++;
        if (node[i].right != -1) deg++;
  
        printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, "
            ,i,node[i].p,sibling,deg,depth,searchHight(i));
  
        if(node[i].p == -1) printf("root\n");
        else if(node[i].left == -1 && node[i].right == -1) printf("leaf\n");
        else printf("internal node\n");
    }
  
    return 0;
}
  
int searchHight(int index){
    int hLeft = 0;
    int hRight = 0;
  
    if (node[index].left != -1){
        hLeft = searchHight(node[index].left) +1;
    }
    if (node[index].right != -1){
        hRight = searchHight(node[index].right) +1;
    }
    if (hLeft < hRight) return hRight;
    else return hLeft;
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

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

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	int N, K;
	vector<llong> plus(1,0), minus(1,0), zero;
	cin >> N >> K;
	int in;
	for(int i = 0; i < N; i++){
		cin >> in;
		if(in < 0)
			minus.push_back(in);
		else if(in > 0)
			plus.push_back(in);
		else
			zero.push_back(in);
	}
	sort(BE(minus), greater<llong>());

	K -= zero.size();
	llong ans = inf;
	for(int i = 0; i <= K; i++){
		llong left, right;
		if(minus.size() <= i)
			left = inf;
		else
			left = -minus[i];

		if(plus.size() <= K-i)
			right = inf;
		else
			right = plus[K-i];

		ans = min({ans, left*2+right, left+right*2});
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1656
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	iv, _ := strconv.Atoi(scanString())
	return iv
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 100001), 100001*100)
}

func main() {
	h, w := scanInt(), scanInt()
	a := make([]string, h)
	for i := range a {
		a[i] = scanString()
	}

	for i := range a {
		for j := range a[i] {
			if a[i][j] == '.' {
				continue
			}

			from := 0
			if i-1 >= 0 && a[i-1][j] == '#' {
				from++
			}
			if j-1 >= 0 && a[i][j-1] == '#' {
				from++
			}
			if i == 0 && j == 0 {
				from = 1
			}
			to := 0
			if i+1 < h && a[i+1][j] == '#' {
				to++
			}
			if j+1 < w && a[i][j+1] == '#' {
				to++
			}
			if i == h-1 && j == w-1 {
				to = 1
			}
			if !(from == 1 && to == 1) {
				fmt.Println("Impossible")
				return
			}
		}
	}
	fmt.Println("Possible")
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
typedef long long ll;

int t;

int main()
{
	ios::sync_with_stdio(false);
	for (int i = 1; i <= 5; i++)
	{
		cin >> t;
		if (t != i) {cout << i << endl; exit(0);}
	}  
	return 0;
}


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

using namespace std;

const int maxn = 8;

int main()
{
	int n;
	cin >> n;
	
	int a[maxn], p[maxn], q[maxn];
	
	for (int i = 1; i <= n; i++) a[i - 1] = i;
	for (int i = 0; i < n; i++) cin >> p[i];
	for (int i = 0; i < n; i++) cin >> q[i];
	
	int countp = 1, countq = 1;
	int count = 1;
	do
	{
		int checkp = 0, checkq = 0;
		for (int i = 0; i < n; i++)
		{
			if (p[i] == a[i])
			{
				checkp++;
			}
			if (q[i] == a[i])
			{
				checkq++;
			}
		}

		if (checkp == n)
		{
			countp = count;
		}
		if (checkq == n)
		{
			countq = count;
		}
		count++;
	} while (next_permutation(a, a+ n));
	
	
	cout << abs(countp - countq);
	
	return 0;
}


Measured memory_bytes: 256
#include <bitset>
#include <cstdio>
#include <list>

using namespace std;

int main() {
    int n;
    int m;
    scanf("%d %d", &n, &m);
    bitset<200001> b;
    list<int> v;
    for (int i = 0; i < m; ++i) {
        int e;
        scanf("%d", &e);
        v.push_front(e);
    }

    for (auto&& i : v) {
        if (b[i]) {
        } else {
            printf("%d\n", i);
            b[i] = true;
        }
    }
    for (auto i = 1; i <= n; ++i) {
        if (!b[i]) {
            printf("%d\n", i);
        }
    }
}

Measured memory_bytes: 5960
import sys
# from collections import defaultdict, deque
# import math
# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 1000000007

def dfs(n, s):
    if s:
        num = int(s)
        if num > n:
            return 0

    tmp = 0
    if "3" in s and "5" in s and "7" in s:
        # print(s)
        tmp += 1
    tmp += dfs(n, s + "3")
    tmp += dfs(n, s + "5")
    tmp += dfs(n, s + "7")
    return tmp


def solve():
    n = getN()
    ans = dfs(n, "")
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    # main()
    solve()


Measured memory_bytes: 74640
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define EPS (1e-10)
#define equals(a, b) (fabs((a)-(b)) < EPS)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef pair<double,double> PD;
typedef pair<int,P> ed;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  ll s = 0;
  srep(k,1,N+1) {
    if(k%3!=0&&k%5!=0) {
      s += k;
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3636
import sys
input =sys.stdin.readline

N=int(input().rstrip('\n'))
s = {}
for _ in range(N):
  A,B = (int(x) for x in input().rstrip('\n').split())
  if B in s:
    s[B] += A
  else:
    s[B] = A
m = sorted(list(set(s)))
check = 0
used = 0
for i in m:
  used += s[i]
  if used > i:
    check += 1
    print('No')
    break
if check == 0:
  print('Yes')


Measured memory_bytes: 39956
//#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<cmath>
#include<map>
#include<functional>
#include<queue>
#include<set>
#include<stack>
#include<iomanip>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
template<typename T =ll> using v = vector<T>;
template<typename T =ll> using vv = v<v<T>>;
template<typename T =ll,typename U =ll> using p = pair<T,U>;
template<typename T> T chmin(T &a,T b) {return a=min(a,b);}
template<typename T> T chmax(T &a,T b) {return a=max(a,b);}
const ll INF = (ll)1e9;

void a(){
    double r; cin >> r;
    cout<< fixed <<setprecision(15) <<2*M_PI*r<<endl;
}

void b(){
    ll n,m; cin >> n >> m;
    ll sum=0;
    rep(i,m){
        ll a;
        cin >> a;
        sum+=a;
    }
    cout << ((sum<=n?n-sum:-1));
}


void c(){

}

void d(){

}

void e(){

}

int main(){
    b();
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <map>
#include <queue>
#include <algorithm> 
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define ll long long

int main(int argc, char** argv) {
	
	int n;
	cin>>n;	
	cout<<n/2+n%2;
	return 0;
}

Measured memory_bytes: 256
from copy import deepcopy

S = str(input())
T = str(input())

if len(S) < len(T):  ## ヒントの文字列が長すぎる場合
  print('UNRESTORABLE')
  exit()

solve = []
for i in range(len(S)-len(T)+1):
  bool_match = True
  for j in range(len(T)):
    if S[i+j] != '?' and S[i+j] != T[j]:
      bool_match = False
      break
  if bool_match == True:
    if len(S) == len(T):
      S_tmp = T
    elif i == 0:
      S_tmp = T + S[len(T):]
    elif i+len(T) == len(S):
      S_tmp = S[:-len(T)] + T
    else:
      S_tmp = S[:i] + T + S[i+len(T):]
    solve.append(S_tmp.replace('?', 'a'))

if len(solve) == 0:
  print('UNRESTORABLE')
else:
  print(sorted(solve)[0])
  





Measured memory_bytes: 3444
#include <iostream>

int main(){
	char b;
	std::cin>>b;
	if(b == 'A'){
		std::cout<<'T'<<std::endl;
	}else if(b == 'T'){
		std::cout<<'A'<<std::endl;
	}else if(b == 'G'){
		std::cout<<'C'<<std::endl;
	}else if(b == 'C'){
		std::cout<<'G'<<std::endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int A,B;
    int a,s,m;
    scanf("%d%d",&A,&B);
    a = A+B;
    s = A-B;
    m = A*B;
    if(a>=s&&a>=m) printf("%d\n",a);
    else if(s>=a&&s>=m)printf("%d\n",s);
    else if (m>=a&&m>=s)printf("%d\n",m);
    return 0;
}


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

//Do not get frustrated over WA. Check for edge cases and runtime errors :)
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> s;
    ll a = count(s.begin(), s.end(), 'A');
    ll b = count(s.begin(), s.end(), 'B');
    if (a == 0 || b == 0) cout << "No";
    else cout << "Yes";
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int D[15];

int main(){

	int N,K;

	scanf("%d %d",&N,&K);

	int i;

	for(i=0;i<K;i++){
		int Di;
		scanf(" %d",&Di);
		D[Di]=1;
	}

	for(i=N;;i++){
		int flag=0;
		int tmp=i;
		while( tmp >= 1 )   {
			if(D[tmp%10]==1){
				flag=1;
				break;
			}
			tmp = tmp / 10;
		}
		if(flag==0){
			printf("%d\n",i);
			break;
		}
	}

	return 0;
}

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

int main(){
    int n,a,t;
    cin >> n;
    cin >> t;
    cin >> a;
    int h[n];
    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    int flag = 0;
    int num;
    float sa;
    for(int j = 0; j < n; j++){
        if(flag == 0){
            sa = abs(a - (t - h[j]*0.006));
            num = j+1;
            flag++;
        }else{
            if(sa > abs(a - (t - h[j]*0.006))){
                sa = abs(a - (t - h[j]*0.006));
                num = j+1;
            }
        }
    }
    cout << num << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef ll Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<double,int,double> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf=sizeof(Def)==sizeof(long long)?2e18:1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	string s;
	cin>>s;
	ll n=s.size();
	ll out=n*(n-1)/2+1;
	vi co(26);
	rep(i,n)co[s[i]-'a']++;
	rep(i,26)out-=co[i]*(co[i]-1)/2;
	cout<<out<<endl;
}







Measured memory_bytes: 640
#include<bits/stdc++.h>
using  namespace std;
#define ll long long
#define pb push_back
#define sc second
#define fr first
#define mp make_pair
const int N = 3e5 + 10 , Max = 50 + 10;
const ll  MOD = 998244353 , OO = 1e14 + 2;
int dp[N] , in_degree[N];
int n , m ;
vector<int> g[N];
bool visited[N];
void dfs(int src) {
    visited[src] = 1;
    for(int i =0 ;i < g[src].size();++i) {
        int nx = g[src][i];
        dp[nx] = max(dp[nx],dp[src] + 1);
        --in_degree[nx];
        if(in_degree[nx] == 0) {
            dfs(nx);
        }
    }
}
int main() {
    cin >> n >> m;
    for(int i = 1;i<=m;++i) {
        int a,b;
        cin >> a >> b;
        ++in_degree[b];
        g[a].pb(b);
    }
    for(int i = 1;i<=n;++i) {
        if(!visited[i] && in_degree[i] == 0)
            dfs(i);
    }
    int ans = 0;
    for(int i = 1;i<=n;++i) {
        ans = max(ans,dp[i]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 16384
n=int(input())

tasks=[]

for i in range(n):
  a,b = map(int, input().split())
  tasks.append((a,b))

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

suma=0
for i in range(n):
  suma+=  tasks[i][0]
  if suma > tasks[i][1]:
    print("No")
    exit()
print("Yes")

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

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> cnt(n,0);
  for (int i = 1; i < n; i++) {
    if(s[i] == 'E') cnt[0]++;
  }
  int ans = cnt[0];
  for (int i = 1; i < n; i++) {
    if(s[i] == 'E' && s[i-1] == 'E') cnt[i] = cnt[i-1] - 1;
    else if((s[i] == 'E' && s[i-1] == 'W') || (s[i] == 'W' && s[i-1] == 'E')) cnt[i] = cnt[i-1];
    else cnt[i] = cnt[i-1] + 1;//s[i] == 'W' && s[i-1] == 'W'
    ans = min(ans, cnt[i]);
  }
  cout << ans;
}

Measured memory_bytes: 4784
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

  int n, q;
  string s;
  cin >> n >> q;
  cin >> s;

  vector<int> v(n + 1);
  for (int i = 1; i < n; i++) {
    int x = 0;
    if (s[i - 1] == 'A' && s[i] == 'C') x = 1;
    v[i + 1] = v[i] + x;
  }

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


Measured memory_bytes: 1488
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<cstring>
#include<sstream>
using namespace std;

typedef long long ll;
int gcd(int a, int b) {
    if ( b == 0 ) return a;
    return gcd(b,a%b);
}

int main() {
  int N,K; cin >> N >> K;
  int A[100010];
  for ( int i = 0; i < N; i++ ) {
    cin >> A[i];
  }
  sort(A,A+N);
  int maxA = A[N-1];
  int a = A[0];
  for ( int i = 1; i < N; i++ ) {
    a = gcd(a,A[i]);
  }

  if ( K % a == 0 && K <= maxA ) cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  return 0;
}


Measured memory_bytes: 640
def main():
    n, a, b, c, d = map(int, input().split())
    a -= 1; b -= 1; c -= 1; d -= 1;
    s = input()

    if c < d:
        for i in range(a, d-1):
            if s[i:i+2] == "##":
                print("No")
                return 0
        print("Yes")

    else:
        for i in range(a, c-1):
            if s[i:i+2] == "##":
                print("No")
                return 0
        for i in range(b-1, d):
            if s[i:i+3] == "...":
                print("Yes")
                return 0
        print("No")

main()


Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main()
{
    int i, n, m, a[50], b[50], c[50], d[50];
    cin >> n >> m;
    for(i=0; i<n; i++) cin >> a[i] >> b[i];
    for(i=0; i<m; i++) cin >> c[i] >> d[i];

    int cp, dis, dmin;
    for(int i=0; i<n; i++){
        dmin = 1000000007;
        for(int j=0; j<m; j++){
            dis = fabs(c[j]-a[i]) + fabs(d[j]-b[i]);
            if(dis < dmin){
                dmin = dis;
                cp = j + 1;
            }
        }
        cout << cp << endl;
    }

    return 0;
}


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

ll dp[500001];

int main(){
  int n,m;cin>>n>>m;
  rep(i, n+1)dp[i]=INF;
  dp[0]=0;

    rep(i, m){
    int c;cin>>c;
    rep1(j, n)if(j-c>=0)dp[j]=min<ll>(dp[j], dp[j-c]+1);
  }

  cout<<dp[n]<<endl;

  return 0;
}



Measured memory_bytes: 3480
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD (1000000007)
#define MOD2 (998244353)
#define MOD3 (1000000009)
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("in.txt");ofstream coutt("out.txt");
int poww(int a,int b,int m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}



vector<pair<int,pii>> g[50];
int dp[50][2451];

signed main(){
    FASTER;
    int n,m,s;cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int u,v,a,b;cin>>u>>v>>a>>b;
        u--,v--;
        g[u].push_back({v,{a,b}});
        g[v].push_back({u,{a,b}});
    }
    for(int i=0;i<50;i++)for(int j=0;j<2451;j++)dp[i][j]=INF;
    s=min(s,2450LL);
    vi c(n),d(n);
    for(int i=0;i<n;i++)cin>>c[i]>>d[i];
    
    multiset<pair<int,pii>> q;
    
    auto push=[&](int v,int s,int x){
        if(s<0)return;
        if(dp[v][s]<=x)return;
        dp[v][s]=x;
        q.insert({x,{v,s}});
    };
    
    push(0,s,0);
    while(!q.empty()){
        int x=(*q.begin()).first;
        int v=(*q.begin()).second.first;
        int s=(*q.begin()).second.second;
        q.erase(q.begin());
        push(v,min(s+c[v], 2450LL),x+d[v]);
        for(auto u:g[v])push(u.first,s-u.second.first,x+u.second.second);
    }
    
    for(int i=1;i<n;i++){
        int ans=INF;
        for(int j=0;j<=2450;j++)ans=min(ans,dp[i][j]);
        cout<<ans<<"\n";
    }
}

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

int N, M;
array<int, 100000> X;

int main(){
  cin >> N >> M;
  for(int i = 0; i < M; i++){
    cin >> X.at(i);
  }
  sort(X.begin(), X.begin() + M);

  array<int, 99999> diffs;
  for(int i = 0; i + 1 < M; i++){
    diffs.at(i) = X.at(i + 1) - X.at(i);
  }
  sort(diffs.begin(), diffs.begin() + M - 1);

  long long ans = 0;
  for(int i = 0; i < M - N; i++){
    ans += diffs.at(i);
  }

  cout << ans << endl;
}



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

vector<int> G[100010];
int dp[100010];

int dfs(int now){
    if(dp[now] != -1) return dp[now];
    if(G[now].size() == 0) return dp[now] = 0;
    vector<int> d;
    for(int i = 0; i < G[now].size(); i++){
        d.push_back(dfs(G[now][i]));
    }
    sort(d.begin(), d.end(), greater<int>());
    int MAX = -1;
    for(int i = 0; i < d.size(); i++){
        MAX = max(MAX, d[i] + i + 1);
    }
    return dp[now] = MAX;
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i < n; i++){
        cin >> a[i];
        a[i]--;
        G[a[i]].push_back(i);
    }
    cout << dfs(0) << endl;
}

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

const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;
  vector<string> grid(h);
  for (int i = 0; i < h; i++) {
    cin >> grid[i];
  }
  int ans = 0;
  for (int x1 = 0; x1 < h; x1++) {
    for (int y1 = 0; y1 < w; y1++) {
      if (grid[x1][y1] == '#') {
        continue;
      }
      queue< pair<int, int> > q;
      q.push({x1, y1});
      vector< vector<int> > dist(h, vector<int>(w, -1));
      dist[x1][y1] = 0;
      while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int k = 0; k < 4; k++) {
          int nx = x + dx[k];
          int ny = y + dy[k];
          if (nx < 0 || nx >= h || ny < 0 || ny >= w) {
            continue;
          }
          if (grid[nx][ny] == '#' || dist[nx][ny] != -1) {
            continue;
          }
          dist[nx][ny] = dist[x][y] + 1;
          q.push({nx, ny});
        }
      }
      for (int x2 = 0; x2 < h; x2++) {
        for (int y2 = 0; y2 < w; y2++) {
          if (grid[x2][y2] != '#') {
            ans = max(ans, dist[x2][y2]);
          }
        }
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#ifdef ONLINE_JUDGE
#define debug(x)
#define debug2(x, y)
#define debug3(x, y, z)
#define dbg(v)
#else
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
#endif

// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

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

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

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cerr.tie(nullptr);

    int n, x, t;
    cin >> n >> x >> t;
    print((n + x - 1) / x * t);

    return 0;
}

/*
  __ _   ___ _ __  _ __
 / _` | / __| '_ \| '_ \
| (_| || (__| |_) | |_) |
 \__,_(_)___| .__/| .__/
            |_|   |_|
*/


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

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

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

int n, A[MAX], cnt[MAX];

void ans(bool b){
	puts(b ? "Yes" : "No");
	exit(0);
}

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

	cin>>n;
	for(int i=1; i<=n; i++) cin>>A[i];
	sort(A+1, A+n+1);
	if(A[n]-A[1]>1) ans(0);
	int c = A[n];
	if(A[n]==A[1]) ans(c==n-1 || c<=n/2);

	// assert(A[n]==A[1]+1);
	for(int i=1; i<=n; i++) cnt[A[i]]++;
	int x = cnt[A[1]], y = cnt[A[n]];
	ans(x+1 <= c && c <= x + y/2);

	return 0;
}


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

ll vac[100005][3], dp[100005][3];
int main(){
    int n, k;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> vac[i][0] >> vac[i][1] >> vac[i][2];
    for(int i = 0; i < n; i++){
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + vac[i][0];
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + vac[i][1];
        dp[i + 1][2] = max(dp[i][0], dp[i][1]) + vac[i][2];
    }
    cout << max({dp[n][0], dp[n][1], dp[n][2]}) << endl;
    return 0;
}


Measured memory_bytes: 4992
#define _USE_MATH_DEFINES
#include<cmath>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<tuple>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<numeric>
#include<functional>
#include<iomanip>
#include<random>
using namespace std;


#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define REP(i,n) for(int i = 0;i < n;i++)
#define FOR(i,a,b) for(int i = a;i < b;i++)
#define ALL(x) (x).begin(),(x).end()
#define dump(x) cout << (x) << endl
#define LMAX 9223372036854775807LL
#define LMIN -9223372036854775807LL

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) {}
	void unionSet(int x, int y) {
		x = root(x), y = root(y);
		if (x != y) {
			if (data[y] < data[x])swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll digitsum(ll a) {
	int sum = 0;
	while (a) {
		sum += a % 10;
		a /= 10;
	}
	return sum;
}
int getdigit(ll a) {
	return to_string(a).size();
}
int countpow(ll a, ll b) {
	int ans = 0;
	if (b == 0)return -1;
	while (1) {
		if (a % b == 0) {
			a /= b;
			ans++;
		}
		else break;
	}
	return ans;
}
int to_num(char c) {
	if (c >= '0' && c <= '9')return (c - '0');
	else return -1;
}



int main() {
	IOS;
	ll n, k;
	cin >> n >> k;
	ll ans;
	if (k % 2 == 0) {
		ll m = n / k;
		ll l = 2 * n / k - m;
		ans = l * l * l + m * m * m;
	}
	else {
		ll l = n / k;
		ans = l * l * l;
	}
	dump(ans);
}




Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int x = 800 * N;
		int y = N / 15 * 200;
		System.out.println(x-y);
				
	}

}

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

int main() {
	int n,m;
	cin >> n >> m;
	int **mat = new int*[n]; // the matrix
	for (int i = 0;i != n;++i) {
		mat[i] = new int[m];
		for (int j = 0;j != m;++j) {
			cin >> mat[i][j];
		}
	}
	int *vec = new int[m]; // the vector
	for (int i = 0;i != m;++i) {
		cin >> vec[i];
	}
	int *res = new int[n](); // the result
	for (int i = 0;i != n;++i) {
		for (int j = 0;j != m;++j) {
			res[i] += mat[i][j]*vec[j];
		}
		cout << res[i] << endl;
	}
}

Measured memory_bytes: 3100
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#define LL long long
#define mp(x,y) make_pair(x,y)
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void print(int x){write(x);printf(" ");}
int n,a[110000];
int vis[110000][2];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),vis[a[i]][i%2]++;
	int mx1=0,p1,p2,mx2=0;
	for(int i=1;i<=100000;i++)
	{
		if(vis[i][0]>=mx1)mx2=mx1,p2=p1,mx1=vis[i][0],p1=i;
		else if(vis[i][0]>mx2)mx2=vis[i][0],p2=i;
	}
	int ans=999999999;
	for(int i=1;i<=100000;i++)
	{
		if(i!=p1)ans=min(ans,(n/2)-vis[i][1]+(n/2)-mx1);
		else ans=min(ans,(n/2)-vis[i][1]+(n/2)-mx2);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1280
S = input()
N = len(S)
def calc(ln, i):
    ans = [0]*ln
    ans[i] += i // 2 + 1
    ans[i] += (ln - i - 1) // 2
    ans[i+1] += (i + 1) // 2
    ans[i+1] += (ln-i) // 2
    print(" ".join(map(str, ans)), end=" ")

left = 0
right = 0
while left < N:
    while S[right] == "R":
        right += 1
    ind = right - 1
    while right < N and S[right] == "L":
        right += 1
    calc(right - left, ind-left)
    left = right


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

typedef long long ll;

ll A[100005];
ll B[100005];


ll Q(ll A,ll B)
{
    ll cnt=A/B;
    if(A%B)cnt+=1;
    return cnt;
}

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>A[i]>>B[i];
    ll cnt=0;
    for(int i=n;i>=1;i--){
        if(A[i]%B[i]==0)continue;
        A[i]+=cnt;
        ll div=Q(A[i],B[i]);
        cnt+=div*B[i]-A[i];
    }
    cout<<cnt;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector<vector<int>>
typedef long long ll;
const int INF = 1000000007;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
    ll N, M;
    cin >> N >> M;
    ll ans = (M - 2 * N) / 4;
    if(ans < 0) cout << M / 2 << endl;
    else{
        ll a1 = min(N + ans, M / 2 - ans);
        ans++;
        ll a2 = min(N + ans, M / 2 - ans);
        cout << max(a1, a2) << endl;
    }

}

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

#define int long long

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int mod = 1E9 + 7;

int32_t main() {
    fastIO();
    
    int n, ans = 0;
    cin >> n;
    
    vector<int> p{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    
    for (int i = 0; i < 25; ++i) {
        int tmp, cnt = 0;
        tmp = n; while (tmp) cnt += tmp /= p[i];
        ans += cnt >= 74;
    }
    
    for (int i = 0; i < 25; ++i) {
        for (int j = 0; j < 25; ++j) {
            if (i == j) continue;
            int tmp, cnt1 = 0, cnt2 = 0;
            tmp = n; while (tmp) cnt1 += tmp /= p[i];
            tmp = n; while (tmp) cnt2 += tmp /= p[j];
            ans += cnt1 >= 2 and cnt2 >= 24;
            ans += cnt1 >= 4 and cnt2 >= 14;
        }
    }
    
    for (int i = 0; i < 25; ++i) {
        for (int j = 0; j < 25; ++j) {
            for (int k = j+1; k < 25; ++k) {
            if (i == j or i == k) continue;
                int tmp, cnt1 = 0, cnt2 = 0, cnt3 = 0;
                tmp = n; while (tmp) cnt1 += tmp /= p[i];
                tmp = n; while (tmp) cnt2 += tmp /= p[j];
                tmp = n; while (tmp) cnt3 += tmp /= p[k];
                ans += cnt1 >= 2 and cnt2 >= 4 and cnt3 >= 4;
            }
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

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

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

const int SIZE = 100000;
bool isprime[SIZE];
vector<deque<int> > prime(5);

int main() {
  int N; cin>>N;
  fill(isprime,	isprime+SIZE,true);
  for(int i = 2; i < SIZE; i++) {
    if(isprime[i]) {
      prime[i%5].push_back(i);
      for(int j = i*2; j < SIZE; j+=i) isprime[j] = false;
    }
  }
  REP(i,N) {
    if(i>0) cout << " ";
    cout << prime[1].front() ;
    prime[1].pop_front();
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a==1||a==9||a==7||a==4){
       if(b==1||b==9||b==7||b==4){
           if(c==1||c==9||c==7||c==4){
               if(d==1||d==9||d==7||d==4){
                   if(a!=b&&a!=c&&a!=d&&b!=c&&b!=d&&c!=d){
                       cout<<"YES"<<endl;
                       return 0;
                   }
               }
           }
       }
    }
    cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long

using namespace std;

int main() {
  string str;
  cin >> str;

  vector<string> list;

  list.emplace_back("Sunny");
  list.emplace_back("Cloudy");
  list.emplace_back("Rainy");
  list.emplace_back("Sunny");

  bool next = false;
  for (int i = 0; i < list.size(); i++) {
    if (next) {
      cout << list[i] << endl;
      break;
    }
    if (list[i] == str) {
      next = true;
    }
  }
}


Measured memory_bytes: 256
n = int(input())
l0 = list(map(int, input().split()))
l = sorted(l0)

m1 = l[n//2 - 1]
m2 = l[n//2]
for i in range(len(l0)):
    if l0[i] < m2:
        print(m2)
    elif l0[i] > m1:
        print(m1)
    elif l0[i] == m1:
        print(m2)
    elif l0[i] == m2:
        print(m1)

Measured memory_bytes: 25224
#include <iostream>

int main(int argc, char const *argv[]) {
	int r,g,b;
	std::cin >> r >> g >> b;
	r = 100 * r + 10 * g + b;
	r %= 4;
	if (r == 0) {
		std::cout << "YES" << '\n';
	}
	else{
		std::cout << "NO" << '\n';
	}
	return 0;
}


Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.*;

public class Main {
    int n;
    Edges[] g;
    long[] counter;

    void run() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int q = sc.nextInt();
        g = new Edges[n];
        counter = new long[n];

        for (int i = 0; i < n; i++) {
            g[i] = new Edges();
        }

        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt() - 1, b = sc.nextInt() - 1;
            g[a].add(b);
            g[b].add(a);
        }

        for (int i = 0; i < q; i++) {
            int p = sc.nextInt() - 1, x = sc.nextInt();
            counter[p] += x;
        }

        dfs(0, 0, new boolean[n]);

        PrintWriter out = new PrintWriter(System.out);
        out.print(counter[0]);
        for (int i = 1; i < n; i++) {
            out.print(" " + counter[i]);
        }
        out.println();
        out.flush();


    }

    void dfs(int idx, long cnt, boolean[] visited) {
        counter[idx] += cnt;
        visited[idx] = true;

        for (int next: g[idx]) if (!visited[next]) {
            dfs(next, counter[idx], visited);
        }
    }

    class Edges extends ArrayList<Integer> {}

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

    public static void main(String[] args) {
        new Main().run();
    }

}


Measured memory_bytes: 233020
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

int main() {

	string s, t, u;
	int  a, b;
	cin >> s >> t >> a >> b >> u;

	if (s == u) {
		a--;
	}
	else {
		b--;
	}
	
	cout << a << " " << b << endl;


	return 0;
}

Measured memory_bytes: 256
if __name__ == '__main__':
    n,x = map(int,raw_input().split())
    m = []
    for i in range(n):
        m.append(input())
    m.sort()
    count = 0
    for a in m:
        x -= a
        count += 1
    while x > 0:
        x -= m[0]
        if x >= 0:
            count += 1
        else:
            break
    print count


Measured memory_bytes: 2568
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	typedef long long ll;
	#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(ll &x,const ll y) {x=x>y?x:y;}
	void chmin(ll &x,const ll y) {x=x<y?x:y;}
	const int MAX_N=3e2+10;
	const ll MOD=998244353;
	void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
	ll qpower(ll x,int e)
	{
		ll ans=1;
		while(e)
		{
			if(e&1) ans=ans*x%MOD;
			x=x*x%MOD;e>>=1;
		}
		return ans;
	}
	const ll inv2=(MOD+1)/2;

	int f[MAX_N*MAX_N],g[MAX_N*MAX_N];
	void main()
	{
		int n=qread(),sum=0;f[0]=qpower(2,n);g[0]=1;
		for(int i=1;i<=n;i++)
		{
			int aa=qread();
			for(int s=sum;s>=0;s--) add(f[s+aa],(ll)f[s]*inv2%MOD),add(g[s+aa],g[s]);
			sum+=aa;
		}
		int ans=qpower(3,n);
		for(int a=ceil(sum/2.0);a<=sum;a++) add(ans,-(ll)f[a]%MOD*3%MOD);
		if(sum%2==0) add(ans,(ll)g[sum/2]*3%MOD);
		write((ans+MOD)%MOD);
	}
};
signed main()
{
//	freopen("connect.in","r",stdin);
//	freopen("connect.out","w",stdout);
	srand(time(0));
	mine::main();
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SHIFT_LEFT(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e,n,ans = 0,cnt = 0;
  string s,ss,sss;
  cin>>a>>b;
  cout<<a*(a-1)/2+b*(b-1)/2<<endl;
  return 0;
}


Measured memory_bytes: 768