akhauriyash/Code-Regression huggingface dataset:
//Warmdust Code
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define db double
#define ll long long
#define ull unsigned long long
#define ft float
#define PI acos(-1)
#define L(i,a,b) for(int i=a;i<=b;i++)
#define R(i,a,b) for(int i=a;i>=b;i--)
#define inf 0x3f3f3f3f
#define linf  0x3f3f3f3f3f3f3f3f
#define Warmdust int main(){
#define RETURN return 0;}
#define TvT ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int maxn = 1e5+7;
const int mod = 10000+7;
ll sz[maxn];
//vector<ll>v;
Warmdust
	TvT;
	ll a,b;
	int cnt=0;
	cin >> a >> b;
	ll s= __gcd(a,b);
//	cout << s << endl;
	for(ll i=1;i*i<=s;i++){
		if(s % i == 0) {
			sz[cnt++]= i;
			if(i*i == s) continue;
			sz[cnt++] = s/i;
		}
	}
	sort(sz,sz+cnt);
	R(i,cnt-1,1){
//		int sum = cnt;
		R(j,i-1,1){
			if(sz[i] % sz[j] == 0) {
					cnt--;
					break;	
			}
		}
		//mn=min(mn,sum) ;
	}
	cout << cnt << endl;
RETURN 


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using ull = unsigned long long;
//#define int ll
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<V<T>>;
#define fi first
#define se second
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))
using pii = pair<int,int>; using pll = pair<ll,ll>;
#define FOR(i,a,b) for(ll i = (a); i < (ll)(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(ll i = (ll)(b)-1;i >= a;--i)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define eb(val) emplace_back(val)
const double PI = acos(-1), EPS = 1e-10;
const ll MOD = 1e9+7;
void cioacc(){//accelerate cin/cout
  cin.tie(0);
  ios::sync_with_stdio(false);
}
signed main(){
  int n;
  cin >> n;
  vector<pii> a(n);
  REP(i,n){
    int s,t;
    cin >> s >> t;
    a[i].first = t;
    a[i].se = s;
  }
  sort(ALL(a));
  int last = 0;
  int ans = 0;
  REP(i,n){
    if(last>=a[i].se) continue;
    ans++;
    last = a[i].fi;
  }
  cout << ans << endl;
}



Measured memory_bytes: 3560
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;
const int N = 1001;
const int C = 6;
const int INF = 1e9;

int main() {
  int dp[N];
  REP(i, N) dp[i] = INF;
  dp[0] = 0;
  int cs[C] = {1, 5, 10, 50, 100, 500};
  REP(i, C) FOR(j, cs[i], N) dp[j] = min(dp[j], dp[j - cs[i]] + 1);
  int N;
  while(cin >>N && N) cout <<dp[1000 - N] <<endl;
  return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int (i)=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)
#define MOD 1000000007

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }


int main(){
    int N;
    cin >> N;
    vector<int> P(N);
    REP(i, N) cin >> P[i];
    int mn = 10*N;
    int ans = 0;
    REP(i, N){
        if(P[i] <= mn) ans++;
        mn = min(mn, P[i]);
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 1024
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;


typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
	stringstream ss;
	ss << f;
	ss >> t;
}


#define REP(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(v) (v).rbegin(),(v).rend()
#define PB push


#define MOD 1000000007LL
#define EPS 1e-10

int main()
{
	int K;
	cin >> K;
	int ans = 0;
	for( int i = 1; i <= K; ++i )
	{
		for( int j = 1; j <= K; ++j )
		{
			if( i % 2 == 0 && j % 2 == 1 )
			{
				++ans;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
	long long X, Y, i, j, t;

	cin >> X >> Y;

	t = 1;

	for ( i = 0; i <=100000000; i++)
	{
		X = X * 2;

		if (X <= Y)
		{
			t = t + 1;
		}
		else
			break;
	}

	cout << t;

			return 0;
	
}

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


int main() {
    ll N;
    set<ll> S;
    cin >> N;
    if (N == 2) { puts("1"); return 0; }
    S.insert(N);
    for (ll p = 2; p*p <= N; p++) {
        if (N % p != 0) continue;
        ll n = N;
        while (n % p == 0) n /= p;
        if (n % p == 1) S.insert(p);
    }
    N--;
    S.insert(N);
    for (ll p = 2; p*p <= N; p++) {
        if (N % p == 0) {
            S.insert(p);
            S.insert(N/p);
        }
    }
    cout << S.size() << endl;
    return 0;
}


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

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

	int n,a,b;
	vector <pair<int,int>> v;

	cin >> n;

	for(int i=0;i<n;i++)
	{
		cin >> a >> b;
		v.push_back(make_pair(b,a));
	}

	sort(v.begin(),v.end());

	int t = 0;

	for(int i=0;i<n;i++)
	{
		if(t + v[i].second > v[i].first)
		{
			cout << "No" << '\n';
			return 0;
		}
		t+=v[i].second;
	}

	cout << "Yes" << '\n';

	return 0;
}


Measured memory_bytes: 2420
use proconio::input;

#[allow(non_snake_case)]
fn main() {
    input! {
        N: usize,
        D: i64,
        XY: [(i64, i64); N],
    }

    let mut ans = 0;
    for (x, y) in XY {
        if D * D >= x * x + y * y {
            ans += 1;
        }
    }

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


Measured memory_bytes: 7808
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

using namespace std;

int main() {
    string nyan;
    cin >> nyan ;
    size_t nyanyanya = count(nyan.begin(), nyan.end(), '7');
    if(1<=nyanyanya){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
long long a[5010],c[5010];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    long long n,m,ans=-1e18;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    cin>>c[i];
    for(int i=1;i<=n;i++){
        long long s=i,sum=0,k=0;
        for(int j=1;j<=m;j++){
            s=a[s];
            sum+=c[s];
            ans=max(ans,sum);
            if(s==i){
                k=j;
                break;
            }
        }
        if(m==k||k==0)continue;
        sum=sum*((m-1)/k);
        ans=max(ans,sum);
        long long mm=(m-1)%k+1;
        s=i;
        for(int j=1;j<=mm;j++){
            s=a[s];
            sum+=c[s];
            ans=max(ans,sum);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 3728
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
s = [0] * (n+1)

for i in range(n-1, 0, -1):
    s[i] = (a[i] + s[i+1]) % mod


ans = 0
for i in range(n-1):
    tmp = (a[i] * s[i+1]) % mod
    ans += tmp
    ans %= mod

print(ans)

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

int main() {
  long long n,a,b;
  cin >> n >> a >> b;
  long long tmp = n / (a + b) * a;
  long long t = n %(a + b);
  if (a == 0)
  {
    cout << 0;
    return 0;
  }
    if (t>a){
      cout << tmp+ a;
    }else{
      cout << tmp+ t;
      }
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int, input().split()))
cnt = 0
ans = 0
for i in range(n):
    if a[i]%2 == 0:
        cnt += 1
        if a[i]%3 == 0 or a[i]%5 == 0:
            ans += 1
       
if cnt == ans: print("APPROVED")
else: print("DENIED") 

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>

#define H 250

int main(){
  int h, i;
  int a[H];

  scanf("%d", &h);
  if(h > H) exit(1);

  for(i=0; i<h; i++){
    scanf("%d", &a[i]);
    if(a[i] < -2000000000 || a[i] > 2000000000) exit(2);
  }

  for(i=1; i<h+1; i++){
    printf("node %d: ", i);
    printf("key = %d, ", a[i-1]);
    if(i != 1) printf("parent key = %d, ", a[i/2-1]);
    if(i*2 < h+1) printf("left key = %d, ",a[i*2-1]);
    if(i*2+1 < h+1) printf("right key = %d, ", a[i*2]);
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2104
def main():
    N = int(input())
    S = input()
    from collections import Counter
    c = Counter(S)
    ans = c["R"]*c["G"]*c["B"]
    less = 0
    for d in range(1, N+1):
        for i in range(N):
            # 差dで三つが異なるなら条件を満たさないので取り除く
            if i+d < N and i+2*d < N and \
                    S[i] != S[i+d] and S[i] != S[i+2*d] and S[i+d] != S[i+2*d]:
                less += 1
    print(ans - less)


if __name__ == '__main__':
    main()


Measured memory_bytes: 74156
#include <bits/stdc++.h>
#include <iostream>
typedef long long ll;
#define rep(i,a,b) for(ll i =a ;i <= b;i++)
#define per(i,a,b) for(ll i =a ;i >= b;i--)
using namespace std;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;


int main(int argc, char const *argv[])
{
	//ifstream cin("input.txt");
	string s;
	unordered_map <string, bool>cnt;

	int n;
	cin>>n;
	rep(i, 0, n-1)
	{
		cin>>s;
		cnt[s] = true;
	}
	cout<<cnt.size();
	
	
}

Measured memory_bytes: 17616
#include<iostream>
#include<time.h>
#include<stdlib.h>

using namespace std;

void swap(int i, int j, int* A, int* B);
void quicksort_with_index(int l, int r, int* A, int* B);
int selectrandomposition(int l, int r, int* A);
int partition(int l, int r, int* A, int* B);

int selectrandomposition(int l, int r, int* A){
    int ans = (int)rand()%(r - l + 1) + l;
    return ans;
}

void swap(int i, int j, int* A, int* B){
    int tmpa = 0; int tmpb = 0;
    tmpa = A[i]; tmpb = B[i];
    A[i]=A[j]; B[i] = B[j];
    A[j] = tmpa; B[j] = tmpb;
}

int partition(int l, int r, int* A, int* B){
    int rand = selectrandomposition(l, r, A);
    swap(rand, r, A, B); 
    int pivot = A[r];
    int i = l - 1;
    int j = r;

    for(;;){
        for(i++; A[i] < pivot; i++){}
        for(j--; A[j] > pivot && (i < j); j--){}
        if(i >= j) break;
        swap(i, j, A, B);
    }
    swap(i, r, A, B);
    return i;
}

//Aに従ってBをソートします。Aに付帯した状態Bが、Aの昇順で並び替えられます。Aも並び変わるので、コピーを取っておいてもよい。
void quicksort_with_index(int l, int r, int* A, int* B){
    if(l < r){
        int i = partition(l, r, A, B);
        quicksort_with_index(l, i - 1, A, B);
        quicksort_with_index(i + 1, r, A, B);
    }
}

int main(void){
    srand(time(NULL));
    int n = 0;
    cin >> n;
    int* A = (int*)malloc(sizeof(int)*n);
    int* Aprime = (int*)malloc(sizeof(int)*n);
    
    for(int i = 0; i < n; i++) A[i] = 0;
    for(int i = 0; i < n; i++) cin >> A[i];
    for(int i = 0; i < n; i++) Aprime[i] = A[i];
    
    int* B = (int*)malloc(sizeof(int)*n);
    for(int i = 0; i < n; i++) B[i] = i + 1;


    quicksort_with_index(0, n-1, A, B);
    
    for(int i = 0; i < n; i++) cout << B[i] <<" ";
    
    return 0;
}

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

#define count_ones __builtin_popcountl
#define all(a) a.begin(), a.end()
#define gcd(a, b) __gcd(a, b)
#define lca(a, b) a / __gcd(a, b) * b
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<pair<ll, ll>> ivec(n);
    for (ll i = 0; i < n; i++) {
        ll x;
        cin >> x;
        ivec[i] = {x, i + 1};
    }
    sort(all(ivec));
    for (auto i : ivec) {
        cout << i.second << ' ';
    }

    return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int a[maxn],n,k;
bool check(int mval)
{
	int cnt=0;
	for(int i=1;i<=n;i++)
		cnt+=a[i]/mval-(a[i]%mval==0);
	return cnt<=k;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=1,r=1e9;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
}

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


Measured memory_bytes: 2032
#include <iostream>
using namespace std;
int main() {  
  int n, m;
  while(1) {  
    int masu[1001]={}, ac[1001], p=1, i; 
    cin >> n >> m;   
    if(n==0 && m==0) break; 
    for(i=1; i<=n; i++) {  
      cin >> masu[i]; 
    }     
    for(i=1; i<=m; i++)  {    
      cin >> ac[i]; 
    }   
    for(i=1; i<=m; i++)  {  
      p+=ac[i];  
      if(p>=n) break; 
      if(masu[p]!=0) p+=masu[p]; 
      if(p>=n) break;
    }    
    cout << i << endl; 
  }  
  return 0;
}


Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
int inf=1000001000;
ll INF=100000000000000000;

int main() {
    int n;
    cin >> n;
    vector<vector<pp>> a(101,vector<pp>(0));
    a[3].push_back(mk(1,3));
    a[3].push_back(mk(2,3));
    a[4].push_back(mk(1,2));
    a[4].push_back(mk(1,3));
    a[4].push_back(mk(2,4));
    a[4].push_back(mk(3,4));
    for (int i=5;i<101;i++){
        if (i%2==0){
            rep(j,i-2){
                a[i].push_back(mk(1,2+j));
                a[i].push_back(mk(i,2+j));
            }
            rep(j,a[i-2].size()){
                a[i].push_back(mk(a[i-2][j].first+1,a[i-2][j].second+1));
            }
        }
        if (i%2==1){
            rep(j,i-1){
                a[i].push_back(mk(i,1+j));
            }
            rep(j,a[i-1].size()){
                a[i].push_back(mk(a[i-1][j].first,a[i-1][j].second));
            }
        }
    }
    cout << a[n].size() << endl;
    rep(i,a[n].size()){
        cout << a[n][i].first << " " << a[n][i].second << endl;
    }
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>//头文件
using namespace std;
string a,b;//定义不多说
int main(){
    cin>>a>>b;//输入这两个字符串
    if(a[0]==b[2]&&a[1]==b[1]&&a[2]==b[0])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;//直接判断
    return 0;//完美结束
}

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

#define int long long
#define double long double

using namespace std;

#define REP(i, a, b) for (int(i) = (a); i < (b); (i)++)
#define rep(i, n) REP(i, 0, n)
#define PER(i, a, b) for (int(i) = (a - 1); i >= (b); (i)--)
#define per(i, n) PER(i, n, 0)
#define each(i, n) for (auto &i : n)
#define clr(a) memset((a), 0, sizeof(a))
#define mclr(a) memset((a), -1, sizeof(a))
#define all(a) (a).begin(), (a).end()
#define dum(val) cerr << #val " = " << val << " ";
#define dump(val) cerr << #val " = " << val << endl;
#define FILL(a, v) fill(a, a + sizeof(a) / sizeof(*a), v)

typedef pair<int, int> P;

const int mod = 1e9 + 7;
const int INF = 1e9;

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

	vector<int> a(n), b(n);

	rep(i, n) {
		cin >> a[i];
	}
	rep(i, n) {
		cin >> b[i];
	}

	int c = 0;
	int t = 0;
	rep(i, n) {
		if (a[i] < b[i]) {
			c += (b[i] - a[i]) / 2;
		}
		if (a[i] > b[i]) {
			t += a[i] - b[i];
		}
	}

	if (c >= t) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	/*
	 * a_i < b_i ○
	 * a_i == b_i ○
	 * a_i > b_i  
	 * 
	*/

	return 0;
}


Measured memory_bytes: 384
<?php
    $a;
    $b;
    $c;
    $r;
    fscanf(STDIN, "%d %d %d", $a, $b, $c);
    $r = max($a, $b, $c) * 3 - $a - $b - $c;
    if($r % 2 == 1){
        $r += 3;
    }
    $r = floor($r / 2);
    echo "$r\n";
?>

Measured memory_bytes: 3576
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		int flag=0;
		if(x==2) {
			System.out.println(2);
			System.exit(0);
		}
		if(x%2==0) {
			for(long i=x+1;;i+=2) {
				for(long j=3;j<Math.sqrt(i);j++) {
					flag=0;
					if(i%j==0) {
						flag=1;
						break;
					}
				}
				if(flag==0) {
					System.out.println(i);
					break;
				}
			}
		}else {
			for(long i=x;;i+=2) {
				for(long j=3;j<Math.sqrt(i);j++) {
					flag=0;
					if(i%j==0) {
						flag=1;
						break;
					}
				}
				if(flag==0) {
					System.out.println(i);
					break;
				}
			}
		}
	}

	public static long f(long n) {
		if(n%5!=0) {
			return 0;
		}else{
			return 1+f(n/5);
		}
	}
}




Measured memory_bytes: 23764
l = []

while True:
  xy = list(map(int, input().split()))
  if (xy[0] == 0 and xy[1] == 0):
    break
  else:
    l.append(xy)

for i in range(0, len(l)):
  x, y = l[i][1], l[i][0]
  if (x > y):
    print(y, x)
  else:
    print(x, y)


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << ""; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = LLONG_MAX;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(16);

	//cout << setprecision(10) << scientific << ans << endl;
}

signed main() {
	ll n;
	ll t, a;

	cin >> n;

	ll nowt = 1;
	ll nowa = 1;

	REP(i, n) {
		cin >> t >> a;
		ll x = max((nowt + t - 1) / t, (nowa + a - 1) / a);
		nowt = x * t;
		nowa = x * a;
	}

	cout << nowt + nowa << endl;
}

Measured memory_bytes: 256
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())

h1,m1,h2,m2,k=reads()
limit=(h2-h1)*60+m2-m1
res=0
if limit-k>=0:
    limit-=k
else:limit=0
print(limit)

Measured memory_bytes: 9552
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int main() {
  string s; cin >>s;
  int K; cin >>K;
  int N = s.size();
  set<string> S;

  rep(i, N){
    string t = "";
    rep(j, K){
      if (i+j == N) break;
      t += s[i+j];
      S.insert(t);
    }
  }
  int i = 0;
  for (string t : S){
    i++;
    if (i == K){
      cout <<t <<endl;
      return 0;
    }
  }
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
    ll X;
    cin >> X;

    ll n = floor(-0.5 + sqrt(1+8*X)/2);

    ll ans;
    if(n*n + n - 2*X == 0) ans = n;
    else ans = n+1;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int a,b;
    cin >> a >> b;
    if(a <= 0 && b >= 0) {
        cout << "Zero"  << endl;
    }
    else if(a >= 1 && b >= 1) {
        cout << "Positive"  << endl;
    }
    else if(abs(b-a)%2 == 0) {
        cout << "Negative" << endl;
    }
    else {
        cout << "Positive" << endl;
    }
}

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

using namespace std;

bool f(pair<int, pair<string, int> >a,pair<int, pair<string, int> >b){
  if(a.second.first == b.second.first && a.second.second > b.second.second)
    return 1;
  else if(a.second.first < b.second.first)
    return 1;
  else
    return 0;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int N;
  cin>>N;
  string str;
  int score;
  vector< pair<int , pair<string, int> > >v(N);
  for(int i=0;i<N;i++){
    cin>>str>>score;
    v[i]=make_pair(i+1, make_pair(str,score));
  }
  sort(v.begin(),v.end(),f);
  for(int i=0;i<N;i++) cout<<v[i].first<<"\n";
  return 0;
}


Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
Used = [1] * M
Q = []

for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    Edge[a].append((b, c, _))
    Edge[b].append((a, c, _))

for i in range(N):
    now = (0, i)
    Seen = [-1] * N
    used = [-1] * N
    wait = []
    heapq.heappush(wait, now)
    Seen[i] = 0
    while len(wait) > 0:
        time, now = heapq.heappop(wait)
        for nex, cost, bridgenum in Edge[now]:
            if Seen[nex] == -1:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
            elif Seen[nex] > time + cost:
                Ne = (time + cost, nex)
                Seen[nex] = time + cost
                heapq.heappush(wait, Ne)
                used[nex] = bridgenum
    for j in range(N):
        if used[j] != -1:
            Used[used[j]] = 0
print(sum(Used))

Measured memory_bytes: 54620
/*input
121
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

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

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

void solve(){
  	int n;cin >> n;
  	int odd = (n+1)/2;
  	double ans = (double)odd/(double)n;
  	cout << fixed << setprecision(10) << ans;
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Measured memory_bytes: 256
// Author: Shusuke Ueda
// AtCoder Beginner Contest 126 - Problem E

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<bool> visited(n, false);
    std::vector<std::vector<int>> to(n, std::vector<int>(0));
    for (int i = 0; i < m; i++) {
        int x, y, z;
        std::cin >> x >> y >> z;
        x--;
        y--;
        to[x].push_back(y);
        to[y].push_back(x);
    }

    auto dfs = [&](auto&& dfs_, int pos) -> void {
        visited[pos] = true;
        for (int next: to[pos]) {
            if (visited[next] == false) {
                dfs_(dfs_, next);
            }
        }
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i] == false) {
            ans++;
            dfs(dfs, i);
        }
    }

    std::cout << ans << std::endl;
    
    return 0;
}

Measured memory_bytes: 7808
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
#include <cstdint>
#include <chrono>

using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=a-1;i>=n;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pii>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=5e5+10,oo=0x3f3f3f3f,MOD=1e9+7;
const long double PI = acos(-1),eps=1.0e-14;

void solve(){
    ll n,m;
    cin>>n>>m;
    vii v(n);
    for(auto &i:v)
        cin>>i.f>>i.s;
    sort(allv(v));
    ll res=0;
    loop(n,i,0){
        ll x=min(m,v[i].s);
        m-=x;
        res+=x*v[i].f;
        if(!m)
            break;
    }
    cout<<res<<Endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();

}


Measured memory_bytes: 4764
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    public static long count;
    static void Main(string[] args)
    {
        int[] arr = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int n = arr[0];
        int k = arr[1];
        int value = 1;
        int ans = 0;
        while(value <= n)
        {
            value *= k;
            ans++;
        }
        Console.WriteLine(ans);
    }

  

}




Measured memory_bytes: 13396
def tasu(i):
    global bubun
    if i >= len(string):
        return
    elif string[i] == "A" or string[i] == "C" or string[i] == "G" or string[i] == "T":
        bubun += string[i]
        tasu(i + 1)

string = input()

lst = [""]

for i in range(len(string)):
    if string[i] == "A" or string[i] == "C" or string[i] == "G" or string[i] == "T":
        bubun = ""
        tasu(i)
        lst.append(bubun)

print(len(max(lst, key=len)))

Measured memory_bytes: 3064
N = int(input())
L = []
L.append(input())

A = L[0].split()
B = [0] * N
for i in range(N):
	B[i] = int(A[i])


ans = 0

C = [0] *3
C2 = [0] *3

for i in range(N-2):
	C[0] = B[i]
	for j in range(N-1):
		C[1] = B[j]
		for k in range(N):
			C[2] = B[k]
			C2 = sorted(C)
			if i<j<k and  C2[2] < C2[1] + C2[0] and B[i] != B[j] and B[j] != B[k] and B[k] != B[i]:
				ans += 1


print(ans)


Measured memory_bytes: 9164
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


# x,y,z,k = map(int,input().split())
# a = list(map(int,input().split()))
# b = list(map(int,input().split()))
# c = list(map(int,input().split()))
#
# a.sort()
# b.sort()
# c.sort()
# a = a[::-1]
# b = b[::-1]
# c = c[::-1]
#
# d=0
# e=0
# f=0
# for i in range(k):


n = int(input())
mov = []
for i in range(5):
    mov.append(int(input()))

mov.sort()

min = mov[0]

if min >= n:
    print(5)
else:
    if n % min != 0:
        ex = n // min
    else:
        ex = n//min -1

    print(5+ex)



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

int main()
{
    int N;
    cin >> N;
    vector<long unsigned int> A, B;
    int nA = N+1;
    int nB = N;
    while(nA--) {
        int a;
        cin >> a;
        A.push_back(a);
    }
    while(nB--) {
        int b;
        cin >> b;
        B.push_back(b);
    }

    long unsigned int nm = 0;
    for (int i=0; i<N; i++) {
        int hit = min(A[i], B[i]);;
        // A[i] -= hit;
        B[i] -= hit;
        nm += hit;

        hit = min(A[i+1], B[i]);
        A[i+1] -= hit;
        // B[i] -= hit;
        nm += hit;
    }

    cout << nm << endl;

    return 0;
}

Measured memory_bytes: 2548
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <bitset>

#define PB push_back
#define MP make_pair
#define YES cout<<"YES"<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define No cout<<"No"<<endl
#define INF (1<<30)
#define LLINF (1LL<<60)
#define MOD 1000000007
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
using namespace std;

struct edge { int u, v, cost; };
int N;
vector<pair<int, int>>x, y;
int par[400005];
int rnk[400005];
edge es[400005];

bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

void init(int n) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rnk[i] = 0;
    }
}

int find(int x) {
    if (par[x] == x) {
        return x;
    }
    else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;

    if (rnk[x] < rnk[y]) {
        par[x] = y;
    }
    else {
        par[y] = x;
        if (rnk[x] == rnk[y])rnk[x]++;
    }
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int kruskal() {
    int E = (N - 1) * 4;
    sort(es, es + E, comp);
    init(N);
    int res = 0;
    for (int i = 0; i < E; i++) {
        edge e = es[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}

int main() {
    cin >> N;
    init(N);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        x.PB(MP(a, i));
        y.PB(MP(b, i));
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    for (int i = 0; i < N - 1; i++) {
        edge e;
        e.u = x[i].second;
        e.v = x[i + 1].second;
        e.cost = x[i + 1].first - x[i].first;
        es[i] = e;
        e.u = x[i + 1].second;
        e.v = x[i].second;
        e.cost = x[i + 1].first - x[i].first;
        es[i + (N - 1)] = e;
        e.u = y[i].second;
        e.v = y[i + 1].second;
        e.cost = y[i + 1].first - y[i].first;
        es[i + (N - 1)*2] = e;
        e.u = y[i + 1].second;
        e.v = y[i].second;
        e.cost = y[i + 1].first - y[i].first;
        es[i + (N - 1)*3] = e;
    }
    cout << kruskal() << endl;
    return 0;
}


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

int main(){
  int a, p;
  cin >> a >> p;
  
  int k = 3*a + p;
  if (k%2 == 0)
    cout << k/2 << endl;
  else
    cout << (k-1)/2 << endl;
}

Measured memory_bytes: 3592
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        //値の取得
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long T = sc.nextLong();
        long[] t = new long[N];
        for (int i = 0; i < N; ++i){
            t[i] = sc.nextLong();
        }
        
        long X = 0; //総和
        
        for (int i = 0; i < N-1; ++i){
            X += Math.min(T,t[i+1]-t[i]);   //t[i+1]-t[i]：次の人が来るまでの時間
        }
        
        X += T; //最後にTを加える
        
        System.out.println(X);
        
    }
}


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

int main() {
    int n,k;
    cin >> n >> k;
    int ans = 0;
    while(n>0){
        n=n/k;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  rep(i,N) cin >> A[i];
  rep(i,N) cin >> B[i];
  vector<int> p(N);
  rep(i,N) p[i] = i+1;

  map<vector<int>, int> mp;
  do {
    mp[p] = mp.size();
  } while (next_permutation(p.begin(), p.end()));
  int ans = abs(mp[A] - mp[B]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 8212
N, M = map(int, input().split())
Adj = [[10 ** 7 for j in range(N)] for i in range(N)]
for i in range(N):
  Adj[i][i] = 0
Edge = []
for m in range(M):
  a, b, c = map(int, input().split())
  Adj[a - 1][b - 1] = c
  Adj[b - 1][a - 1] = c
  Edge.append([a - 1, b - 1, c])
for i in range(N):
  for j in range(N):
    for k in range(N):
      Adj[j][k] = min(Adj[j][i] + Adj[i][k], Adj[j][k])
Unused = [1 for m in range(M)]
for i, e in enumerate(Edge):
  for s in range(N):
    if Adj[s][e[0]] + e[2] == Adj[s][e[1]]:
      Unused[i] = 0
print(sum(Unused))

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

const ll MAX = 1000000+2;
const ll MOD = 1000000007;
ll fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

ll modpow(ll a,ll n){
    ll res = 1;
    while(n>0){
        // &１つはビット積
        if(n&1) res = res * a%MOD;
        a = a*a%MOD;
        n>>=1;
    }
    return res;
}


int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	COMinit();
	ll N;
	cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin>>A[i];
    }
    ll ans = 0;

    rep(i,N){
        ans += inv[A[i]];
        ans %=MOD;
    }
    
    ll maxn = 10e3+1;
    map<ll,ll> gcm;
    map<ll,ll> gcm_mp;
    rep(i,N){
        gcm_mp.clear();
        for(ll j=2;j<=pow(A[i],0.5);j++){
            while(A[i]%j==0){
                gcm_mp[j]++;
                A[i]/=j;
            }
        }
        if(A[i]!=1){
            gcm_mp[A[i]]++;
        }
        for(auto it:gcm_mp){
            gcm[it.first]= max(gcm[it.first],it.second);
        }
    }
    ll lcm = 1;
    for(auto it:gcm){
        lcm *= modpow(it.first,it.second)%MOD;
        // cout<<it.first << " "<< it.second<<"\n";
        lcm %=MOD;
    }
    ans *=lcm;
    ans %=MOD;
    // cout<<lcm<<"\n";
    cout<<ans<<"\n";

	return 0;
}

Measured memory_bytes: 24448
x, n = map(int, input().split())
p = list(map(int, input().split()))
if p == []:
    print(x)
    exit()
t = [0]*(max(p)+2)
for i in p:
    t[i] = 1

mi = t[:x+1]
ma = t[x:]
mi.reverse()
mii = mi.index(0)
maa = ma.index(0)

if mii < maa:
    print(x-mii)
elif mii > maa:
    print(x+maa)
elif mii == maa:
    print(x-mii)

Measured memory_bytes: 9208
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

for i in A:
    data[i] += 1

sum_val = my_sum(data)

for i in range(Q):
    B, C = map(int,input().split())

    sum_val = sum_val - (data[B] * B) + (data[B] * C)

    data[C] += data[B]
    data[B] = 0

    print(sum_val)


Measured memory_bytes: 20804
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    it.next();
    let mut sum = 0;
    let mut ans = 0;
    for s in it {
        let a: u32 = s.parse().unwrap();
        ans += sum * a;
        sum += a;
    }
    println!("{}", ans);
}

fn main() {
    run();
}


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

using namespace std;
const int mod = 1e9 + 7;
int mem[2003][2003][5];
vector<int> v1, v2;
int solve(int a, int b, int right=0) {
    if(a == v1.size() || b == v2.size())
        return right == 0;

    int &ret = mem[a][b][right];
    if(~ret) return ret;
    ret = 0;
    if(v1[a] == v2[b]) ret += solve(a + 1, b + 1);
    if(right == 1 || right == 0) ret += solve(a + 1, b, 1);
    ret %= mod;
    if(right == 2 || right == 0) ret += solve(a, b + 1, 2);
    ret %= mod;
    if(right == 0) ret += solve(a + 1, b + 1);
    ret %= mod;
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
#endif

    memset(mem, -1, sizeof(mem));
    int n, m;
    scanf("%d %d", &n, &m);
    v1.resize(n);
    for(int i=0; i<n; i++)
        scanf("%d", &v1[i]);
    v2.resize(m);
    for(int i=0; i<m; i++)
        scanf("%d", &v2[i]);
    printf("%d\n", solve(0, 0));


    return 0;
}

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

public class Main {
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			String[] array = br.readLine().split(" ");
			int N = Integer.parseInt(array[0]);
			int C = Integer.parseInt(array[1]);

			int[] channels = new int[N];
			int[] starts = new int[N];
			int[] ends = new int[N];
			for (int i = 0; i < N; i++) {
				String[] tmp = br.readLine().split(" ");

				starts[i] = Integer.parseInt(tmp[0]);
				ends[i] = Integer.parseInt(tmp[1]);
				channels[i] = Integer.parseInt(tmp[2]);
			}
			final int[] table = new int[2 * 100_001];
			final boolean[] tmp = new boolean[2 * 100_001];
			boolean updated = false;
			for (int channel = 1; channel <= C; channel++) {
				if (updated) {
					for (int i = 0; i < tmp.length; i++) {
						tmp[i] = false;
					}
					updated = false;
				}

				for (int index = 0; index < N; index++) {
					if (channels[index] == channel) {
						for (int i = starts[index] * 2 - 1; i <= ends[index] * 2; i++) {
							tmp[i] = true;
						}
						updated = true;
					}
				}

				for (int i = 0; i < table.length; i++) {
					if (tmp[i]) {
						table[i]++;
					}
				}
			}

			int max = Integer.MIN_VALUE;
			for (int i = 0; i < table.length; i++) {
				max = Math.max(max, table[i]);
			}

			System.out.println(max);
		}
	}
}


Measured memory_bytes: 49204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int N1,N2,N3,N4;
  int keepA=0,keepB=0,countA=1,countB=1;
  cin >> N;
  N1 = N/1000;
  N2 = (N-N1*1000)/100;
  N3 = (N-N1*1000-N2*100)/10;
  N4 = (N-N1*1000-N2*100-N3*10);
  keepA = N1;
  keepB = N2;
  if(keepA == N2){
    countA++;
  }
  if(keepA == N3){
    countA++;
  }
  if(keepB == N3){
    countB++;
  }
  if(keepB == N4){
    countB++;
  }
  if(countA>=3 || countB>=3){
    cout << "Yes";
  }else{
    cout << "No";
  } 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cctype>

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

using namespace std;

int p,q,r,now;
string s;

int formula(){
	
	if(isdigit(s[now])){return s[now++]-'0';}
	else if(s[now]=='P'){now++;return p;}
	else if(s[now]=='Q'){now++;return q;}
	else if(s[now]=='R'){now++;return r;}
	
	int res=0;
	if(s[now]=='-'){now++;return 2-formula();}
	else if(s[now]=='('){
		now++;
		res=formula();
		if(s[now]=='*'){now++;res=min(res,formula());}
		else if(s[now]=='+'){now++;res=max(res,formula());}
		now++;
	}

	return res;
}

int main(void){
	
	while(cin >> s,s!="."){
		
		int cnt=0;
		rep(p,3)rep(q,3)rep(r,3){
			now=0;
			if(formula()==2)cnt++;
		}
		cout << cnt << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1188
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AtCoder
{
	public class ABC
	{
		static int mod = 1000000007;  // 10^9+7

		static void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });


			int n = int.Parse(Console.ReadLine());
			//string s = Console.ReadLine();
			int[] h = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int ans = 0;

			while (true) {
				bool f = false;
				for (int i = 0; i < n; i++) {
					if (h[i] > 0) {
						h[i]--;
						f = true;
					} else if (f) {
						break;
					}
				}
				if (f) {
					ans++;
				} else {
					break;
				}
			}
			Console.WriteLine(ans);


			Console.Out.Flush();
		}
	}
}


Measured memory_bytes: 13396
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

memo = {}
s = set()

ans = 0
def dfs(idx, money, stocks):
    global ans
    if idx==N:
        ans = max(ans, money)
        return
    a = As[idx]
    if (idx, stocks) in s:
        if money<=memo[(idx, stocks)]:
            return
    s.add((idx, stocks))
    memo[(idx, stocks)] = money
    dfs(idx+1, money+stocks*a, 0)
    dfs(idx+1, money, stocks)
    cnt = money//a
    dfs(idx+1, money-cnt*a, stocks+cnt)

dfs(0, 1000, 0)
print(ans)

Measured memory_bytes: 96704
s = list(input())
renzoku = 0
count = 0
hu_renzoku = 0
renli = []
for i in s:
    count += 1
    if i == "A" or i == "T" or i == "C" or i == "G":
        renzoku += 1
        renli.append(renzoku)
    else:
        renzoku = 0
        hu_renzoku += 1
if count == hu_renzoku:
    print(0)
else:
    print(max(renli))

Measured memory_bytes: 3064
a, b = map(int, input().split())
a_prime_factor = []
b_prime_factor = []
for i in range(2, int(a ** 0.5) + 1):
    if a % i == 0:
        a_prime_factor.append(i)
    while a % i == 0:
        a //= i
if a != 1:
    a_prime_factor.append(a)
for i in range(2, int(b ** 0.5) + 1):
    if b % i == 0:
        b_prime_factor.append(i)
    while b % i == 0:
        b //= i
if b != 1:
    b_prime_factor.append(b)
ans = 1
for i in a_prime_factor:
    if i in b_prime_factor:
        ans += 1
print(ans)

Measured memory_bytes: 3064
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		// スペース区切りの整数の入力
		int b = sc.nextInt();
		
		
		// 出力
                if(a%500<=b)
		System.out.println( "Yes");
else
System.out.println( "No");
	}
}


Measured memory_bytes: 22484
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
*X, = map(int, input().split())
E = []
for i in range(M):
    a, b, y = map(int, input().split())
    E.append((y, a-1, b-1))
E.sort()

*p, = range(N)
Z = [0]*M
A = X[:]
C = [-1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

if N > 1:
    from collections import deque
    que = deque()
    if sx < E[C[0]][0]:
        que.append(C[0])
    #print(G, C)
    while que:
        v = que.popleft()
        #print(v)
        if G[v] is not None:
            ans += 1
            for w in G[v]:
                que.append(w)
print(ans)

Measured memory_bytes: 137516