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())
TA = [tuple(map(int, input().split()))for _ in range(N)]
ans = TA[0]
for ta in TA[1:]:
    x = max((ans[0] + ta[0] - 1) // ta[0], (ans[1] + ta[1] - 1) // ta[1])
    ans = (x * ta[0], x * ta[1])
print(sum(ans))

Submission status: Accepted

Solution code:

n = int(input())
now = [1,1]
data = []

for i in range(n):
    data.append(list(map(int, input().split())))
for i in range(n):
    t,a = data[i]
    mul = max((now[0] + t - 1)//t, (now[1] + a - 1) //a)
    now = list(map(lambda x:x*mul, data[i]))
print(sum(now))

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
x=0
y=0
for i in range(n):
    if x<=a[i][0] and y<=a[i][1]:
        x=a[i][0]
        y=a[i][1]
    else:
        v=-(x//-a[i][0])
        w=-(y//-a[i][1])
        u=max(v,w)
        x=u*a[i][0]
        y=u*a[i][1]

print(x+y)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    TA = [[int(x) for x in input().split()] for _ in range(N)]

    now = TA[0]
    for t, a in TA[1:]:
        i = max(now[0] //t , now[1] // a)
        while now[0] > t * i or now[1] > a * i:
            i += 1
        now[0] = t * i
        now[1] = a * i

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
X,Y=1,1
for i in range(N):
  T,A=map(int,input().split())
  k=max((X+T-1)//T,(Y+A-1)//A)
  X,Y=k*T,k*A
print(X+Y)

Submission status: Accepted

Solution code:
n=int(input())
for i in range(n):
  if i==0:
    t,a=map(int,input().split())
  else:
    x,y=map(int,input().split())
    p=(t+x-1)//x
    q=(a+y-1)//y
    r=max(p,q)
    t,a=x*r,y*r
print(t+a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

t, a = 1, 1
for _ in  range(N):
    T, A = map(int, input().split())
    t = (t + (T - 1)) // T * T
    a = (a + (A - 1)) // A * A
    if a < t * A // T:
        a = t * A // T
    else:
        t = a * T // A
print(a + t)

Submission status: Accepted

Solution code:
n = int(input())
ratio_array = [tuple(map(int, input().split())) for _ in range(n)]

t, a = 1, 1

for x, y in ratio_array:
    m = max((t+x-1)//x, (a+y-1)//y)
    t, a = m*x, m*y

print(t + a)

Submission status: Accepted

Solution code:
n = int(input())
ratio_array = [tuple(map(int, input().split())) for _ in range(n)]

votes_numｓ = (1, 1)

for x, y in ratio_array:
    t, a = votes_numｓ
    m = max((t+x-1)//x, (a+y-1)//y)
    votes_numｓ = (m*x, m*y)

print(sum(votes_numｓ))

Submission status: Accepted

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def lcm(a, b):
    n = fractions.gcd(a, b)
    return a * b // n

def main():
    N = I()
    curT, curA = 1, 1
    for i in range(N):
        newT, newA = LI()
        # if newT >= curT and newA >= curA:
        #     curT, curA = newT, newA
        #     continue
        r1 = (curT-1)//newT + 1
        r2 = (curA-1)//newA + 1
        curT = newT * max(r1, r2)
        curA = newA * max(r1, r2)
    print(curT + curA)
main()

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
L = [list(map(int,input().split())) for k in range(N)]
A, T = 1, 1
for k in range(N):
    a, t = L[k][0], L[k][1]
    m = max(A//a,T//t)
    if a*m < A or t*m < T:
        m += 1
    A = a*m
    T = t*m
print(A+T)

Submission status: Accepted

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction
 
N = int(input())
ca, cb = 0, 0
for _ in range(N):
    a, b = map(int, input().split())
    if ca == 0 and cb == 0:
        ca, cb = a, b
    else:
        r = int(math.ceil(max(Fraction(ca, a), Fraction(cb,b))))
        ca, cb = a*r, b*r

print (ca + cb)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
T=1
A=1

for i in range(n):
    t,a=map(int,input().split())
    x=-(-T//t)
    y=-(-A//a)
    bai=max(x,y)
    T=t*bai
    A=a*bai
print(T+A)

Submission status: Accepted

Solution code:
n=int(input())
tans=1
aans=1
for i in range(n):
  t,a = map(int,input().split())
  tt=(tans+t-1)//t
  at=(aans+a-1)//a
  mt=max([tt,at])
  tans=t*mt
  aans=a*mt
print(tans+aans)

Submission status: Accepted

Solution code:
n=int(input())
x,y=map(int,input().split())

import math
for i in range(n-1):
  t,a=map(int,input().split())
  tbai=(x-1)//t+1
  abai=(y-1)//a+1
  bai=max(tbai,abai)
  x=t*bai
  y=a*bai
  #print(x,y)
print(x+y)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
cura, curb = MAP()
for i in range(N-1):
    a, b = MAP()
    # 比をそのままで、現在の票数より大きくする
    res = bisearch_min(0, INF, lambda m: a*m >= cura and b*m >= curb)
    cura, curb = a * res, b * res
ans = cura + curb
print(ans)

Submission status: Accepted

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

nums=TA[0]

def f(points, rate):
  if points[0]%rate[0]>0:
    a=1
  else:
    a=0
  if points[1]%rate[1]>0:
    b=1
  else:
    b=0
    
  tmp=max(points[0]//rate[0]+a, points[1]//rate[1]+b)
  return [rate[0]*tmp, rate[1]*tmp]

for i in range(1, N):
  nums=f(nums, TA[i])
  
print(sum(nums))

Submission status: Accepted

Solution code:
from decimal import *

n = int(input())
T, A = [], []
for _ in range(n):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)

Taka = 0
Aoki = 0

for i in range(n):

    if (T[i] >= Taka) and (A[i] >= Aoki):
        Taka = T[i]
        Aoki = A[i]
    elif T[i] == A[i]:
        Taka = max(Taka, Aoki)
        Aoki = Taka
    else:
        Taka_up = -(-Taka//T[i])
        Aoki_up = -(-Aoki//A[i])
        multi = max(Taka_up, Aoki_up)
        Taka = T[i] * multi
        Aoki = A[i] * multi   

ans = int(Taka + Aoki)
print(ans)

Submission status: Accepted

Solution code:
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: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N)]
    na,nb = X[0][0],X[0][1]
    for i in range(N-1):
        i += 1
        x,y = X[i][0],X[i][1]
        if (x >= na and y >= nb):
            na,nb = x,y
        elif (x < na and y >= nb):
            q = -(-na//x)
            na,nb = x*q,y*q
        elif (x >= na and y < nb):
            q = -(-nb//y)
            na,nb = x*q,y*q
        else:
            use = max(-(-na//x),-(-nb//y))
            na,nb = x*use,y*use
    
    print(na+nb)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

curr_a, curr_b = 0, 0

for v1, v2 in votes:
    a, b = v1, v2
    i = max(curr_a // v1, curr_b // v2)

    while a < curr_a or b < curr_b:
        a = v1 * i
        b = v2 * i
        i += 1

    curr_a, curr_b = a, b

print(curr_a + curr_b)

Submission status: Accepted

Solution code:

n = int(input())
da = [list(map(int,input().split())) for i in range(n)]

now = da[0]
for i in range(1,n):
    co = max((now[0] - 1)// da[i][0], (now[1] - 1)// da[i][1])
    co += 1
    now[0] = da[i][0] * co
    now[1] = da[i][1] * co
print(now[0] + now[1])

Submission status: Accepted

Solution code:
N = int(input())
ansT = 1
ansA = 1
for i in range(N):
    T, A = map(int,input().split())
    if int(ansT / T) > int(ansA / A):
        ansT = T * int((ansT + T - 1) // T)
        ansA = A * int((ansT + T - 1) // T)
    else:
        ansT = T * int((ansA + A - 1) // A)
        ansA = A * int((ansA + A - 1) // A)

print(int(ansT + ansA))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
t = a = 1
for _ in range(N):
    T, A = list(map(int, input().split()))
    # t->cT,  a->cA                                                                                                                                                                                                                  
    # min(c) s.t. cT>=t && cA>=a                                                                                                                                                                                                     
    c = max((t+T-1)//T, (a+A-1)//A)
    t, a = c*T, c*A
print(t+a)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
import sys
input = sys.stdin.readline

N = int(input())

T = []
A = []

for i in range(N):
    temp = list(map(int,input().split()))
    T.append(temp[0])
    A.append(temp[1])

for i in range(1,N):
    if (T[i-1] <= T[i]) & (A[i-1] <= A[i]):
        # print(T[i],A[i])
        continue
    else:
        rT = - ( - T[i-1] // T[i])
        rA = - ( - A[i-1] // A[i])
        temp = max(rT,rA)
        T[i] *= temp
        A[i] *= temp
        # print(T[i],A[i])

res = T[N-1] + A[N-1]

print(res)

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
max_t = 0
max_a = 0
for _ in range(n):
    t, a = map(int, input().split())
    x = max(max_t//t, max_a//a, 1)
    while 1:
        if max_t <= t*x and max_a <= a*x:
            max_t = t * x
            max_a = a * x
            break
        else:
            x += 1
print(max_t + max_a)

Submission status: Accepted

Solution code:
N = int(input())

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

x, y = 1, 1


def ceil(a, b):
    return a // b + (a % b > 0)


for t, a in TA:
    tv = ceil(x, t)
    av = ceil(y, a)
    n = max(tv, av)
    x = n * t
    y = n * a
print(x + y)

Submission status: Accepted

Solution code:
n = int(input())

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

#a,bの最小公倍数
def lcm(a, b):
   return a * b // gcd (a, b)

def ceil(a, b):
  return a // b + (a % b > 0)

import math
ans = (1, 1)
for _ in range(n):
   t,a = map(int,input().split())
   b = max(ceil(ans[0],t), ceil(ans[1],a))
   ans = [b*t, b*a]
print(sum(ans))

Submission status: Accepted

Solution code:
N = int(input())
takahashi = 1
aoki = 1
for _ in range(N):
  t, a = map(int, input().split())
  X = -(-(takahashi + t-1))//t # 切り上げ
  Y = -(-(aoki + a-1))//a      # 切り上げ
  n = max(X, Y)
  takahashi = t*n
  aoki = a*n
  
print(int(takahashi+aoki))

Submission status: Accepted

Solution code:
N = int(input())
T, A = 1, 1
for i in range(N):
    t, a = map(int, input().split())
    # それぞれ一番近い倍数をもとめる
    tt = (T + t - 1) // t
    at = (A + a - 1) // a
    # 大きい方で掛ける
    mt = max([tt, at])
    T = t * mt
    A = a * mt
print(T + A)

Submission status: Accepted

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

tkhs = 1
aoki = 1

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

print(tkhs+aoki)

Submission status: Accepted

Solution code:
n = int(input())
tpred = 1
apred = 1

for i in range(n):
  t, a = map(int, input().split())
  tpred = t*max(-(-tpred//t), -(-apred//a))
  apred = a*max(-(-tpred//t), -(-apred//a))

print(tpred+apred)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
ratios = [[i for i in map(int,input().split())] for j in range(N)]

ans_a = 0
ans_t = 0
ratio = ratios.pop(0)
ans_a = ratio[0]
ans_t = ratio[1]

for ratio in ratios:
  i = max(ans_a // ratio[0], ans_t // ratio[1])
  while True:
    temp_a = ratio[0]*i
    temp_t = ratio[1]*i
    if temp_a >= ans_a and temp_t >= ans_t:
      ans_a = temp_a
      ans_t = temp_t
      break
    i += 1
    
print(ans_a + ans_t)

Submission status: Accepted

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: Accepted

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: Accepted

Solution code:
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: Accepted

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

import math
dp = ta[0]
for i in range(1, n):
    t = ta[i][0]
    a = ta[i][1]

    k1 = dp[0] // t
    if k1 * t != dp[0]:
        k1 += 1
    k2 = dp[1] // a
    if k2 * a != dp[1]:
        k2 += 1
    k = max(k1, k2)

    dp = [k * t, k * a]
print(sum(dp))

Submission status: Accepted

Solution code:
N = int(input())
t, a = 0, 0
for _ in range(N):
    T, A = map(int, input().split())
    c = max((t - 1) // T + 1, (a - 1) // A + 1)
    t = T * c
    a = A * c
    if t + a == 0:
        t += T
        a += A
    # for n in range(10 ** 18):
    #     if t <= n * T and a <= n * A:
    #         t = n * T
    #         a = n * A
    #         print('{0} {1} {2}'.format(n, t, a))
    #         break
print(int(t + a))

Submission status: Accepted

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
    
answer = t+a
print(answer)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
ab = map(int, sys.stdin.read().split())
ab = zip(ab, ab)

def main():
    c_a = c_b = 1
    for a, b in ab:
        t_a = (c_a + a - 1) // a
        t_b = (c_b + b - 1) // b
        t = max(t_a, t_b)
        c_a = a * t
        c_b = b * t
    
    ans = c_a + c_b
    return ans

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

Submission status: Accepted

Solution code:
from sys import stdin

n = int(stdin.readline().rstrip())
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n)]
A,B = li[0][0],li[0][1]
for i in range(1,n):
    a,b = li[i][0],li[i][1]
    bai = max(-(-A//a),-(-B//b))
    A = bai*a
    B = bai*b
print(A+B)

Submission status: Accepted

Solution code:
N = int(input())

# 最初の入力を初期値とする
T, A = map(int, input().split())

# N-1回入力を繰り返す
for i in range(N-1):
    # tとaを入力
    t, a = map(int, input().split())

    # 最小公倍数nは max(⌈A/x⌉, ⌈B/y⌉) で求めることができる
    #マイナスの//は切り上げになる
    n = max(-(-T // t), -(-A // a))
    # 最小公倍数に比率を掛ける
    T = n*t
    A = n*a
    
# 結果の出力
print(T+A)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
x,y = a[0][0],a[0][1]
for i in range(1,n):
  xr=(x+a[i][0]-1)//a[i][0]
  yr=(y+a[i][1]-1)//a[i][1]
  r=max(xr,yr)
  x=r*a[i][0]
  y=r*a[i][1]
print(x+y)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def ceil(a, b):
  return a // b + (a % b > 0)

N = int(input())
T = A = 1
for i in range(N):
  t, a = map(int, input().split())
  m = max(ceil(T, t), ceil(A, a))
  T = t * m
  A = a * m
print(T + A)

Submission status: Accepted

Solution code:
n = int(input())
a, b = [int(x) for x in input().split()]
for _ in range(n - 1):
	c, d = [int(x) for x in input().split()]
	k = max((a - 1) // c + 1, (b - 1) // d + 1)
	a, b = c * k, d * k
print(a + b)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A, B = 1, 1
    for _ in range(N):
        t, a = (int(i) for i in input().split())
        mul = max(-(-A//t), -(-B//a))
        A = t*mul
        B = a*mul
    print(A+B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    TA=LLIN(N)
    C=1
    D=1
    for t,a in TA:
        n = max((C+t-1)//t , (D+a-1)//a)
        # n = (max(int(ceil(C/t)),int(ceil(D/a))))
        C,D = n*t,n*a
    ans = C+D
    print(int(ans))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    TA=LLIN(N)
    C=1
    D=1
    for t,a in TA:
        n = max( -(-C//t), -(-D//a))
        C,D = n*t,n*a
    ans = C+D
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
nt, na = 1, 1
for _ in range(n):
  t, a = map(int, input().split())
  x, y = -(-nt//t), -(-na//a)
  m = max(x, y)
  nt, na = t*m, a*m
print(nt+na)

Submission status: Accepted

Solution code:
N = int(input())
t, a = map(int, input().split())

ans = t + a

for _ in range(N - 1):
    T, A = map(int, input().split())

    n = max(t // T + (1 if t % T else 0), a // A + (1 if a % A else 0))

    ans = (T + A) * n

    t, a = T * n, A * n

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A,B=map(int,input().split())
for i in range(N-1):
  a,b=map(int,input().split())
  if a==b:
    if A<B:
      A=B
    else:
      B=A
    
  else:
    if a/b > A/B:
      # Bに対していく
      if B%b!=0:
        plus=b-(B%b)
        B+=plus
      A=(B*a)//b
    else:
      # Aに足していく
      if A%a!=0:
        plus=a-(A%a)
        A+=plus
      B=(A*b)//a

print(A+B)

Submission status: Accepted

Solution code:
N = int(input())
T = 0
A = 0
for _ in range(N):
    t, a = map(int, input().split())
    i = max(T//t, A//a, 1)
    while T > i*t or A > i*a:
        i += 1
    T = i*t
    A = i*a
    
print(T+A)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    x,y=1,1
    for _ in range(n):
        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)
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
n = int(input())
ls = []
for i in range(n):
    t, a = [int(i) for i in sys.stdin.readline().split()]
    ls.append((t, a))
_min = 1e-10
_min_a = 1
_min_t = 1
res = []
for l in ls:
    t, a = l
    _sum = t + a
    cnt = max(-(-_min_a//a), -(-_min_t//t))
    _min_a = cnt * a
    _min_t = cnt * t
    _min = cnt * _sum
    res.append(_min)
print(res[-1])

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return abs(a)

N = int(input())
s, t = 1, 1
for _ in range(N):
    a, b = map(int, input().split())
    g = gcd(a, b)
    a, b = a//g, b//g
    mi = max(-(-s//a), -(-t//b))
    s, t = a*mi, b*mi
print(s+t)

Submission status: Accepted

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

def UP(V1,V2,R1,R2):
    n=max(-(-V1//R1),-(-V2//R2))
    return(n*R1,n*R2)

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
#    print(up)
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)

Submission status: Accepted

Solution code:
import sys

def read():
	return tuple([int(d) for d in sys.stdin.readline().rstrip().split(" ")])

N, = read()

cur_T = 1
cur_A = 1

for i in range(N):
	T, A = read()

	current = cur_T + cur_A
	sum = T + A

	mult1 = (current + sum - 1) // sum
	mult2 = (cur_T + T - 1) // T
	mult3 = (cur_A + A - 1) // A

	mult = mult1
	if mult2 > mult: mult = mult2
	if mult3 > mult: mult = mult3

	cur_T = T * mult
	cur_A = A * mult

print(cur_T + cur_A)

Submission status: Accepted

Solution code:
import math
n = int(input())
ta = [list(map(int, input().split())) for i in range(n)]
T,A = 1,1
for t,a in ta:
  mul = max(-(-A//a), -(-T//t))
  T,A = t * mul,a * mul
print(T+A)

Submission status: Accepted

Solution code:
#C
import math
from decimal import *
N = int(input())
TA = [list(map(int,input().split())) for i in range(N)]

t,a = 1,1
for i in range(N):
    ti,ai = TA[i]
    n = Decimal(max(math.ceil(t/ti),math.ceil(a/ai)))
    t = n*ti
    a = n*ai
        
    #print(t,a)
    
print(t+a)

Submission status: Accepted

Solution code:
n=int(input())
b,u=map(int,input().split())
x,c,v=1,1,1
for i in range(n-1):
  a,t=map(int,input().split())
  c=b if b%a==0 else (b//a+1)*a
  v=u if u%t==0 else (u//t+1)*t
  x=max(c//a,v//t)
  b=a*x
  u=t*x
print(b+u)

Submission status: Accepted

Solution code:
import math
n=int(input())
A=B=1
for i in range(n):
    x,y=[int(i) for i in input().split()]
    n=max(-(-A//x),-(-B//y))
    A=n*x
    B=n*y
print(A+B)

Submission status: Accepted

Solution code:
def ceil(a, b):
    return a//b+(1 if a % b else 0)


n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = [int(i) for i in input().split()]
    k = max(ceil(x, t), ceil(y, a))
    x, y = t * k, a * k
print(x+y)

Submission status: Accepted

Solution code:
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
T=ta[0][0]
A=ta[0][1]
for i in range(1,n):
    t,a=ta[i]
    if T%t==0:
        s=T//t
    else:
        s=T//t+1
    if A%a==0:
        b=A//a
    else:
        b=A//a+1
    T=t*max(s,b)
    A=a*max(s,b)
print(T+A)

Submission status: Accepted

Solution code:
n=int(input())
x,y=1,1
for i in range(n):
  a,b=map(int,input().split())
  if x%a==0:
    x1=x//a
  else:
    x1=x//a+1
  if y%b==0:
    y1=y//b
  else:
    y1=y//b+1
  z1=max(x1,y1)
  x,y=a*z1,b*z1
print(x+y)

Submission status: Accepted

Solution code:
from math import ceil

N = int(input())
prv_t, prv_a = 1, 1
for _ in range(N):
  t,a = map(int,input().split())
  x = max(-(-prv_t//t), -(-prv_a//a))
  prv_t, prv_a = t*x, a*x
print(prv_t+prv_a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N = int(input())
t,a = [],[]
for _ in range(N):
	t_tmp, a_tmp = map(int, input().split())
	t.append(t_tmp)
	a.append(a_tmp)

T,A=1,1

for i in range(N):
	n = max(-(-A//a[i]), -(-T//t[i]))
	A = a[i] * n
	T = t[i] * n

print(A+T)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil
from fractions import Fraction

N = int(input())

t, a = 1, 1
for T, A in [tuple(map(int, input().split())) for _ in range(N)]:
    n = max(ceil(Fraction(t, T)), ceil(Fraction(a, A)))
    t, a = n * T, n * A
print(t + a)

Submission status: Accepted

Solution code:
# python3 (3.4.3)
import sys
input = sys.stdin.readline

# main
from math import ceil
from decimal import *
N = int(input())
TA = [list(map(int,input().split())) for _ in range(N)]


t,a = 1,1
for i in range(N):
    n = Decimal(max(ceil(t/TA[i][0]), ceil(a/TA[i][1])))
    t = n*TA[i][0]
    a = n*TA[i][1]

print(t+a)

Submission status: Accepted

Solution code:
def examC():
    N = I()
    cur = [1,1]
    for i in range(N):
        T, A = LI()
        k = max((cur[0]+T-1)//T,(cur[1]+A-1)//A)
        cur[0] = T * k
        cur[1] = A * k
#        print(cur)
    print(sum(cur))



import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

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


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    t_ratio = TA[n][0]
    a_ratio = TA[n][1]
    # coeff = 1
    # while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
    #     coeff += 1
    # ↓
    coeff = max((t_ratio + t_votes - 1) // t_ratio,
                (a_ratio + a_votes - 1) // a_ratio)

    t_votes = coeff * t_ratio
    a_votes = coeff * a_ratio

print(t_votes + a_votes)