Problem:


Score : 300 points

Problem Statement

AtCoDeer the deer is seeing a quick report of election results on TV.
Two candidates are standing for the election: Takahashi and Aoki.
The report shows the ratio of the current numbers of votes the two candidates have obtained, but not the actual numbers of votes.
AtCoDeer has checked the report N times, and when he checked it for the i-th (1≦i≦N) time, the ratio was T_i:A_i.
It is known that each candidate had at least one vote when he checked the report for the first time.

Find the minimum possible total number of votes obtained by the two candidates when he checked the report for the N-th time.
It can be assumed that the number of votes obtained by each candidate never decreases.

Constraints

1≦N≦1000

1≦T_i,A_i≦1000 (1≦i≦N)

T_i and A_i (1≦i≦N) are coprime.

It is guaranteed that the correct answer is at most 10^{18}.

Input

The input is given from Standard Input in the following format:

N
T_1 A_1
T_2 A_2
:
T_N A_N

Output

Print the minimum possible total number of votes obtained by Takahashi and Aoki when AtCoDeer checked the report for the N-th time.

Sample Input 1

3
2 3
1 1
3 2

Sample Output 1

10

When the numbers of votes obtained by the two candidates change as 2,3 → 3,3 → 6,4, the total number of votes at the end is 10, which is the minimum possible number.

Sample Input 2

4
1 1
1 1
1 5
1 100

Sample Output 2

101

It is possible that neither candidate obtained a vote between the moment when he checked the report, and the moment when he checked it for the next time.

Sample Input 3

5
3 10
48 17
31 199
231 23
3 2

Sample Output 3

6930



Sample input:
3
2 3
1 1
3 2


Sample output:
10

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ta = []
for i in range(n):
    tmp = list(map(int,input().split()))
    ta.append(tmp)
vote=[1,1]
for v in ta:
    t_ratio=(vote[0]-1)//v[0]+1
    a_ratio=(vote[1]-1)//v[1]+1
    ratio = max(t_ratio,a_ratio)
    vote[0] = v[0] * ratio
    vote[1] = v[1] * ratio

print(sum(vote))

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(p, q):
    t, a = q
    pt, pa = p

    nt = max((pt - 1) // t + 1, 1)
    na = max((pa - 1) // a + 1, 1)

    n = max(nt, na)

    return (n * t, n * a)


def main():
    N = int(input())
    p = (1, 1)
    for _ in range(N):
        q = read_list()
        p = f(p, q)
    
    print(sum(p))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
T, A = 0, 0
for i in range(N):
  a1, a2 = map(int, input().split())
  if i == 0:
    T, A = a1, a2
  else:
    if T <= a1 and A <= a2:
      T, A = a1, a2
    elif T > a1 and A <= a2:
      if T % a1 == 0:
        X = T // a1
      else:
        X = T // a1 + 1
      T, A = a1 * X, a2 * X
    elif T <= a1 and A > a2:
      if A % a2 == 0:
        X = A // a2
      else:
        X = A // a2 + 1
      T, A = a1 * X, a2 * X
    elif T > a1 and A > a2:
      X, Y = (T - 1) // a1 + 1, (A - 1) // a2 + 1
      if X <= Y:
        T, A = a1 * Y, a2 * Y
      else:
        T, A = a1 * X, a2 * X
print(T + A)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
t,a = inm()
for i in range(n-1):
    tt,aa = inm()
    k = max((t+tt-1)//tt, (a+aa-1)//aa)
    t = k*tt
    a = k*aa
print(t+a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string
from functools import lru_cache
import heapq

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7

def main():
    N = cin.int()
    T = cin.intListList(N)
    a,b = 1,1
    for t in T:
        n = max(Math.roundUp(a , t[0]),Math.roundUp(b , t[1]))
        a,b = n * t[0],n * t[1]
    print(a + b)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
P = [1,1]

for i in range(N):
  Q = list(map(int,input().split()))
  t = Q[0]
  a = Q[1]
  m = max(P[0]//t,P[1]//a,1)
  while True:
    t = Q[0] * m
    a = Q[1] * m
    if t >= P[0] and a >= P[1]:
      P[0] = t
      P[1] = a
      break
    m += 1

print(sum(P))

Submission status: Accepted

Solution code:
def ceil_div(a, b):
    return (a + b - 1) // b

N = int(input())
t, a = 1, 1
for _ in range(N):
    T, A = map(int, input().split())
    # find the smallest integer k such that
    # t <= k * T and a <= k * A
    k = max(ceil_div(t, T), ceil_div(a, A))
    t = k * T
    a = k * A
print(t + a)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    T, A = map(int, input().split())
    n = max(-(-a//A), -(-t//T))  # ここ、バグが埋まってる？ math.ceilだと失敗する
    t, a = n*T, n*A
print(int(t+a))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
x = 1
y = 1
for _ in range(N):
  t, a = map(int, input().split())
  if x * a != y * t:
    z = -(-(x + y) // (a + t))
    z = max(z, -(-x // t), -(-y // a))
    x = t * z
    y = a * z
  #print(x, y)
print(x + y)

Submission status: Accepted

Solution code:
import math

N = int(input())
ta = list(map(int, input().split()))
T, A = ta[0], ta[1]

# 繰り返し
for i in range(N - 1):
    tmp_ta = list(map(int, input().split()))
    t, a = tmp_ta[0], tmp_ta[1]
    # print("(t,a):" + str(t) + " " + str(a))
    # T,Aが各々t,aの倍数かつそのような比になればいい.
    # Tが最小 ->　Aも最小になる
    # ダメ.小さい方を揃えないと(3,3) -> (3,2)のような変化になる
    # (2,5) -> (2,4)でも死にそう
    # (2,5) -> (4,8)になるのが良さそう -> なっている
    # (1,2) -> (2,1) は？　(4,2)が答 -> なっている
    # intの範囲超えてintキャストしたら死ぬ,それはそう
    # どっちかを最小にすればいいんじゃないか？
    # まずt基準
    tmpTt = T if T % t == 0 else (T // t + 1) * t
    tmpTa = tmpTt * a // t
    tmpAa = A if A % a == 0 else (A // a + 1) * a
    tmpAt = tmpAa * t // a
    # print(str(tmpAt) + " " + str(tmpAa) + " " + str(tmpTt) + " " + str(tmpTa))
    if tmpTa < A:
        T = tmpAt
        A = tmpAa
    elif tmpAt < T:
        T = tmpTt
        A = tmpTa
    elif (tmpTt + tmpTa) < (tmpAa + tmpAt):
        T = tmpTt
        A = tmpTa
    else:
        T = tmpAt
        A = tmpAa
    # print("(T, A) = (" + str(T) + ", " + str(A) + ")")

print(T + A)

Submission status: Accepted

Solution code:
import sys
import math

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

#実際の二人の得票数を数える
N = ri()
T_cnt = 1
A_cnt = 1
for _ in range(N):
    t, a = rl()
    n = max(-(-T_cnt//t), -(-A_cnt//a))
    T_cnt, A_cnt = t * n, a * n

answer = T_cnt + A_cnt
print(answer)
#24

Submission status: Accepted

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

ma,mb = AB[0]
for a, b in AB[1:]:
  i = -(-ma //a)
  j = -(-mb //b)
  k = max(i, j)
  
  ma = k*a
  mb = k*b
  
print(ma + mb)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    ta = tb = 1
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        r = max((a + ta - 1) // a, (b + tb - 1) // b)
        ta = a * r
        tb = b * r
    print(ta + tb)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def bisect(x,X):
  l=0
  r=10**18
  while r>l+1:
    n=(r+l)//2
    if n*x>=X:
      r=n
    else:
      l=n
  return r    

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a, b): 
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return((a*b)//gcd(a,b))

def main():
    n=int(input())
    a=1
    b=1
    for _ in range(n):
        x,y = map(int,input().split())
        n=a//x
        m=b//y
        if a%x!=0:
            n+=1
        if b%y!=0:
            m+=1
        a=max(n,m)*x
        b=max(n,m)*y
    print(a+b)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
t,a=map(int,input().split())
for i in range(N-1):
    Ti,Ai=map(int,input().split())
    kt=(t+(Ti-1))//Ti;ka=(a+(Ai-1))//Ai
    k=max(kt,ka)
    t=k*Ti;a=k*Ai
print(t+a)

Submission status: Accepted

Solution code:
N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
x,y=1,1
for t,a in TA:
    if -(-x//t)*a>=y:
        x,y=-(-x//t)*t,-(-x//t)*a
    else:
        x,y=-(-y//a)*t,-(-y//a)*a
print(x+y)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    tt = ta = 0
    for i in range(n):
        t, a = list(map(int, input().rstrip('\n').split()))
        if i == 0:
            tt = t
            ta = a
        else:
            r = max((tt + t - 1) // t, (ta + a - 1) // a)
            tt = t * r
            ta = a * r
    print(tt + ta)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())

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

print(t + a)

Submission status: Accepted

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

import math

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ARC062C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report
def main():
    N, *TA = map(int, open(0).read().split())
    t, a = TA[:2]
    for i, j in zip(*[iter(TA[2:])] * 2):
        x = max((t + i - 1) // i, (a + j - 1) // j)
        t, a = i * x, j * x
    print(t + a)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import os
import math

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
import math
import sys
N = int(input())
T = []
A = []
for n in range(N):
    t, a = map(int, input().split())
    T.append(t)
    A.append(a)

if N == 1:
    ans = T[N - 1] + A[N - 1]
    print(ans)
    sys.exit()

for n in range(1, N):
    tmp_a = -(-A[n - 1] // A[n])
    tmp_t = -(-T[n - 1] // T[n])
    if A[n - 1] <= A[n] and T[n - 1] <= T[n]:
        continue
    elif A[n - 1] > A[n] and T[n - 1] <= T[n]:
        A[n] = tmp_a * A[n]
        T[n] = tmp_a * T[n]
    elif A[n - 1] <= A[n] and T[n - 1] > T[n]:
        A[n] = tmp_t * A[n]
        T[n] = tmp_t * T[n]
    elif A[n - 1] > A[n] and T[n - 1] > T[n]:
        if tmp_a * T[n] >= T[n - 1]:
            T[n] = tmp_a * T[n]
            A[n] = tmp_a * A[n]
        elif tmp_t * A[n] >= A[n - 1]:
            T[n] = tmp_t * T[n]
            A[n] = tmp_t * A[n]
print(T[N - 1] + A[N - 1])

Submission status: Accepted

Solution code:
import math
n = int(input())
rat = [list(map(int, input().split(' '))) for _ in range(n)]
a = 1
b = 1
for i in range(n):
    x = max(-(-a//rat[i][0]), -(-b//rat[i][1]))
    a = x*rat[i][0]
    b = x*rat[i][1]
print(a+b)

Submission status: Accepted

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

t,a = TA[0]
for T,A in TA[1:]:
    t1 = t + (-t%T)
    a1 = (t1//T) * A
    a2 = a + (-a%A)
    t2 = (a2//A) * T
    if t > t2:
        t,a = t1,a1
    else:
        t,a = t2,a2
print(t+a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n = int(input())
rat = [list(map(int, input().split(' '))) for _ in range(n)]
a = 1
b = 1
for i in range(n):
    x = max(-(-a//rat[i][0]), -(-b//rat[i][1]))
    a = x*rat[i][0]
    b = x*rat[i][1]
print(a+b)

Submission status: Accepted

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

A,B=1,1

for at in AT:
  n=max(-(-A//at[0]//1),-(-B//at[1]//1))
  #print("n,a,b",n,-(-A//at[0]//1),-(-B//at[1]//1))
  #print("a,b", at[0],at[1])
  A=n*at[0]
  B=n*at[1]
  #print(A,B)
print(A+B)

Submission status: Accepted

Solution code:
from math import ceil

N = int(input())
A, B = map(int, input().split())
ans = 1
for i in range(1, N):
    x, y = map(int, input().split())
    ans = max(A//x+min(1, A%x), B//y+min(1, B%y))
    A = ans*x
    B = ans*y
print(A+B)

Submission status: Accepted

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

takahasi, aoki = ratio[0]
for i in range(1, N):
    t_ratio, a_ratio = ratio[i]
    n = max(takahasi//t_ratio + min(1, takahasi % t_ratio), aoki//a_ratio + min(1, aoki % a_ratio))
    takahasi = n * t_ratio
    aoki = n * a_ratio

print(takahasi+aoki)

Submission status: Accepted

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

def main():
    N = int(input())
    ta = [list(map(int, input().split())) for i in range(N)]

    a, b = 1, 1
    for i in range(N):
        x, y = ta[i]
        if a%x == 0:
            tmp = a//x
        else:
            tmp = a//x + 1
        if b%y == 0:
            tmp = max(tmp, b//y)
        else:
            tmp = max(tmp, b//y + 1)
        a = x * tmp
        b = y * tmp
    print(a+b)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

pret,prea = TA[0]
for i in range(1,N):
  t,a = TA[i]
  if pret == t and prea == a:
    continue
  elif pret <= t and prea <= a:
    pret,prea = t,a
  else:
    if (pret+t-1)//t > (prea+a-1)//a:
      pret = (pret+t-1)//t * t
      prea = pret // t * a
    else:
      prea = (prea+a-1)//a * a
      pret = prea // a * t
print(pret+prea)

Submission status: Accepted

Solution code:
n=int(input())
vote=list(map(int,input().split()))
for i in range(n-1):
    a,b=map(int,input().split())
    if vote[0]%a==0:
        A=vote[0]//a
    else:A=vote[0]//a+1
    if vote[1]%b==0:
        B=vote[1]//b
    else:B=vote[1]//b+1
    if A>B:
        if B*a>=vote[0]:
            vote[0]=B*a;vote[1]=B*b
        else:
            vote[0]=A*a;vote[1]=A*b
    elif A<B:
        if A*b>=vote[1]:
            vote[0]=A*a;vote[1]=A*b
        else:
            vote[0]=B*a;vote[1]=B*b
    else:
        vote[0]=A*a;vote[1]=A*b
print(sum(vote))

Submission status: Accepted

Solution code:
N = int(input())

nowT = 1
nowA = 1
for i in range(N):
    nextT, nextA = map(int, input().split())

    # mul = max(ceil(nowT / nextT), ceil(nowA / nextA))
    mul = max(-(-nowT // nextT), -(-nowA // nextA))
    nowT = nextT * mul
    nowA = nextA * mul

print(nowT + nowA)

Submission status: Accepted

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

    if y % a == 0:
        lb = y//a
        if lb == 0:
            lb = 1
    else:
        lb = y//a +1

    l = max(la,lb)
    x = t*l
    y = a*l

print(x+y)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=max((t+a+wa-1)//wa,(t+ta[i+1][0]-1)//ta[i+1][0],(a+ta[i+1][1]-1)//ta[i+1][1])
    # while wa*j<t+a or j*ta[i+1][0]<t or j*ta[i+1][1]<a:
    #     j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)

Submission status: Accepted

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


def main():
    n = int(input())
    vote_t, vote_a = 1, 1

    # See:
    # http://arc062.contest.atcoder.jp/data/arc/062/editorial.pdf
    # KeyInsight：各状態で，できるだけ得票数が少ないほうがよい
    # 高橋君にA票，青木君にB票あるとき，満たすべき比率がx：yだとすると，
    # A <= m * x ^ B <= m * yとなるような最小の自然数mを取ればよい
    for i in range(n):
        ti, ai = map(int, input().split())

        # 小数点の処理に注意
        m = max((vote_t - 1) // ti + 1, (vote_a - 1) // ai + 1)
        vote_t = ti * m
        vote_a = ai * m

    print(vote_t + vote_a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
x=0
t=0
n=0
pre_t=1
pre_n=1
for i in range(N):
    t,n = map(int,input().split())
    if(pre_t > t or pre_n > n):
        mul = max(-(-pre_t//t),-(-pre_n//n))
        t *= mul
        n *= mul
    pre_t = t
    pre_n = n
    x = t+n
print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# かんにんぐ
n=int(input())

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

Submission status: Accepted

Solution code:
N = int(input())

tNow = 1
aNow = 1

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

    n = max(-(-tNow // t), -(-aNow // a))

    tNow = n * t
    aNow = n * a

print(tNow + aNow)

Submission status: Accepted

Solution code:
n=int(input())
ta=[]
t=0
a=0
ans=[[1,1]]
for i in range(n):
    p=[int(j) for j in input().split()]
    i=max(ans[-1][0]//p[0],ans[-1][1]//p[1])
    while True:
        if p[0]*i>=ans[-1][0] and p[1]*i>=ans[-1][1]:
            ans.append([p[0]*i,p[1]*i])
            break
        i+=1

print(sum(ans[-1]))

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
L = [[int(i) for i in input().split()] for _ in range(N)]
T = 1
A = 1
for l in L:
    k = max((T+l[0]-1)//l[0], (A+l[1]-1)//l[1])
    T = k * l[0]
    A = k * l[1]
print(T+A)

Submission status: Accepted

Solution code:
a = int(input())
d = e = 0
for i in range(a):
    b, c = map(int, input().split())
    if d <= b and e <= c:
        d = b
        e = c
    else:
        f = max((b + d - 1) // b, (c + e - 1) // c)
        d = b * f
        e = c * f
print(d + e)

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())

x = 1
for i in range(N):
    t = T[i] * x
    a = A[i] * x
    if i == N - 1:
        break
    tx = ((T[i] * x) + (T[i+1] - 1)) // T[i+1]
    ax = ((A[i] * x) + (A[i+1] - 1)) // A[i+1]
    x = max(tx , ax)

print(t + a)

Submission status: Accepted

Solution code:
a = int(input())
d = e = 0
for i in range(a):
    b, c = map(int, input().split())
    if i == 0:
        d = b
        e = c
    else:
        if d <= b and e <= c:
            d = b
            e = c
        else:
            h = max((b + d - 1) // b, (c + e - 1) // c)
            d = b * h
            e = c * h
print(d + e)

Submission status: Accepted

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

ans = 1
ct = 1
ca = 1
for t, a in zip(T, A):
    n = max((ct + t - 1) // t, (ca + a - 1) // a)
    ct = n * t
    ca = n * a

print(ct+ca)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
a = int(input())
b = [list(map(int, input().split()))for _ in range(a)]
c = []
for i in range(len(b)):
    c.append(b[i].copy())
    if len(c) != 1:
        while True:
            if c[i][0] < c[i-1][0] or c[i][1] < c[i-1][1]:
                c[i][0] = b[i][0] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
                c[i][1] = b[i][1] * max((c[i-1][0] + b[i][0] - 1) // b[i][0], (c[i-1][1] + b[i][1] - 1) // b[i][1])
            else:
                break
print(c[len(c)-1][0] + c[len(c)-1][1])

Submission status: Accepted

Solution code:
def solve(v_t, v_a, t, a):
    tmpt = 0
    tmpa = 0
    if v_t % t == 0:
        tmpt = v_t // t
    else:
        tmpt = v_t // t + 1
    if v_a % a == 0:
        tmpa = v_a // a
    else:
        tmpa = v_a // a + 1
    return max(tmpt, tmpa)

N = int(input())
vote_t = 0
vote_a = 0
for i in range(N):
    t, a = map(int,input().split())
    if i == 0:
        vote_t = t
        vote_a = a
    else:
        #ganbaru
        n = solve(vote_t, vote_a, t, a)#t*n >= vote_t and a*n >= vote_tとなる最小のnを求める
        vote_t = t*n
        vote_a = a*n
print(str(vote_t + vote_a))

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
ab=[list(map(int,input().split())) for _ in [0]*n]
l,r=1,1
for i in range(n):
    a,b=ab[i]
    c=max((l-1)//a+1,(r-1)//b+1)
    l=a*c
    r=b*c
print(l+r)

Submission status: Accepted

Solution code:
A, B = 1, 1
for _ in range(int(input())):
    x, y = map(int, input().split())
    n = max(-(-A // x), -(-B // y))
    A, B = n * x, n * y

print(A + B)

Submission status: Accepted

Solution code:
import math
n=int(input())
T,A=map(int,input().split())
for i in range(n-1):
    t,a=map(int,input().split())
    x=T//t if T%t==0 else T//t+1
    y=A//a if A%a==0 else A//a+1
    c=max(x,y)
    T=t*c
    A=a*c

print(A+T)

Submission status: Accepted

Solution code:
N=int(input())
 
X=[]
for i in range(N):
  a=input().split()
  X.append([int(a[0]),int(a[1])])
 
 
a=X[0][0]
b=X[0][1]
 
for i in range(1,N):
  c=X[i][0]
  d=X[i][1]
 

  x= (a + (c - 1)) // c
  y= (b + (d -1)) // d
  
  a1=1000000000000000000
  b1=1000000000000000000
  a2=1000000000000000000
  b2=1000000000000000000
  if d*x-b>=0:
    a1=c*x
    b1=d*x
 
  
  if c*y-a>=0:
    a2=c*y
    b2=d*y
  if (a1+b1)<(a2+b2):
    a=a1
    b=b1
  else:
    a=a2
    b=b2
 
  #print("i = "+str(i)+" a = "+str(a)+" b = "+str(b)+" a1 = "+str(a1)+" b1 = "+str(b1)+" a2 = "+str(a2)+" b2 = "+str(b2)+" c = "+str(c)+" d = "+str(d))
  
 
 
 
 
  
print(a+b)

Submission status: Accepted

Solution code:
N = 1000
def ee(a, b, c):
	arr = [[1,0,a],[0,1,-b]]

	while arr[1][2]!=0:
		for j in range(3):
			arr[0][j] -= arr[1][j]*(arr[0][2]//arr[1][2])
			arr[0][j], arr[1][j] = arr[1][j], arr[0][j]
	
	x0 = c*arr[0][0]
	y0 = c*arr[0][1]
	
	if arr[0][2]==-1:
		x0 *= -1
		y0 *= -1

	t = max(-(x0//b), -(y0//a))

	x0 = x0+b*t
	y0 = y0+a*t

	return x0, y0

def main():
	n = int(input())
	t0, a0 = [int(i) for i in input().split()]

	for ctr in range(1,n):
		t, a = [int(i) for i in input().split()]
		d =  ee(a,t,t*a0-a*t0)
		t0 += d[0]
		a0 += d[1]

	print(t0+a0)

main()

Submission status: Accepted

Solution code:
# ARC062C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report (ABC046C)
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())
T=A=1
for i in range(n):
    t,a=map(int,input().split())
    k=max(-(-T//t),-(-A//a))
    T,A=k*t,k*a
print(T+A)

Submission status: Accepted

Solution code:
import math

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

A, B = 1, 1

for t in TA:
    a = A // t[0]
    b = B // t[1]
    if A % t[0] != 0:
        a += 1
    if B % t[1] != 0:
        b += 1
    n = max(a, b)
    # n = max(math.ceil(A / t[0]), math.ceil(B / t[1]))
    A, B = t[0] * n, t[1] * n

print(A + B)

Submission status: Accepted

Solution code:
N = int(input())
T = [0 for i in range(N)]
A = [0 for i in range(N)]
for i in range(N):
    T[i], A[i] = map(int, input().split())
    
vote_num = A[0] + T[0]
a_num = A[0]
t_num = T[0]
for i in range(1, N):
    #print("nums: ", t_num, a_num, vote_num)
    mult_a = a_num // A[i] if a_num % A[i] == 0 else a_num // A[i] + 1
    mult_t = t_num // T[i] if t_num % T[i] == 0 else t_num // T[i] + 1
    mult_vote = vote_num // (A[i] + T[i]) if vote_num % (A[i] + T[i]) == 0 else vote_num // (A[i] + T[i]) + 1
    #print("mults: ", mult_t, mult_a, mult_vote)
    mult = max(mult_a, mult_t, mult_vote)
    a_num = A[i] * mult
    t_num = T[i] * mult
    vote_num = mult * (A[i] + T[i])

print(vote_num)

Submission status: Accepted

Solution code:
N = int(input())
TA = [[int(_) for _ in input().split()] for _ in range(N)]
tak = TA[0][0]
aok = TA[0][1]

if N == 1:
    print(tak+aok)
else:
    for i in range(1, N):
        nowTrate = TA[i][0]
        nowArate = TA[i][1]
        T = tak//nowTrate if tak % nowTrate == 0 else tak//nowTrate+1
        A = aok//nowArate if aok % nowArate == 0 else aok//nowArate+1
        y = max(T, A)
        tak = nowTrate * y
        aok = nowArate * y
    print(tak+aok)

Submission status: Accepted

Solution code:
N = int(input())
for i in range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = x//a if x%a==0 else x//a+1
    yt = y//t if y%t==0 else y//t+1
    c = max(xa,yt)
    x,y = a*c,t*c
print(x+y)

Submission status: Accepted

Solution code:
N = int(input())
ratio = []
for _ in range(N):
    ratio.append(tuple(map(int, input().split())))
total_t = 1; total_a = 1;
for t, a in ratio:
    q = max((total_t + t - 1) // t, (total_a + a - 1) // a)
    total_t = t*q
    total_a = a*q
ans = total_t + total_a
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
T_current, A_current = 1,1

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

Submission status: Accepted

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

Submission status: Accepted

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

# ans = vote_ratio[0] は同じオブジェクトを参照してしまうので避ける
ans = [vote_ratio[0][0], vote_ratio[0][1]]

for i in range(1,n):
	# bairitsu = max( math.ceil(ans[0] / vote_ratio[i][0]), math.ceil(ans[1] / vote_ratio[i][1]))
	# と書きたいところだが、浮動小数点数を経由したときに不正確になるので代わりにこうする。
	bairitsu = max( 
		(ans[0] + vote_ratio[i][0] - 1)// vote_ratio[i][0],
		(ans[1] + vote_ratio[i][1] - 1)// vote_ratio[i][1])
	ans = [vote_ratio[i][0] * bairitsu, vote_ratio[i][1] * bairitsu]

print(sum(ans))

Submission status: Accepted

Solution code:
# WA math.ceilは浮動小数点演算の影響を受けるので、正しく切り上げできないときがある
# >>> math.ceil((12345678901234*456+0.1)/12345678901234)
# 456
# >>> math.ceil((12345678901234*456+1)/12345678901234)
# 457

import math

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

# ans = vote_ratio[0] は同じオブジェクトを参照してしまうので避ける
ans = [vote_ratio[0][0], vote_ratio[0][1]]

for i in range(1,n):
	bairitsu = max(ans[0] // vote_ratio[i][0], ans[1] // vote_ratio[i][1])
	if vote_ratio[i][0] * bairitsu < ans[0] \
	or vote_ratio[i][1] * bairitsu < ans[1]:
		bairitsu += 1
	ans = [vote_ratio[i][0] * bairitsu, vote_ratio[i][1] * bairitsu]

print(sum(ans))

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)
    
v1 = 1
v2 = 1

for i in range(N):
    n = max((v1+T[i]-1)//T[i],(v2+A[i]-1)//A[i])
    v1 = T[i]*n
    v2 = A[i]*n

print(v1+v2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
TA = [[int(x) for x in input().split()]for _ in range(N)]
t = 1
a = 1

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

print(t+a)

Submission status: Accepted

Solution code:
N = int(input())
t = 1
a = 1
TA = [0]*N
for i in range(N):
    TA[i] = map(int,input().split(" "))

for T,A in TA:
    n = max(t//T+(t%T and 1),a//A+(a%A and 1))
    t = n * T
    a = n * A

print(t+a)