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())
p=[]
for i in range(n):
  p.append(list(map(int,input().split())))

v=[1,1]
for i in p:
  r=max((v[0]-1)//i[0],(v[1]-1)//i[1])+1
  v=[i[0]*r,i[1]*r]

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

Submission status: Accepted

Solution code:
import math
n=int(input())
a,b=map(int,input().split())
for _ in range(n-1):
    c,d=map(int,input().split())
    l,r,ans=1,10**18,-1
    while(l<=r):
        m=(l+r)//2
        if(m*c>=a and m*d>=b):
            ans=m
            r=m-1
        else:
            l=m+1
    a=ans*c
    b=ans*d
print(a+b)

Submission status: Accepted

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

a, b = 1, 1

for i in range(n):
    ra, rb = ratios[i]
    m = max(-(-a // ra), -(-b // rb))
    a, b = ra * m, rb * m

print(a + b)

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())
  x = max((t - 1) // T + 1, (a - 1) // A + 1)
  t = T * x
  a = A * x
print(t + a)

Submission status: Accepted

Solution code:
N, *TA = [int(_) for _ in open(0).read().split()]
x, y = TA[:2]
for t, a in zip(TA[2::2], TA[3::2]):
    m = 1 + max((x - 1) // t, (y - 1) // a)
    x = m * t
    y = m * a
print(x + y)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
t,a = map(int, input().split())
import math
for i in range(n-1):
    tt,aa = map(int, input().split())
    if t<=tt and a<=aa:
        t,a = tt,aa
    else:
        t1,a1 = tt*(t//tt + int(t%tt!=0)), aa*(t//tt + int(t%tt!=0))
        t2,a2 = tt*(a//aa + int(a%aa!=0)), aa*(a//aa + int(a%aa!=0))
#         print(t1,a1, t2,a2)
        if (t1<t2 and t1>=t and a1>=a) or (t2<t or a2<a):
            t,a = t1,a1
        else:
            t,a = t2,a2
ans = t+a
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

t, a = map(int, input().split())
taka = t
aoki = a
t_a = t / a
for _ in range(n - 1):
    t, a = map(int, input().split())
    if t_a == t / a:
        continue
    elif t_a < t / a:
        tmp = ((aoki - 1) // a + 1)
        aoki = tmp * a
        taka = tmp * t
    else:
        tmp = ((taka - 1) // t + 1)
        aoki = tmp * a
        taka = tmp * t
    t_a = t / a
print(taka + aoki)

Submission status: Accepted

Solution code:
n=int(input())
ta=[]
for i in range(n):
    ta.append(list(map(int,input().split())))
#print(ta)
for i in range(n-1):
    if ta[i+1][0]<ta[i][0] or ta[i+1][1]<ta[i][1]:
        k=max(((ta[i][0]-1)//ta[i+1][0]+1), ((ta[i][1]-1)//ta[i+1][1]+1))
        ta[i+1][0]*=k
        ta[i+1][1]*=k
#print(ta)
print(ta[-1][0]+ta[-1][1])

Submission status: Accepted

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

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ta = [list(map(int, input().split())) for _ in range(n)]
    ans = sum(ta[0])
    for i in range(1, n):
        si1 = sum(ta[i - 1])
        si = sum(ta[i])
        cand1 = (ans * ta[i - 1][0] // si1) // ta[i][0] if (ans * ta[i - 1][0] // si1) % ta[i][0] == 0 else (ans * ta[i - 1][0] // si1) // ta[i][0] + 1
        cand2 = (ans * ta[i - 1][1] // si1) // ta[i][1] if (ans * ta[i - 1][1] // si1) % ta[i][1] == 0 else (ans * ta[i - 1][1] // si1) // ta[i][1] + 1
        ans = si * max([cand1, cand2])
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
n=int(input())
t1, a1=map(int, input().split())
t_now=t1
a_now=a1
for _ in range(n-1):
    t, a=map(int, input().split())
    if t==a:
        t_now=max(t_now, a_now)
        a_now=t_now
    else:
        t_tmp=((t_now-1)//t+1)*t
        a_tmp=((a_now-1)//a+1)*a
        t_now=max(t_tmp//t, a_tmp//a)*t
        a_now=max(t_tmp//t, a_tmp//a)*a
print(t_now+a_now)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    TA = in_nl2(N)

    t_score, a_score = 1, 1
    for i in range(N):

        t, a = TA[i]

        if t == a:
            t_score = max(t_score, a_score)
            a_score = t_score
        else:
            t_s = -(-t_score // t) * t
            a_s = (t_s // t) * a
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s
                continue

            a_s = -(-a_score // a) * a
            t_s = (a_s // a) * t
            if t_s >= t_score and a_s >= a_score:
                t_score = t_s
                a_score = a_s

    print(t_score + a_score)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from decimal import Decimal

n = int(input())
cura,curb = 1,1

for i in range(n):
    t,a = map(int,input().split())
    
    xa,xb = Decimal(cura)/Decimal(t),Decimal(curb)/Decimal(a)
    x = math.ceil(max(xa,xb))
    
    cura,curb = t*x,a*x
    
print(cura+curb)

Submission status: Accepted

Solution code:
def ceil(X, Y):  # 天井関数 ceil(X/Y) Y>1
    return (X + Y - 1) // Y


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

t, a = 1, 1
for ti, ai in ta:
    tmp = max(ceil(t, ti), ceil(a, ai))
    t, a = ti * tmp, ai * tmp
print(t + a)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x,y = 1,1
    for _ in range(n):
        t,a = map(int,input().split())
        z = -1*min(-x//t,-y//a)
        x = z*t
        y = z*a
        # print(x,y)
    print(x+y)

main()

Submission status: Accepted

Solution code:
import math

N = int(input())

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

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()
	x,y=1,1

	for _ in range(n):
		a,b=MI()
		k=max((x-1)//a,(y-1)//b)+1
		#print(k,x,y)
		x,y=k*a,k*b

	print(x+y)



if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

import math

N = int(readline())
T,A = map(int,readline().split())

def update(T,A,t,a):
    T1 = (T+t-1)//t*t
    A1 = T1//t*a
    A2 = (A+a-1)//a*a
    T2 = A2//a*t
    return max(T1,T2),max(A1,A2)

for i in range(N-1):
    t,a = map(int,readline().split())
    T,A = update(T,A,t,a)
print(T+A)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
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
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()
x,y=MI()
def nex(a,b,c,d):
    u=max(-(-a//c),-(-b//d))
    return [u*c,u*d]

for i in range(n-1):
    a,b=MI()
    x,y=nex(x,y,a,b)
print(x+y)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc062/tasks/arc062_a
# C - AtCoDeerくんと選挙速報

from math import ceil
from decimal import Decimal

N=int(input())
T=[0]*N
A=[0]*N
p=1
q=1
for i in range(N):
    T[i],A[i]=map(int,input().split())
   
    s = ceil(p/T[i])
    t = ceil(q/A[i])
    r = max(s,t)
    p = Decimal(T[i]*r)
    q = Decimal(A[i]*r) 
    #print(p,q)
    
print(p+q)

Submission status: Accepted

Solution code:
n = int(input())
t,a = map(int,input().split())
nowt = t
nowa = a
for i in range(n-1):
    t , a = map(int,input().split())
    kou = max(nowt//t,nowa//a)
    while True:
        if t*kou >= nowt and a*kou >= nowa:
            break
        else:
            kou += 1
    nowt = t*kou
    nowa = a*kou
print(nowt+nowa)

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 main():
    n = int(input())
    a, b = 1, 1
    ceil = lambda x, y: -(-x // y)
    for _ in range(n):
        c, d = list(map(int, input().split()))
        r = max(ceil(a, c), ceil(b, d))
        a = c * r
        b = d * r
    print(a + b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
na,nt = 1,1
for i in range(n):
    a,t = map(int, input().split())
    ra = (na-1)//a + 1        
    rt = (nt-1)//t + 1
    r = max(ra,rt)        
    na = a*r
    nt = t*r
    # print("t:a",t,a,"r",ra,rt,"n",na,nt)

# print(na,nt)
print(na+nt)

Submission status: Accepted

Solution code:
def ceil(a, b):
	return -(-a//b)

n = int(input())
chokudai, aoki = 0, 0
for i in range(n):
	t, a = map(int,input().split())
	if i == 0:
		chokudai, aoki = t, a
		continue
	bairitsu = max(ceil(chokudai, t), ceil(aoki, a))
	t *= bairitsu
	a *= bairitsu
	#print(t, a)
	chokudai, aoki = t, a
print(chokudai + aoki)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,*ta = map(int, read().split())


v=w=1
mp = iter(ta)
for t,a in zip(mp,mp):
    x = max((v+t-1)//t,(w+a-1)//a)
    v = t*x
    w = a*x
    #print(v,w)
    
print(v+w)

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())
    num1=-1*(T//-t)
    num2=-1*(A//-a)
    T=t*max(num1,num2)
    A=a*max(num1,num2)
print(T+A)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = max((p + x - 1) // x, (q + y - 1) // y)
        p = x * k
        q = y * k
    return p + q


print(solve())

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N = ini()


def solve():
    p = q = 1
    for i in range(N):
        x, y = inm()
        k = max(p // x, q // y, 1)
        while True:
            if x * k >= p and y * k >= q:
                p = x * k
                q = y * k
                break
            k += 1
    return p + q


print(solve())

Submission status: Accepted

Solution code:
n = int(input())


def check(i):
    return T <= t*i and A <= a*i


T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    L = 1
    R = 10**18
    flag = 0
    while True:
        M = (L+R)//2
        if check(M):
            R = M
        else:
            L = M
        if flag:
            break
        if L == R-1:
            flag = 1
    T = t*R
    A = a*R


print(T+A)

Submission status: Accepted

Solution code:
n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    x = max(-(-T//t), -(-A//a))
    T = t*x
    A = a*x

print(T+A)

Submission status: Accepted

Solution code:
n = int(input())

T = A = 1
for _ in range(n):
    t, a = map(int, input().split())
    total = T+A
    x = -(-total//(a+t))
    x = max(x, -(-T//t))
    x = max(x, -(-A//a))
    T = t*x
    A = a*x

print(T+A)

Submission status: Accepted

Solution code:
n = int(input())
TA = [tuple(map(int, input().split())) for _ in range(n)]
s, a = 1, 1
for d, f in TA:
    k = max(-(-a//d), -(-s//f))
    s, a = f*k, d*k
print(s+a)

Submission status: Accepted

Solution code:
n=int(input())
a,b=map(int,input().split())
for i in range(n-1):
  x,y=map(int,input().split())
  if x*b>y*a:
    if b%y!=0:
      b+=y-(b%y)
    r=b//y
    a=x*r
  else:
    if a%x!=0:
      a+=x-(a%x)
    r=a//x
    b=y*r
print(a+b)

Submission status: Accepted

Solution code:
from math import ceil

N = int(input())
T = []
A = []

for _ in range(N):
    t, a = list(map(int, input().split()))
    T.append(t)
    A.append(a)

t_num = T[0]
a_num = A[0]
for i in range(1, N):
    tn = (t_num + T[i] - 1) // T[i]
    an = (a_num + A[i] - 1) // A[i]
    n = max(tn, an)
    t_num = T[i] * n
    a_num = A[i] * n

print(t_num + a_num)

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')


def main():
	n=II()
	a=1
	b=1

	for n in range(n):
		x,y=MI()
		if a<=x and b<=y:
			a,b=x,y
		elif a>x and b>y:
			t=max((a-1)//x,(b-1)//y)+1
			a,b=t*x,t*y
		elif a>x:
			t=(a-1)//x+1
			a,b=t*x,t*y
		else:
			t=(b-1)//y+1
			a,b=t*x,t*y

	print(a+b)





















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n=int(input())
a,s=map(int,input().split())
for i in range(n-1):
    d,f=map(int,input().split())
    k=max(-(-a//d),-(-s//f))
    a=d*k;s=f*k

print(a+s)

Submission status: Accepted

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

L = [[0]*2 for i in range(N)]

L[0][0] = TA[0][0]
L[0][1] = TA[0][1]

for i in range(1,N):
    T = TA[i][0]
    A = TA[i][1]
    Tm = L[i-1][0]
    Am = L[i-1][1]

    Tamari = Tm%T
    if Tamari==0:
        Tn = Tm
    else:
        Tn = Tm + (T-Tamari)

    Aamari = Am%A
    if Aamari==0:
        An = Am
    else:
        An = Am + (A-Aamari)

    if T<A:
        L[i][0],L[i][1] = Tn,Tn//T*A
        if L[i][1]<L[i-1][1]:
            L[i][0],L[i][1] = An//A*T,An
    elif T>A:
        L[i][0],L[i][1] = An//A*T,An
        if L[i][0]<L[i-1][0]:
            L[i][0],L[i][1] = Tn,Tn//T*A
    else:
        L[i][0],L[i][1] = max(L[i-1][0],L[i-1][1]),max(L[i-1][0],L[i-1][1])

print(L[-1][0]+L[-1][1])

Submission status: Accepted

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

N = int(readline())
T, A = map(int,readline().split())

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

Submission status: Accepted

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

N = int(readline())
T, A = map(int,readline().split())

for i in range(N - 1):
  t,a = map(int,readline().split())
  # newT % t == 0 , newA % a == 0である
  # newT >= T , newA >= Aである
  
  # T以上の、tの倍数の最小値 = T / tの切り上げ
  minT = ((T + t - 1) // t) * t
  minA = minT * a // t
  if minA >= A:
    T,A = minT,minA
    continue
  minA = ((A + a - 1) // a) * a
  minT = minA * t // a
  T,A = minT,minA
  
print(T + A)

Submission status: Accepted

Solution code:


from fractions import Fraction
import math

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

"""
Ti : Ai = t : a の時、整数xを使って、i回目のそれぞれの得票数を、t * x, a * x と表せる。
なので、一回前のそれぞれの得票数がわかっている場合、xの範囲がわかるので、xが最小になるように更新していく
"""


T = 0
A = 0
for i,(t,a) in enumerate(TA):
    if i == 0:
        T = t
        A = a
    else:
        x = math.ceil(max(Fraction(T, t), Fraction(A, a)))
        T = t * x
        A = a * x


print(T+A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
t,a = map(int,input().split())
mi = [t,a]
for i in range(1,n):
    t,a = map(int,input().split())
    ts = max((mi[0]-1)//t,(mi[1]-1)//a)+1
    mi = [t*ts,a*ts]

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    from math import ceil

    t_cur, a_cur = list(map(int, readline().split()))

    for _ in range(n - 1):
        t, a = list(map(int, readline().split()))
        i_t = (t_cur + t - 1) // t
        i_a = (a_cur + a - 1) // a
        x = max(i_t, i_a)
        t_cur, a_cur = t * x, a * x

    print(t_cur + a_cur)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    A, B = 1, 1
    for i in range(N):
        x, y = TA[i]
        n = max((A + x - 1) // x, (B + y - 1) // y,)
        A = n * x
        B = n * y

    ans = A + B
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import Fraction
import math

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


"""

・Ti, Ai を i回目の二人の得票数の比
・Pti, Pai をi回目の二人の得票数とすると、

Pti : Pai = Ti : Ai なので、　Pti = M * Ti, Pai = M * Ai (M=1,2,3,...)と表せる。

とあらわせる。ここで、
Pti-1 <= Pti
Pai-1 <= Pai
なので、Mは
M >= Pti-1 / Ti
M >= Pai-1 / Ai
の両方を満たすものになり、得票数を最小に保つにはMもなるべく小さくとる
"""
t,a = 0,0
for i in range(N):
    if i == 0:
        t,a = TA[i][0], TA[i][1]

    else:
        M = math.ceil(max(Fraction(t , TA[i][0]), Fraction(a , TA[i][1])))
        t = M * TA[i][0]
        a = M * TA[i][1]


print(t+a)

Submission status: Accepted

Solution code:
l,r=1,1
for _ in range(int(input())):
    k,t=map(int,input().split())
    gen = max((l+k-1)//k,(r+t-1)//t)
    l,r=gen*k,gen*t
print(l+r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline())
lst = [list(map(int, i.split())) for i in sys.stdin.readlines()]
a, b = lst[0]
for i, j in lst[1:]:
  if i >= a and j >= b:
    a, b = i, j
  else:
    tmp1 = (a // i) + (a % i != 0)
    tmp2 = (b // j) + (b % j != 0)
    if i < a and j >= b:
      a, b = tmp1 * i, tmp1 * j
    elif i >= a and j < b:
      a, b = tmp2 * i, tmp2 * j
    else:
      if tmp1 > tmp2:
        a, b = tmp1 * i, tmp1 * j
      else:
        a, b = tmp2 * i, tmp2 * j
print(a + b)

Submission status: Accepted

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

Submission status: Accepted

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((b[i-1][0]-1)//b[i][0],(b[i-1][1]-1)//b[i][1]) + 1
            b[i][0] *= r
            b[i][1] *= r
    print(sum(b[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math

N = int(sys.stdin.readline().strip())

ratios = []
for _ in range(N):
    t, a = map(int, sys.stdin.readline().strip().split())
    ratios.append((t, a))

ans = 0
for i in range(N-1):
    t1, a1 = ratios[i]
    t2, a2 = ratios[i+1]

    # math.ceilが直球だが、精度が悪い？
    # rate = max(math.ceil(t1 / t2), math.ceil(a1 / a2))
    rate = max((t1 - 1) // t2, (a1 - 1) // a2) + 1
    ratios[i+1] = (t2 * rate, a2 * rate)

print(sum(ratios[N-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
info = []
for i in range(n):
    info.append(list(map(int, input().split())))
    

for i in range(n-1):
    ratio = max((info[i][0]-1)//info[i+1][0]+1, (info[i][1]-1)//info[i+1][1]+1)
    info[i+1][0]*=ratio
    info[i+1][1]*=ratio

print(sum(info[-1]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
ta = [list(map(int, readline().split())) for _ in range(n)]
t, a = ta.pop(0)
for tt, aa in ta:
    v = max((t + tt - 1) // tt, (a + aa - 1) // aa)
    t = v * tt
    a = v * aa
print(t + a)

Submission status: Accepted

Solution code:
import math
def  results(a,b):
    return ((a+b-1)//b)
 
n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
    ti,ai=map(int,input().split())
    if ti<=t or ai<=a:
        k=max(results(t,ti),results(a,ai))
        t=k*ti
        a=k*ai
    else:
        t=ti
        a=ai
    #print(t,a)
print(t+a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n=int(input())
t,a=map(int,input().split())
for i in range(1,n):
    ti,ai=map(int,input().split())
    if ti<=t or ai<=a:
        k=max((t+ti-1)//ti,(a+ai-1)//ai)
        t=k*ti
        a=k*ai
    else:
        t=ti
        a=ai
    #print(t,a)
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())
    aa = 0
    bb = 0
    if A % a == 0:
        aa = A // a
    else:
        aa = A // a + 1
    if B % b == 0:
        bb = B // b
    else:
        bb = B // b + 1
    m = max(aa, bb)
    A,B = a * m, b * m
print(A+B)

Submission status: Accepted

Solution code:
n = int(input())
p, q = map(int, input().split())
for i in range(n-1):
  t, a = map(int, input().split())
  key = max([(p-1)//t+1, (q-1)//a+1])
  p = key*t
  q = key*a
print(p+q)

Submission status: Accepted

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

def ceil(a, b):
  return (a + b - 1) // b

def main():
  n = int(input())
  nt, na = 1, 1
  for i in range(n):
    t, a = map(int, input().split())
    r = max([ceil(nt, t), ceil(na, a)])
    nt, na = r*t, r*a
  print(nt + na)

if __name__=='__main__':
  main()

Submission status: Accepted

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

for i in range(n-1):
    ti, ai = map(int,input().split())
    cand = set()
    cand.add( 1 + (t+a-1)//ti+ai )
    cand.add( 1 + (a-1)//ai )
    cand.add( 1 + (t-1)//ti )

    tn,an = 10**18,10**18
    for i in cand:
        tt,at = ti*i, ai*i
        if(t<=tt)&(a<=at):
            tn = min(tn, tt)
            an = min(an, at)
    t,a = tn, an

print(t+a)

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(n-1):
    ti,ai = map(int, input().split( ))
    coef = max((ti+t-1)//ti,(ai+a-1)//ai)
    t,a = ti*coef,ai*coef
    
    
print(t+a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd
import sys
#input = sys.stdin.readline

import copy
"""
from collections import *
N=int(input())
AB=[list(map(int,input().split())) for i in range(N)]
x,y=1,1

for a,b in AB:
    if x<=a and y<=b:
        x=a;y=b

    elif x>a and y>b:
        c=max([x//a+bool(x%a),y//b+bool(y%b)])
        x=a*c
        y=b*c

    elif x>a:
        c=x//a+bool(x%a)
        x=a*c
        y=b*c
    elif y>b:
        c=y//b+bool(y%b)
        x=a*c
        y=b*c
print(sum([x,y]))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

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

n = INT()
ans = [1, 1]
for i in range(n):
    t,a = MAP()
    k = max((ans[0] + t - 1) // t, (ans[1] + a - 1) // a)
    ans[0] = k * t
    ans[1] = k * a
    #print('a', t+a, ans)
print(sum(ans))

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    t1, a1 = map(int, input().split())
    ans = t1 + a1
    for i in range(n - 1):
        t, a = map(int, input().split())
        t1 = (t1 + t - 1) // t * t
        a1 = (a1 + a - 1) // a * a
        if t1 < a1 * t // a:
            t1 = a1 * t // a
        elif a1 < t1 * a // t:
            a1 = t1 * a // t
        ans = t1 + a1
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

taka = 1
aoki = 1

for T,A in TA:
    tmp = max((taka + T - 1) // T, (aoki + A - 1) // A)
    taka = tmp * T
    aoki = tmp * A

print(taka + aoki)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

nx = 1
ny = 1

for _ in range(N):
    x, y = map(int, input().split())
    Xmul = (nx + x - 1) // x
    Ymul = (ny + y - 1) // y
    mul = max(Xmul, Ymul)
    nx = x * mul
    ny = y * mul

ans = nx + ny
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
for i in range(n):
    a,b = inpl()
    if i == 0:
        x = a; y = b
        continue
    if x <= a and y <= b:
        x = a; y = b
        continue
    c = -(-x//a); d = -(-y//b)
    tmp = max(c,d)
    x = a*tmp; y = b*tmp
    # print(x,y)
print(x+y)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def next_mul(x,y):
    if x%y == 0:
        return x
    else:
        return x+y-x%y

N = I()
T,A = LIR(N,2)

t = T[0]
a = A[0]
for i in range(1,N):
    an = next_mul(a,A[i])
    tn = an*T[i]//A[i]
    if tn >= t:
        t = tn
        a = an
    else:
        t = next_mul(t,T[i])
        a = t*A[i]//T[i]
        
print(t+a)