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: Time Limit Exceeded

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

n = int(input())
ta = [[0,0] for i in range(n)]
for i in range(n):
    ta[i][0],ta[i][1] = map(int,input().split())

val = ta[-1][0] + ta[-1][1]

ans = 0
for i in range(1,1000000000000):
    cand = val * i
    temp = cand
    flag = True
    win = ""
    temp_ll = float("inf")
    temp_rr = float("inf")
    for j in range(n-1,-1,-1):
        if ta[j][0] < ta[j][1]:
            if win == "left":
                temp -= 1
            win = "right"
        if ta[j][0] > ta[j][1]:
            if win == "right":
                temp -= 1
            win = "left"
        for k in range(temp,0,-1):
            temp_l = (k * ta[j][0]) // (ta[j][0] + ta[j][1])
            temp_r = (k * ta[j][1]) // (ta[j][0] + ta[j][1])
            if k % (ta[j][0] + ta[j][1]) == 0 and temp_l <= temp_ll and temp_r <= temp_rr:
                temp_ll = temp_l
                temp_rr = temp_r
                temp = k
                break
        else:
            flag = False
            break
    if flag == True:
        ans = cand
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
th,ah=1,1
for i in range(n):
    t,a=map(int,input().split())
    while 1:
        if th*a>ah*t:ah+=1
        elif th*a<ah*t:th+=1
        elif th*a==ah*t:break
print(th+ah)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

t_prev,a_prev=map(int,input().split())
for i in range(n-1):
  t,a=map(int,input().split())
  i=1
  t_now=t
  a_now=a
  
  while not (t_prev<=t_now and a_prev<=a_now):
    t_now=t*i
    a_now=a*i
    i+=1
    
  t_prev=t_now
  a_prev=a_now

print(t_prev+a_prev)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t, a = map(int, input().split())
for _ in range(n-1):
    t1, a1 = map(int, input().split())
    t2, a2 = t1, a1
    while not ((t2 >= t) & (a2 >= a)):
        t2 += t1
        a2 += a1
    t = t2
    a = a2
ans = t + a
print(ans)

Submission status: Time Limit Exceeded

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

total_T = _input[0][0]
total_A = _input[0][1]

for t,a in _input[1:]:
    count = 0
    while t*count < total_T or a*count < total_A:
        count += 1
    total_T = t*count
    total_A = a*count

print(total_A+total_T)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans_t, ans_a = map(int,input().split())
for i in range(n-1):
    t, a = map(int,input().split())
    now_t, now_a = t, a
    q = True
    while q:
        if ans_t <= now_t and ans_a <= now_a:
            q = False
            ans_t = now_t
            ans_a = now_a
        else:
            now_t += t
            now_a += a

print(ans_a + ans_t)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a,b=map(int,input().split())
for i in range(n-1):
    e,f=map(int,input().split())
    t=e
    k=f
    while e<a or f<b:
        t+=e
        k+=f
    a=t
    b=k
print(a+b)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() 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)]
mod = 1000000007

#A
"""
a,b = LS()
c = int(a+b)
for i in range(1,1000):
    if i * i == c:
        print("Yes")
        quit()
print("No")
"""

#B
"""
a,b = LI()
if a*b <= 0:
    print("Zero")
else:
    if b < 0:
        if (a-b) %2 == 1:
            print("Positive")
        else:
            print("Negative")
    else:
        print("Positive")
"""

#C
"""
n = II()
s = SR(n)
march = [[] for i in range(5)]
ch = list("MARCH")
for i in s:
    for j in range(5):
        if i[0] == ch[j]:
            march[j].append(i)
ans = 0
for i in range(5):
    for j in range(i):
        for k in range(j):
            if len(march[i])*len(march[j])*len(march[k]) == 0:
                break
            ans += len(march[i])*len(march[j])*len(march[k])
print(ans)
"""

#D
"""
n = II()
d = LIR(n)
q = II()
p = IIR(q)
d.insert(0,[0 for i in range(n+1)])
for i in range(n):
    d[i+1].insert(0,0)
for i in range(n):
    for j in range(n):
        d[i+1][j+1] += d[i+1][j]+d[i][j+1]-d[i][j]
ans = [0 for i in range(n**2+1)]

for a in range(n+1):
    for b in range(n+1):
        for c in range(a):
            for e in range(b):
                ans[(a-c)*(b-e)] = max(ans[(a-c)*(b-e)],d[a][b]-d[c][b]-d[a][e]+d[c][e])

for i in p:
    an = 0
    for a in range(i+1):
        an = max(an, ans[a])
    print(an)
"""
#E

"""
s = list(S())
ans = -1
s.insert(0,0)
d = 0
for i in range(1,len(s)):
    if s[i] != d:
        d = s[i]
        ans += 1
print(ans)
"""

#F
n = II()
x,y = LI()
for _ in range(n-1):
    a,b = LI()
    if a == b:
        x = max(x,y)
        y = x
    else:
        i = min(x//a,y//b)
        while 1:
            if a*i >= x and b*i >= y:break
            i += 1
        x = a*i
        y = b*i
print(x+y)
#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() 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)]
mod = 1000000007

#A
"""
a,b = LS()
c = int(a+b)
for i in range(1,1000):
    if i * i == c:
        print("Yes")
        quit()
print("No")
"""

#B
"""
a,b = LI()
if a*b <= 0:
    print("Zero")
else:
    if b < 0:
        if (a-b) %2 == 1:
            print("Positive")
        else:
            print("Negative")
    else:
        print("Positive")
"""

#C
"""
n = II()
s = SR(n)
march = [[] for i in range(5)]
ch = list("MARCH")
for i in s:
    for j in range(5):
        if i[0] == ch[j]:
            march[j].append(i)
ans = 0
for i in range(5):
    for j in range(i):
        for k in range(j):
            if len(march[i])*len(march[j])*len(march[k]) == 0:
                break
            ans += len(march[i])*len(march[j])*len(march[k])
print(ans)
"""

#D
"""
n = II()
d = LIR(n)
q = II()
p = IIR(q)
d.insert(0,[0 for i in range(n+1)])
for i in range(n):
    d[i+1].insert(0,0)
for i in range(n):
    for j in range(n):
        d[i+1][j+1] += d[i+1][j]+d[i][j+1]-d[i][j]
ans = [0 for i in range(n**2+1)]

for a in range(n+1):
    for b in range(n+1):
        for c in range(a):
            for e in range(b):
                ans[(a-c)*(b-e)] = max(ans[(a-c)*(b-e)],d[a][b]-d[c][b]-d[a][e]+d[c][e])

for i in p:
    an = 0
    for a in range(i+1):
        an = max(an, ans[a])
    print(an)
"""
#E

"""
s = list(S())
ans = -1
s.insert(0,0)
d = 0
for i in range(1,len(s)):
    if s[i] != d:
        d = s[i]
        ans += 1
print(ans)
"""

#F
n = II()
x,y = LI()
for _ in range(n-1):
    a,b = LI()
    if a == b:
        x = max(x,y)
        y = x
    else:
        i = 0
        while 1:
            if a*i >= x and b*i >= y:break
            i += 1
        x += a*i-x
        y += b*i-y
print(x+y)
#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
t = []
a = []
for _ in range(n):
    line = input().split(" ")
    t.append(int(line[0]))
    a.append(int(line[1]))

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

for i in range(1,n):
    c = 1
    tt = t[i]
    aa = a[i]
    while T>tt or A>aa:
        c += 1
        tt = t[i]*c
        aa = a[i]*c
    T = tt
    A = aa

print(T+A)

Submission status: Time Limit Exceeded

Solution code:
n = input()

v = [[0, 0] for i in range(n)]
for i in range(n):
	v[i] = map(int, raw_input().split(' '))

a, b = 1, 1

for i in range(n):
	while a * v[i][1] != b * v[i][0]:
		if a * v[i][1] < b * v[i][0]:
			a += 1
		else:
			b += 1

print a + b

Submission status: Time Limit Exceeded

Solution code:
# coding : utf-8
n=int(input())
p=1 #a/b
x,y=1,1
for i in range(n):
    a,b=map(int,input().split())
    while p != a/b:
        if p < a/b:
            x+=1
        else:
            y+=1
        p=x/y
print(x+y)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ratio = []
for i in range(N):
  ratio.append([int(j) for j in input().split(" ")])
               
vote = ratio[0]

for i in range(len(ratio)-1):
  if ratio[i+1][0] >= vote[0] and ratio[i+1][1] >= vote[1]:
    vote = ratio[i+1]
  
  else:
    a0 = 0
    b0 = 0
    if ratio[i+1][0] < vote[0]:
      seed = ratio[i+1][0]
      base = ratio[i+1][0]
      while(True):
        seed += base
        
        if seed >= vote[0]:
          break
      a0 = seed
      a1 = int(seed * ratio[i+1][1]/ratio[i+1][0])
      la = [a0,a1] 
    
    if ratio[i+1][1] < vote[1]:
      seed = ratio[i+1][1]
      base = ratio[i+1][1]
      while(True):
        seed += base
        if seed >= vote[1]:
          break
      b1 = seed
      b0 = int(seed * ratio[i+1][0]/ratio[i+1][1])
      lb = [b0,b1]
    if a0 > b0:
      vote = [la[0],la[1]]
    else:
      vote = [lb[0],lb[1]]
    
print(sum(vote))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
ans = 2
tp, ap = 0, 0
for i in range(N):#ans以上での比からの最小値でans更新,
    #A+Tのn倍、ただしn>=ans/(t+a)
    t, a = map(int, input().split())
    k = 1
    while True:
        if t*k>=tp and a*k>=ap:
            t, a = t*k, a*k
            break
        k += 1
    c = math.ceil(ans/(t+a))
    while True:#ansが前回のans以上になるようにする
        if (t+a)*c >= ans:
            ans = (t+a)*c
            break
        c += 1
    tp, ap = t*c, a*c
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ans=0
prea=0
pret=0
for i in range(n):
    
    i=0
    t,a=map(int,input().split())
    while 1:
        
        i+=1
        if ans<=(a+t)*i and a*i>=prea and t*i>=pret:
            ans=(a+t)*i
            prea,pret=a*i,t*i
            break
print(ans)

Submission status: Time Limit Exceeded

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


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


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


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

Submission status: Time Limit Exceeded

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

    tak = aok = 0
    for i in range(votes):
        takTemp,  aokTemp = ratio[i][0], ratio[i][1]

        while tak > takTemp or aok > aokTemp:
            takTemp += ratio[i][0]
            aokTemp += ratio[i][1]

        tak, aok = takTemp, aokTemp

        #print("turn:" + str(i))
        #print("votes:" + str(ratio[i][0]) + ":" + str(ratio[i][1]) )
    print(tak + aok)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

N=int(raw_input())

a_num = 1
b_num = 1

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

        base_n = min(math.floor(a_num / ratio_a), math.floor(b_num / ratio_b))

        while a_num > ratio_a * base_n or b_num > ratio_b * base_n:
                base_n += 1

        a_num = ratio_a * base_n
        b_num = ratio_b * base_n

print int(a_num + b_num)

Submission status: Time Limit Exceeded

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

N=int(raw_input())

a_num = 0
b_num = 0

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

        # 初期化
        if a_num == 0 or b_num == 0:
                a_num = ratio_a
                b_num = ratio_b
                continue

        # a:b = c:d
        # a/b == c/d などと分数で比較してしまうと0近似で値がなくなってしまうおそれがあるので
        # ad == bc の掛け算で検討する

        while ratio_a * b_num != ratio_b * a_num:
                if ratio_a * b_num < ratio_b * a_num:
                        b_num += 1
                if ratio_a * b_num > ratio_b * a_num:
                        a_num += 1

print a_num + b_num

Submission status: Time Limit Exceeded

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

def aa(a,t,na,nt):
    c = 1
    while not(a<=na*c and t<=nt*c):
        c += 1
    return (na*c,nt*c)
t = T[0]
a = A[0]
for i in range(N):
    a,t = aa(a,t,A[i],T[i])
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        tmp1=ta[i][0]
        tmp2=ta[i][1]
        if ta[i-1][0]>ta[i][0]:
            a=ta[i-1][0]/ta[i][0]
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        if ta[i-1][1]>ta[i][1]:
            a=ta[i-1][1]/ta[i][1]
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        ta[i][0]=tmp1
        ta[i][1]=tmp2
    print(ta[n-1][0]+ta[n-1][1])
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        tmp1=ta[i][0]
        tmp2=ta[i][1]
        if ta[i-1][0]>ta[i][0]:
            a=2
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        if ta[i-1][1]>ta[i][1]:
            a=2
            while 1:
                tmp1=ta[i][0]*a
                tmp2=ta[i][1]*a
                if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                    break
                a+=1
        ta[i][0]=tmp1
        ta[i][1]=tmp2
    print(ta[n-1][0]+ta[n-1][1])
main()

Submission status: Time Limit Exceeded

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(raw_input())
ta=[map(int,raw_input().split()) for _ in xrange(n)]
for i in xrange(1,n):
    tmp1=ta[i][0]
    tmp2=ta[i][1]
    if ta[i-1][0]>ta[i][0]:
        a=2
        while 1:
            tmp1=ta[i][0]*a
            tmp2=ta[i][1]*a
            if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                break
            a+=1
    if ta[i-1][1]>ta[i][1]:
        a=2
        while 1:
            tmp1=ta[i][0]*a
            tmp2=ta[i][1]*a
            if ta[i-1][0]<=tmp1 and ta[i-1][1]<=tmp2:
                break
            a+=1
    ta[i][0]=tmp1
    ta[i][1]=tmp2
print(ta[n-1][0]+ta[n-1][1])

Submission status: Time Limit Exceeded

Solution code:
N = input()
t, a = map(int, raw_input().split())
for i in xrange(N-1):
    new_t, new_a = map(int, raw_input().split())
    dt, da = new_t, new_a
    while new_t < t or new_a < a:
        new_t += dt
        new_a += da
    t, a = new_t, new_a
print t+a

Submission status: Accepted

Solution code:
N = int(input())

ans = 1
minT, minA = 1, 1
for _ in range(N):
    T, A = map(int, input().split())
    fT, fA = (minT-1)//T+1, (minA-1)//A+1
    f = max(fT, fA)
    minT, minA = T*f, A*f
print(minT+minA)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = 1
    t = 1
    for _ in range(N):
        T, A = map(int, input().split())
        if t <= T and a <= A:
            t = T
            a = A
        elif t <= T and a > A:
            tmp = a // A
            if a % A != 0:
                tmp += 1
            t = T * tmp
            a = A * tmp
        elif t > T and a <= A:
            tmp = t // T
            if t % T != 0:
                tmp += 1
            t = T * tmp
            a = A * tmp
        else:
            tmp_A = a // A
            if a % A != 0:
                tmp_A += 1
            tmp_T = t // T
            if t % T != 0:
                tmp_T += 1
            tmp = max(tmp_A, tmp_T)
            t = T * tmp
            a = A * tmp
    print(a + t)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from decimal import Decimal
import math

N = int(input())

T, A = map(Decimal, input().split())

for i in range(1, N):
    t, a = map(Decimal, input().split())
    td = math.ceil(T / t)
    ad = math.ceil(A / a)

    if td < ad:
        T = t * ad
        A = a * ad
    else:
        T = t * td
        A = a * td

print(T + A)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())

t_cunt = a_cunt = 1

for _ in range(N):
    T,A = map(int,input().split())
    if T < t_cunt or A < a_cunt:
        nt = t_cunt//T + 1 if t_cunt%T else t_cunt//T
        na = a_cunt//A + 1 if a_cunt%A else a_cunt//A
        n = max(nt, na)
        t_cunt = n*T
        a_cunt = n*A
    else:
        t_cunt = T
        a_cunt = A
    #print(t_cunt, a_cunt)
print(t_cunt+a_cunt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
T,A = 1,1
for _ in range(N):
    t,a = map(int,input().split())
    k1 = T//t
    if T%t>0:
        k1 += 1
    k2 = A//a
    if A%a>0:
        k2 += 1
    k = max(k1,k2)
    T = k*t
    A = k*a
print(T+A)

Submission status: Accepted

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

A, B = 1, 1
for t, a in TA:
    n = max((A-1)//t+1, (B-1)//a+1)
    A = n*t
    B = n*a

print(A+B)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
T,A = MI()
for _ in range(N-1):
    t,a = MI()
    x = (T+t-1)//t
    y = (A+a-1)//a
    if x >= y:
        T,A = t*x,a*x
    else:
        T,A = t*y,a*y

print(T+A)

Submission status: Accepted

Solution code:
import sys

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

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

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

    rate = max((t1 - 1) // t2, (a1 - 1) // a2) + 1
    rates[i+1] = (t2 * rate, a2 * rate)

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
T,A = MI()
for _ in range(N-1):
    t,a = MI()
    x = (T+t-1)//t
    y = (A+a-1)//a
    if x >= y:
        T,A = t*x,a*x
    else:
        T,A = t*y,a*y

print(T+A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
ans = 1
prea = 1; preb = 1
for i in range(N):
  a,b = map(int,input().split())
  MIN = max((prea+a-1)//a,(preb+b-1)//b)
  #print(MIN)
  ans = MIN*(a+b)
  prea = a*MIN; preb = b*MIN
  #print(MIN,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A, B = 0, 0

for i in range(N):
    x, y = map(int, input().split())
    if i == 0:
        A = x
        B = y
        continue
    tmpa = (A - 1) // x + 1
    tmpb = (B - 1) // y + 1
    tmp = max(1, tmpa, tmpb)
    x *= tmp
    y *= tmp
    A = x
    B = y

print(A + B)

Submission status: Accepted

Solution code:
n=int(input())
a,b=1,1
from math import ceil
from decimal import Decimal as D
from fractions import Fraction as F
# ans=0
for i in range(n):
    x,y=map(int,input().split())
    base= max(ceil(F(b,y)),ceil(F(a,x)))
    a= base*x ; b=base*y 
    # print(a,b)
print(a+b)

Submission status: Accepted

Solution code:
n=int(input())
a,b=1,1
from math import ceil
# ans=0
for i in range(n):
    x,y=map(int,input().split())
    base= max((b//y if b%y==0 else b//y+1),(a//x if a%x==0 else a//x+1))
    a= base*x ; b=base*y 
    # print(a,b)
print(a+b)

Submission status: Accepted

Solution code:
n=int(input())
from math import gcd
a,b=map(int,input().split())
temp=a+b
for i in range(1,n):
    c,d=map(int,input().split())
    j=c+d
    
    x=max(a-c,0)//c
    if max(a-c,0)%c!=0:
        x+=1
    y=max(b-d,0)//d
    if max(b-d,0)%d!=0:
        y+=1
    z=max(temp-j,0)//j
    if max(temp-j,0)%j!=0:
        z+=1
    l=[x,y,z]
    temp=max(l)*j+j
    a=max(l)*c+c
    b=max(l)*d+d
        
print(temp)

Submission status: Accepted

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

Tnow=T[0]
Anow=A[0]


for i in range(1,N):
    t=T[i]
    a=A[i]
    t1=(Tnow+t-1)//t*t
    a1=t1//t*a
    a2=(Anow+a-1)//a*a
    t2=a2//a*t
    if a1<Anow:
        Tnow=t2
        Anow=a2
    elif t2<Tnow:
        Tnow=t1
        Anow=a1
    elif t1+a1<=t2+a2:
        Tnow=t1
        Anow=a1
    else:
        Tnow=t2
        Anow=a2
print(Tnow+Anow)

Submission status: Accepted

Solution code:
def Expand_Euclid(a,b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1

    return x0,y0
#================================================
N=int(input())
p=q=1
for _ in range(N):
    T,A=map(int,input().split())
    d=T*q-A*p

    alpha,beta=Expand_Euclid(A,T)
    beta=-beta

    x=(-d*alpha+(T-1))//T
    y=(-d*beta+(A-1))//A
    K=max(x,y)

    p+=T*K+d*alpha
    q+=A*K+d*beta
print(p+q)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N = NI()
    TA = [NLI() for _ in range(N)]
    nt, na = 0, 0
    for t, a in TA:
        if t >= nt and a >= na:
            nt = t
            na = a
        elif t >= nt and a < na:
            k = na // a if na % a == 0 else na // a + 1
            nt = k*t
            na = k*a
        elif t < nt and a >= na:
            k = nt // t if nt % t == 0 else nt // t + 1
            nt = k*t
            na = k*a
        else:
            kt = nt // t if nt % t == 0 else nt // t + 1
            ka = na // a if na % a == 0 else na // a + 1
            k = max(kt, ka)
            nt = k * t
            na = k * a
    print(nt+na)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===
# 最小公倍数
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    n = ni()
    t, a = 1, 1

    for _ in range(n):
        ti, ai = ns()

        # if ti == ai:
        #     t = max(t, a)
        #     a = max(t, a)
        #     continue

        x = t // ti
        x += 1 if t % ti else 0
        y = a//ai
        y += 1 if a % ai else 0

        nxt = max(x, y)

        t, a = ti * nxt, ai * nxt

    print(t + a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = 1
B = 1
for _ in range(N):
    a, b = map(int, input().split())
    if a == b:
        A = max(A, B)
        B = max(A, B)
    else:
        if A%a == 0:
            aa = A//a
        else:
            aa = A//a + 1
        if B%b == 0:
            bb = B//b
        else:
            bb = B//b + 1
        tmp = max(aa, bb)
        A = tmp*a
        B = tmp*b

print(A+B)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    TA = [LI() for _ in range(N)]

    t, a = TA[0]
    for i in range(1, N):
        T, A = TA[i]
        # t/T>a/A
        if t * A > a * T:
            rate = (t - 1) // T + 1
            t = T * rate
            a = A * rate
        else:
            rate = (a - 1) // A + 1
            t = T * rate
            a = A * rate

    print(t + a)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    TA = [LI() for _ in range(N)]

    t, a = TA[0]
    for i in range(1, N):
        T, A = TA[i]
        # t/T>a/A
        if t * A > a * T:
            t = T * ((t - 1) // T + 1)
            a = A * ((t - 1) // T + 1)
        else:
            t = T * ((a - 1) // A + 1)
            a = A * ((a - 1) // A + 1)

    print(t + a)

if __name__ == '__main__':
    resolve()

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())
  ma=max(t, a)
  if ti==1 and ai ==1:
    t=ma
    a=ma
  else:
    temp=[0]*7
    temp[1] = t%ti
    if temp[1]!=0:
      temp[1] = ti-temp[1]
    temp[2] = t+temp[1]       #takahashiをt1で割れる最小に
    temp[3] = (temp[2]//ti)*ai #その時のaoki
    
    temp[4] = a%ai
    if temp[4] != 0:
      temp[4] = ai-temp[4]
    temp[5] = a+temp[4]
    temp[6] = (temp[5]//ai)*ti
    #print(temp[1:])
    if temp[3]-a<0 and temp[4]+temp[6]-t>=0:
      a=temp[5]
      t=temp[6]
    elif temp[1]+temp[3]-a>=0 and temp[6]-t<0:
      a=temp[3]
      t=temp[2]
    elif temp[1]+temp[3]-a<temp[4]+temp[6]-t:
      a=temp[3]
      t=temp[2]
    else:
      a=temp[5]
      t=temp[6]
  #print("t "+str(t)+" a "+str(a))
#print(" ")
print(int(a+t))

Submission status: Accepted

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

N = int(input())
nt, na = map(int, input().split())

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

print(nt+na)

Submission status: Accepted

Solution code:
n = int(input())

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

x = ab[0][0]
y = ab[0][1]
j = 1
flg = True
for i in range(1,n):
    xx = ab[i][0]
    yy = ab[i][1]
    j = max(x//xx,y//yy)
    while flg:
        if x> j*xx or y > j*yy:
            j +=1
        else:
            x = xx *j
            y = yy *j
            break

print(x+y)