akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    int n;
    while (cin >> n, n) {
        vi data(n), num(n);
        rep(i, n) {
            cin >> data[i] >> num[i];
        }
        vvi dp(n+1, vi(70200, 0));
        dp[0][0] = 1;
        rep(i, n) {
            rep(j, 70200) {
                dp[i+1][j] += dp[i][j];
            }
            Rep(j, num[i]+1) {
                for (int k = 70100; k >= 0; k--) {
                    if (dp[i][k]) {
                        dp[i+1][k+data[i]*j] += dp[i][k];
                    }
                }
            }
        }
        Int(g);
        while (g--) {
            Int(tmp);
            cout << dp[n][tmp] << endl;
        }
    }

    return 0;
}

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

int main()
{
    string A;
    string B;
    string C;
    cin >> A >> B >> C;

    char next = 'a';
    string next_str = A;
    while (true) {
        if (next == 'a') {
            if (A.size() == 0) {
                break;
            }
            next = A.at(0);
            A = A.substr(1);
        }
        else if (next == 'b') {
            if (B.size() == 0) {
                break;
            }
            next = B.at(0);
            B = B.substr(1);
        }
        else {
            if (C.size() == 0) {
                break;
            }
            next = C.at(0);
            C = C.substr(1);
        }
    }

    cout << (char)(next - ('a' - 'A')) << endl;

    return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=a;i>=n;i--)
#define trav(a,x) for(auto& a:x)
#define all(c) c.begin(), c.end()
#define fst first
#define sec second
#define pb push_back
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX 100007
 
typedef vector<int> vi;
typedef pair<int,int> pii;


int32_t main()
{
  int n,val,ans=0;
  cin>>n;
  rep(i,n)
  {
    cin>>val;
    ans+=(val-1);
  }

  cout<<ans<<endl;
  return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int fact(int n)
{
    if(n==0)
        return 1;
    return (n*fact(n-1));
}
int main()
{
    int n,i,j,d;
    cin>>n;
    int x[n],y[n];
    for(i=0;i<n;i++)
        cin>>x[i]>>y[i];

   double len=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i!=j)
                {
                    len+=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                }
        }
    }
    d=fact(n);
    len=(len*fact(n-1))/d;
    cout.precision(10);
    cout<<fixed<<len<<endl;
    return 0;
}

Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#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 reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int q;
    cin >> q;
    multimap<string, int> mmp;
    while (q--) {
        int com, x; string key, l, r;
        cin >> com;
        if (com == 0) {
            cin >> key >> x;
            mmp.emplace(key, x);
        } else if (com == 1) {
            cin >> key;
            auto ret = mmp.equal_range(key);
            for (auto it = ret.first; it != ret.second; ++it) {
                cout << it->second << endl;
            }
        } else if (com == 2) {
            cin >> key;
            mmp.erase(key);
        } else {
            cin >> l >> r;
            auto it = mmp.lower_bound(l);
            auto last = mmp.upper_bound(r);
            while (it != last) {
                cout << it->first << " " << it->second << endl;
                ++it;
            }
        }
    }
}



Measured memory_bytes: 24740
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define FOR(idx, begin, end) for(int idx = (int)(begin); idx < (int)(end); ++idx)

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

using namespace std;
typedef long long lint;

const int MOD = 100000007;
const int INF = 1 << 29;
const double EPS = 1e-9;


int main() {

	cin.tie(0);

	int A[5], B[5], ans = 0;

	FOR(i, 0, 5) {
		cin >> A[i];
		B[i] = (A[i] - 1) % 10;
		ans += ((A[i]-1) / 10 + 1) * 10;
	}
	cout << ans - 9 + *min_element(B, B + 5);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;
public class Hello
{
    public static void Main()
    {
        int N = NextInt();
        int L = NextInt();
        int[] a = LineInt();
        //全ての結び目をほどくので、2つの長さがLある区間があれば勝ち

        int l = -1, r = -1;
        for (int i = 1; i < N; i++)
            if (a[i - 1] + a[i] >= L) { l = i - 1; r = i; break; }
        if (l == -1) { Console.WriteLine("Impossible"); return; }
        Console.WriteLine("Possible");
        for (int i = 1; i <= l; i++) Console.WriteLine(i);
        for (int i = N - 1; i > r; i--) Console.WriteLine(i);
        Console.WriteLine(r);
    }
}

public class Input
{
    private static Queue<string> queue = new Queue<string>();
    private static void Confirm() { if (queue.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) queue.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(queue.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(queue.Dequeue()); }
    public static string NextString() { Confirm(); return queue.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(queue.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 29916
#include <stdio.h>

int main()
{
	int i,j,k;
	for(i=0, j=0; ; i++, j++){
		scanf("%d %d", &i, &j);
		if(i>j){
			k=i;
			i=j;
			j=k;
		}
		if(i==0 && j==0) break;
		printf("%d %d\n", i, j);
	}

	return 0;
}

Measured memory_bytes: 600
def binary_search_a(n, a, k):
    #a_i < kを満たすa_iの個数を返す関数

    lb = 0
    ub = n - 1

    if a[ub] < k:
        return n
    elif a[lb] >= k:
        return 0

    while (ub - lb > 1):
        mid = int((ub + lb) / 2)
        if a[mid] < k:
            lb = mid
        elif a[mid] >= k:
            ub = mid
    
    return lb + 1

def binary_search_c(n, c, k):
    #c_i > kを満たすc_iの個数を返す関数

    lb = 0
    ub = n - 1

    if c[ub] <= k:
        return 0
    elif c[lb] > k:
        return n

    while (ub - lb > 1):
        mid = int((ub + lb) / 2)
        if c[mid] > k:
            ub = mid
        elif c[mid] <= k:
            lb = mid
    
    return n - ub
        

def answer(n, a, b, c):
    ans = 0

    a.sort()
    c.sort()
    #bはソートしなくてもよい

    for k in b:
        ans += binary_search_a(n, a, k) * binary_search_c(n, c, k)
        #print(binary_search_a(n, a, k),binary_search_c(n, c, k))
    return ans


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

print(str(answer(n, a, b, c)))

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

#define int long long

using namespace std;

int n, ans, k;

main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		int a;
		cin >> a;
		k += a;
		if(a == 0){
			ans += k / 2;
			k = 0;
		}
	}
	cout << ans + k / 2;
}

Measured memory_bytes: 256
n, x, m = gets.split.map(&:to_i)

opens = Hash.new()
accum = [0]
cnt = 0
a = x

while !opens.include?(x)
  accum << a
  opens[x] = cnt
  x = (x * x) % m
  a += x
  cnt += 1
end

pathlen = opens[x]
pathaccum = accum[pathlen]
loopsize = cnt - pathlen
loopaccum = accum[cnt] - accum[pathlen]
loopstart = x


res = 0
if n <= pathlen
  res = accum[n]
else
  t = (n - pathlen) / loopsize
  rest = n - pathlen - t * loopsize

  a = pathaccum + loopaccum * t
  x = loopstart
  rest.times do |i|
    a += x
    x = x * x % m
  end

  res = a
end

p res


Measured memory_bytes: 16784
fn main() {
    let (k, n): (isize, usize) = (read::<isize>(), read::<usize>());
    let mut a: Vec<isize> = vec![];
    for _ in 0..n {
        a.push(read());
    }
    let s = a[0];
    a.push(s);
    let mut anss: isize = k - a[n - 1] + a[0];
    for i in 1..n + 1 {
        anss = max(anss, a[i] - a[i - 1]);
    }
    println!("{}", k - anss);
}

// =========
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};
#[allow(unused_imports)]
use std::process::exit;

#[allow(dead_code)]
const MOD: usize = 1000000007;

fn read<T: std::str::FromStr>() -> T {
    use std::io::Read;
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

// =========


Measured memory_bytes: 6396
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#define int long long
#define uint unsigned long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;

int a[300000];

signed main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N * 3; i++)
	{
		cin >> a[i];
	}

	ARY_SORT(a, N * 3);
	reverse(a, a + N * 3);

	int sum = 0;
	for (int i = 0; i < N; i++)
	{
		sum += a[i * 2 + 1];
	}
	cout << sum << endl;
}


Measured memory_bytes: 2560
var dp=[];
for(var i=0;i<=10;i++){
   dp[i]=[];
   for(var j=0;j<=330;j++){
      dp[i][j]=0;
   }
}
 
var used=[];
for(var i=0;i<=9;i++)used[i]=false;
 
function bomb(sum,cnt){
   dp[cnt][sum]++;
   cnt++;
   for(var i=0;i<=9;i++){
      if(used[i])continue;
      used[i]=true;
      bomb(sum+i*cnt,cnt);
      used[i]=false;
   }
}
 
bomb(0,0);
 
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
arr.forEach(function(v){
   var ns=v.split(" ").map(Number);
   var n=ns[0];
   var s=ns[1];
   var ans=(dp[n][s]==undefined)?0:dp[n][s]
   console.log(ans);
});

Measured memory_bytes: 15964
#include<stdio.h>
int main ()
{
    int A1,A2,A3;
    scanf("%d %d %d",&A1,&A2,&A3);
    if(1<=A1 && A1<=13 &&  1<=A2 && A2<=13 && 1<=A3 && A3<=13 && A1+A2+A3>=22)
    {
    printf("bust");
    }
    else

    {
        printf("win");
        }
        return 0;
}


Measured memory_bytes: 128
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


def lcm(x, y): return (x * y) // gcd(x, y)


N, K = inp_list()

mod = N % K
sho = N // K

if mod == 0:
    print(0)
else:
    ans = min(abs(sho * K - N), abs((sho + 1) * K - N))
    print(ans)



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

signed main () {
	unordered_map < int, long long > cnt;
	int n;
	cin >> n;
	vector < int > a(n);
	for (int &x: a) {
		cin >> x;
		++cnt[x];
	}
	long long tt = 0;
	for (auto p: cnt) 
		tt += (p.second * (p.second - 1)) / 2;
	for (int i = 0; i < n; ++i) 
		cout << tt - (cnt[a[i]] - 1) << '\n';
	
	return 0;
}


Measured memory_bytes: 8392
#include <iostream>
using namespace std;
int main()
{
int n, val, x = 1, ans = -1;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> val;
if (val == x) x++;
}
if (x == 1) cout << -1;
else
cout << n - x + 1;
return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
        Scanner stdin = new Scanner(System.in);

        int N = stdin.nextInt();
        int d[] = new int[N];
        int sum =0;

        for(int i=0;i<N;i++) {
        	d[i] = stdin.nextInt();
        }
        for(int i=0;i<N-1;i++) {
        	for(int j=i+1;j<N;j++) {
        		sum += d[i]*d[j];
        	}
        }
        System.out.println(sum);
	}
}


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

int main() {
	vector<int> v = {111, 222, 333, 444, 555, 666, 777, 888, 999};
	int n;
	cin >> n;
	for (auto num: v) {
		if (n <= num) {
			cout << num << endl;
			break;
		}
	}
	return 0;
}

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

int main(void){
  
  string s,t;
  cin >> s;
  cin >> t;
  int all_i = 0,s_i=0,t_i=0;
  int len = s.size() + t.size();
  
  while(1){
      if(all_i %2 == 0){
          cout << s[s_i];
          s_i++;
      }
      else{
          cout << t[t_i];
          t_i++;
      }
      all_i++;
      if(all_i >= len) break;
  }
  cout << endl;
}


Measured memory_bytes: 3564
s = input()

tmp = ""
cnt = 0
ans = 0
flag = False  # skip用
for i in range(0, len(s) - 1):
    if flag:
        flag = False
        continue
    if s[i] == "A":
        cnt += 1
    elif s[i] + s[i + 1] == "BC":
        ans += cnt
        flag = True
    else:
        cnt = 0

print(ans)

Measured memory_bytes: 67840
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

#define NUM 10000

bool fixed[101];
int fixed_menu[101];

int main(){

	int ans = 0;

	for(int i = 1; i <= 100; i++)fixed[i] = false;

	int N,K,day,menu;

	scanf("%d %d",&N,&K);
    int dp[N+1][4][4];

    for(int i = 0; i < N+1; i++){
    	for(int k = 1; k <= 3; k++){
    		for(int p = 1; p <= 3; p++){
    			dp[i][k][p] = 0;
    		}
    	}
    }

	for(int loop = 0; loop < K; loop++){
		scanf("%d %d",&day,&menu);
		fixed[day] = true;
		fixed_menu[day] = menu;
	}

	if(fixed[1] == true && fixed[2] == true){
		dp[2][fixed_menu[1]][fixed_menu[2]] = 1;
	}else if(fixed[1] == true && fixed[2] == false){
		dp[2][fixed_menu[1]][1] = 1;
		dp[2][fixed_menu[1]][2] = 1;
		dp[2][fixed_menu[1]][3] = 1;
	}else if(fixed[1] == false && fixed[2] == true){
		dp[2][1][fixed_menu[2]] = 1;
		dp[2][2][fixed_menu[2]] = 1;
		dp[2][3][fixed_menu[2]] = 1;
	}else{
		for(int row = 1; row <= 3; row++){
			for(int col = 1; col <= 3; col++){
				dp[2][row][col] = 1;
			}
		}
	}

	for(int i = 3; i <= N; i++){
		if(fixed[i] == true){
			switch(fixed_menu[i]){
			case 1:
				dp[i][1][1] = (dp[i-1][2][1] + dp[i-1][3][1])%NUM;
				dp[i][2][1] = (dp[i-1][1][2] + dp[i-1][2][2] + dp[i-1][3][2])%NUM;
				dp[i][3][1] = (dp[i-1][1][3] + dp[i-1][2][3] + dp[i-1][3][3])%NUM;
				break;
			case 2:
				dp[i][1][2] = (dp[i-1][1][1] + dp[i-1][2][1] + dp[i-1][3][1])%NUM;
				dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][3][2])%NUM;
				dp[i][3][2] = (dp[i-1][1][3] + dp[i-1][2][3] + dp[i-1][3][3])%NUM;
				break;
			case 3:
				dp[i][1][3] = (dp[i-1][1][1] + dp[i-1][2][1] + dp[i-1][3][1])%NUM;
				dp[i][2][3] = (dp[i-1][1][2] + dp[i-1][2][2] + dp[i-1][3][2])%NUM;
				dp[i][3][3] = (dp[i-1][1][3] + dp[i-1][2][3])%NUM;
				break;
			}
		}else{
			dp[i][1][1] = (dp[i-1][2][1] + dp[i-1][3][1])%NUM;
			dp[i][2][1] = (dp[i-1][1][2] + dp[i-1][2][2] + dp[i-1][3][2])%NUM;
			dp[i][3][1] = (dp[i-1][1][3] + dp[i-1][2][3] + dp[i-1][3][3])%NUM;
			dp[i][1][2] = (dp[i-1][1][1] + dp[i-1][2][1] + dp[i-1][3][1])%NUM;
			dp[i][2][2] = (dp[i-1][1][2] + dp[i-1][3][2])%NUM;
			dp[i][3][2] = (dp[i-1][1][3] + dp[i-1][2][3] + dp[i-1][3][3])%NUM;
			dp[i][1][3] = (dp[i-1][1][1] + dp[i-1][2][1] + dp[i-1][3][1])%NUM;
			dp[i][2][3] = (dp[i-1][1][2] + dp[i-1][2][2] + dp[i-1][3][2])%NUM;
			dp[i][3][3] = (dp[i-1][1][3] + dp[i-1][2][3])%NUM;
		}

	}

	for(int row = 1; row <= 3; row++){
		for(int col = 1; col <= 3; col++){
			ans += dp[N][row][col];
		}
	}

	ans %= NUM;

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

    return 0;
}

Measured memory_bytes: 2652
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    string s;
    cin >> s;
    bool flag = true;
    rep(i, s.size() - 1)
    {
        if(s[i]!=s[i+1]){
            flag = false;
        }
    }
    if(flag){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
using namespace std;
bitset<10000> cookie[10];
bool now;
int main()
{
	int r,c;
	while(cin>>r>>c && r>0)
	{
		int i,j;
		for(int i=0;i<r;i++)
		{
			for(int j=0;j<c;j++)
			{
				cin>>now;
				cookie[i][j]=now;
			}
		}
		int ans=0;
		for(int i=0;i<(1<<r);i++)
		{
			for(int j=0;j<r;j++)
			{
				if(i & (1<<j))
				{
					cookie[j].flip();
				}
			}
			
			int possible_ans=0;
			for(int j=0;j<c;j++)
			{
				int up_cookie=0;
				for(int k=0;k<r;k++)
				{
					if(cookie[k][j])
					up_cookie++;
				}
				possible_ans+=max(up_cookie,r-up_cookie); 
			}
			ans=max(ans,possible_ans);
			
			for(int j=0;j<r;j++)
			{
				if(i & (1<<j))
				{
					cookie[j].flip();
				}
			}
			
		}
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 3084
// g++ -std=gnu++1y -O2 -I/opt/boost/gcc/include -L/opt/boost/gcc/lib -o ./a.out ./X.cpp & a.out //
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ull unsigned long long


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);	
    cin.tie(NULL); cout.tie(NULL);
    
    string n; cin >> n;
    
    cout << (n=="ABC" ? "ARC" : "ABC");
    
    return 0;
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int M = 1000000007;
#define pb push_back
#define fs fist
#define sc second
#define forn(i,n) for(int i = 0; i < n; ++i)
#define nfor(i,n) for(int i = n; i >= 0; --i)
#define vi vector<int>
#define pii pair<int,int>
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
ll freq[500001] = {0};
ll distinct = 0;
int BLK;
struct query{
	int L;
	int R;
	int id;
	int block;
//	bool operator < (query & q2){
//		if(block < q2.block) return 1;
//		else if(block > q2.block) return 0;
//		else return R < q2.R;
//	}
};
bool comp(query a, query b){
	if(a.L/BLK != b.L/BLK) return a.L/BLK < b.L/BLK;
	if(a.L/BLK & 1) return a.R < b.R;
	else return a.R > b.R;
}
void Add(ll elem){
	//distinct -= freq[elem] * freq[elem] * elem;
	if(freq[elem] == 0) distinct++;
	freq[elem]++;
//	distinct += freq[elem] * freq[elem] * elem;
}
void Remove(ll elem){
	//distinct -= freq[elem] * freq[elem] * elem;
	if(freq[elem] == 1) distinct--;
	freq[elem]--;
	//distinct += freq[elem] * freq[elem] * elem;
}
void adjust(int &curr_l,int &curr_r,query &q,vector<int> &arr){
	while(curr_l < q.L){
		Remove(arr[curr_l]);
		curr_l++;
	}
	while(curr_l > q.L){
		curr_l--;
		Add(arr[curr_l]);
	}
	while(curr_r < q.R){
		curr_r++;
		Add(arr[curr_r]);
	}
	while(curr_r > q.R){
		Remove(arr[curr_r]);
		curr_r--;
	}
}
void solve(vector<query> queries, vector<int> &arr){
	vector<ll> answer(queries.size());
	sort(queries.begin(),queries.end(),comp);
	int curr_l = queries[0].L;
	int curr_r = queries[0].R;
	for(int i = queries[0].L; i <= queries[0].R; ++i){
		Add(arr[i]);
	}
	answer[queries[0].id] = distinct;
	for(int i = 1; i < queries.size(); ++i){
		adjust(curr_l,curr_r,queries[i],arr);
		answer[queries[i].id] = distinct;
	}
	for(auto x : answer) cout << x << '\n';
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n; cin >> n;
    int q; cin >> q;
    vector<int> arr(n);
    forn(i,n) cin >> arr[i];
    int rootN = sqrt(n);
    BLK = rootN;
    vector<query> queries(q);
    forn(i,q){
    	int u,v; cin >> u >> v;
    	queries[i].L = u - 1;
    	queries[i].R = v - 1;
    	queries[i].id = i;
    	queries[i].block = u/rootN;
	}
	solve(queries,arr);
    return 0;
}


Measured memory_bytes: 29176
//#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
//using namespace atcoder;
#define int long long
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
    const int MAX =3001;
const int MOD =998244353;

  
  
signed main(){
  int n,d1,d2;
  cin>>n;
  bool b[n]={};
  for(int i=0;i<n;i++){
    cin>>d1>>d2;
    if(d1==d2)b[i]=true;
  }
  for(int i=0;i<n-2;i++)if(b[i]&&b[i+1]&&b[i+2]){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
  


}

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


int main()
{
	int a, b, c, n;
	int i, j;

	cin >> a >> b >> c;

	for (i = 0; i < 100; i++) {
		if ((i*b + c) % a == 0) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using vst=vector<string>;
using P = pair<ll,ll>;
const int inf=1e9+7;
const ll INF=9e18;
template <typename T> bool chmin(T &a, const T& b){if(a > b){a = b;return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b;return true;}return false;}
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

int par[200010];//親
int rnk[200010];// rankだと怒られる

void init(int n){//初期化
  for(int i=0;i<n;i++){
     par[i]=i;
     rnk[i]=1;
  }
}

int find(int x){//親を求める
  if(par[x]==x) return x;
  return par[x]=find(par[x]);
}

void unite(int x,int y){//union
  x=find(x);
  y=find(y);
  if(x==y)return;
  if(rnk[x]<rnk[y]){//rankが小さい方にくっつける
    par[x]=y;
  }
  else{
   par[y]=x;
    if(rnk[x]==rnk[y])rnk[x]++;//rankが同じ時は1増やす
  }
}

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

int main(){cout<<fixed<<setprecision(20);
		   int n,m;
           cin>>n>>m;
           init(n);
           rep(i,0,m){
             int a,b;
             cin>>a>>b;
             a--;b--;
             unite(a,b);
           }
           /////////
           vin cnt(n,0);
           rep(i,0,n){
            cnt[find(i)]++; 
           }
           int ans=0;
           rep(i,0,n){
            chmax(ans,cnt[i]); 
           }
           cout<<ans<<endl;
           
}

Measured memory_bytes: 5624
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,i,j,k,l,m=0,n;
   char cc[1234];
   scanf("%s",&cc);
   n=strlen(cc);
   for(i=0;i<n/2;i++){
    if(cc[i]!=cc[n-1-i] && i!=n-1-i)
    m++;
   }
   printf("%d",m);
}


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

typedef long long ll;
typedef int64_t i6;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep2(i, n) for (ll i = 1; i <= n; ++i)
#define Sort(x) sort(x.begin(), x.end())
#define Sort_rev(x) sort(x.begin(), x.end(), greater<int>())
#define ALL(v) (v).begin(), (v).end()

// π M_PI
// deg = rad*180/M_PI

bool pairCompare(const pair<ll, ll>& firstElof, const pair<ll, ll>& secondElof) {
    return firstElof.first < secondElof.first;
}

int main() {
    ll n, m;
    cin >> n >> m;
    int ans = 0;
    if ( m == 0 ) {
        if ( n != 1 ) {
            ans = pow(10, n-1);
        }
        cout << ans << endl;
        return 0;
    }
    ll s[m], c[m];
    ll Ans[n] = {};
    vector<pair<ll, ll> > pairs;

    int j = 1;
    rep(i, m) {
        cin >> s[i] >> c[i];
        if ( n != 1 && s[i] == 1 && c[i] == 0 ) {
            j = 0;
        }
        pairs.push_back( make_pair(s[i], c[i]) );
    }
    if (!j) {
        cout << -1 << endl;
        return 0;
    }

    sort(ALL(pairs), pairCompare);

    rep(i, m) {
        if ( i == 0 ) {
            Ans[pairs.at(i).first-1] = pairs.at(i).second;
        } else {
            if ( Ans[pairs.at(i).first-1] != 0 ) {
                if ( Ans[pairs.at(i).first-1] != pairs.at(i).second ) {
                    j = 0;
                    break;
                }
            } else {
                Ans[pairs.at(i).first-1] = pairs.at(i).second;
            }
        }
    }

    if (!j) {
        cout << -1 << endl;
        return 0;
    }
    if ( n > 1 && Ans[0] == 0 ) {
        Ans[0] = 1;
    }

    if ( Ans[0] != 0 || Ans[1] != 0 || Ans[2] != 0 ) {
        rep(i, n) {
            if ( Ans[i] != 0 && i != n-1 ) {
                ans += Ans[i]*pow(10, n-i-2);
            } else if ( i == n-1 ) {
                ans *= 10;
                ans += Ans[i];
            }
        }
    } else {
        ans += pow(10, n-1);
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int w[200],ans[200],i=1,count;
  int sa[200];
  ans[0]=4280;
  cin>>w[1];
  while(w[i]!=-1){
    count=0;
    ans[i]=1150;
    while(count<=w[i]){
      if(count>10&&count<=20){
	ans[i]+=125;
      }
      if(count>20&&count<=30){
	ans[i]+=140;
      }
      if(count>30){
	ans[i]+=160;
      }
      count++;
    }
    sa[i]=4280-ans[i];
    i++;
    cin>>w[i];
  }
  for(int j=1;j<i;j++){
    cout<<sa[j]<<"\n";
  }
  
  
  return 0;
}
    



Measured memory_bytes: 3096
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int[] card = new int[9];
        for(int i = 0; i < 9; i++){
            card[i] = sc.nextInt();
        }
        int num = sc.nextInt();
        for(int i = 0; i< num; i++){
            int b = sc.nextInt();
            for(int j = 0; j < 9; j++){
                if (b == card[j]){
                    card[j] = 0;
                }
            }
        }
        if((card[0]==0 && card[1]==0 && card[2]==0) ||
                (card[0]==0 && card[3]==0 && card[6]==0) ||
                (card[0]==0 && card[4]==0 && card[8]==0) ||
                (card[3]==0 && card[4]==0 && card[5]==0) ||
                (card[6]==0 && card[7]==0 && card[8]==0) ||
                (card[2]==0 && card[4]==0 && card[6]==0) ||
                (card[1]==0 && card[4]==0 && card[7]==0) ||
                (card[2]==0 && card[5]==0 && card[8]==0)        
        ){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
        
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
 vector<int> A(9);
  for(int i=0;i<9;i++){
  	cin>>A.at(i);
  }
  cin>>N;
  vector<int>b(N);
  for(int i=0;i<N;i++){
  	cin>>b.at(i);
  }
  for(int i=0;i<N;i++){
  	for(int j=0;j<9;j++){
    	if(b.at(i)==A.at(j)) A.at(j)=0;
    }
  }
  if(A[1]==0&&A[2]==0&&A[0]==0) cout<<"Yes";
  else if(A[4]==0&&A[5]==0&&A[3]==0) cout<<"Yes";
  else if(A[7]==0&&A[8]==0&&A[6]==0) cout<<"Yes";
  else if(A[1]==0&&A[4]==0&&A[7]==0) cout<<"Yes";
  else if(A[2]==0&&A[5]==0&&A[8]==0) cout<<"Yes";
  else if(A[3]==0&&A[6]==0&&A[0]==0) cout<<"Yes";
  else if(A[0]==0&&A[4]==0&&A[8]==0) cout<<"Yes";
  else if(A[2]==0&&A[4]==0&&A[6]==0) cout<<"Yes";
  else cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> PPI;
typedef pair<LL, LL> PL;
typedef long long LL;
// LLONG_MIN, INT_MIN
#define xx first
#define yy second

// int seg[810000];
// void build(int id=1, int l=0, int r = n){
//   if(l==r-1){
//     seg[id] = da[l];
//   }
//   int mid = (l+r)/2;
//   build(id*2, l, mid);
//   build(id*2+1,mid, r);
//   s[id] = max(s[id*2],s[id*2+1]);
// }
// void mx(int x, int y, int id=1, int l=0, int r = n){
//   if(x>=r||y<=l) return -1;
//   if(l>=x&&r<=y)return seg[id];
//   int mid = (l+r)/2;
//   return max(mx(x,y,id*2,l,mid),mx(x,y,id*2+1,mid, r));
// }

multiset<int> ms;

int main()
{
  //freopen("input", "r", stdin);
  // freopen("output", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int t;cin>>t;
    auto it = ms.lower_bound(t);
    if(it==ms.begin())
      ms.insert(t);
    else{
      it--;
      ms.erase(it);
      ms.insert(t);
    }
  }
    cout<<ms.size()<<endl;

}


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

int main(){
    int N,M;
    cin >> N >> M;
    vector<pair<int,int>> graph(M);
    for(int i=0; i<M; i++){
        int a,b;
        cin >> a >> b;
        pair<int, int> p;
        p = make_pair(a-1,b-1);
        graph.at(i) = p;
    }
    vector<int> visit_order(N);
    for(int i=0; i<N; i++){
        visit_order.at(i) = i;
    }
    int count=0;
    do{
        if(visit_order.at(0) != 0){
            break;
        }
        bool possible_order=true;
        for(int i=0; i<N-1;i++){
            bool possible_move=false;
            int begin=visit_order.at(i);
            int end=visit_order.at(i+1);
            for(int j=0; j<M; j++){
                if(graph.at(j).first==begin && graph.at(j).second==end){
                    possible_move = true;
                }
                if(graph.at(j).first==end && graph.at(j).second==begin){
                    possible_move =true;
                }
            }
            if (possible_move == false){
                possible_order = false;
            }
        }
        if(possible_order){
            count++;
        }
    }while(next_permutation(visit_order.begin(), visit_order.end()));
    cout << count <<endl;
}

Measured memory_bytes: 3600
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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

int cnt[200200],A,N,now=1;

int main(){
    cin>>N;
    rep(i,N){
        cin>>A;
        if(A==now){
            now++;
        }
    }
    if(now==1)out(-1);
    else out(N-(now-1));
    

}


Measured memory_bytes: 256
//----------------------------templates
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("tune=native")
    #pragma GCC target ("avx")
    //----------------------------
    #include <bits/stdc++.h>
    using namespace std;

    typedef long long ll;
    typedef unsigned long long ull;
    #define int ll

    #define FOR(i,j,n) for (int i=(int)(j);i<(n);i++)
    #define REP(i,n) for (int i=0;i<(int)(n);i++)
    #define REPS(i,n) for (int i=1;i<=(int)(n);i++)
    #define REPN(i,n) for (int i=(int)(n)-1;i>=0;i--)
    #define REPNS(i,n) for (int i=(int)(n);i>0;i--)

    #define I(n) scanf("%lld", &(n))
    #define LL(n) scanf("%lld", &(n))
    #define pb(n) push_back((n))
    #define mp(i,j) make_pair((i),(j))
    #define eb(i,j) emplace_back((i),(j))
    #define y0 y3487465
    #define y1 y8687969
    #define j0 j1347829
    #define j1 j234892
    #define uniq(v) v.erase( unique(v.begin(), v.end()), v.end() )

    #define all(x) (x).begin(),(x).end()
    #define sz(x) ((int)(x).size())

    typedef vector<int> vi;
    typedef pair<int,int> pi;
    typedef vector<pi> vpi;
    typedef vector<vi> vvi;
    typedef vector<vpi> vvpi;
    typedef vector<vvi> vvvi;

    const int mod = 1000000007;

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

int n;

signed main(){
    I(n);
    vi a(n), b(n);
    REP(i,n) I(a[i]);
    REP(i,n) I(b[i]);
    vi ax(n), bx(n);
    REP(i,n) ax[i] = a[i] ^ a[(i+1)%n];
    REP(i,n) bx[i] = b[i] ^ b[(i+1)%n];
    ax.insert(ax.end(), all(ax));

    //KMP table
    vi t(n);
    int i = 2, j = 0;
    t[0] = -1;
    while( i < n ){
        if(bx[i-1] == bx[j]){
            t[i] = j+1;
            i++;
            j++;
        } else if (j > 0){
            j = t[j];
        } else {
            i++;
        }
    }
    // REP(i,n) cerr << t[i] << " "; cerr << endl;
    // for(auto i : bx) cerr << i << " "; cerr << endl;

    // KMP
    int m = 0;
    i = 0;
    while ( m < n ){
        // cerr << "pos " << i << " " << m << endl;
        if (bx[i] == ax[i+m]){
            i++;
            if (i >= n-1){
                cout << m << " " << (a[m] ^ b[0]) << endl;
                
                m = m + i - t[i];
                if (i) i = t[i];
            }
        } else {
            m = m + i - t[i];
            if (i) i = t[i];
        }
    }
}

Measured memory_bytes: 12900
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        FastReader in = new FastReader();
        FastWriter out = new FastWriter();
        int n = in.nextInt();
        String s = in.nextLine();
        int ans = 0;
        for (int i = 1; i < n; i++){
            if (s.charAt(i) != s.charAt(i-1)){
                ans++;
            }
        }
        out.pl(ans+1);

        out.close();
    }
}
class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 
    public FastReader() { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    String next(){ 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            }catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
    long nextLong(){ 
        return Long.parseLong(next()); 
    } 
    double nextDouble(){ 
      return Double.parseDouble(next()); 
    } 
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
        catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}
class FastWriter{
    PrintWriter out;
    FastWriter(){
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	out.flush();
    }
    void pl(Object o){
        out.write(o.toString());
	    out.write("\n");
        out.flush();
    }
    void pl(){
        out.write("\n");
    }
    void p(Object o){
        out.write(o.toString());
    }
    void close(){
        out.flush();
        out.close();
    }  
}


Measured memory_bytes: 35080
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto a = readln.chomp.to!int;
  auto b = readln.chomp.to!int;
  auto c = readln.chomp.to!int;
  auto x = readln.chomp.to!int;
  
  int cnt;

  foreach (i; 0..a+1) {
    foreach (j; 0..b+1) {
      foreach (k; 0..c+1) {
        if (i*500+j*100+k*50 == x) {
          cnt++;
        }
      }
    }
  }

  cnt.writeln;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FOR(a,b,c) for(a = b;a<c;a++)
#define IFOR(a,b,c) for(a = b;a>c;a--)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a)  ((a)<(0)?-(a):(a))
#define INF 1000000000



long long int a,b;

int main(){
	scanf("%lld",&a);
	scanf("%lld",&b);
	
	long long int total=0;
	long long int temp = a;
	long long int i;
	FOR(i,a,b+1){
		if(temp<=b) total += 1;
		else break;
		temp *= 2;
		
	}
	printf("%d\n",total);
	return 0;
}



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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node);
Node treeMaximum(Node);
Node treeSearch(Node,int);
Node treeSuccessor(Node);
//void treeDelete(Node);
void insert (int);
void inorder (Node);
void preorder(Node);

//void transplant(Node,Node);

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
       inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
       scanf("%d", &x);
      //treeDelete(treeSearch(root, x));
      }
  }

  
  
  return 0;
}


Node treeMinimum(Node x){
  
  while(x->left != NIL){
    x = x->left;
  }

  return x;

}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;

}

Node treeSearch(Node u, int k){

  if(u == NIL || k == u->key) return u;
  if(k < u->key) return treeSearch(u->left,k);
  else return treeSearch(u->right,k);

}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right); //case1

  y = x->parent;

  while( y != NIL && x == y->right ){
    x = y;
    y = y->parent;
  }
  return y; //case2

}

/*void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z.left == NIL)

}
*/

void insert(int k){
  Node y = NIL; // x parent
  Node x = root; 
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x; //parent set
    if( z->key < x->key) x = x->left;//左の子へ移動
    else x = x->right;//右の子へ移動
  }
  z->parent = y;

  //Tが空の場合
  if(y == NIL) root = z;
  else if(z->key < y->key) y->left = z; //z を y の左の子にする
  else y->right = z; // z を yの右の子にする 

}

void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }

}
void preorder(Node u){
  if(u != NIL) {
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }

}




Measured memory_bytes: 20456
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main {
	
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		
		int t = sc.nextInt(), a = sc.nextInt();
		long voteT = t, voteA = a;
		for (int i = 1; i < n; i++) {
			t = sc.nextInt();
			a = sc.nextInt();
			
			long multi = Math.max((voteT + (t - voteT % t) % t) / t, (voteA + (a - voteA % a) % a) / a);
			voteT = t * multi;
			voteA = a * multi;
		}
		
		out.println(voteT + voteA);
		out.flush();
	}
	
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	
	private byte readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}
	
	private boolean isPrintableChar(int c) {
		return '!' <= c && c <= '~';
	}
	
	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}
	
	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}
	
	public int nextInt() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		int n = 0;
		boolean minus = false;
		byte b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
}


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

#define mp       make_pair
#define mt	  make_tuple
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

const int INF=1<<29;
const double EPS=1e-9;
const ll MOD = 1000000007;

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

int W,H,N;
const int py = 100;
const int px = 100;

int main(){
  cin >> W >> H >> N;

  int lx,ly;
  lx = ly = 0;
  int ux,uy;
  ux = W;
  uy = H;
  for (int i = 0; i < N; i++){
    int x,y,a;
    cin >> x >> y >> a;
    if (a == 1){
      lx = max(lx, x);
    }else if(a == 2){
      ux = min(ux, x);
    }else if(a == 3){
      ly = max(ly, y);
    }else{
      uy = min(uy, y);
    }
  }
  cout << max(0, (uy - ly)) * max(0, (ux - lx)) << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if((a == b && a != c) || (a == c && a != b) || (b == c && a != c)) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
		sc.close();
	}
}


Measured memory_bytes: 23124
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define rep(i, j, k) for(int i=(j);i<(k);++i)
#define repi(i, j, k) for(int i=(j);i<=(k);++i)
#define per(i, j, k) for(int i=(j);i>(k);--i)
#define peri(i, j, k) for(int i=(j);i>=(k);--i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).begin(),(x).end(), greater<int>()
#define sz(x) ((int)(x).size())
#define endl "\n"
#define INF 0x20202020
#define EPS 1e-9
#define PI 3.1415926535897932384626
#define MOD 1000000007
typedef long long ll;
typedef long double ld;

ll powmod(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    assert(b >= 0);
    for (; b; b >>= 1) {
        if (b & 1)res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef map<int, int> mpii;
typedef set<int> si;

struct DSU {
    int *val, *rank;

    DSU(int n) {
        val = new int[n];
        rank = new int[n];
        rep(i, 0, n) {
            val[i] = i;
            rank[i] = 0;
        }
    }

    int find(int a) {
        if (val[a] == a) return a;
            //find, recur parents
        else return val[a] = find(val[a]);
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y); //root of x and y
        if (x == y) return; //same root return
        if (rank[x] < rank[y]) val[x] = y;
        else {
            val[y] = x;
            if (rank[x] == rank[y]) ++rank[x];
        }
    }

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

class D {
public:
    void solve(std::istream &cin, std::ostream &cout) {
        //jth op = 1 swaps with 2
        int n, m;
        cin >> n >> m;
        vi p(n);
        rep(i, 0, n) {
            cin >> p[i];
            --p[i];
        }
        DSU tree = DSU(n);
        rep(i, 0, m) {
            int a, b;
            cin >> a >> b;
            tree.unite(a - 1, b - 1);
        }
        int res = 0;
        rep(i, 0, n) {
            if (tree.same(i, p[i])) ++res; //check roots same for index and value, if so
        }
        cout << res << endl;

    }
};


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    D solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 1408
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include <sstream>
#include <iomanip>



using namespace std;
using ll = long long;

int n, m, p[100005], a, b;
ll y[100005];
unordered_map<ll, int>M;
vector<pair<int, ll> >V;
vector<pair<int, string> >ANS;
string S[100005];

int main(){
  cin >> n >> m;
  for(int i = 0; i < m; ++i){
    cin >> p[i] >> y[i];
    M[y[i]] = i;
    V.push_back(make_pair(p[i], y[i]));
  }
  sort(V.begin(), V.end());
  int tmp = 0;
  int cnt = 0;
  for(int i = 0; i < m; ++i){
    //cout << V[i].first << " " << V[i].second << endl;
    //cout << M[V[i].second] << endl;
    
    if(tmp != V[i].first){
      cnt = 0;
    }
    cnt++;
    a = V[i].first;
    b = cnt;
    ostringstream x, y;
    x << setw(6) << setfill('0') << to_string(a);
    string s_1(x.str());
    y << setw(6) << setfill('0') << to_string(b);
    string s_2(y.str());
    S[i] = s_1 + s_2;
    //cout << S[i] << endl;
    ANS.push_back(make_pair(M[V[i].second], S[i]));
    tmp = V[i].first;
    
  }
  sort(ANS.begin(), ANS.end());
  for(int i = 0; i < m; ++i){
    cout << ANS[i].second << endl;
  }


}

Measured memory_bytes: 15508
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    int a;
    cin>>a;
    cout<<"ABC"<<a<<endl;

    return 0;
}


Measured memory_bytes: 3576