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:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n=i()
t=[0]*n
a=[0]*n
for j in range(n):
    t[j],a[j]=ii()

tt,aa=1,1
for j in range(n):
    if t[j]>=tt and a[j]>=aa:
        tt,aa=t[j],a[j]
    else:
        k=max(tt/t[j]+int(tt%t[j]!=0),aa/a[j]+int(aa%a[j]!=0))
        tt,aa=t[j]*k,a[j]*k

print tt+aa

Submission status: Accepted

Solution code:
def getLnInput():
    return input().split()


def getNewVote(currentVote, newRatio):
    multFacCeil = []
    for i in range(2):
        multFacCeil.append((currentVote[i] - 1) // newRatio[i] + 1)
    newVote = []
    maxMF = max(multFacCeil)
    for i in range(2):
        newVote.append(newRatio[i] * maxMF)
    return newVote


def main():
    N = int(getLnInput()[0])
    voteNum = list(map(int, getLnInput()))
    for i in range(N - 1):
        newRatio = list(map(int, getLnInput()))
        voteNum = getNewVote(voteNum, newRatio)
    print(sum(voteNum))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin

n = int(stdin.readline())

m = 10 ** 18 + 7


t_votes, a_votes = (int(x) for x in stdin.readline().split())

p_t, p_a = t_votes, a_votes

for _ in range(n-1):
    t, a = (int(x) for x in stdin.readline().split())
    if (t, a) == (p_t, p_a):
        continue
    for i in range(max(t_votes // t, a_votes // a) - 1, m):
        t_v, a_v = t * i, a * i
        if t_v >= t_votes and a_v >= a_votes:
            break
    t_votes, a_votes = t_v, a_v
    p_t, p_a = t, a

print(t_votes + a_votes)

Submission status: Accepted

Solution code:
N = int(raw_input())
Ts = []
As = []
for t in xrange(N):
    T, A = map(int, raw_input().split())
    Ts.append(T)
    As.append(A)
    
leastT= Ts[0]
leastA= As[0]

for i in xrange(1,len(Ts)):
    maxcoeff = max( (leastA + As[i] - 1) / As[i], 
                    (leastT + Ts[i] - 1) /Ts[i])
    leastT = Ts[i] * maxcoeff
    leastA = As[i] * maxcoeff

print leastT+leastA

Submission status: Accepted

Solution code:
N = input()
x,y = 1,1
for i in range(N):
    T,A = map(int, raw_input().split())
    k = max((x+T-1)/T, (y+A-1)/A)
    x,y = k*T,k*A
print x+y

Submission status: Runtime Error

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
import bisect
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    N = i_input()
    t0,a0 = 1,1

    for i in range(N):
        t1,a1 = i_map()
        f0 = t0//t1
        if t0%t1 != 0:
            f0 += 1
        f1 = a0 // a1
        if a0%a1 != -:
            f1 += 1
        f = max(f0, f1)
        t0, a0 = t1*f, a1*f
    print(t0+a0)


if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
n = int(input())
A, B = 0, 0
for i in range(n):
    x, y = int(input.split())
    dx, dy = 1, 1
    if A > x:
        dx = A // x
        if A % x != 0:
            dx += 1
    
    if B > y:
        dy = B // y
        if B % y != 0:
            dy += 1

    a = max(dx, dy)
    A, B = a * x, a * y
print(A + B)

Submission status: Runtime Error

Solution code:
import fractions 

N = int(input())
for i in range(N):#1000
  t, a = map(int, input().split())
  if i == 0:
    taka, aoki = t, a
  else:
    now = [10 ** 10, -1, -1]
    for i in range(1001):
      if ((taka + i) * (a / t)) % 1 == 0:
        a2 = int((taka + i) * (a / t))
        if (now[0] >= a2 + taka + i) and (a2 >= aoki):
          now = [taka + i + a2, taka + i, a2]
      if ((aoki + i) * (t / a)) % 1 == 0:
        b2 = int((aoki + i) * (t / a))
        if (now[0] >= b2 + aoki + i) and (b2 >= taka):
          now = [aoki + i + b2, b2, aoki + i]
    taka = now[1]
    aoki = now[2]
    #print(now)
print(now[0])

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
import random
import math
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	x, y = 1, 1
	for _ in range(n):
		t, a = LI()
		m = max((x+t-1)//a,(y+a-1)//b)
		x, y = m*t, m*a
	print(x+y)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
from fractions import Fraction
n = int(input())

x, y = map(int, input().split())
t, a = x, y

for _ in range(n - 1):
    tt, aa = map(int, input().split())

    #c = 1
    '''
    if (t >= a):
        c = math.ceil(tt / t)

    else:
        c = math.ceil(aa / a)
    '''
    #c = math.ceil(t / tt, a / aa)
    c = math.ceil(Fraction(t, tt), Fraction(a / aa))

    t = tt * c
    a = aa * c


ans = t + a
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
pairs=[LI() for i in range(n)]
def pair_revise(x,y,a,b):
    global p
    global q
    #print(x,y,a,b)
    for i in range(max(1,min(floor(x/a),floor(y/b))),max(ceil(x/a),ceil(y/b))+1):
        p,q=a*i,b*i
        if p>=x and q>=y:
            break
    return [p,q]
    #return [x*max(ceil(x/a),ceil(y/b)),y*max(ceil(x/a),ceil(y/b))]
    #for i in range(max(ceil(x/a),ceil(y/b)),):
u,v=pairs[0]
for i in range(n-1):
    u,v=pair_revise(u,v,pairs[i+1][0],pairs[i+1][1])
print(u+v)

Submission status: Runtime Error

Solution code:
import math
n=int(input())
x,y=map(int,input().split())
gcd=math.gcd(x,y)
x=int(x/gcd)
y=int(y/gcd)
for i in range(n-1):
  s,t=map(int,input().split())
  if s<x:
    w=int(x/s)+1
    s*=w
    t*=w
  if t<y:
    w=int(y/t)+1
    s*=w
    t*=w
  x=s
  y=t
print(x+y)

Submission status: Runtime Error

Solution code:
from math import gcd, ceil

n = int(input())
a, b = 1, 1
for _ in range(n):
    x, y = map(int, input().split())
    xx, yy = (ceil(a / x) * x, ceil(b / y) * y)
    f = max(xx // x, yy // y)
    a, b = f * x, f * y
print(a + b)

Submission status: Runtime Error

Solution code:
from math import gcd, ceil

n = int(input())
a, b = map(int, input().split())
g = gcd(a, b)
a //= g
b //= g
for _ in range(n - 1):
    x, y = map(int, input().split())
    xx, yy = (ceil(a / x) * x, ceil(b / y) * y)
    f = max(xx // x, yy // y)
    a, b = f * x, f * y
print(a + b)

Submission status: Runtime Error

Solution code:
from math import *

n = int(input())
a, b = map(int, input().split())
g = gcd(a, b)
a //= g
b //= g
for _ in range(n - 1):
    x, y = map(int, input().split())
    x //= gcd(x, y)
    y //= gcd(x, y)
    xx, yy = (ceil(a / x) * x, ceil(b / y) * y)
    f = max(xx // x, yy // y)
    a, b = f * x, f * y
print(a + b)

Submission status: Runtime Error

Solution code:
from sys import stdin
import math
N = int(stdin.readline().rstrip())
t,a = [int(x) for x in stdin.readline().rstrip().split()]
 
for _ in range(N-1):
    T,A = [int(x) for x in stdin.readline().rstrip().split()]
    int(n) = max(math.ceil(t/T),math.ceil(a/A))
    t = n*T
    a = n*A
    
print(t+a)

Submission status: Runtime Error

Solution code:
n = int(input())
ary = []
for i in range(n):
  tmp_ary = list(map(int, input().split()))
  if len(ary) == 0:
    ary = tmp_ary[:]
  else:
    t_rate = math.ceil(ary[0] / tmp_ary[0])
    a_rate = math.ceil(ary[1] / tmp_ary[1])
    rate = max([t_rate, a_rate])
    ary = list(map(lambda x: x * rate, tmp_ary))

print(ary[0] + ary[1])

Submission status: Runtime Error

Solution code:
N = int(input())
TA = [[int(i) for i in input().split()] for i in range(N)]
Takahashi, Aoki = TA[0][0], TA[0][1]

for ta, ao in TA:
    if Takahashi <= ta and Aoki <= ao:
        Takahashi, Aoki = ta, ao
    else:
        num = max(math.ceil(Takahashi / ta), math.ceil(Aoki / ao))
        Takahashi, Aoki = num * ta, num * ao


print(Takahashi + Aoki)

Submission status: Runtime Error

Solution code:
def main():
    from math import ceil
    n = int(input())
    a, b = 1, 1
    for _ in range(n):
        i, j = map(int, input().split())
        x = max((a + s - 1) // s, (b + t - 1) // t)
        a, b = x * i, x * j
    print(a + b)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
t_lst, a_lst = [], []
for i in range(n):
    ti, ai = map(int, input().split())
    t_lst.append(ti)
    a_lst.append(ai)

t, a = 1, 1
for i in range(n):
    ti, ai = t_lst[i], a_lst[i]
    if ti>=t and ai>=a:
        t, a = ti, ai
    elif ti<t and ai>=a:
        t = ti * math.ceil(t/ti)
        a = ai * math.ceil(t/ti)
    elif ti>=t and ai<a:
        t = ti * math.ceil(a/ai)
        a = ai * math.ceil(a/ai)
    else:
        t_lcm = lcm_base(ti, t)
        a_lcm = lcm_base(ai, a)
        new1 = [t_lcm*math.ceil(a/(t_lcm/ti*ai)), t_lcm/ti*ai*math.ceil(a/(t_lcm/ti*ai))]
        new2 = [a_lcm/ai*ti*math.ceil(t/(a_lcm/ai*ti)), a_lcm*math.ceil(t/(a_lcm/ai*ti))]
        if sum(new1) < sum(new2):
            t, a = new1[0], new1[1]
        else:
            t, a = new2[0], new2[1]
print(t+a)

Submission status: Runtime Error

Solution code:
import math

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
t_lst, a_lst = [], []
for i in range(n):
    ti, ai = map(int, input().split())
    t_lst.append(ti)
    a_lst.append(ai)

t, a = 1, 1
for i in range(n):
    ti, ai = t_lst[i], a_lst[i]
    if ti>=t and ai>=a:
        t, a = ti, ai
    elif ti<t and ai>=a:
        t = ti * math.ceil(t/ti)
        a = ai * math.ceil(t/ti)
    elif ti>=t and ai<a:
        t = ti * math.ceil(a/ai)
        a = ai * math.ceil(a/ai)
    else:
        t_lcm = lcm_base(ti, t)
        a_lcm = lcm_base(ai, a)
        new1 = [t_lcm*math.ceil(a/(t_lcm//ti*ai)), t_lcm//ti*ai*math.ceil(a/(t_lcm//ti*ai))]
        new2 = [a_lcm//ai*ti*math.ceil(t/(a_lcm//ai*ti)), a_lcm*math.ceil(t/(a_lcm//ai*ti))]
        if sum(new1) < sum(new2):
            t, a = new1[0], new1[1]
        else:
            t, a = new2[0], new2[1]
print(t+a)

Submission status: Runtime Error

Solution code:
import math

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

n = int(input())
t, a = 1, 1
for i in range(n):
    ti, ai = map(int, input().split())
    if ti>=t and ai>=a:
        t, a = ti, ai
    elif ti<t and ai>=a:
        t = ti * math.ceil(t/ti)
        a = ai * math.ceil(t/ti)
    elif ti>=t and ai<a:
        t = ti * math.ceil(a/ai)
        a = ai * math.ceil(a/ai)
    else:
        t_lcm = lcm_base(ti, t)
        a_lcm = lcm_base(ai, a)
        new1 = [t_lcm*math.ceil(a/(t_lcm//ti*ai)), t_lcm//ti*ai*math.ceil(a/(t_lcm//ti*ai))]
        new2 = [a_lcm//ai*ti*math.ceil(t/(a_lcm//ai*ti)), a_lcm*math.ceil(t/(a_lcm//ai*ti))]
        if sum(new1) < sum(new2):
            t, a = new1[0], new1[1]
        else:
            t, a = new2[0], new2[1]
print(t+a)

Submission status: Runtime Error

Solution code:
def resolve():
	n = int(input())
	v = []
	for _ in range(n):
		v.append(list(map(int, input().split())))
	t, a = 1, 1
	for i in range(n):
		tv, av = v[i]
		c = max(math.ceil(t/tv), math.ceil(a/av))
		t, a = c*tv, c*av
	print(t+a)
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
	n = int(input())
	v = []
	for _ in range(n):
		v.append(list(map(int, input().split())))
	t, a = v[0][0], v[0][1]
	for i in range(1, n):
		tv, av = v[i]
		c = max(math.ceil(t/tv), math.ceil(a/av))
		t, a = c*tv, c*av
	print(t+a)
resolve()

Submission status: Runtime Error

Solution code:
import math
n = int(input())
A,B = map(int,input().split())
for _ in range(n-1):
  a,b = map(int,input().split())
  m = max(math.ceil(A/a), math.ceil(B/b))
  A,B = A * m, B * m
print(A+B)

Submission status: Runtime Error

Solution code:
n = int(input())
A,B = map(int,input().split())
for _ in range(n-1):
  a,b = map(int,input().split())
  m = max(math.ceil(A/a), math.ceil(B/b))
  A,B = A * m, B * m
print(A+B)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    else:
        m = max(math.ceil(pret / t), math.ceil(prea / a))
        pret = m * t
        prea = m * a
print(pret + prea)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

N = int(input())
t = [0] * N
A = [0] * N
total = []
for i in range(N):
    t[i], A[i] = map(int, input().split())
    total.append(t[i]+A[i])

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm_list(total))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
vlist = [input().split() for i in range(n)]
for m in range(n) :
    vlist[m] = [int(l) for l in vlist[m]]
for j in range(n-1) :
    if vlist[j][0] <= vlist[j+1][0] and vlist[j][1] <= vlist[j][1] :
        continue
    if vlist[j][0] > vlist[j+1][0] and vlist[j][0] > vlist[j][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
        continue
    elif vlist[j][1] > vlist[j+1][1] and vlist[j][1] > vlist[j][0]:
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    elif vlist[j+1][0] > vlist[j+1][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    else :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
print(sum(vlist[n-1]))

Submission status: Runtime Error

Solution code:
n = int(input())
vlist = [input().split() for i in range(n)]
for m in range(n) :
    vlist[m] = [int(l) for l in vlist[m]]
for j in range(n-1) :
    if vlist[j][0] <= vlist[j+1][0] and vlist[j][1] <= vlist[j][1] :
        continue
    if vlist[j][0] > vlist[j+1][0] and vlist[j][0] > vlist[j][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
        continue
    elif vlist[j][1] > vlist[j+1][1] and vlist[j][1] > vlist[j][0]:
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    elif vlist[j+1][0] > vlist[j+1][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    else :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
print(sum(vlist[n-1]))

Submission status: Runtime Error

Solution code:
for j in range(n-1) :
    if vlist[j][0] <= vlist[j+1][0] and vlist[j][1] <= vlist[j][1] :
        continue
    if vlist[j][0] > vlist[j+1][0] and vlist[j][0] > vlist[j][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
        continue
    elif vlist[j][1] > vlist[j+1][1] and vlist[j][1] > vlist[j][0]:
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    elif vlist[j+1][0] > vlist[j+1][1] :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][1], vlist[j+1][1]))/vlist[j+1][1]) for k in vlist[j+1]]
        continue
    else :
        vlist[j+1] = [int(k*(np.lcm(vlist[j][0], vlist[j+1][0]))/vlist[j+1][0]) for k in vlist[j+1]]
print(sum(vlist[n-1]))

Submission status: Runtime Error

Solution code:
https://atcoder.jp/contests/abc046/tasks/arc062_a
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  t,a=LI()
  l=[LI() for _ in range(n-1)]

  # t<=nt' and a<=na'
  # t/t'<=n and a/a'<=n
  for _t,_a in l:
    _n=max(-(-t//_t),-(-a//_a))
    t=_n*_t
    a=_n*_a

  return t+a

# main()
print(main())

Submission status: Runtime Error

Solution code:
n = int(input())
from math import ceil, gcd

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = map(int, input().split())
    t, a = t // gcd(t,a), a // gcd(t,a)
    k = max(ceil(tkhs/t), ceil(aoki/a))
    tkhs = k*t
    aoki = k*a

print(tkhs+aoki)

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
ans1 = 1
ans2 = 1
for _ in range(N):
  i1, i2 = list(map(int, input().split()))
  n = max(np.ceil(ans1/i1), np.ceil(ans2/i2))
  ans1 = i1 * n
  ans2 = i2 * n
print(int(ans1+ans2))

Submission status: Runtime Error

Solution code:
def ceil(x,y):
    return x//y+(not( not x%y))
n=int(input())
a,b=1,1
for i in range(n):
    t,s = map(int,input().split())
    i = max( ceil(a/t), ceil(b/s) )
    a=t*i;b=s*i
print(a+b)

Submission status: Runtime Error

Solution code:
from math import ceil
# def ceil(x,y):
#   return (x-1)//y+1
N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]
t, a = 1, 1
for T, A in TA:
  rate = max(ceil(t, T), ceil(a, A))
  t = T * rate
  a = A * rate
print(t + a)

Submission status: Runtime Error

Solution code:
from math import ceil
N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]
t, a = 1, 1
for T, A in TA:
  rate = max(ceil(t, T), ceil(a, A))
  t = T * rate
  a = A * rate
print(t + a)

Submission status: Runtime Error

Solution code:
n=int(input())

t=[0]*n
a=[0]*n

for i in range(n):
    t,a=map(int,input().split()) 
  
  
  
for i in range(n-1):
  while (t[i]>t[i+1]) or (a[i]>a[i+1]):
    for k in range(1,100000000000000000000000000000000):
      t[i+1]*=k
      a[i+1]*=k
      
print(a[n]+t[n])

Submission status: Runtime Error

Solution code:
# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dとなるようにc,dに同じ数をかける

import math

N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]

a, b = TA[0]

for idx in range(1,N):
    c, d = TA[idx]
    multi = max(math.ceil(a/c), math.ceil(b/d))
    c *= multi
    d *= multi
    a,b = c,d
    
print(c+d)

Submission status: Runtime Error

Solution code:
5
3 10
48 17
31 199
231 23
3 2

Submission status: Runtime Error

Solution code:
#greedy方法
import fractions
n=int(input())
lists=[]
for x in range(n):
    x,y=map(int,input().split())
    lists.append([x,y])
lists.append([1,1])
a=lists[0][0]
b=lists[0][1]
k=0
cnt=0
while cnt<n:
    k=max(fractions.ceil(a/lists[cnt+1][0]),fractions.ceil(b/lists[cnt+1][1]))
    a=lists[cnt+1][0]*k
    b=lists[cnt+1][1]*k   
    cnt+=1    
print(a+int(a*(min(lists[n-1][0],lists[n-1][1])/max(lists[n-1][0],lists[n-1][1])) ))

Submission status: Runtime Error

Solution code:
n = int(input())
a,b = map(int,input().split())
for i in range(n-1):
    c,d = map(int,input().split())
    if  (c>=a and d>=b):
        a = c
        b = d
    elif not(c>=a and d>=b):
        if a%c != 0:
            e = a//c+1
        elif a%c == 0:
            e = a//c
        if b%d != 0:
            f = b//d+1
        elif b%d == 0:
            f = b//d
        c *= max(e,f)
        d *= max(e,f)
        a = c
        b = d
print(c+d)

Submission status: Runtime Error

Solution code:
n = int(input())
a,b = map(int,input().split())
for i in range(n-1):
    c,d = map(int,input().split())
    if  (c>=a and d>=b):
        a = c
        b = d
    if not(c>=a and d>=b):
        #print(not(c>=a and d>=b))
        #print(c,d)
        k,l = c,d
        m = 1
        while True:
            #print(c,d)
            c += k
            d += l
            if c>=a and d>=b:
                a = c
                b = d
                break
            else:
                m += 1
print(c+d)

Submission status: Runtime Error

Solution code:
N = int(input())
t = 0
a = 0

for _iin range(N):
  rt,ra = map(int,input().split())
  c = max((t-1)//rt+1,(a-1)//ra+1)
  t = rt*c
  a = ra*c
  if a+t == 0:
    t += rt
    a += ra

print(a+t)

Submission status: Runtime Error

Solution code:
N = int(input())
t = 0
a = 0

for _ in range(N):
  rt,ra = map(int,input().split())
  c = max((t-1)//rt+1 (a-1)//ra+1)
  t = rt*c
  a = ra*c
  if a+t == 0:
    t += rt
    a += ra

print(a+t)

Submission status: Runtime Error

Solution code:
x

Submission status: Runtime Error

Solution code:
N = int(input())
T, A = map(int, input().split())
num = T + A
for _ in range(N-1):
  t, a = map(int, input().split())
  while True:
    if num%(t+a) == 0 and (num*t)//(t+a) >= T and (num*a)//(t+a) >= A:
      T = (num*t)//(t+a)
      A = (num*a)//(t+a)
      break
    if num%(t+a) == 0
      num += num
    else:
      num += num%(t+a)
print(num)

Submission status: Runtime Error

Solution code:
num = int(input())
arr = [list(map(int, input().split())) for i in range(num)]

ans = [[arr[0][0], arr[0][1]]
for i in range(num-1):
    ans.append([arr[i+1][0], arr[i+1][1]])
    while ans[i][0] > ans[i+1][0] or ans[i][1] > ans[i+1][1]:
        ans[i+1][0] += arr[i+1][0]
        ans[i+1][1] += arr[i+1][1]
print(ans[num-1][0] + ans[num-1][1])

Submission status: Runtime Error

Solution code:
N = int(input())
num = 1
for _ in range(N):
  x, y = map(int, input().split())
  sum_xy = sum(x, y)
  while True:
    if num%sum_xy == 0:
      break
    else:
      num += num%sum_xy
print(num)

Submission status: Runtime Error

Solution code:
if __name__ =="__main__":
    n = int(input())
    ls = [[int(x) for x in input().split()] for _ in range(n)]

    now_t,now_a = ls[0]

    for i in range(1,n):
        x = max([~-now_t/ls[i][0] +1 ,~-now_a/ls[i][1] +1])
        now_t,now_a = x*ls[i][0],x*ls[i][1]
    print(now_t+now_a)

Submission status: Runtime Error

Solution code:
if __name__ =="__main__":
    n = int(input())
    ls = [[int(x) for x in input().split()] for _ in range(n)]

    now_t,now_a = ls[0]

    for i in range(1,n):
        x = max([~-now_t/ls[i][0]+1 ,~-now_a/ls[i][1]+1])
        now_t,now_a = x*ls[i][0],x*ls[i][1]
    print(now_t+now_a)

Submission status: Runtime Error

Solution code:
from math import gcd

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

Submission status: Runtime Error

Solution code:
from math import gcd
from math import ceil

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

Submission status: Runtime Error

Solution code:
from math import gcd
from math import ceil

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

Submission status: Runtime Error

Solution code:
from math import gcd

rs = 1
for _ in range(int(input())):
  x = sum(map(int, input().split()))
  rs = x * rs / gcd(x, rs)
print(rs)

Submission status: Runtime Error

Solution code:
from collections import deque
def main():
    n = int(input())
    t = []
    a = []
    for i in range(n):
        in_t,in_a = map(int,input().split(' '))
        t.append(in_t)
        a.append(in_a)
    q= deque()
    q.append([t[0],a[0]])

    for i in range(1,n):
        while True:
            tmp_t,tmp_a=q.popleft()
            if tmp_t/tmp_a == t[i]/a[i]:
                q.clear()
                q.append([tmp_t,tmp_a])
                break
            elif tmp_t/tmp_a < t[i]/a[i]:
                q.append([tmp_t+1,tmp_a])
            else:
                q.append([tmp_t,tmp_a+1])
    return tmp_t+tmp_a

if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    # n=max(-(-a//A),-(-t//T))
    n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)

Submission status: Runtime Error

Solution code:
import fractions

N=int(input())
t,a=1,1
for i in range(N):
    T,A=map(int,input().split())
    n=max(fractions.ceil(a/A),fractions.ceil(t/T))
    t,a=n*T,n*A

print(t+a)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ta = [list(map(int,input().split())) for i in range(n)]

cur_t = 1
cur_a = 1


def ceil(a, b):
    return a // b + int(a % b != 0)

for t,a in ta:
    if cur_t > t or cur_a > a:
        rate = ceil(max([cur_t/t,cur_a/a]))
        cur_t = t*rate
        cur_a = a*rate
    else:
        cur_t=t
        cur_a=a
print(cur_t+cur_a)

Submission status: Runtime Error

Solution code:

import math

def read_input():
    n = int(input())

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

    return n, ratios


def get_votes(ex_votes, ratio):
    base = max(math.ceil(ex_votes[0]/ratio[0]), math.ceil(ex_votes[1]/ratio[1]))
    return (base * ratio[0], base * ratio[1])


def submit():
    n, ratios = read_input()

    votes = ratios[1]
    for ratio in ratios[1:]:
        votes = get_votes(votes, ratio)

    print(sum(votes))


if __name__ == '__main__':
    submit()

Submission status: Runtime Error

Solution code:
import math
n = int(input())

pt = [0] * n
pa = [0] * n

for i in range(n):
  t, a = map(int, input().split())
  if i == 0:
    pt[0] = t
    pa[0] = a
  else:
    tmp = math.ceil(max(pt[i-1]/, pa[i-1]/a))
    pt[i]=tmp*t
    pa[i]=tmp*a

print(int(pt[-1] + pa[-1]))

Submission status: Runtime Error

Solution code:
import math
n = int(input())

pt = [0] * n
pa = [0] * n

for i in range(n):
  t, a = map(int, input().split())
  if i == 0:
    pt[0] = t
    pa[0] = a
  else:
    tmp = math.ceil(max(pt[i-1]/t*, pa[i-1]/a))
    pt[i]=tmp*t
    pa[i]=tmp*a

print(int(pt[-1] + pa[-1]))

Submission status: Runtime Error

Solution code:
import math
n = int(input())

pt = [0] * n
pa = [0] * n

for i in range(n):
  t, a = map(int, input().split())
  if i == 0:
    pt[0] = t
    pa[0] = a
  else:
    tmp = math.ceil(max([pt[i-1]/t*1.0, pa[i-1]a*1.0]))
    pt[i]=tmp*t
    pa[i]=tmp*a

print(int(pt[-1] + pa[-1]))

Submission status: Runtime Error

Solution code:
import sys
import math
import bisect
import heapq
import copy
from fractions import gcd
from itertools import permutations, combinations,combinations_with_replacement,product
from collections import defaultdict, Counter, deque

N = int(input())
T, A = [0]*N, [0]*N
for i in range(N):
    T[i], A[i] = map(int, input().split())
a, b = T[0], A[0]
if N == 1:
    print(a+b)
else:
    for x, y in zip(T[1:], A[1:]):
        c = max((a11)//(x+1), (b-1)/(y+1))
        a, b = x*c, y*c
    print(a+b)