Problem:


Score : 300 points

Problem Statement

AtCoDeer the deer is seeing a quick report of election results on TV.
Two candidates are standing for the election: Takahashi and Aoki.
The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes.
AtCoDeer has checked the report N times, and when he checked it for the i-th (1≦i≦N) time, the ratio was T_i:A_i.
It is known that each candidate had at least one vote when he checked the report for the first time.

Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the N-th time.
It can be assumed that the number of votes obtained by each candidate never decreases.

Constraints

1≦N≦1000

1≦T_i,A_i≦1000 (1≦i≦N)

T_i and A_i (1≦i≦N) are coprime.

It is guaranteed that the correct answer is at most 10^{18}.

Input

The input is given from Standard Input in the following format:

N
T_1 A_1
T_2 A_2
:
T_N A_N

Output

Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the N-th time.

Sample Input 1

3
2 3
1 1
3 2

Sample Output 1

10

When the numbers of votes obtained by the two candidates change as 2,3 → 3,3 → 6,4, the total number of votes at the end is 10, which is the minimum possible number.

Sample Input 2

4
1 1
1 1
1 5
1 100

Sample Output 2

101

It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.

Sample Input 3

5
3 10
48 17
31 199
231 23
3 2

Sample Output 3

6930



Sample input:
3
2 3
1 1
3 2


Sample output:
10

Submission status: Accepted

Solution code:
n = int(input())
t = []
a = []
for i in range(n):
    c = list(map(int,input().split()))
    t.append(c[0])
    a.append(c[1])
for i in range(n-1):
    d = max(1,-(-t[i]//t[i+1]),-(-a[i]//a[i+1]))
    t[i+1] =t[i+1]*d
    a[i+1] =a[i+1]*d
print(t[-1]+a[-1])

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = []
for i in range(n):
    c = list(map(int,input().split()))
    a.append(c[0])
    b.append(c[1])
for i in range(n-1):
    d = max(1,-(-a[i]//a[i+1]),-(-b[i]//b[i+1]))
    a[i+1] =a[i+1]*d
    b[i+1] =b[i+1]*d
print(a[-1]+b[-1])

Submission status: Accepted

Solution code:
N = int(input())

T,A = 0,0

for i in range(N):
    F = 0
    Ti,Ai = map(int,input().split())
    if Ti<T: F += 2
    if Ai<A: F += 1
    
    if F==3: #両方大
        KT = T//Ti if T%Ti==0 else (T//Ti)+1
        KA = A//Ai if A%Ai==0 else (A//Ai)+1
        T = Ti*max([KT,KA])
        A = Ai*max([KT,KA])
        
    elif F==2: #T側大
        K = T//Ti if T%Ti==0 else (T//Ti)+1
        T = Ti*K
        A = Ai*K
        
    elif F==1: #A側大
        K = A//Ai if A%Ai==0 else (A//Ai)+1
        T = Ti*K
        A = Ai*K
        
    else: #両方小
        T = Ti
        A = Ai
        
print(T+A)

Submission status: Accepted

Solution code:
from math import ceil
from decimal import *
n=int(input())
prea=Decimal("1.0")
pret=Decimal("1.0")
for i in range(n):
    
    t,a=map(Decimal,input().split())
    i=max(ceil(prea/a),ceil(pret/t))
    pret,prea=t*i,a*i

print(pret+prea)

Submission status: Accepted

Solution code:
from decimal import *
n=int(input())
log=[]
H=[]
for i in range(n):
    log.append(tuple(map(int,input().split())))
t,a=1,1
for x,y in log:
    nxt=max(t//x + (1 if t%x else 0),a//y + (1 if a%y else 0))
    t=x*nxt
    a=y*nxt
print(t+a)

Submission status: Accepted

Solution code:
import math
from decimal import *
a=b=Decimal("1.0")
for i in range(int(input())):
    p,q=map(Decimal,input().split())
    x=math.ceil(max(a/p,b/q))
    a,b=p*x,q*x
print(a+b)

Submission status: Accepted

Solution code:
n=int(input())
a,b=map(int,input().split())
for i in range(1,n):
    s,t=map(int,input().split())
    m=max((a+s-1)//s,(b+t-1)//t)
    a,b=m*s,m*t
print(a+b)

Submission status: Accepted

Solution code:
import math
N=int(input())
T,A=1,1
for i in range(N):
  t,a=map(int,input().split())
  k=(T+t-1) //t
  l=(A+a-1) //a
  T=t*max(k,l)
  A=a*max(k,l)
print(T+A)

Submission status: Accepted

Solution code:
N = int(input())
A, B= map(int, input().split())
for _ in range(N - 1):
    a, b= map(int, input().split())
    d = max(A // a, B // b)
    while (a * d < A) or (b * d < B):
        d += 1
    A = a * d
    B = b * d
print(A + B)

Submission status: Accepted

Solution code:
n = int(input())

x, y = map(int, input().split())
for i in range(n-1):
    a, b = map(int, input().split())
    k = max((x-1)//a+1, (y-1)//b+1)
    x, y = k * a, k * b
print(x+y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys
import itertools
import numpy as np
import functools
import collections
mo = 1000000007
r = range

n = int(input())

x, y = map(int, input().split())
for i in range(n-1):
    a, b = map(int, input().split())
    k = max((x-1)//a+1, (y-1)//b+1)
    x, y = k * a, k * b
print(x+y)

Submission status: Accepted

Solution code:
n = input()
t = []
a = []
c_t = 1
c_a = 1
for i in xrange(n):
    p,q = map(int, raw_input().split())
    t.append(p)
    a.append(q)

for i in xrange(n):
    if t[i] >= c_t and a[i] >= c_a:
        c_t = t[i]
        c_a = a[i]
    else:
        m = max(-(-c_t/t[i]), -(-c_a/a[i]))
        c_t = t[i]*m
        c_a = a[i]*m

print c_t+c_a

Submission status: Accepted

Solution code:
n = int(input())
ta = [list(map(int, input().split())) for x in range(n)]


def fit(a, b):
    for i in range(1000, 1, -1):
        if a%i == b%i == 0:
            return a // i, b // i
    return a, b


def to(a, b, limit):
    cnt = (limit[0] + a - 1) // a
    ac = a * cnt
    bc = b * cnt
    if limit[0] <= ac and limit[1] <= bc:
        return ac, bc

    cnt = (limit[1] + b - 1) // b
    ac = a * cnt
    bc = b * cnt
    if limit[0] <= ac and limit[1] <= bc:
        return ac, bc


now = [1, 1]
for t, a in ta:
    t, a = fit(t, a)
    now = to(t, a, now)
print(sum(now))

Submission status: Accepted

Solution code:
n = int(input())
p = []
for i in range(n):
    t,a = map(int, input().split())
    p.append((t,a))
q = [p[0][i] for i in range(2)]
for i in range(1, n):
    l = 0
    r = 10**18 + 1
    while l+1 < r:
        m = (l+r) //2 
        if any([p[i][j] * m < q[j] for j in range(2)]):
            l = m
        else:
            r = m
    for j in range(2):
        q[j] = r * p[i][j]

print(sum(q))

Submission status: Accepted

Solution code:
N=int(input())
A, B = 1, 1
for _ in range(N):
    C, D = map(int,input().split())
    m = max( (A+C-1)//C, (B+D-1)//D )
    A, B = m*C, m*D
print(A+B)

Submission status: Accepted

Solution code:
import sys

N = int(raw_input())
votes = []
for _ in range(N):
	t, a = map(int, raw_input().split())
	votes.append((t, a))

pt, pa = 0, 0

for v in votes:
	if (v[0] >= pt and v[1] >= pa):
		pt, pa = v[0], v[1]
	else:
		if (pt % v[0]):
			nt = pt / v[0] + 1
		else:
			nt = pt / v[0]
		if (pa % v[1]):
			na = pa / v[1] + 1
		else:
			na = pa / v[1]
		m = max(nt, na)
		pt, pa = v[0] * m, v[1] * m

print str(pt + pa)

Submission status: Accepted

Solution code:
import math
from decimal import *

def main():
    votes = int(input())
    ratio = [[ int(i) for i in input().split() ] for j in range(votes)]

    votesTemp = [0, 0]
    for i in range(votes):
        if i == 0:
            votesTemp = ratio[i]
            continue

        ceil = [ math.ceil(Decimal(votesTemp[j]) / Decimal(ratio[i][j])) for j in range(2)]

        votesTemp = [ max(ceil) * ratio[i][j] for j in range(2) ]

        """
        print("turn: " + str(i))
        print("votes: " + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
        print("Temp: " +str(votesTemp[0])+":"+str(votesTemp[1]))
        """
    print(sum(votesTemp))

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math

def cceil(x,y):
	res = x //y
	if x % y != 0:res += 1
	return res

def gcd(x, y):
	if(x == 0):return y
	return gcd(y % x, x)
 
def main():
    votes = int(input())
    ratio = [[ int(i) for i in input().split() ] for j in range(votes)]
 
    votesTemp = [0, 0]
    for i in range(votes):
        if i == 0:
            votesTemp = ratio[i]
            continue
        if(gcd(ratio[i][0], ratio[i][1]) != 1):
        	x = 1 / 0
        ceil = [ cceil(votesTemp[j], ratio[i][j]) for j in range(2)]
 
        votesTemp = [ max(ceil) * ratio[i][j] for j in range(2) ]
        
        #print("turn: " + str(i))
        #print("votes: " + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
        #print("Temp: " +str(votesTemp[0])+":"+str(votesTemp[1]))
        
    print(sum(votesTemp))
 
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())

a, b = map(int, input().split())

for _ in range(n-1):
    x, y = map(int, input().split())
    p = max(a // x, b // y)
    while x * p < a or y * p < b:
        p += 1
    a, b = x * p, y * p
    
print(a + b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N=int(raw_input())

a_num = 1
b_num = 1

for i in xrange(N):
        ratio_a, ratio_b = map(int,raw_input().split())

        base_n = max( (a_num - 1) // ratio_a + 1 , (b_num - 1 ) // ratio_b + 1)

        a_num = ratio_a * base_n
        b_num = ratio_b * base_n

print int(a_num + b_num)

Submission status: Accepted

Solution code:
N = int(input())
T = [0]*N
A = [0]*N
for i in range(N):
    T[i],A[i] = map(int,input().split())

def aa(a,t,na,nt):
    c = max( (1+(a-1)//na,1+(t-1)//nt) )
    return (na*c,nt*c)
t = T[0]
a = A[0]
for i in range(N):
    a,t = aa(a,t,A[i],T[i])
print(t+a)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
a = []
b = []
for _ in xrange(n):
 x,y = map(int,stdin.readline().split())
 a.append(x)
 b.append(y)
x = a[0]
y = b[0]
for i in xrange(1,n):
 fir = a[i]
 sec = b[i]
 if fir>=x and sec >= y:
  x = fir;y=sec
 elif fir>=x:
  k = y/sec
  if y%sec:
   k+=1
  x = fir * k
  y = sec * k
 elif sec>=y:
  k = x/fir
  if x%fir:
   k += 1
  x = fir * k
  y = sec * k
 else:
  u = x/fir
  if x%fir:
   u+=1
  v = y/sec
  if y%sec:
   v+=1
  k = u
  if v > k:
   k = v
  x = fir * k
  y = sec * k
 
 
 
print x + y

Submission status: Accepted

Solution code:
# coding: utf-8

from __future__ import print_function
from __future__ import unicode_literals
from __future__ import division
from __future__ import absolute_import
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect

def array2d(d1, d2, init = None):
    return [[init for _ in range(d2)] for _ in range(d1)]

N = int(input())

va, vb = 1, 1
for i in range(N):
    pa, pb = [int(x) for x in input().split(" ")]
    r = int(max((va + pa - 1) // pa, (vb + pb - 1) // pb))
    va = pa * r
    vb = pb * r
print(va + vb)

Submission status: Accepted

Solution code:
N = int(input())
TA = []
for i in range(N):
	TA.append(list(map(int, input().split())))
 
TA.reverse()
(voteA, voteB) = (1,1)
while TA:
	(Ti, Ai) = TA.pop()
	tmp = max((voteA + Ti -1) // Ti, (voteB + Ai -1) // Ai)
	voteA = Ti * tmp
	voteB = Ai * tmp
print(voteA + voteB)

Submission status: Accepted

Solution code:

ans = 0

for i in range(int(input())):
    t_i, a_i = list(map(lambda x: int(x), input().split()))

    if i == 0:
        t, a = t_i, a_i

    else:
        n = max((t + t_i - 1) // t_i, (a + a_i - 1) // a_i)
        t = n*t_i
        a = n*a_i

    ans = t + a

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mt, ma = 1, 1
for t, a in (map(int, input().split()) for _ in range(n)):
    l = max((mt-1)//t, (ma-1)//a)  + 1
    mt, ma = l*t, l*a
print(mt+ma)

Submission status: Accepted

Solution code:
def increase(a, b, c, d):
    k = (b + d - 1) // d
    return k*c, k*d

n = int(raw_input())
a, b = map(int, raw_input().split())
for i in range(n - 1):
    c, d = map(int, raw_input().split())
    if a*d == b*c:
        continue
    if a*d < b*c:
        a, b = increase(a, b, c, d)
    else:
        b, a = increase(b, a, d, c)
print(a + b)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 解説に従い実装

N=int(input())

for i in range(N):
    ti,ai = map(int,input().split())
    if i == 0:
        t,a = ti,ai
    else:
        # t <= n * ti and a <= n * ai を満たす最小のnを求める
        n = max((t + ti - 1) // ti, (a + ai - 1) // ai)
        t = n * ti
        a = n * ai

print(a+t)

Submission status: Accepted

Solution code:
N = int(input())
T,A = [0 for i in range(N)],[0 for i in range(N)]
for i in range(N):
    T[i],A[i] = map(int,input().split())
a = 1
b = 1
for i in range(N):
    low = 0
    high = 10**18
    while high - low > 1:
        x = (high + low) // 2
        if a <= T[i] * x and b <= A[i] * x:
            high = x
        else:
            low = x
    a = high * T[i]
    b = high * A[i]
print(a + b)

Submission status: Accepted

Solution code:
def f(a, b, c, d):
    n = max(1,a//c, b//d)
    while a > c * n or b > d * n : n += 1
    return c * n, d * n
    
def main():
    a, b = 0, 0
    for i in range(int(input())):
        c, d = map(int, input().split())
        a, b = f(a, b, c, d)
    print(a+b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        if ta[i-1][0]>ta[i][0] and ta[i-1][1]>ta[i][1]:
            mx=max((ta[i-1][0]-1)/ta[i][0]+1,(ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][0]=ta[i][0]*mx
            ta[i][1]=ta[i][1]*mx
        elif ta[i-1][0]>ta[i][0]:
            ta[i][1]=ta[i][1]*((ta[i-1][0]-1)/ta[i][0]+1)
            ta[i][0]=ta[i][0]*((ta[i-1][0]-1)/ta[i][0]+1)
        elif ta[i-1][1]>ta[i][1]:
            ta[i][0]=ta[i][0]*((ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][1]=ta[i][1]*((ta[i-1][1]-1)/ta[i][1]+1)
    print(ta[n-1][0]+ta[n-1][1])
main()

Submission status: Accepted

Solution code:
n = int(raw_input())
t = []
a = []
for i in xrange(n):
    mem = map(int, raw_input().split())
    t.append(mem[0])
    a.append(mem[1])

for i in xrange(n):
    if i == 0:
        tn = t[0]
        an = a[0]
    else:
        mt = tn / t[i] if (tn%t[i] == 0) else tn / t[i] + 1
        ma = an / a[i] if (an%a[i] == 0) else an / a[i] + 1
        if mt > ma:
            tn = mt * t[i]
            an = mt * a[i]
        else:
            tn = ma * t[i]
            an = ma * a[i]
print tn + an

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

def f(a, b, c, d):
    n = max(1,a//c, b//d)
    while a > c * n or b > d * n : n += 1
    return c * n, d * n
    
def main():
    a, b = 0, 0
    for i in range(int(input())):
        c, d = map(int, input().split())
        a, b = f(a, b, c, d)
    print(a+b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

N = int(input())
X, Y = map(int, input().split())
for i in range(N - 1):
    T, A = map(int, input().split())
    if T >= X and A >= Y:
        X = T
        Y = A
    else:
        if X % T == 0:
            t = X // T
        else:
            t = X // T + 1
        if Y % A == 0:
            a = Y // A
        else:
            a = Y // A + 1
        X = T * max(a, t)
        Y = A * max(a, t)
print(X + Y)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N=int(input())

def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b / gcd(a, b)

def func1(x, xi):
    if x % xi == 0:
        return x
    else:
        return xi * (x // xi) + xi

for i in range(N):
    ti,ai = map(int,input().split())
    if i == 0:
        t,a = ti,ai
    else:
        t,a = func1(t, ti),func1(a, ai)

        # a is short
        if ti / ai < t / a:
            a = t // ti * ai
        else:
            t = a // ai * ti

    # print("t,a=",t,a)
print(a+t)

Submission status: Accepted

Solution code:
import math

def GCD(a, b):
    if a > b: 
        return GCD(b, a)
    if a == 0:
        return b
    return GCD(b%a, a)

def LCM(a, b):
    return a * b / GCD(a, b)

def GetSmallest(a, b, c, d):
    # Get smallest multiple 
    tgt = max([a * d, b * c])
    lcm = LCM(c, d)
    if tgt % lcm == 0:
        factor = tgt / lcm
    else:
        factor = tgt / lcm + 1

    cm = factor * lcm
    newA = cm / d
    newB = cm / c

    return newA, newB

N = int(raw_input())
qn = []
for n in xrange(N):
    qn.append(map(int, raw_input().split()))

cur = (qn[0][0], qn[0][1])
for n in xrange(1, N):
    cur = GetSmallest(cur[0], cur[1], qn[n][0], qn[n][1])

print cur[0] + cur[1]

Submission status: Accepted

Solution code:
n = int(raw_input())

xx = 1
yy = 1
for i in xrange(n):
  [x, y] = [int(e) for e in raw_input().strip().split()]
  #print "===%d, %d===" % (x, y)
  if i == 0:
    xx = x
    yy = y
  else:
    #print "===(%d, %d)  (%d, %d)===" % (x, y, xx, yy)
    if x >= xx and y >= yy:
	  xx = x
	  yy = y
    else:
	  multi_x = -1
	  multi_y = -1
	  if x < xx:
	    multi_x = xx / x
	    if xx % x != 0: multi_x += 1
	  if y < yy:
	    multi_y = yy / y
	    if yy % y != 0: multi_y += 1
	  multi = max(multi_x, multi_y)
	  xx = x * multi
	  yy = y * multi
	  #print "===" + str(multi)
print xx + yy

Submission status: Accepted

Solution code:
if __file__ == '/tmp/code.py':
	import sys
	sys.stdin = open('input.txt')

n = int(raw_input())

a, b = 0, 0
for _ in xrange(n):
	x, y = map(int, raw_input().split())

	k = 1
	if x < a:
		k = (a + x - 1) / x
	if y < b:
		k = max(k, (b + y - 1) / y)

	a, b = k * x, k * y

print a + b

Submission status: Accepted

Solution code:
n = input()
p, q = [-1, -1]
for i in xrange(n):
    t, a = map(int, raw_input().split())
    if p == -1 or q == -1:
        p = t
        q = a
        continue
    if t >= p and a >= q:
        p = t
        q = a
    else:
        z = max(p / t + (p % t != 0), q / a + (q % a != 0))
        p = t * z
        q = a * z
print p + q

Submission status: Accepted

Solution code:
def f(x, y):
    return y * (x // y + (1 if x % y else 0))
n = int(input())
x, y = 1, 1
for i in range(n):
    t, a = (int(_) for _ in input().split())
    nx = f(x, t)
    ny = max(nx // t * a, f(y, a))    
    nx = ny // a * t
    x, y = nx, ny
print(x + y)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a,b = 1,1
    t = 0
    for _ in range(n):
        l,r = list(map(int, input().split()))
        ll = l
        rr = r
        if ll < a:
            s = a - ll
            ss = (s // l)
            while ss * l + ll < a:
                ss += 1
            ll += l*ss
            rr += r*ss
        if rr < b:
            s = b - rr
            ss = (s // r)
            while ss * r + rr < b:
                ss += 1
            ll += l*ss
            rr += r*ss
        a = ll
        b = rr
        t = ll + rr
    return t

print(f())

Submission status: Accepted

Solution code:
n = int(raw_input())
x = y = 1
for _ in xrange(n):
    t, a = map(int, raw_input().split())
    xi = x / t + (x % t != 0)
    yi = y / a + (y % a != 0)
    k = max(xi, yi)
    x = k * t
    y = k * a
print x + y

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

N = n()

z, x = ln()

for i in xrange(N - 1):
    t, a = ln()
    q = t + a
    r1 = (z + x) / q
    if (z + x) % q != 0:
        r1 += 1
    r2 = z / t
    if z % t != 0:
        r2 += 1
    r3 = x / a
    if x % a != 0:
        r3 += 1
    m = max(r1, r2, r3)
    z = t * m
    x = a * m

print z + x

Submission status: Accepted

Solution code:
N = input()
t, a = map(int, raw_input().split())
for i in xrange(N-1):
    new_t, new_a = map(int, raw_input().split())
    d = max((t-1)/new_t+1, (a-1)/new_a+1, 1)
    t, a = new_t*d, new_a*d
print t+a

Submission status: Accepted

Solution code:
N = int(raw_input())
# T_list = []
# A_list = []
T = 1
A = 1

for n in range(N):
    t, a = map(int, raw_input().split())
    k = max(int(T/t), int(A/a))
    if T > t*k or A > a*k:
        T = t*(k+1)
        A = a*(k+1)
    else:
        T = t*k
        A = a*k

print T+A

Submission status: Accepted

Solution code:
n = int(input())
x, y = 0, 0
for i in range(n):
    a, b = map(int, input().split())
    lb, ub = 0, 10 ** 19
    while ub - lb > 1:
        md = (lb + ub) // 2
        if a * md >= x and b * md >= y:
            ub = md
        else:
            lb = md
    x, y = a * ub, b * ub
print(x + y)

Submission status: Accepted

Solution code:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))


INF = 2147483647


import sys
stdin = sys.stdin

T =        int( stdin.readline().strip() )

ct = 1
ca = 1
for icase in range(1, T+1):
    t, a = map(int, stdin.readline().strip().split())
    n = max((ct + t - 1) // t,
            (ca + a - 1) // a)
    ct = n*t
    ca = n*a

print ct + ca

Submission status: Runtime Error

Solution code:
import math
N = int(input())
t= 1
a= 1

def t_small(t,a,t1,a1):
    gain = -(-t//t1)
    t = gain*t1
    a_tmp=gain*a1
    if a_tmp<a:
        gain_a = -(-a//a_tmp)
        t *= gain_a
        a = a_tmp*gain_a
    else:
        a = a_tmp
    return t,a,t+a

def a_small(t,a,t1,a1):
    gain = -(-a//a1)
    a = gain*a1
    t_tmp=gain*t1
    if t_tmp<t:
        gain_t = -(-t//t_tmp)
        a *= gain_t
        t = t_tmp*gain_t
    else:
        t = t_tmp
    return t,a,t+a

ans = 0
for _ in range(N):
    t1,a1 = map(int,input().split())
    tt1,aa1,sta1 = t_small(t,a,t1,a1)
    tt2,aa2,sta2 = a_small(t,a,t1,a1)
    if sta1<=sta2:
        t=tt1;a=aa1,ans = sta1
    else:
        t=tt2,a=aa2,ans=sta2
print(ans)

Submission status: Runtime Error

Solution code:
import math
def f(x1,y1,x2,y2,z):
    a = gcd(x1,x2)
    z = max(z,math.ceil((x2+y2)*x1/x2))
    x = x2+y2
    n = z//x
    k = z%x
    if k==0:
        z = n*x
        x1 = (z*x2)//x
        y1 = (z*y2)//x
        return z,x1,y1
    else:
        z = (n+1)*x
        x1 = (z*x2)//x
        y1 = (z*y2)//x
        return z,x1,y1
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
x1,y1 = A[0]
s = x1+y1
for i in range(1,N):
    t,a = A[i]
    s,x1,y1 = f(x1,y1,t,a,s)
print(s)

Submission status: Runtime Error

Solution code:
#include <iostream>
using namespace std;
using ex = int;
#define ar(i,n) for(ex i=0;i<(n);++i)
#define ebmr >>
#define ebar <<
ex arsalmal = 1;

ex main(){
  ex albio ,ars = 0 ,almal = 0;
  cin ebmr albio;
  ar(i,albio){
    ex eb, mr;
    cin ebmr eb ebmr mr;
    if(i==0){
      ars = eb; almal = mr;
    }
    else{
      ex exalbio = max((ars - arsalmal)/ eb + arsalmal,( almal - arsalmal) / mr + arsalmal);
      ars = eb * exalbio;almal = mr * exalbio;
    }
  }
  cout ebar ars + almal ebar endl;
}

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    b = [LI() for _ in range(N)]

    for i in range(1,N):
        if b[i][0] < b[i-1][0] or b[i][1] < b[i-1][1]:
            r = max(math.ceil([i-1][0]/b[i][0]),math.ceil([i-1][1]/b[i][1]))
            b[i][0] *= r
            b[i][1] *= r
    print(sum(b[-1]))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from math import ceil

def main():
  n = int(input())
  for i in range(n):
    t, a = map(int, input().split())
    if i == 0:
      nt, na =  t, a
      continue
    cands = list(filter(lambda x: x[0] >= nt and x[1] >= na, [(ceil(nt/t)*t, ceil(nt/t)*a), (ceil(na/a)*t, ceil(na/a)*a)]))
    nt, na = min(cands)
  print(nt + na)

if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
N = int(input())
T, A = map(int, input().split())
for i in range(N-1):
    t, a = map(int, input().split())
    n = max(-(-T//t), -(-A//a))
    T, A = n * t, n, * a
print(T+A)

Submission status: Runtime Error

Solution code:
N = int(input())
x, y = 0
for i in range(N):
  a, b = map(int, input().split())
  mul = max((x-1)//a+1, (y-1)//b+1)
  x = mul*a
  y = mul*b
print(x+y)

Submission status: Runtime Error

Solution code:
N=int(input())
 
X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])
 
 
a=X[0][0]
b=X[0][1]
 
for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
 

  x= (a + (c - 1)) // c
  y= (b + (d -1))) // d
  
  a1=1000000000000000000
  b1=1000000000000000000
  a2=1000000000000000000
  b2=1000000000000000000
  if d*x-b>=0:
    a1=c*x
    b1=d*x
 
  
  if c*y-a>=0:
    a2=c*y
    b2=d*y
  if (a1+b1)<(a2+b2):
    a=a1
    b=b1
  else:
    a=a2
    b=b2
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" a1 = "+str(a1)+" b1 = "+str(b1)+" a2 = "+str(a2)+" b2 = "+str(b2)+" c = "+str(c)+" d = "+str(d))
  
 
 
 
 
  
print(a+b)

Submission status: Runtime Error

Solution code:
N=int(input())
 
X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])
 
 
def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)
 
 
a=X[0][0]
b=X[0][1]
 
for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
 
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" c = "+str(c)+" d = "+str(d))
  x=ceil(a/c)
  y=ceil(b/d)
  
 
  if d*x-b>=0:
    a=c*x
    b=d*x

    t=a+b

 
  
  if c*y-a>=0:

    if c*y+d*y<t:
      a=c*y
      b=d*y
 
 
  
print(a+b)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

def f(a,b,i):
  c=X[i+1][0]
  d=X[i+1][1]

  x=ceil(a/c)
  y=ceil(b/d)
  ans=1000000000000
  if i!=N-2:
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,f(a,b,i+1))
    
    if d*x-b>=0:
      z=f(c*x,d*x,i+1)
      if z<ans:
        a=c*x
        b=d*x
        ans=z

  elif i==N-2:
    
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,a+b)
    
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,a+b)

  return ans



print(f(a,b,0))

Submission status: Runtime Error

Solution code:
N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

def f(a,b,i):
  c=X[i+1][0]
  d=X[i+1][1]

  x=ceil(a/c)
  y=ceil(b/d)
  ans=1000000000000
  if i!=N-2:
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,f(a,b,i+1))
    
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,f(a,b,i+1))

  elif i==N-2:
    
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,a+b)
    
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,a+b)

  return ans



print(f(a,b,0))

Submission status: Runtime Error

Solution code:
N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

def f(a,b,i):
  c=X[i+1][0]
  d=X[i+1][1]

  x=ceil(a/c)
  y=ceil(b/d)

  if i!=N-2:


    ans=100000000000
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,f(a,b,i+1))
    
  
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,f(a,b,i+1))
    
    return ans


  elif i==N-2:

    ans=100000000
    if c*y-a>=0:
      a=c*y
      b=d*y
      ans=min(ans,a+b)
    
  
    if d*x-b>=0:
      a=c*x
      b=d*x
      ans=min(ans,a+b)

    return ans



print(f(a,b,0))

Submission status: Runtime Error

Solution code:
N=int(input())

X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])


def ceil(x):
  if int(x)==x:
    return int(x)
  else:
    return int(x//1+1)


a=X[0][0]
b=X[0][1]

for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
  a1=a*d/c
  if a1<b:
    y=math.ceil(a/c)*d-b
  else:
    y=math.ceil(a/c)*d-b

  while y<0:
    y+=d


  x=c*(b+y)//d-a
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" c = "+str(c)+" d = "+str(d)+" x = "+str(x)+" y = "+str(y))
  a=a+x
  b=b+y
print(a+b)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, t, a;
long long int ans = 0;
long long int tWahl, aWahl;

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

	cin >> n;

	tWahl = aWahl = 0;

	for(int i = 0; i < n; i++) {
		cin >> t >> a;
		if(aWahl == 0 || aWahl % a != 0) {
			aWahl += a;
			aWahl -= (aWahl % a);
		}
		if(tWahl == 0 || tWahl % t != 0) {
			tWahl += t;
			tWahl -= (tWahl % t);
		}
		if(tWahl/t > aWahl/a) {
			aWahl = (tWahl/t)*a;
		} else if(tWahl/t < aWahl/a) {
			tWahl = (aWahl/a)*t;
		}
	}

	cout << aWahl + tWahl << endl;

	return 0;
}

Submission status: Runtime Error

Solution code:
import math
N = int(input())
for i in range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = math.ceil(x/a)
    yb = math.ceil(y/b)
    c = max(xa,yb)
    x,y = a*c,b*c
print(x+b)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
for i range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = math.ceil(x/a)
    yb = math.ceil(y/b)
    c = max(xa,yb)
    x,y = a*c,b*c
print(x+y)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
for i range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = math.ceil(x/a)
    yb = math.ceil(y/b)
    c = max(xa,yb)
    x,y = a*c,b*c
print(x+b)

Submission status: Runtime Error

Solution code:
N = int(input())
lia=[int(it) for it in input().split()]
lib=[int(it) for it in input().split()]
lip=[lia[i]-lib[i] for i in range(N)]
sb = 0
for i in range(N):
    if (lip[i]>0):
        sb+=lip[i]
sa2 = 0
sas = 0
for i in range(N):
    if (lip[i]<0):
        sa2=(-lip[i])//2
        sas+=(-lip[i])
sas-=sb*2
x = sum(lib)-sum(lia)

if (sa2>=sb and sb+sas == x):
    print ("Yes")
else:
    print ("No")

Submission status: Runtime Error

Solution code:
N = int(input())
T = []
A = []
for i in range(N):
  a, b = map(int, input().split())
  T.append(a)
  A.append(b)

t = T[0]
a = A[0]

for i in range(1, N):
  if t < T[i] and a < A[i]:
    t = t[i]
    a = A[i]
  else:
    x = int((t + T[i] - 1) / T[i])
    y = int((a + A[i] - 1) / A[i])
    t = T[i] * max(x, y)
    a = A[i] * max(x, y)

print(t + a)

Submission status: Runtime Error

Solution code:
import math

N = int(input())
ratios = []
for i in range(N):
    t, a = map(int, input().split())
    ratios.append([t, a])

def min_vote(index):
    if index == N-1:
        return ratios[N-1-index]

    mt, ma = min_vote(index+1)
    t, a = ratios[N-1-index]
    min_ratio = max(math.ceil(mt / t), math.ceil(ma / a))
    return [t * min_ratio, a * min_ratio]

print(sum(min_vote(0)))