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:
from collections import defaultdict
from heapq import heappush, heappop
import math
import bisect
import random

def LI(): return list(map(int, input().split()))
def I(): return int(input())
def LIM(): return list(map(lambda x:int(x) - 1, input().split()))
def LS(): return input().split()
def S(): return input()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007



def div(a, b):
    if a % b:
        return a // b + 1
    return a // b


def main():
    n = I()
    xy = LIR(n)
    x, y = 1, 1
    for nxt_x, nxt_y in xy:
        ratio_x = div(x, nxt_x)
        ratio_y = div(y, nxt_y)
        mul = math.ceil(max(ratio_x, ratio_y))
        x = mul * nxt_x
        y = mul * nxt_y
    return x + y


print(main())

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
from fractions import Fraction
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N = _I()
TA = [LI() for _ in range(N)]
"""
まず割合を求める
割合が違ったら数字を変更する必要がある
2:1にしないといけないのに
10-20
だったら、
答えは40-20であるが、
2:1をまず10-20より大きくする
まず割る
10/2=5
20/1=20
だからまず20倍する
40:20
これが答えであればok
逆ならどうか
17:25
2-3
なら
そもそも17:25が正解
じゃあ一方だけこえてたら？
17:25
21-3
これなら
まず小さい方は25にする
21-25
そこから割合を求める
21/17=1....
25/25 = 1
2倍する
34:50
満たしている
"""

vals = [1,1]
for t, a in TA:
    #  # まず同じ大きさにする
    #  if vals[0] < t:
    #      vals[0] = t
    #  if vals[1] < a:
    #      vals[1] = a

    xt = math.ceil(Fraction(vals[0], t))
    xa = math.ceil(Fraction(vals[1] , a))

    max_x = max(xt, xa)
    #  t *= max_x
    #  a *= max_x
    vals[0] = t * max_x
    vals[1] = a * max_x

print(sum(vals))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc046/tasks/arc062_a

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def div(a, b):
    if a % b == 0:
        return a // b
    else:
        return (a // b) + 1

def main():
    n = int(input())
    t, a = 1, 1
    for _ in range(n):
        tt, at = map(int, input().split())

        temp_t = div(t, tt)
        temp_a = div(a, at)
        co = max(temp_t, temp_a)

        t = co * tt
        a = co * at

    print(t + a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

# https://atcoder.jp/contests/abc046/tasks/arc062_a

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def div(a, b):
    if a % b == 0:
        return a // b
    else:
        return (a // b) + 1

def main():
    n = int(input())
    t, a = 1, 1
    for _ in range(n):
        tt, at = map(int, input().split())

        temp_t = div(t, tt)
        temp_a = div(a, at)
        co = max(temp_t, temp_a)

        t = co * tt
        a = co * at

    print(t + a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

from decimal import Decimal

# エントリーポイント
def main():
    N = input(int)
    TA = input([int, int, N])

    a, b = 1, 1
    for x, y in TA:
        n = max(ceil(Decimal(a) / Decimal(x)), ceil(Decimal(b) / Decimal(y)))
        a, b = n * x, n * y
    print(a + b)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

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

n1n2=[1,1]

for i in range(N):
  nn=max(n1n2[0]//tiai[i][0]+(0 if not n1n2[0]%tiai[i][0] else 1),n1n2[1]//tiai[i][1]+(0 if not n1n2[1]%tiai[i][1] else 1))
  n1n2=[nn*tiai[i][0],nn*tiai[i][1]]
print(sum(n1n2))

Submission status: Accepted

Solution code:
import sys
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]

# エントリーポイント
def main():
    N = input(int)
    TA = input([int, int, N])

    a, b = 1, 1
    for x, y in TA:
        # n = max(ceil(a / x), ceil(b / y))
        n = max((a - 1) // x, (b - 1) // y) + 1
        a, b = n * x, n * y
    print(a + b)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

Submission status: Accepted

Solution code:
n=int(input())
li=[]
result=[]
for i in range(n):
  li.append(list(map(int,input().split())))
result.append(int(li[0][0]))
result.append(int(li[0][1]))
dic={}
for i in range(1,n):  
  if result[0]<=li[i][0] and result[1]<=li[i][1]:
    result=li[i]
    #result[1]=li[i][1]
  else:
    a=result[0]//li[i][0]
    b=result[1]//li[i][1]
    c=max(a,b)
    if result[0]>li[i][0]*c or result[1]>li[i][1]*c:
      c+=1
    result[0]=li[i][0]*c
    result[1]=li[i][1]*c
  #print(result[0],result[1])
print(result[0]+result[1])

Submission status: Accepted

Solution code:
import math

n = int(input())

a,b = 1,1
for _ in range(n):
    ai ,bi =[int(x) for x in input().split()]
    n = max((a-1)//ai, (b-1)//bi)+1
    a = n * ai
    b = n * bi
print(a+b)

Submission status: Accepted

Solution code:
N = int(input())
pt = 1
pa = 1
for _ in range(N):
    t, a = map(int, input().split())
    if t >= pt and a >= pa:
        pt = t
        pa = a
    else:
        tt = pt // t
        if pt % t != 0:
            tt += 1
        aa = pa // a
        if pa % a != 0:
            aa += 1
        k = max(tt, aa)
        pt = t * k
        pa = a * k
print(pt + pa)

Submission status: Accepted

Solution code:
N = int(input())

a, b = 1, 1

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

print(a + b)

Submission status: Accepted

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

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())
    if (c>=a and d>=b):
        a=c
        b=d
    else:
        left = (a+c-1)//c
        right = (b+d-1)//d
        mx = max(left,right)
        a= c*mx
        b=d*mx
print(a+b)

Submission status: Accepted

Solution code:
#%%
def ceil(x, y):
    if x % y == 0:
        return x//y
    else:
        return x//y+1

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

#print('----------')

tmp1 = A[0][0]
tmp2 = A[0][1]
#print(tmp1, tmp2)

for i in range(1, N):
    a = ceil(tmp1,A[i][0])
    b = ceil(tmp2,A[i][1])
    c = max(a, b)    
    tmp1 = A[i][0] * c
    tmp2 = A[i][1] * c
#    print(tmp1, tmp2)

ans = (tmp1 + tmp2)
print(ans)











#%%

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from sys import exit, stdin

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

n, x, y = 1, 1, 1

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

for i in range(N):
    n = max(ceil(x, TA[i][0]), ceil(y, TA[i][1]))
    x = TA[i][0]*n
    y = TA[i][1]*n

print(x+y)

Submission status: Accepted

Solution code:
n = int(input())
ll = [list(map(int,input().split())) for _ in [0]*n]
t=1
a=1
for l in ll:
  if l[0]>=t and l[1]>=a:
    t=l[0]
    a=l[1]
  else:
    c = max([-(-t//l[0]), -(-a//l[1])])
    t = l[0]*c
    a = l[1]*c
print(t+a)

Submission status: Accepted

Solution code:
n = int(input())


x = list(map(int,input().split())) 
for i in range(n-1):
    t,a = map(int,input().split())
    if x[0]%t==0 and x[1]%a==0:
        k = max(x[0]//t,x[1]//a)
    elif x[0]%t==0:
        k = max(x[0]//t,x[1]//a+1)
    elif x[1]%a==0:
        k = max(x[0]//t+1,x[1]//a)
    else:
        k = max(x[0]//t,x[1]//a)+1
    x = [t*k,a*k]

print(sum(x))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

num = int(input())
arr = [list(map(int, input().split())) for i in range(num)]
 
t = 1
a = 1
r = 0
for i in range(num):
    r = max(divceil(t, arr[i][0]), divceil(a, arr[i][1]))
    t = arr[i][0] * max(r, 1)
    a = arr[i][1] * max(r, 1)
print(t + a)

Submission status: Accepted

Solution code:
def ceil(x,y):
    if x%y==0:
        return x//y
    else:
        return (x//y)+1
N=int(input())
T,A=1,1
for _ in range(N):
    t,a=map(int,input().split())
    x=max(ceil(T,t),ceil(A,a))
    if x==0:x=1
    T,A=t*x,a*x
print(T+A)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int, T: "List[int]", A: "List[int]"):
    tmpT = 1
    tmpA = 1
    for i in range(N):
        d = max((tmpT-1)//T[i]+1, (tmpA-1)//A[i]+1)
        tmpT = T[i] * d
        tmpA = A[i] * d
    print(tmpT+tmpA)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = [int()] * (N)  # type: "List[int]" 
    A = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        T[i] = int(next(tokens))
        A[i] = int(next(tokens))
    solve(N, T, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# C問題
N = int(input())
TA = []
for i in range(N):
    TA.append(list(map(int, input().split())))
#T, A互いに素なので1枚目はそのまま取ってきて良い
t = TA[0][0]
a = TA[0][1]
flag = True
for i in range(1,  N+1):
    tmp_t = 0
    tmp_a = 0
    if i == N:
        flag = False
        break
    k = max(t // TA[i][0], a // TA[i][1])   # 整数k
    while flag:   # 整数倍(足していく)していって両方がが超えた時の値が得票数になる
        tmp_t = k * TA[i][0]
        tmp_a = k * TA[i][1]
        if tmp_t >= t and tmp_a >= a:
            t = tmp_t
            a = tmp_a
            break
        k += 1
    
print(t+a)

Submission status: Accepted

Solution code:
N = int(input())
def func(T_pre, A_pre, T, A):
  if T_pre <= T and A_pre <= A:
    return T, A
  else:
    t = -(-T_pre//T)
    a = -(-A_pre//A)
    x = max(t, a)
    return T*x, A*x
for i in range(N):
  T, A = map(int, input().split())
  if i == 0:
    T_pre = T
    A_pre = A
  else:
    T_pre, A_pre = func(T_pre, A_pre, T, A)
print(int(T_pre+A_pre))

Submission status: Accepted

Solution code:
N=int(input())
R=[list(map(int,input().split())) for _ in range(N)]
T=0
A=0
for t,a in R:
  n=max((T-1)//t+1,(A-1)//a+1)
  T=n*t
  A=n*a
  if T+A==0:
    T+=t
    A+=a
print(T+A)

Submission status: Accepted

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

pt = [0] * N
pa = [0] * N

for i in range(N):
    t, a = map(int, input().split())
    if i == 0:
        pt[i] = t
        pa[i] = a
    else:
        #最小単位というかなんというか
        n = max(math.ceil(Fraction(pt[i-1],t)), math.ceil(Fraction(pa[i-1],a)))
        pt[i] = n*t
        pa[i] = n*a

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

Submission status: Accepted

Solution code:
def solve():
    list_t_and_a = read()
    result = think(list_t_and_a)
    write(result)


def read():
    n = read_int(1)[0]
    list_t_and_a = []
    for _ in range(n):
        list_t_and_a.append(read_int(2))
    return list_t_and_a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(list_t_and_a):
    n = len(list_t_and_a)
    vote_t, vote_a = list_t_and_a[0][0], list_t_and_a[0][1]
    for i in range(1, n):
        ti, ai = list_t_and_a[i][0], list_t_and_a[i][1]
        ratio_t = vote_t // ti
        if vote_t % ti != 0:
            ratio_t += 1
        ratio_a = vote_a // ai
        if vote_a % ai != 0:
            ratio_a += 1
        ratio = max(ratio_t, ratio_a)
        vote_t = ratio * ti
        vote_a = ratio * ai
    return vote_t + vote_a


def expected_lower_value_than_actual(actual, expected):
    return actual > expected


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import bisect
import math

def div(a, b):
    if a % b == 0:
        return a // b
    else:
        return (a // b) + 1

def main():
    num = int(input())
    vote_a, vote_b = 1, 1
    for i in range(num):
        a, b = map(int, input().split())
        aaa = div(vote_a, a)
        bbb = div(vote_b, b)
        ccc = max(aaa, bbb)
        vote_a, vote_b = a * ccc, b * ccc

    print(vote_a + vote_b)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, T: "List[int]", A: "List[int]"):
    t, a = 1, 1
    for i in range(N):
        if T[i] == A[i]:
            tmp = max(t, a)
            t = tmp
            a = tmp
        elif t <= a / A[i] * T[i]:
            a = ((a - 1) // A[i] + 1) * A[i]
            t = (a // A[i]) * T[i]
        else:
            t = ((t - 1) // T[i] + 1) * T[i]
            a = (t // T[i]) * A[i]
        #print(T[i], A[i], t, a)
    ret = a + t
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = [int()] * (N)  # type: "List[int]" 
    A = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        T[i] = int(next(tokens))
        A[i] = int(next(tokens))
    solve(N, T, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

pa = 1
pt = 1
for t, a in TA:
    k = max(pt//t, pa//a)
    if a*k < pa or t*k < pt:
        k += 1
    pa = a*k
    pt = t*k

print(pa+pt)

Submission status: Accepted

Solution code:
N = int(input())
A = 1
B = 1

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

for i in range(N):
  x, y = map(int, input().split())
  n = max(div(A, x), div(B, y))
  if n == 0:
    n = 1
  A = n * x
  B = n * y
print(A + B)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

    now_t,now_a = ls[0]

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

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y:
		return x
	return y

N = int(input())
T, A = map(int, input().split())
for i in range(1, N):
	newT, newA = map(int, input().split())
	multiT = T // newT
	if T % newT != 0:
		multiT += 1
	multiA = A // newA
	if A % newA != 0:
		multiA += 1
	T = newT * larger(multiT, multiA)
	A = newA * larger(multiT, multiA)
print(T+A)

Submission status: Accepted

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

def div(k,l):
    if k%l==0:
        return k//l
    else:
        return k//l+1

for i in range(n):
    x,y=map(int,input().split())
    m=max(div(a,x),div(b,y))
    a=m*x
    b=m*y
print(a+b)

Submission status: Accepted

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


n = int(input())
p = 1
q = 1
for _ in range(n):
    t, a = map(int, input().split())
    n = max(div(p, t), div(q, a))
    p = n * t
    q = n * a

print(p + q)

Submission status: Accepted

Solution code:
t=a=1;exec('u,b=map(int,input().split());x=0-min(-t//u,-a//b);t,a=u*x,b*x;'*int(input()));print(t+a)

Submission status: Accepted

Solution code:
n,t,a,*u=map(int,open(0).read().split())
for u,b in zip(u[::2],u[1::2]):
    x=0-min(-t//u,-a//b)
    t,a=u*x,b*x
print(t+a)

Submission status: Accepted

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

import math
n = int(input())
A,B = 1,1
for i in range(n):
    t,a = map(int,input().split())
    if A % t == 0:
        na = A//t
    else:
        na = A//t+1
    if B % a == 0:
        nb = B//a
    else:
        nb = B//a+1
    n = max(na,nb)
    A,B = n*t,n*a
print(A+B)

Submission status: Accepted

Solution code:

N = int(input())

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


for i in range(N-1):

    NT,NA = map(int,input().split())

    if T // NT > A // NA and T % NT == 0:

        n = T // NT
        #print ("ばあい１")

    elif T // NT < A // NA and A % NA == 0:

        n = A // NA
        #print ("ばあい２",A,NA)

    elif T // NT == A // NA and T % NT == 0 and A % NA == 0:

        n = T // NT
        #print ("ばあい３")

    else:

        n = max( T // NT , A // NA ) + 1
        #print ("ばあい４")

    T = n * NT
    A = n * NA

    #print (n)
    #print (T,A)

print (T+A)

Submission status: Accepted

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

Submission status: Accepted

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

T, A = TA[0]
for i in range(1, N) :
    t, a = TA[i]
    if T / A < t / a :
        i = 0
        while (A + i) * t % a != 0 :
            i += 1
        T = (A + i) * t // a
        A = A + i
    else :
        i = 0
        while (T + i) * a % t != 0 :
            i += 1
        A = (T + i) * a // t
        T = T + i
    
print(T + A)

Submission status: Accepted

Solution code:
# import math
n = int(input())
x = 1
y = 1
for i in range(n):
    t, a = [int(_) for _ in input().split()]
    if x%t == 0:
        kt = x//t
    else:
        kt = x//t + 1
    if y % a == 0:
        ka = y // a
    else:
        ka = y // a + 1

    k = max(kt, ka)
    x = t*k
    y = a*k

print(x+y)

Submission status: Accepted

Solution code:
import math
N = int(input())
t = 1
a = 1
for i in range(N):
  ti, ai = map(int, input().split())
  
  # trick to calc m accurately, instead of ceil(t/ti). '/' isn't accurate. 
  m = max( (t-1)//ti+1, (a-1)//ai+1 ) 
  t = m*ti
  a = m*ai
print(t+a)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    t = []
    a = []
    for i in range(n):
        in_t,in_a = map(int,input().split(' '))
        t.append(in_t)
        a.append(in_a)
    if n == 1:
        return t[0]+a[0]
    tmp_t = t[0]
    tmp_a = a[0]
    for i in range(1,n):
        if tmp_t%t[i] != 0:
            x = (tmp_t - tmp_t%t[i] + t[i])//t[i]
        else:
            x = tmp_t//t[i]

        if tmp_a%a[i] != 0:
            y = (tmp_a - tmp_a%a[i] + a[i])//a[i]
        else:
            y = tmp_a//a[i]

        if x <= y:
            x = y
        else:
            y = x
        tmp_t = t[i]*x
        tmp_a = a[i]*y
    return tmp_t+tmp_a

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

Submission status: Accepted

Solution code:
# ABC046C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report (ARC062C)
def main():
    n = int(input())
    arr = tuple(tuple(map(int, input().rstrip().split())) for _ in range(n))
    t, a = 1, 1
    for i, j in arr:
        r = max((t - 1) // i + 1, (a - 1) // j + 1)
        t, a = i * r, j * r
    print(t + a)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
dat = []
import fractions

for i in range(n):
    a, b = map(int, input().split())
    c = fractions.gcd(a, b)
    #a, b = a // c, b // c # 約分する
    dat.append( (a, b) )

a, b = 1, 1

import math
for i in range(n):
    x, y = dat[i]
    c = max( (a + x - 1) // x, (b + y - 1) // y)
    #print("{0},{1}: c= {4} : {2},{3}".format(x, y, a,b,c))
    a, b = x * c, y * c
print(a + b)

Submission status: Accepted

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


t1 = 1
t2 = 1
for T1, T2 in ratio:
        tmp_a = -( - t1 // T1)
        tmp_b = -( - t2 // T2)
        n = max(tmp_a, tmp_b)
        t1 = n * T1 
        t2 = n * T2
print(t1 + t2)

Submission status: Accepted

Solution code:
import fractions

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

print(t+a)

Submission status: Accepted

Solution code:
N = int(input())

s, b = 0, 0

for loop in range(N):
    t, a = map(int, input().split())

    if loop == 0:
        s, b = t, a
    else:
        k = max((s + t - 1) // t, (b + a - 1) // a)
        s, b = k * t, k * a
print(s + b)

Submission status: Accepted

Solution code:
N = int(input())
pt = pa = 0
for _ in range(N):
    t,a = map(int,input().split())
    if pt == 0:
        pt,pa = t,a
    else:
        #print(pt,pa,t,a)
        if (pt <= t) and (pa <= a):
            pt,pa = t,a
        else:
            '''
            i = 2
            while True:
                if (pt <= t*i) and (pa <= a*i):
                    pt,pa = t*i,a*i
                    break
                i += 1
            '''
            if t == a:
                #that is t = a = 1
                maxta = max(pt,pa)
                pt = pa = maxta
            else:
                w1 = -1 * ((-1 *pt) // t)
                w2 = -1 * ((-1 *pa) // a)
                w = max(w1,w2)
                pt = w * t
                pa = w * a
                #print(pt,pa)
print(pt+pa)

Submission status: Accepted

Solution code:
N = int(input())

def check(t, a):
    T, A = map(int, input().split())
    t = T * max((t + (T-1))//T, (a + (A-1))//A)
    a = A * max((t + (T-1))//T, (a + (A-1))//A)
    return t, a

t = 1
a = 1
for _ in range(N):
    t, a = check(t, a)

print (t + a)

Submission status: Accepted

Solution code:
N = int(input())

def check(t, a):
    T, A = map(int, input().split())
    if T >= t and A >= a:
        t = T
        a = A
        return t, a
    if T >= t and A < a:
        t = T * ((a + (A-1))//A)
        a = A * ((a + (A-1))//A)
        return t, a
    if T < t and A >= a:
        t = T * ((t + (T-1))//T)
        a = A * ((t + (T-1))//T)
        return t, a
    if T < t and A < a:
        t = T * max((t + (T-1))//T, (a + (A-1))//A)
        a = A * max((t + (T-1))//T, (a + (A-1))//A)
        return t, a
t = 0
a = 0
for _ in range(N):
    t, a = check(t, a)

print (t + a)

Submission status: Accepted

Solution code:
N = int(input())

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

tmp_T = T[0]
tmp_A = A[0]

for i in range(1,N):
    ma = tmp_A // A[i] + (1 if tmp_A % A[i] > 0 else 0)
    mt = tmp_T // T[i] + (1 if tmp_T % T[i] > 0 else 0)
    n = max(mt,ma)
    tmp_A = n * A[i]
    tmp_T = n * T[i]

print(tmp_T + tmp_A)

Submission status: Accepted

Solution code:
import math
import sys
from decimal import Decimal


N = int(sys.stdin.readline())
TA = []
for i in range(N):
    TA.append(list(map(int, sys.stdin.readline().split())))

current_T = 1
current_A = 1
for i in range(N):
    count = max(math.ceil(Decimal(current_T)/Decimal(TA[i][0])), math.ceil(Decimal(current_A)/Decimal(TA[i][1])))
    current_T = TA[i][0] * count
    current_A = TA[i][1] * count

print(current_T + current_A)

Submission status: Accepted

Solution code:
N = int(input())

lst_S = []
for i in range(N):
    lst_S.append(input().split())
    lst_S[i][0] = int(lst_S[i][0])
    lst_S[i][1] = int(lst_S[i][1])

bote_A = lst_S[0][0]
bote_B = lst_S[0][1]

for i in range(1, N):
    bai_A = (bote_A - 1) // lst_S[i][0]
    bai_B = (bote_B - 1) // lst_S[i][1]

    bai = max(bai_A, bai_B) + 1

    bote_A = lst_S[i][0] * bai
    bote_B = lst_S[i][1] * bai

ans = bote_A + bote_B

print(ans)

Submission status: Accepted

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

vote_T = TA[0][0]
vote_A = TA[0][1]
for i in range(1,N):
  var_T = (vote_T + (TA[i][0]-1)) // TA[i][0]
  var_A = (vote_A + (TA[i][1]-1)) // TA[i][1]
  multiple = max(var_T, var_A)
  vote_T = TA[i][0] * multiple
  vote_A = TA[i][1] * multiple
  
print(vote_T + vote_A)

Submission status: Accepted

Solution code:
n = int(input())
ta = []
for i in range(n):
    ta.append(input().split())

l_sum = int(ta[0][0])
r_sum = int(ta[0][1])

for i in range(n):
    if int(ta[i][0]) > l_sum and int(ta[i][1]) > r_sum:
        l_sum = int(ta[i][0])
        r_sum = int(ta[i][1])
    elif int(ta[i][0]) <= l_sum and int(ta[i][1]) > r_sum:
        times_num = -(- l_sum // int(ta[i][0]))
        l_sum = int(ta[i][0]) * times_num
        r_sum = int(ta[i][1]) * times_num
    elif int(ta[i][0]) > l_sum and int(ta[i][1]) <= r_sum:
        times_num = -(- r_sum // int(ta[i][1]))
        l_sum = int(ta[i][0]) * times_num
        r_sum = int(ta[i][1]) * times_num
    elif int(ta[i][0]) <= l_sum and int(ta[i][1]) <= r_sum:
        r_times_num = -(- r_sum // int(ta[i][1]))
        l_times_num = -(- l_sum // int(ta[i][0]))
        times_num = max(r_times_num, l_times_num)
        l_sum = int(ta[i][0]) * times_num
        r_sum = int(ta[i][1]) * times_num
print(l_sum + r_sum)

Submission status: Accepted

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

Submission status: Accepted

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

def current_result(t, a, x, y):
  #n = max(int(math.ceil(t/x)), int(math.ceil(a/y)))
  #n = max(int((t-1)/x)+1, int((a-1)/y)+1)
  tx, ay = 0, 0
  if t % x == 0:
    tx = t // x 
  else:
    tx = t // x + 1
  if a % y == 0:
    ay = a // y
  else:
    ay = a // y + 1
  n = max(tx, ay)
  return n*x, n*y

if __name__ == "__main__":
  t, a = 1, 1
  for i in range(n):
    x, y = ta_li[i]
    t, a = current_result(t, a, x, y)
  print(t+a)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
from decimal import Decimal

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

min_T,min_A = 1,1
for i in range(N):
    t,a = TA[i]
    # if min_T >= t or min_A>= a:
    multi = max(math.ceil(Decimal(min_T) / Decimal(t)),math.ceil(Decimal(min_A)/Decimal(a)),1)
    min_T,min_A = t*multi, a*multi

print(min_A+min_T)

Submission status: Accepted

Solution code:
import itertools
from math import ceil
from decimal import Decimal

N = input()
N = int(N)
lasta,lastb = 1,1
temp = []
for _ in range(N):
    temp.append(list(map(int,input().split(" "))))


for hoge in temp:
    a,b = hoge
    diffa = ceil(Decimal(lasta)/Decimal(a))
    diffb = ceil(Decimal(lastb)/Decimal(b))
    diff = max(diffa,diffb)
    lasta,lastb = a*diff,b*diff
print(lasta+lastb)

Submission status: Accepted

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

cur_t = 1
cur_a = 1


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

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

Submission status: Accepted

Solution code:
N = int(input())
a,b = 1,1
for i in range(N):
    aa,bb = map(int,input().split())
    k = max((a+aa-1)//aa,(b+bb-1)//bb)
    aa *= k
    bb *= k
    a,b = aa,bb

print(a+b)