akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD =  998244353;
const int  Inv2 = (MOD+1)/2;
template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  E d0;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int n_,F f,G g,T d1,
	      vector<T> v=vector<T>()):
    f(f),g(g),d1(d1){
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(int a,int b){
    T vl=d1,vr=d1;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
  
};
     signed main(){
         string s;
         cin>>s;
         SegmentTree<int,int> rmq(2*s.size()+1,
			   [](int a,int b){return a+b;},
			   [](int a,int b){return b;},
			   0);
            vector<int> k[('z'-'a')+1];
            for(int i=0;i<s.size();i++){
               k[s[i]-'a'].push_back(i);
            }
            int c[s.size()],t=s.size()%2;
            for(int i=0;i<='z'-'a';i++){
               if(k[i].size()%2){
                  if(t){
                     c[k[i][k[i].size()/2]]=s.size();
                     t--;
                  }else{
                     cout<<-1;
                  return 0;
                  }
                  

               }
               for(int j=0;j<k[i].size()/2;j++)c[k[i][j]]=k[i][j];
               for(int j=0;j<k[i].size()/2;j++)c[k[i][k[i].size()-1-j]]=2*s.size()-k[i][j];

            }
            int ans=0;
            for(int i=0;i<s.size();i++){
               ans+=rmq.query(c[i],2*s.size()+1);
               rmq.update(c[i],1);
            }
            cout<<ans<<endl;



      }

        


Measured memory_bytes: 12280
def main():
    A,B,C  = map(int,input().split())
    K = int(input())
    cnt = 0
    while(A >= B):
        B *= 2
        cnt += 1
    while(B >= C):
        C *= 2
        cnt += 1
    if K >= cnt:
        print('Yes')
    else:
        print('No')
if __name__ == '__main__':
    main()

Measured memory_bytes: 9088
import java.util.*

fun main(args: Array<String>) {
    val list = arrayListOf<Int>()
    val scanner = Scanner(System.`in`)
    list.add(scanner.nextInt())
    list.add(scanner.nextInt())
    list.add(scanner.nextInt())
    list.sort()
    println(list.joinToString(" "))
}


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

#define start \
    int t;    \
    cin >> t; \
    while (t--)

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

    int d, t, s;
    cin >> d >> t >> s;

    if (d == 0)
    {
        cout << "Yes";
        return 0;
    }
    if (s <= 0)
    {
        cout << "No";
        return 0;
    }

    double time = (double)d / s;
    if (time <= t)
        cout << "Yes";
    else
        cout << "No";
}

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

#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define forup(i,l,r) for (register int i = l ; i <= r ; i += lowbit(i))
#define fordown(i,id) for (register int i = id ; i ; i -= lowbit(i))
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define lowbit(x) (x&(-x))

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pr;

const ll MAX = 2e18;
const ld inf = 2e18;
const int maxn = 2200;
const ll mod = 1e9 + 7;

char ch[maxn][maxn];
int a[maxn][maxn];
int h[maxn],r[maxn],l[maxn],st[maxn],tops;
int mx,n,m;

int main(){
	scanf("%d %d",&n,&m);
	rep(i,1,n) scanf("%s",ch[i] + 1);
	rep(i,1,n) rep(j,1,m)
	   	if ( ch[i][j] == '#' ) a[i][j] = 1;
	rep(x,1,n){
		rep(i,1,m){
			if ( x == 1 || i == 1 ) h[i]++;
			else{
				if ( !((a[x - 1][i - 1] == a[x - 1][i]) ^ (a[x][i - 1] == a[x][i])) ) h[i]++;
				else h[i] = 1;
			}
		}
		rep(i,1,m){
			while ( tops && h[i] < h[st[tops]] ) r[st[tops--]] = i - 1;
			st[++tops] = i;
		}
		while ( tops ) r[st[tops--]] = m;
		repd(i,m,1){
			while ( tops && h[i] < h[st[tops]] ) l[st[tops--]] = i + 1;
			st[++tops] = i;
		}
		while ( tops ) l[st[tops--]] = 1;
		rep(i,1,m){
			int w = r[i] - max(1,l[i] - 1) + 1;
			mx = max(mx,w * h[i]);
		}
	}
	cout<<mx<<endl;;
}



Measured memory_bytes: 23424
#include<stdio.h>
#include<iostream>
#include<algorithm>

using namespace std;

int main(void) {

	int n, a[100], k, ali, bob;
	ali = 0;
	bob = 0;

	cin >> n;
	for (k = 0; k < n; k++)cin >> a[k];
	sort(a, a + n,greater<int>());

	for (k = 0; k < n; k++) {
		if (k % 2 == 0) ali += a[k];
		else bob += a[k];
	}

	cout << ali - bob << endl;

	return 0;
}

Measured memory_bytes: 256
N, K = [int(el) for el in input().split()]
snukes = set(range(1, N + 1))
snacks = set()
for _ in range(K):
    _ = input()
    arr = [int(el) for el in input().split()]
    snacks.update(arr)
print(N - len(snukes.intersection(snacks)))

Measured memory_bytes: 9120
unittest
{
	assert( [ "10", "ZABCDBABCQ" ].parse.expand.solve == 2 );
	assert( [ "19", "THREEONEFOURONEFIVE" ].parse.expand.solve == 0 );
	assert( [ "33", "ABCCABCBABCCABACBCBBABCBCBCBCABCB" ].parse.expand.solve == 5 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	input.popFront;
	auto as = input.front.split.to!( dchar[] );
	return tuple( as );
}

auto solve( dchar[] as )
{
	auto ans = 0L;
	while( true )
	{
		as = as.find( "ABC" );
		if( as.empty ) break;
		as.popFrontN( 3 );
		ans++;
	}
	return ans;
}


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

using namespace std;

using ll = long long;

using Graph = vector< vector<int> >;

bool dfs(int cur, vector<int>& memo, Graph& g, vector<int>& order) {
    memo[cur] = 1;
    for (int nex : g[cur]) {
        if (memo[nex] == 2) continue;
        if (memo[nex] == 1) return false;
        if (!dfs(nex, memo, g, order)) return false;
    }
    memo[cur] = 2;
    order.push_back(cur);
    return true;
}

bool tsort(Graph& g, vector<int>& order) {
    vector<int> memo(g.size(), 0);
    for (int i = 0; i < g.size(); i++) {
        if (memo[i] != 0) continue;
        if (!dfs(i, memo, g, order)) return false;
    }
    reverse(order.begin(), order.end());
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    Graph g(n), rg(n);
    for (int i = 0; i < n + m - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        rg[b].push_back(a);
    }

    vector<int> order;
    tsort(g, order);

    //for (int i = 0; i < n; i++) cout << order[i] << endl;

    map<int, int> zip;
    for (int i = 0; i < order.size(); i++) {
        zip[order[i]] = i;
    }

    int root = order[0];
    vector<int> par(n, -1);
    par[root] = 0;
    for (int i = 1; i < order.size(); i++) {
        int p = -1, hoge = -1;
        for (int nex : rg[order[i]]) {
            if (par[nex] == -1) continue;
            if (hoge < zip[nex]) {
                hoge = zip[nex];
                p = nex;
            }
        }
        par[order[i]] = p + 1;
    }

    for (int i = 0; i < n; i++) {
        cout << par[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 21492
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int N,num_query;
vector<int> V;

int main(){

	scanf("%d",&N);

	int tmp;
	for(int i = 0; i < N; i++){

		scanf("%d",&tmp);
		V.push_back(tmp);
	}

	scanf("%d",&num_query);

	int L,R,mid;
	int left,right;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d",&tmp);

		L = 0,R = N-1,mid = (L+R)/2;
		left = N;

		while(L <= R){

			if(V[mid] >= tmp){

				left = mid;
				R = mid-1;
			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		L = 0,R = N-1,mid = (L+R)/2;
		right = N;

		while(L <= R){

			if(V[mid] > tmp){

				right = mid;
				R = mid-1;
			}else{

				L = mid+1;
			}
			mid = (L+R)/2;
		}

		printf("%d %d\n",left,right);
	}

	return 0;
}




Measured memory_bytes: 3500
function main(input):void {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	const inpt: Array<string> = input.split('\n');

	const odd: Array<string> = inpt[0].split('');
	const even: Array<string> = inpt[1].split('');

	const len: number = odd.length + even.length;

	let ans: string = ''
	for (let i = 0; i < len; i++) {
		if (i % 2 === 0) {
			ans += odd.shift();
		} else {
			ans += even.shift()
		}
	}

	console.log(ans);
}

// *** debug start ***
function debug(): void{
	const input = (<HTMLInputElement>document.getElementById('input')).value;
	input && main(input);
}
// *** debug end ***

//
declare function require(x: string): any;
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 7372
import java.util.Scanner;

public class Main {
	  
	public static void main(String args[]) {
		    Scanner scanner = new Scanner(System.in);
		    
		    String s  = scanner.nextLine();
		    int count = 0;
		    if( s.substring(0, 1).equals("1") ) 
		    {
		    	count = count + 1;
		    }
		    if( s.substring(1, 2).equals("1") ) 
		    {
		    	count = count + 1;
		    }
		    if( s.substring(2, 3).equals("1") ) 
		    {
		    	count = count + 1;
		    }
		    System.out.println(count);
		    scanner.close(); }
		  }

Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;
class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int Int() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Int() + add;
        }
        return Array;
    }

    public long Long() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = Long() + add;
        }
        return Array;
    }
}
class Program {
    
    static Scanner cin = new Scanner();
    static void Main() {
        //string X = Console.ReadLine();
        //string tmp = "";
        //long cnt = 0; //減らす文字数
        //for (int i = 0; i < X.Length; i++) {
        //    if(X[i] == 'S') {
        //        if (tmp == "") tmp += "S";
        //        else if (tmp[tmp.Length - 1] == 'S') tmp += "S";
        //        else {
        //            cnt += 2 * Math.Min(tmp.ToCharArray().Count(x => x == 'S'), tmp.ToCharArray().Count(x => x == 'T'));
        //            tmp = "S";
        //        }
        //    }
        //    else {
        //        if (tmp != "") tmp += "T";
        //    }
        //}

        //cnt += Math.Min(tmp.ToCharArray().Count(x => x == 'S'), tmp.ToCharArray().Count(x => x == 'T'));
        //Console.WriteLine(X.Length - cnt);

        long A = cin.Long();
        long B = cin.Long();
        long C = cin.Long();

        long p = B * C * (A - A / 2) - B * C * (A / 2);
        long q = A * B * (C - C / 2) - A * B * (C / 2);
        long r = C * A * (B - B / 2) - C * A * (B / 2);

        Console.WriteLine(Math.Min(Math.Min(p, q), r));

        Console.ReadLine();
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int A;
  int B;
  cin >> N >> A >> B;
  if (B < A*N) {
    cout << B << endl;
  }
  else {
    cout << A*N << endl;
  }
  
  
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>

int main() {
	int m, f, r;
	char rank[5][2] = {"A", "B", "C", "D", "F"};
	int flug;
	while (1) {
		scanf("%d%d%d", &m, &f, &r);
		if (m + f + r == -3)break;
		if (m + f >= 80) flug = 0;
		else if (m + f >= 65) flug = 1;
		else if (m + f >= 50) flug = 2;
		else if (m + f >= 30 && r >= 50) flug = 2;
		else if (m + f >= 30 && r <= 50) flug = 3;
		else flug = 4;
                if(m==-1||f==-1) flug = 4;
		printf("%s\n", rank[flug]);
	}
	return 0;
}

Measured memory_bytes: 2568
$><<x=y=[0,2].zip(*P=$<.map{_1.split.map(&:to_i)<<_1}).all?{|f,w,j|l=w,0
(1..P[0][2]).all?{|k|4.times{|i|P[~h=i/2][1][~k]==:UDLR[f+i&=1]&&l[h^=i]=4[g=i*2-l[h]]-g+-2[w+g]}
x,y=l
y<x}&&y<j&&j<=x}?:YES: :NO

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

using namespace std;

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

  int n, d;
  cin >> n >> d;

  vector<vector<int>> x(n, vector<int>(d));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < d; ++j) {
      cin >> x[i][j];
    }
  }

  int cnt = 0;
  for (int i = 0; i < n - 1; ++i) {
    for (int j = i + 1; j < n; ++j) {
      double dist = 0.0;
      for (int k = 0; k < d; ++k) {
        dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
      }
      dist = sqrt(dist);
      if (floor(dist) == dist) {
        ++cnt;
      }
    }
  }

  cout << cnt << '\n';

  return 0;
}


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

int main() {
  int x;
  cin >> x;
  
  if (360 % x == 0){
    cout << 360 / x << endl;
    return 0;
  }
  
  int counter = 1;
  
  while(true){
    if((360*counter) % x == 0){
      cout << 360*counter / x;
      return 0;
    }
    counter++;
  }
  return -1;
}


Measured memory_bytes: 3620
#include <stdio.h>

void swap(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int partition(int a[], int p, int r) {
  int i = p - 1;
  for (int j = p; j <= r - 1; j++) {
    if (a[j] <= a[r]) {
      i++;
      swap(&a[i], &a[j]);
    }
  }
  swap(&a[i+1], &a[r]);
  return i+1;
}
int main() {
  int n;
  scanf("%d", &n);
  int a[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int v = partition(a, 0, n - 1);
  for (int k = 0; k <= n-1; k++) {
    if (k == v) {
      printf("[%d]", a[k]);
    } else {
      printf("%d", a[k]);
    }
    if (k == n-1) {
      printf("\n");
    } else {
      printf(" ");
    }
  }

  return 0;
}



Measured memory_bytes: 2108
N = gets.to_i
A = gets.split.map(&:to_i)

flag = true
A.each do |a|
  if a % 2 == 0
    if a % 3 != 0 && a % 5 != 0
      flag = false
    end
  end
end

if flag
  puts "APPROVED"
else
  puts "DENIED"
end


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector <ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <vector<ll>> vv;
typedef vector <string> vs;
typedef vector <char> vc;


ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
//char c;

#define Endl endl


/*--------------------template--------------------*/

int main() {
    string t;
    cin >> s >> t;
    if (s > t) {
        cout << '>' << endl;
        return 0;
    } else if (s < t) {
        cout << '<' << endl;
        return 0;
    }
    cout << '=' << Endl;
}

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

int main() {
	int N; cin >> N;
	long long int A[100001];
	long long int W[100001];
	for(int i=0;i<N;i++) {
		cin >> A[i];
	}
	
  	W[0]=A[0];
	for(int i=1;i<N;i++) {
      if (i%2==0)
        W[0]+=A[i];
      if (i%2==1)
        W[0]-=A[i];
	}
	for(int i=1;i<N;i++) {
      W[i]=2*A[i-1]-W[i-1];
    }
	
	for(int i=0;i<N;i++) {
		cout << W[i] << " ";
	}
	
	return 0;
}


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

int dp[105][105];
char g[105][105];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf(" %s", g+i);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(!i && !j) {
                if(g[i][j] == '#') dp[i+1][j+1] = 1;
                else dp[i+1][j+1] = 0;
            }
            else if(!i) {
                if(g[i][j] == '#' && g[i][j-1] != '#')
                    dp[i+1][j+1] = dp[i+1][j]+1;
                else dp[i+1][j+1] = dp[i+1][j];
            }
            else if(!j) {
                if(g[i][j] == '#' && g[i-1][j] != '#')
                    dp[i+1][j+1] = dp[i][j+1]+1;
                else dp[i+1][j+1] = dp[i][j+1];
            }
            else {
                int a, b;
                if(g[i][j] == '#' && g[i][j-1] != '#')
                    a = dp[i+1][j]+1;
                else a = dp[i+1][j];
                if(g[i][j] == '#' && g[i-1][j] != '#')
                    b = dp[i][j+1]+1;
                else b = dp[i][j+1];
                dp[i+1][j+1] = min(a, b);
            }
        }
    }
    printf("%d", dp[n][m]);
    return 0;
}


Measured memory_bytes: 256
N, A, B, C, D = list(map(int, input().split()))
S = input()
A -= 1
B -= 1
C -= 1
D -= 1

def f(x, y):
    flag = False
    for i in range(x + 1, y):
        if S[i] == "#":
            if flag:
                return True
            flag = True
        else:
            flag = False
    return False


if f(A, C) or f(B, D):
    print("No")
    exit()


if D < C:
    flag = 0
    for i in range(B - 1, D + 2):
        if S[i] == "#":
            flag = 0
        else:
            flag += 1
            if flag == 3:
                print("Yes")
                exit()
    print("No")
else:
    print("Yes")





Measured memory_bytes: 3572
(let ((n (read))
      (m (read)))
  (let ((lrs (loop repeat m
                   collect (cons (read) (read)))))
    (labels ((rec (pairs left right)
               (declare (optimize (speed 3) (debug 0) (safety 0)))
               (if (endp pairs)
                   (1+ (- right left))
                   (rec (cdr pairs) (max left (caar pairs)) (min right (cdar pairs))))))
      (let ((result (rec lrs 1 n)))
        (princ (if (plusp result)
                   result
                   0))))))


Measured memory_bytes: 59752
n=int(input())
a=[int(input()) for i in range(n)]

a_sort=sorted(a)

max_a=max(a)
next_max=a_sort[-2]

lis=[0]*n

for i in range(n):
    if a[i]!=max_a:
        lis[i]=max_a
    else:
        lis[i]=next_max

L=[str(a) for a in lis]
L="\n".join(L)
print(L)

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

int  BinarySearch(int S[],int n,int T[],int q){

    int count=0;
    int buttom=0;
    int top=n;
    int mid=(buttom+top)/2;
    for(int i=0;i<q;i++){
      while(buttom+1 != top){
            if(S[mid]<T[i]){
              buttom = mid;
            }
            else if(S[mid] == T[i]){
                count++;
                buttom=0;
                top=n;
                mid=(buttom+top)/2;
                break;
            }
            else{
              top = mid;
            }
            if(buttom+1 == top){
              if(buttom==0){
                if(S[0]==T[i]){
                  count++;
                }
              }
              else if(top==n){
                if(S[n-1] == T[i]){
                  count++;
                }
              }
            }
            mid=(buttom+top)/2;
      }
      buttom=0;
      top=n;
      mid=(buttom+top)/2;
    }

    return count;
}

int main(){

    int n=0,q=0;

    cin >> n;
    int* S = new int[n];
    for(int i=0;i<n;i++){
        cin >> S[i];
    }

    cin >> q;
    int* T = new int[q];
    for(int i=0;i<q;i++){
        cin >> T[i];
    }

    cout << BinarySearch(S,n,T,q) << endl;

    return 0;
}

Measured memory_bytes: 3588
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>

using namespace std;

typedef long long ll;

#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define rep1(i,n) for(int i=1; i<=(int)(n); i++)
#define all(c) c.begin(),c.end()
#define psb push_back
#define ppb pop_back

const int INF = 1001001001;

int main() {
    long double A, B;

    cin >> A >> B;

    ll ans = A*B;

    cout << ans << endl;
    // cout << fixed << setprecision(20) << ans << endl;
    // printf("%.0lf\n", ans);
}


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

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

  std::vector<ll> l(n);
  rep(i,n)std::cin >> l[i];
  // sort(l.begin(),l.end());
  // l.erase(std::unique(l.begin(), l.end()), l.end());

  ll ans=0;
  n=l.size();
  rep(a,n)
  for (int b = a+1; b < n; b++) {
    for (int c = b+1; c < n; c++) {
      if(l[a]+l[b]>l[c] && l[b]+l[c]>l[a]  && l[c]+l[a]>l[b] ){
        if(l[a]!=l[b] && l[b]!=l[c] && l[c]!=l[a]){
          ans++;
          // std::cout << l[a]<<":"<<l[b]<<":"<<l[c] << '\n';
        }
      }
    }
  }

  std::cout << ans << '\n';




  return 0;
}


Measured memory_bytes: 3636
#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 1000000007
 
typedef vector<int> vi;
typedef pair<int,int> pii;

int32_t main()
{
  int n,ans=0,count=1,val;
  vi v;
  cin>>n;

  rep(i,n)
  {
    cin>>val;
    v.pb(val);
  }

  rep(i,n-1)
  {
    if(v[i]==v[i+1])
      count++;
    else
    {
      ans+=(count/2);
      count=1;
    }
  }
  ans+=(count/2);
  cout<<ans;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here
        Scanner scanner=new Scanner(System.in);
        int A=scanner.nextInt();
        int B=scanner.nextInt();
        int result=0;
        for(int i=A;i<=B;i++){
            if(isKaibun(i)) result++;
        }
        System.out.println(result);
    }
    public static boolean isKaibun(int x){
        int a=x/10000;
        int b=(x-a*10000)/1000;
        int c=(x-a*10000-b*1000)/100;
        int d=(x-a*10000-b*1000-c*100)/10;
        int e=(x-a*10000-b*1000-c*100-d*10);
        return a==e&&b==d;
    }
}


Measured memory_bytes: 23380
/*  -*- coding: utf-8 -*-
 *
 * b.cc: D: Restoring Road Network
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 300;

typedef long long ll;
const ll LINF = 1LL << 60;

/* typedef */

/* global variables */

ll as[MAX_N][MAX_N], bs[MAX_N][MAX_N];

/* subroutines */

inline void setmin(ll &a, ll b) { if (a > b) a = b; }

/* main */

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

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      scanf("%lld", &as[i][j]), bs[i][j] = as[i][j];

  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
	setmin(bs[i][j], bs[i][k] + bs[k][j]);

  ll sum = 0;
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j < n; j++) {
      if (as[i][j] > bs[i][j]) {
	puts("-1");
	return 0;
      }

      ll mind = LINF;
      for (int k = 0; k < n; k++)
	if (k != i && k != j) setmin(mind, bs[i][k] + bs[k][j]);
      if (mind > as[i][j]) sum += as[i][j];
    }

  printf("%lld\n", sum);
  return 0;
}


Measured memory_bytes: 1664
#!/usr/bin/env python3
import sys
from queue import PriorityQueue
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


N = int(input())
a = list(map(int, input().split()))


left_queue = PriorityQueue()

for i in range(N):
    item = (a[i], None)
    left_queue.put(item)


score = sum(a[:N])
left_scores = [score]

for i in range(N, 2*N):
    b, none = left_queue.get()
    if a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (a[i], None)
        dscore = a[i] - b
    left_queue.put(item)
    score += dscore
    left_scores.append(score)


right_queue = PriorityQueue()

for i in range(2*N, 3*N):
    item = (-a[i], None)
    right_queue.put(item)


score = - sum(a[2*N:])
right_scores = [score]

for i in range(2*N-1, N-1, -1):
    b, none = right_queue.get()
    if -a[i] < b:
        item = (b, None)
        dscore = 0
    else:
        item = (-a[i], None)
        dscore = -a[i] - b
        # debug(a[i], b, i)
    right_queue.put(item)
    # debug(item, score, dscore)
    score += dscore
    right_scores.append(score)


scores = []
for i in range(N+1):
    scores.append(left_scores[i] + right_scores[N-i])

debug(scores)
print(max(scores))


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

int H, W, K, A[309][309], num; //A[i][j]は答えの番号を保持する配列
int cnt[309];
char c[309][309]; //入力

void solve(int cl, int cr) { //cl行目からcr行目まで
	vector<int> P;
	for (int i = cl; i <= cr; i++) {
		for (int j = 1; j <= W; j++) {
			if (c[i][j] == '#') P.push_back(j); //いちごが置いてあるマスの列番号
		}
	}
	sort(P.begin(), P.end());

	for (int i = 0; i < P.size(); i++) { //いちごごとに切り分ける範囲を決める
		int v1 = 1, v2 = W;
		if (i >= 1) v1 = P[i - 1] + 1; //前のいちごの次の列
		if (i < (int)P.size() - 1) v2 = P[i];

		num++;
		for (int j = cl; j <= cr; j++) {
			for (int k = v1; k <= v2; k++) A[j][k] = num;
		}
	}
}

int main() {
	cin >> H >> W >> K;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> c[i][j];
			if (c[i][j] == '#') cnt[i]++;
		}
	}

	vector<int> vec;
	for (int i = 1; i <= H; i++) { if (cnt[i] >= 1) vec.push_back(i); } //いちごがある行を入れる
	for (int i = 0; i < vec.size(); i++) {
		int v1 = 1, v2 = H;
		if (i >= 1) v1 = vec[i - 1] + 1;
		if (i < (int)vec.size() - 1) v2 = vec[i]; //縦にみて、切り分ける範囲を決める

		solve(v1, v2); //ある一つの行にしかイチゴが載っていないケーキについて、色を塗る。
	}

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (j >= 2) cout << " "; cout << A[i][j];
		}
		cout << endl;
	}
	return 0;
}


Measured memory_bytes: 1280
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let mut s: i64 = read();
    let mut count = 1;

    while s != 4 && s != 2 && s != 1 {
        count += 1;
        if s & 1 == 1 {
            s = 3 * s + 1
        } else {
            s /= 2;
        }
    }

    print!("{}", count + 3);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
using namespace std;
bool isNotPrime[302000];
bool isMonSat[302000];
int main(){
	isNotPrime[0] = isNotPrime[1] = isNotPrime[2] = isNotPrime[3] = isNotPrime[4] = isNotPrime[5] = true;

	for(int i = 0;i < 301000;i++){
		if(i%7==1||i%7==6)isMonSat[i] = true;
	}
	for(int i = 2;i * i < 301000;i++){
		if(isMonSat[i]){
			for(int j = i+i;j < 301000;j+=i){
				isNotPrime[j] = true;

				//if(j<100)cout<<j<<endl;
			}
		}
		else{
			isNotPrime[i] = true;
		}
	}
	//for(int i = 0;i < 100;i++)cout<<i<<" "<<!isNotPrime[i]<<endl;
	int n;
	while(cin>>n,n!=1){
		cout<<n<<":";
			for(int i = 0;i < 301000;i++){
				if(!isNotPrime[i]&isMonSat[i]){
					if(n%i==0){
						cout<<" "<<i;
					}
				}
			}
		
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1748
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();
        int ans = 0;
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= k; j++) {
                int z = s-i-j;
                if(0 <= z && z <= k)ans++;
            }
        }
        System.out.println(ans);
        sc.close();

    }

}


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

x = int(input())

a = 0
while True:
    for b in range(a + 1):
        if a**5 - b**5 == x:
            print(a, b)
            sys.exit()
        if a**5 + b**5 == x:
            print(a, -b)
            sys.exit()
    a += 1


Measured memory_bytes: 64280
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	LL x,y,ans=1;
	scanf("%lld%lld",&x,&y);
	while(x*2<=y)
	{
		x*=2;ans++;
	}
	printf("%lld",ans);
	return 0;
}

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

long long int memo[111][11][1111];

long long int solve(int p, int n, int s){
  
  if(!n && !s) return memo[p][n][s] = 1;
  if(!n || s < 0) return 0;
  if(~memo[p][n][s]) return memo[p][n][s];
  
  long long int ans = 0;
  for(int i=p;i<101;i++) ans += solve(i+1, n-1, s-i);
  
  return memo[p][n][s] = ans;
}

int main(){

  memset(memo, -1, sizeof(memo));
  for(int i=1;i<10;i++)
    for(int j=0;j<1001;j++) 
      solve(0, i, j);
  
  int n, s;
  while(cin >> n >> s, n+s) cout << solve(0, n, s) << endl;
  
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

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

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

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

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n;
    cin>>n;
    vi a(n);
    vi b(n);
    REP(i,n) {
        int temp;
        cin>>temp;
        a[i] = temp;
        b[a[i]-1] = i;
    }

    REP(i,n){
        if(i!=0) cout << " ";
        cout << b[i]+1;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1664
#include<iostream>
#include<cstring>
#include<cstdio>
int main()
{
    char a[10],b[10],c[10];
    scanf("%s %s %s",a,b,c);
    printf("%c%c%C\n",toupper(a[0]),toupper(b[0]),toupper(c[0]));
    return 0;

}


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

#define LL long long
#define Dl double
#define Pb push_back
#define Mp make_pair

using namespace std;

typedef vector<LL> Vl;
typedef pair<LL, LL> Pll;
typedef vector<Pll> Vpl;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
#define X first
#define Y second

LL l;
string s[110];

bool cmp(string A, string B)
{
    for(LL i = 0; i < l; i++){
        if(A[i] != B[i])
            return A[i] < B[i];
    }
    return 0;
}

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

    for(LL i = 0; i < n; i++)
        cin >> s[i];

    sort(s, s + n, cmp);
    for(LL i = 0; i < n; i++)
        cout << s[i];

    cout << '\n';
    return 0;
}


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

bool g[10][10];

int main() {
    int n, m;
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a][b] = g[b][a] = true;
    }

    vector<int> ord(n);
    rep(i, n) ord[i] = i;

    int res = 0;
    do {
        if(ord[0] != 0) break;

        bool can = true;
        for(int i = 0; i + 1 < n; i++) {
            int from = ord[i];
            int to = ord[i + 1];
            if(!g[from][to]) can = false;
        }
        if(can) res++;
    } while(next_permutation(ord.begin(), ord.end()));

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SORT(i) sort((i).begin(),(i).end())
constexpr int INF = 2000000000;
constexpr int mod = 1000000007;

int main() {
	int N; cin >> N;
	vector<ll>a(N);
	rep(i, N)cin >> a[i];
	int cnt = 0;
	rep(i, N) {
		if (a[i] % 4 == 0)cnt += 2;
		else if (a[i] % 2 == 0)++cnt;
	}
	if (N % 2 == 1)--N;
	cout << (N <= cnt ? "Yes" : "No") << "\n";

	return 0;
}

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

int main() {
  long long N;
  int K;
  
  cin >> N;
  cin >> K;

  string R;
  
  int res;
  
  long long tmp;
  
  if( N < K ){
    R = to_string(N);
    cout << R.size() << endl;
    return 0;
  }
  
  while(true){
    tmp = N%K;
    N = N/K;
    R = to_string(tmp) + R;
    //cout << "N:" << N << " R:" << R << endl;
    if( N < K){
      R = to_string(N) + R;
      break; 
    }
  }
  //cout << " R:" << R << endl;
  res = R.size();
  
  cout << res << endl;
}







Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main() {
	ll i,j,n;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)
  {
    cin>>a[i];
  }
  vector<vector<ll> > dp(n+1, vector<ll>(n+1, 0));
  for (i = 1; i <= n;i++){
    for (j = i; j > 0 ;j--){
      dp[i][j] = max(a[i-1] - dp[i - 1][j], a[j-1] - dp[i][j+1]);
    }
  }
  cout << dp[n][1] << endl;
  return 0;
}

Measured memory_bytes: 70784
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
const int mod=1000000007;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	vector<int> a(5);
	rep(i,5) cin >> a.at(i);
	sort(a.rbegin(),a.rend());
	int k=9,j=0,ans=0;
	rep(i,5){
		if(a.at(i)%10!=0 && a.at(i)%10<k){
			k=a.at(i)%10;
			j=i;
		}
	}
	rep(i,5){
		if(i==j) continue;
		else{
			ans+=a.at(i);
			if(ans%10!=0) ans+=10-ans%10;
		}
	}
	ans+=a.at(j);
	cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
	int t;
	cin>> t;
	bool x=false;
	while(t){
	    if(t%10 == 7){
	    	x=true;
	    	cout<<"Yes"<<endl;
	    	break;
	    }
		t = t/10;
	}
	if(!x) cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 3124
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int a,b,c,d,e;
  for(;cin>>a>>b>>c>>d>>e,a||b||c||d||e;)
    {
      int na,nb,nc;
      cin>>na>>nb>>nc;
      int ans=a*na+b*nb+c*nc;
      if(d<=nc)
	ans=min(ans,a*na+b*nb+e*nc);
      else
	ans=min(ans,a*na+b*nb+d*e);

      while((nc<d &&(nb>0 || na>0)))
	{
	  if(nb>0)
	    nb--;
	  else
	    na--;
	  
	  nc++;
	}
      if(d<=nc)
	ans=min(ans,a*na+b*nb+e*nc);
      else
	ans=min(ans,a*na+b*nb+e*d);
      cout<<ans<<endl;
    }

}

Measured memory_bytes: 1160
#include<iostream>
using namespace std;
int main() {
	int n, m,date[111],hito,oki;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> date[i];
	}
	for (int i = 1; i <= m; i++) {
		hito = 1;
		while(hito != n) {
			if (date[hito] % i > date[hito + 1]%i) {
				oki = date[hito];
				date[hito] = date[hito + 1];
				date[hito + 1] = oki;
				hito = hito + 1;
			}
			else {
				hito = hito + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << date[i] << endl;
	}
}


Measured memory_bytes: 3108
s = input()
n = len(s)
flg = 0
ans1 = 0
ans2 = 0
for i in range(1,n):
  if s[i] == s[i-1] and flg == 0:
    flg = 1
    ans1 += 1
  else:
    flg = 0
s = s*2
n *= 2
flg = 0
for i in range(1,n):
  if s[i] == s[i-1] and flg == 0:
    flg = 1
    ans2 += 1
  else:
    flg = 0
k = int(input())
if len(set(list(s))) == 1:
  print(n*k//4)
elif ans2>ans1*2:
  print((k//2)*ans2+(k%2)*ans1+(k-1)//2)
else:
  print((k//2)*ans2+(k%2)*ans1)

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

int main() {
    int N;
    cin >> N;
    vector<int> W(N);
    int l = 0, r = 0;
    for (int i = 0; i < N; i++) {
        cin >> W[i];
        r += W[i];
    }
    int ans = INT_MAX;
    for (int i = 0; i < N; i++) {
        l += W[i];
        r -= W[i];
        ans = min(ans, abs(r - l));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3608
n = int(input())
a = []
b = []
for i in range(n):
    x = list(map(int, input().split()))
    a.append(x[0])
    b.append(x[1])
b.sort()
a.sort()
if n%2 == 1:
    left = a[int((n-1)/2)]
    right = b[int((n-1)/2)]
    print(right-left+1)
else:
    left = (a[int(n/2-1)] +a[int(n/2)])/2
    right = (b[int(n / 2 - 1)] + b[int(n / 2)]) / 2
    print(int((right-left)*2 +1))

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template < typename T >
void vprint(T &v){
	REP(i, v.size()){
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(){
	ll N;
	cin >> N;
	vector<ll> ai(N);
	REP(i, N){
		ll x;
		cin >> x;
		if(x==i+1) ai[i] = 1;
		else ai[i] = 0;
	}
	ll res = 0;
	REP(i, N){
		if(i==N-1){
			if(ai[i]==1) res++;
		}else{
			if(ai[i]==1){
				if(ai[i+1]==1){
					ai[i+1] = 0;
				}
				res++;
			}
		}
	}
	cout << res << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Stack<Integer> st = new Stack<Integer>();
		String str = sc.nextLine();
		int x, y;
		for (String s : str.split(" ")) {
			if (s.equals("+") || s.equals("-") || s.equals("*")) {
				switch (s) {
				case "+":
					y = st.pop();
					x = st.pop();
					st.push(x + y);
					break;
				case "-":
					y = st.pop();
					x = st.pop();
					st.push(x - y);
					break;
				case "*":
					y = st.pop();
					x = st.pop();
					st.push(x * y);
					break;
				}
			} else {
				st.push(Integer.parseInt(s));
			}
		}
		System.out.println(st.pop());
		sc.close();
	}
}



Measured memory_bytes: 26348
import java.io.*;
import java.util.*;
public class Main {
	static long MOD = 2 << 29;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		long A = 1;
		long B = 1;
		for(int i = 0; i < N; i++) {
			long T = sc.nextInt();
			long U = sc.nextInt();
			long MA = A/T + (A%T==0?0:1);
			long MB = B/U + (B%U==0?0:1);
			long max = Math.max(MA, MB);
			A = T * max;
			B = U * max;
		}
		System.out.println((A+ B) );
	}
	
	
	
	
}
 
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 int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int 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();
        }
    }
    public int nextInt() {
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        boolean minus = false;
        int 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 rep(i, n) for(int i=0; i < n; i++)
#define REP(i, n, m) for(int i=n; i < m; i++)
#define reps(i, n) for(int i=1; i <= n; i++)
#define ALL(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)

using namespace std;
using ll=long long;

ll mod=1000000007;

const ll INF = 1LL << 60;

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;}

ll modpow(ll a,ll n){
  if(n == 0)return 1;
  if(n%2)return a*modpow(a,n-1)%mod;
  else return modpow(a*a%mod,n/2);
}


ll Cmod(ll n,ll k){
  if(k>n)return 0;
  ll up=1,down=1;
  while(k){
    up = up*n%mod;
    down = down*k%mod;
    n--;k--;
  }
  return up*modpow(down,mod-2)%mod;
}

int main() {
  ll n,a,b;
  cin >> n >> a >> b;
  ll ans=(modpow(2,n)-Cmod(n,a)-Cmod(n,b)-1+mod+mod)%mod;
  cout << ans;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <random>
#include <set>
#include <stack>

//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater<int>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#include <time.h>
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;



int main(){
    int n;
    cin >> n;
    map<int,int> a;
    map<int,int> b;
    rep(i,n){
        int x; cin >> x;
        a[x+i]++;
        b[i-x]++;
    }
    long long ans = 0LL;
    for(auto e:a){
        if(b[e.first]){
            ans += (ll) e.second*b[e.first];
        }
    }
    
    cout << ans;
    
}





Measured memory_bytes: 29260
#include <bits/stdc++.h>
using namespace std;
#define M 200005
int n, m, k, i, j, ans, in, in2; long long a[M], b[M];
int main ()
{
    cin >> n >> m >> k;
    for(i = 1; i <= n; i++)
    {
        cin >> in;
        a[i] += a[i-1] + in;
    }
    for(i = 1; i <= m; i++)
    {
        cin >> in;
        b[i] += b[i-1] + in;
    }
    for(i = 0; i <= n; i++)
    {
        in = a[i]; if(in > k) break;
        in2 = lower_bound(b, b + m + 1, k-in) - b;
        if(b[in2] > k-in or in2 > m) in2--;
        ans = max(ans, i + in2);
    }
    for(i = 0; i <= m; i++)
    {
        in = b[i]; if(in > k) break;
        in2 = lower_bound(a, a + n + 1, k-in) - a;
        if(a[in2] > k-in or in2 > n) in2--;
        ans = max(ans, i + in2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 6752
# -*- coding: utf-8 -*-
N = int(input())
an = list(map(int, input().split()))

cnt_dict = {}

for a in an:
    if a in cnt_dict:
        cnt_dict[a] += 1
    else:
        cnt_dict[a] = 1

ans = 0
for k in range(10**5):
    a,b,c = 0,0,0
    if k-1 in cnt_dict:
        a = cnt_dict[k-1]
    if k in cnt_dict:
        b = cnt_dict[k]
    if k+1 in cnt_dict:
        c = cnt_dict[k+1]

    if ans < a+b+c:
        ans = a+b+c

print(ans)


Measured memory_bytes: 13964
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>

using namespace std;

bitset<2000 * 2000 + 1> dp;

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

  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  dp[0] = true;

  for (int i = 0; i < n; i++) {
    dp |= dp << a[i];
  }

  vector<int> u;
  for (int i = 0; i <= 2000 * 2000; i++) {
    if (dp[i]) u.push_back(i);
  }
  sort(u.begin(), u.end());
  cout << u[u.size() / 2] << endl;
}


Measured memory_bytes: 12016
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <ctime>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cassert>
#include <bitset>
#include <list>


using namespace std;

int main()
{
    int n;
    cin >> n;
    int p[n];
    for(int i=0; i<n; i++) cin >> p[i];

    int ans = 1;
    int min_l[n];
    int mi=1000000;

    for(int i=0; i<n; i++)
    {
        min_l[i] = min(mi, p[i]);
        mi = min(mi, p[i]);
    }
    
    for(int i=1; i<n; i++)
    {
        if(p[i] <= min_l[i-1]) ans++;
    }

    cout << ans << endl;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int n, cnt[N], a[N];

main() {
    cin >> n;
    for(int i=0; i<n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    int sum = 0;
    for(int i=1; i<N; i++)
        sum += cnt[i]*(cnt[i]-1)/2;
    for(int i=0; i<n; i++)
        cout << sum - cnt[a[i]] + 1 << "\n";

}


Measured memory_bytes: 4736