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:
N = int(input())
T = []
A = []
for i in range(N):
    s = input().split()
    T.append(int(s[0]))
    A.append(int(s[1]))


tc = T[0]
ac = A[0] 

if N > 1:
    for i in range(1,N):
        while T[i] * ac != A[i] * tc:
            if T[i] * ac  < A[i] * tc:
                ac += 1
            else:
                tc += 1            
                        
ret = tc + ac
print(ret)

Submission status: Time Limit Exceeded

Solution code:
N  = int(raw_input())

ans = []
T, A = [0] * 1000, [0] * 1000

for i in range(N):
    T[i], A[i] = map(int, raw_input().split())

    ans = [T[i], A[i]]

    j = 2

    if i != 0:
        while T[i] < T[i -1] or A[i] < A[i -1]:
            T[i] *= j
            A[i] *= j
            if T[i] < T[i -1] or A[i] < A[i -1]:
                T[i] /= j
                A[i] /= j
            j += 1
        ans = [T[i], A[i]]

print sum(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

n = int(stdin.readline())

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

p_t, p_a = t_votes, a_votes

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

print(t_votes + a_votes)

Submission status: Time Limit Exceeded

Solution code:
N = input()

t = []
a = []


for i in range(N):
    z = raw_input()
    x,y = [int(j) for j in z.split()]
    t.append(x)
    a.append(y)

t_get = 0
a_get = 0

for i in range(N):
    times = 1
    while(True):
        if(t[i]*times >= t_get and a[i]*times >= a_get):
            t_get = t[i]*times
            a_get = a[i]*times
            break
        else:
            times += 1

print t_get + a_get

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
t_before = 0
a_before = 0
for i in xrange(n):
    v =  map(int, raw_input().split())
    tt = v[0]
    aa = v[1]
    while v[0] < t_before or v[1] < a_before:
        v[0] += tt
        v[1] += aa
    t_before = v[0]
    a_before = v[1]
    
print t_before+a_before,

Submission status: Accepted

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

Submission status: Accepted

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

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


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

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

if __name__=="__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

t0, a0 = 1, 1

for i in range(n):
    t1, a1 = map(int, input().split())
    f0 = t0 // t1
    if t0 % t1 != 0:f0 += 1
    f1 = a0 // a1
    if a0 % a1 != 0:f1 += 1
    f = max(f0, f1)
    t0, a0 = t1*f, a1*f

print(t0 + a0)

Submission status: Accepted

Solution code:
n=int(input())
ans_t=1
ans_a=1
for i in range(n):
    t,a=map(int,input().split())
    if t==1:
        k1=ans_t
    else:
    	k1=(ans_t-1)//t+1
    if a==1:
        k2=ans_a
    else:
    	k2=(ans_a-1)//a+1
    k=max(k1,k2)
    ans_t=k*t
    ans_a=k*a
print(ans_t+ans_a)

Submission status: Accepted

Solution code:
n=int(input())

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

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        pre_a, pre_b = a, b
    if pre_a * b < pre_b * a:
        mul = (pre_b + b - 1) // b
        pre_b = mul * b
        pre_a = pre_b * a // b
    else:
        mul = (pre_a + a - 1) // a
        pre_a = mul * a
        pre_b = pre_a * b // a
    # print(i, pre_a, pre_b)
print(pre_a + pre_b)

Submission status: Accepted

Solution code:
n = int(input())
A,B = 0,0
for i in range(n):
    x,y = map(int,input().split())
    t,a = 1,1
    if A > x:
        t = A // x
        if A % x != 0:
            t += 1
    if B > y:
        a = B // y
        if B % y != 0:
            a += 1
    m = max(t,a)
    A = x*m
    B = y*m
print(A+B)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1 for i in range(self.n + 1)]
        self.finv = [1 for i in range(self.n + 1)]
        for i in range(2, self.n+1):
            self.fac[i] = (self.fac[i - 1] * i) % self.mod
            self.finv[i] = (self.finv[i-1] * pow(i, -1, self.mod)) % self.mod

    def comb(self, n, m):
        return self.fac[n] * (self.finv[n-m] * self.finv[m] % self.mod) % self.mod
def iparse():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    ml = 1
    last = [0,0]
    for i in range(n):
        x = iparse()
        # print(len(x))
        l = (last[0] + x[0] - 1) // x[0]
        r = (last[1] + x[1] - 1) // x[1]
        m = max(l, r)
        if m == 0:
            m = 1
        x[0] *= m
        x[1] *= m
        
        last = x
    print(sum(last))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil
from decimal import Decimal, getcontext
getcontext().prec = 100
N = int(input())
TA = [tuple(map(int, input().split())) for _ in range(N)]

T = 1
A = 1
for i in range(N):
    x, y = TA[i]
    n = max(ceil(Decimal(T)/Decimal(x)), ceil(Decimal(A)/Decimal(y)))
    T = n*x
    A = n*y
print(T+A)

Submission status: Accepted

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

t = 0
a = 0
for i in range(N):
    T, A = map(int, input().split())
    if i == 0:
        t += T
        a += A
        continue
    if (T >= t and A >= a):
        t = T
        a = A
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)

        cout_sn = min((sum_t - t) // T, (sum_a - a) // A)
        # while True:
        sum_t -= T * cout_sn
        sum_a -= A * cout_sn
        # if sum_t < t or sum_a < a:
        #     sum_t += T
        #     sum_a += A
        #     break
        t = sum_t
        a = sum_a
        continue

print(t + a)

Submission status: Accepted

Solution code:
import math

n=int(input())
ans=list(map(int,input().split()))
if n==1:
  print(sum(ans))
  
else:
  ans1=[]
  ans1.append(ans)
  for i in range(n-1):
    x,y=map(int,input().split())
    p,q=ans1[-1][0],ans1[-1][1]
    if p%x==0:
      p1=p//x
    else:
      p1=p//x+1
    if q%y==0:
      q1=q//y
    else:
      q1=q//y+1
    pq=max(p1,q1)
    r=[x*pq,y*pq]
    ans1.append(r)
    
  print(sum(ans1[-1]))

Submission status: Accepted

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

T = 1
A = 1
for i in range(N):
    bai = max(-(-T//ls[i][0]),-(-A//ls[i][1]))
    T = bai * ls[i][0]
    A = bai * ls[i][1]
print(T+A)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    t, a = map(int, input().split())
    for _ in range(N - 1):
        nt, na = map(int, input().split())
        if t * na == a * nt: continue
        # ceilで不動小数点誤差が出てWAになるケースは初めて！
        # C++と同じ流儀で繰り上げしないとダメなんだ。。。
        k = max((t + nt - 1) // nt, (a + na - 1) // na)
        t, a = nt * k, na * k

    print(t + a)




if __name__ == "__main__":
    main()

Submission status: Accepted

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

x, y = 1, 1
for t, a in query:
    if t >= x and a >= y:
        x = t
        y = a
    else:
        if t < x and a < y:
            x = t * max((x + t - 1) // t, (y + a - 1) // a)
            y = a * max((x + t - 1) // t, (y + a - 1) // a)
        elif t < x:
            x = t * ((x + t - 1) // t)
            y = a * ((x + t - 1) // t)
        else:
            x = t * ((y + a - 1) // a)
            y = a * ((y + a - 1) // a)
print(x + y)

Submission status: Accepted

Solution code:
N = int(input())
Ratio = [tuple(map(int, input().split())) for _ in range(N)]
from math import ceil
Vote = (1, 1)
for t,a in Ratio:
    p = max((t+Vote[0]-1)//t, (a+Vote[1]-1)//a)
    Vote = (p*t, p*a)
print(sum(Vote))

Submission status: Accepted

Solution code:
import copy
n = int(input())
vote_ls = [[0,0] for _ in range(n)]
for i in range(n):
    a,b = map(int,input().split())
    vote_ls[i] = [a,b]

def check(previous,now):
    ok = True
    for j in [0,1]:
        if previous[j] > now[j]:
            ok = False
    return ok

previous = vote_ls[0]
for i in range(1,n):
    now = copy.copy(vote_ls[i])
    if check(previous,now):
        previous = now
        continue

    time_a = -(-previous[0]//now[0])
    time = float('inf')
    if now[1] * time_a >= previous[1]:
        time = min(time,time_a)
    time_b = -(-previous[1]//now[1])
    if now[0] * time_b >= previous[0]:
        time = min(time,time_b)
    now[0]*=time
    now[1]*=time
    previous = now

print(sum(previous))

Submission status: Accepted

Solution code:
#
# abc046 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
2 3
1 1
3 2"""
        output = """10"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 1
1 1
1 5
1 100"""
        output = """101"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
3 10
48 17
31 199
231 23
3 2"""
        output = """6930"""
        self.assertIO(input, output)


def resolve():
    N = int(input())
    R = [list(map(int, input().split())) for _ in range(N)]

    t = R[0][0]
    a = R[0][1]
    for i in range(1, N):
        n = max((t+R[i][0]-1)//R[i][0], (a+R[i][1]-1)//R[i][1])
        t = n*R[i][0]
        a = n*R[i][1]

    print(t+a)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
for i in range(int(raw_input())):
	n,d = map(int, raw_input().split())
	if i == 0:
		a,b = n,d
	else:
		q = max((a+n-1)/n, (b+d-1)/d)
		a = n*q
		b = d*q



print a+b

Submission status: Accepted

Solution code:
N = int(input())
TNow,ANow = (int(T) for T in input().split())
for TN in range(1,N):
    TNext,ANext = (int(T) for T in input().split())
    Magn = max(TNow//TNext+(TNow%TNext!=0),ANow//ANext+(ANow%ANext!=0))
    TNow,ANow = TNext*Magn,ANext*Magn
print(TNow+ANow)

Submission status: Accepted

Solution code:
n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    if x <= t and y <= a:
        x = t
        y = a
    else:
        if x % t == 0:
            i_x = x // t
        else:
            i_x = x // t + 1

        if y % a == 0:
            i_y = y // a
        else:
            i_y = y // a + 1
        bigger = max(i_x, i_y)
        x = bigger*t
        y = bigger*a
print(x+y)

Submission status: Accepted

Solution code:
n = int(input())
x, y = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    if x <= t and y <= a:
        x = t
        y = a
    elif x <= t and y > a:
        if y % a == 0:
            i = y // a
        else:
            i = y // a + 1
        y = i*a
        x = i*t
    elif x > t and y <= a:
        if x % t == 0:
            i = x // t
        else:
            i = x // t + 1
        x = i*t
        y = i*a
    elif x > t and y > a:
        if x % t == 0:
            i_x = x // t
        else:
            i_x = x // t + 1

        if y % a == 0:
            i_y = y // a
        else:
            i_y = y // a + 1
        bigger = max(i_x, i_y)
        x = bigger*t
        y = bigger*a
print(x+y)

Submission status: Accepted

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

print(vote_t + vote_a)

Submission status: Accepted

Solution code:
n=int(input())
a,b=1,1

for i in range(n):
  x,y=map(int,input().split())
  s=-(-a//x)
  t=-(-b//y)
  a,b=max(s,t)*x,max(s,t)*y

print(a+b)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    T1, A1 = map(int, input().split())
    for _ in range(N-1):
        T2, A2 = map(int, input().split())
        n = max(-(-T1//T2),-(-A1//A2))
        T1,A1 = T2*n,A2*n
    print(T1 + A1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
p,q=1,1

for _ in range(n):
    t,a=map(int,input().split())
    #n=1
    #hile p>n*t or q>n*a:
    #    n+=1
    n=max((p+t-1)//t,(q+a-1)//a)
    p,q=n*t,n*a
    #print(n,p,q)

print(p+q)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
data = []
X = []
for i in range(N):
    T, A = map(int, readline().split())
    data.append((T,A))

T_pre,A_pre = data[0] 
for i in range(1,N):
    T,A = data[i]
    n = max(-(-T_pre//T),-(-A_pre//A))
    T_pre = n*T
    A_pre = n*A
print(T_pre+A_pre)

Submission status: Accepted

Solution code:
n = int(input())
t_v = a_v = 1
for _ in range(n):
    t, a = [int(x) for x in input().split()]
    r = max((t_v + t - 1) // t, (a_v + a - 1) // a)
    t_v, a_v = r * t, r * a
print(t_v + a_v)

Submission status: Accepted

Solution code:
n = int(input())
t_all, a_all = 0, 0
for i in range(n):
    t, a = map(int, input().split())
    if i == 0:
        t_all = t
        a_all = a
    else:
        if t >= t_all and a >= a_all:
            t_all, a_all = t, a
        else:
            diff1, diff2 = 0, 0
            diff1 = t_all // t if t_all % t == 0 else t_all // t + 1
            diff2 = a_all // a if a_all % a == 0 else a_all // a + 1
            max_diff = max(diff1, diff2)
            t_all = t * max_diff
            a_all = a * max_diff
print(t_all + a_all)

Submission status: Accepted

Solution code:
import math
from fractions import Fraction
from decimal import *
# ex) Fraction(2,6) > 1/3 > 0.33333

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

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

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

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

    t = tt * c
    a = aa * c


ans = t + a
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
t_i,a_i = map(int,input().split())
t = []
a = []
t.append(t_i)
a.append(a_i)
for i in range(1,n):
    t_i,a_i = map(int,input().split())
    t.append(t_i)
    a.append(a_i)
    if t[i-1]>t[i] or a[i-1]>a[i]:
        t_max = t[i-1]//t[i]
        if t[i-1]%t[i]!=0:
            t_max += 1
        a_max = a[i-1]//a[i]
        if a[i-1]%a[i]!=0:
            a_max += 1
        bai = max(t_max,a_max)
        t[i] *= bai
        a[i] *= bai
print(t[-1]+a[-1])

Submission status: Accepted

Solution code:
N = int(input())
x = 1
y = 1
for i in range(N):
    T, A = map(int, input().split())
    p = (T + x - 1) // T
    q = (A + y - 1) // A
    x = T * max(p, q)
    y = A * max(p, q)
    #print(f"[{x} {y}]")
print(x + y)

Submission status: Accepted

Solution code:
N = int(input())
T = 1
A = 1
for i in range(N):
    ti, ai = map(int, input().split())
    if T <= A:
        if T % ti == 0:
            TT = T
        else:
            TT = ti - (T % ti) + T
        if A <= (TT // ti) * ai:
            T = TT
            A = (TT // ti) * ai
        else:
            if A % ai != 0:
                A = ai - (A % ai) + A
            T = (A // ai) * ti
    else:
        if A % ai == 0:
            AA = A
        else:
            AA = ai - (A % ai) + A
        if T <= (AA // ai) * ti:
            A = AA
            T = (AA // ai) * ti
        else:
            if T % ti != 0:
                T = ti - (T % ti) + T
            A = (T // ti) * ai
        
print(T+A)

Submission status: Accepted

Solution code:
from sys import stdin
def input():
    return stdin.readline().strip()

n = int(input())

def adjust(x, y):
    if x % y == 0:
        return x // y
    else:
        return x//y + 1

ta, ao = 1, 1
for _ in range(n):
    t, a = map(int, input().split())
    mul = max([adjust(ta, t), adjust(ao, a)])
    ta = mul * t
    ao = mul * a

print(ta + ao)

Submission status: Accepted

Solution code:
def ceil(x, y):
    # ceil(x / y)
    return (x + y - 1) // y


def main():
    n = int(input())
    takahashi = 1
    aoki = 1
    for _ in range(n):
        t, a = map(int, input().split())
        diff = max(ceil(takahashi, t), ceil(aoki, a))
        takahashi = t * diff
        aoki = a * diff
    print(takahashi + aoki)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
T, A = map(int, input().split())

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

Submission status: Accepted

Solution code:
T = 1
A = 1

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

print(T+A)

Submission status: Accepted

Solution code:
def waru(k,l):
  if k%l==0:
    return k//l
  else:
    return (k//l)+1
A=0
B=0
N=int(input())
for i in range(N):
  a,b=map(int,input().split())
  if a>=A and b>=B:
    A,B=a,b
  elif a>=A and b<B:
    A,B=a*waru(B,b),b*waru(B,b)
  elif a<A and b>=B:
    A,B=a*waru(A,a),b*waru(A,a)
  else:
    c=max(waru(A,a),waru(B,b))
    A,B=a*c,b*c
print(A+B)

Submission status: Accepted

Solution code:
from sys  import stdin,stdout

import bisect

import math

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def soe(limit):
    l=[1]*(limit+1)
    prime=[]
    for i in range(2,limit+1):
        if l[i]:
            for j in range(i*i,limit+1,i):
                l[j]=0

    for i in range(2,limit+1):
        if l[i]:
            prime.append(i)
    return prime

def segsoe(low,high):
    limit=int(high**0.5)+1
    prime=soe(limit)
    n=high-low+1
    l=[0]*(n+1)
    for i in range(len(prime)):
        lowlimit=(low//prime[i])*prime[i]
        if lowlimit<low:
            lowlimit+=prime[i]
        if lowlimit==prime[i]:
            lowlimit+=prime[i]
        for j in range(lowlimit,high+1,prime[i]):
            l[j-low]=1
    for i in range(low,high+1):
        if not l[i-low]:
            if i!=1:
                print(i)
                
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

def power(a,n):
    r=1
    while n:
        if n&1:
            r=(r*a)
        a*=a
        n=n>>1
    return r

    
def solve():
    n=inp()
    a,b=1,1
    for _ in range(n):
        x,y=mp()
        d=max((x+a-1)//x,(y+b-1)//y)
        a=d*x
        b=d*y
    pr(a+b)
for _ in range(1):
    solve()

Submission status: Accepted

Solution code:
N=int(input())
A,B=1,1
for i in range(N):
   tmpl=list(map(int,input().split()))
   tmp=max(-1*(-1*A//tmpl[0]),-1*(-1*B//tmpl[1]))
   A,B=tmpl[0]*tmp,tmpl[1]*tmp
print(A+B)

Submission status: Accepted

Solution code:
import math

n=int(input())
t,a=map(int,input().split())
vt=t
va=a
for i in range(1,n):
    t, a = map(int, input().split())
    if vt<=t and va<=a:
        vt=t
        va=a
    elif vt>t and va<=a:
        x=-(-vt//t)
        vt,va=x*t,x*a
    elif vt<=t and va>a:
        x=-(-va//a)
        vt,va=x*t,x*a
    else:
        x1 = -(-vt // t)
        x2 = -(-va // a)
        if x1*t+x1*a >=x2*t+x2*a:
            vt, va = x1 * t, x1 * a
        else:
            vt, va = x2 * t, x2 * a

print(va+vt)

Submission status: Accepted

Solution code:
N=int(input())
x,y=0,0
for i in range(N):
  p=0
  T,A=map(int,input().split())
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print(x+y)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
N=int(input())
x,y=0,0
for i in range(N):
  p=0
  T,A=map(int,input().split())
  if i==0:
    x,y=T,A
    continue
  if x<=T and y<=A:
    x,y=T,A
  elif x<=T and A<y:
    if y%A!=0:
      p=1
    x=T*(y//A+p)
    y=A*(y//A+p)
  elif T<x and y<=T:
    if x%T!=0:
      p=1
    y=A*(x//T+p)
    x=T*(x//T+p)
  else:
    if (x//T+1)<=(y//A+1):
      if y%A!=0:
        p=1
      x=T*(y//A+p)
      y=A*(y//A+p)
    else:
      if x%T!=0:
        p=1
      y=A*(x//T+p)
      x=T*(x//T+p)
print(x+y)

Submission status: Accepted

Solution code:
n = int(input())

t1, a1 = map(int,input().split())

for i in range(n-1):
    t,a = map(int,input().split())
    if t1 * a == t * a1:
        pass
    elif t1 * a < t * a1:
        a1 = -(-a1 // a) * a
        t1 = a1 // a * t
    else:
        t1 = -(-t1 // t) * t
        a1 = t1 // t * a

print(a1+t1)

Submission status: Accepted

Solution code:
N = int(input())
Q = [tuple(map(int, input().split())) for _ in range(N)]
vote = Q[0]  # 初期値はそのまま得票(互いに素)

for p, q in Q[1:]:
    if p == q:
        g = max(vote)
        vote = (g, g)
    # p基準: 現在の得票以上の最小のpの倍数
    p_v0 = ((vote[0] + p - 1) // p) * p
    p_v1 = q * p_v0 // p
    # q基準
    q_v1 = ((vote[1] + q - 1) // q) * q
    q_v0 = p * q_v1 // q
    # 減っていたら除外
    if p_v1 < vote[1]:
        vote = (q_v0, q_v1)
    elif q_v0 < vote[0]:
        vote = (p_v0, p_v1)
    else:
        # どっちもありえるなら小さいほう
        if p_v0 + p_v1 <= q_v0 + q_v1:
            vote = (p_v0, p_v1)
        else:
            vote = (q_v0, q_v1)

ans = sum(vote)
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *TA = map(int, read().split())

    x, y = 1, 1

    for t, a in zip(*[iter(TA)] * 2):
        m1 = (x + t - 1) // t
        m2 = (y + a - 1) // a
        m = max(m1, m2)
        x, y = t * m, a * m

    print(x + y)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
T = 1
A = 1

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

print(T+A)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
x,y = LI()  # 高橋君、青木君の得票数
for i in range(1,N):
    T,A = LI()
    a = max((x+T-1)//T,(y+A-1)//A)
    x,y = T*a,A*a

print(x+y)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())

    now_t, now_a = 1,1
    for _ in range(N):
        t, a = map(int,input().split())
        n = max(-(-now_t//t), -(-now_a//a))
        now_t = t * n
        now_a = a * n
    
    print(now_t + now_a)
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from math import ceil
def solve():
    N = int(input())
    T = []
    A = []
    for _ in range(N):
        t, a = map(int,input().split())
        T.append(t)
        A.append(a)
    
    now_t = T[0]
    now_a = A[0]

    for i in range(1,N):
        mul = f(now_t,now_a,T[i],A[i])
        now_t = T[i] * mul
        now_a = A[i] * mul
    
    print(now_t + now_a)

def f(now_t, now_a, t, a):
    left = 0
    right = 10 ** 18
    while right - left > 1:
        mid = (right + left) // 2
        if now_t > t * mid or now_a > a * mid:
            left = mid
        else:
            right = mid
    
    return right

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
anst,ansa=map(int,input().split())
for _ in range(1,n):
    t,a=map(int,input().split())
    if anst>t or ansa>a:
        mul=max(-(-anst//t),-(-ansa//a))
        anst=mul*t
        ansa=mul*a
    else:
        anst=t
        ansa=a
print(anst+ansa)

Submission status: Accepted

Solution code:
def nextpt(ratio1, ratio2, pt):
  if ratio1[0]*ratio2[1]-ratio1[1]*ratio2[0]>0:
    pt[0]=pt[0]+((-1)*pt[0])%ratio2[0]
    pt[1]=pt[0]*ratio2[1]//ratio2[0]
  else:
    pt[1]=pt[1]+((-1)*pt[1])%ratio2[1]
    pt[0]=pt[1]*ratio2[0]//ratio2[1]
  return pt

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

pt=ratios[0]
for i in range(n-1):
  pt=nextpt(ratios[i], ratios[i+1], pt)

print(sum(pt))

Submission status: Accepted

Solution code:
n = int(input())
pt, pa = 0, 0
for _ in range(n):
    t, a = tuple(map(int, input().split()))
    l = 0
    r = 10**18+1
    while (r-l) > 1:
        mid = (l+r)//2
        if (t*mid >= pt and a*mid >= pa):
            r = mid
        else:
            l = mid
    pt, pa = t*r, a*r

print(pt+pa)

Submission status: Accepted

Solution code:
from math import gcd
from math import ceil
n = int(input())
T = [0] * n
A = [0] * n
for i in range(n):
    T[i], A[i] = map(int, input().split())

t, a = 1, 1
for i in range(n):
    t_rate, a_rate = T[i], A[i]
    #print(t_rate, a_rate)
    t_mul, a_mul = -(-t // t_rate), -(-a // a_rate)
    #print(t_mul, a_mul)
    mul_num = max(t_mul, a_mul)
    t, a = mul_num * t_rate, mul_num * a_rate

print(t + a)

Submission status: Accepted

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

Submission status: Accepted

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

for _ in range(N - 1):
    nt, na = map(int, input().split(' '))
    if nt >= t and na >= a:
        t = nt
        a = na
    else:
        tr = (t + nt - 1) // nt
        ar = (a + na - 1) // na
        r = max(tr, ar)
        t = r * nt
        a = r * na

print(t + a)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
TA = [LIST() for _ in range(N)]

T = TA[0][0]
A = TA[0][1]

for t, a in TA[1:]:
	p = max(-(-T//t), -(-A//a))
	T = t*p
	A = a*p
	
print(T+A)