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:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
x, y = 0, 0
n = int(input())
for i in range(n):
    t, a = map(int, input().split())
    if i == 0:
        x = t
        y = a
        continue
    b = -(-x // t)
    c = -(-y // a)
    d = max(b, c)
    x = t * d
    y = a * d
print(x + y)

Submission status: Accepted

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

HYOU = li[0]

def f(a, b):
  syou = b // a
  amari = b % a
  if amari == 0:
    c = syou
  else:
    c = syou + 1
  return c

for i in range(N-1):
  if li[i][0] <= li[i+1][0] and li[i][1] <= li[i+1][1]:
    HYOU = li[i+1]
#    print(HYOU)
  elif li[i][0] <= li[i+1][0] and li[i][1] > li[i+1][1]:
    c = f(li[i+1][1], li[i][1])
    li[i+1] = [li[i+1][0]*c, li[i+1][1]*c]
    HYOU = li[i+1]
#    print("これ")
#    print(HYOU)
  elif li[i][0] > li[i+1][0] and li[i][1] <= li[i+1][1]:
    c = f(li[i+1][0], li[i][0])
    li[i+1] = [li[i+1][0]*c, li[i+1][1]*c]
    HYOU = li[i+1]
#    print(HYOU)
  else:
    c1 = f(li[i+1][1], li[i][1])
#    print("c1は" + str(c1))
    hyou1 = [li[i+1][0]*c1, li[i+1][1]*c1]
#    print("hyou1は" + str(hyou1))
    c2 = f(li[i+1][0], li[i][0])
#    print("c2は" + str(c2))
    hyou2 = [li[i+1][0]*c2, li[i+1][1]*c2]
#    print("hyou2は" + str(hyou2))
    if hyou1[0] <= hyou2[0] and hyou1[0] >= li[i][0] and hyou1[1] >= li[i][1]:
      li[i+1] = hyou1
      HYOU = li[i+1]
#      print(HYOU)
    elif hyou2[0] <= hyou1[0] and hyou2[0] >= li[i][0] and hyou2[1] >= li[i][1]: 
      li[i+1] = hyou2
      HYOU = li[i+1]
#      print(HYOU)
    elif hyou1[0] > hyou2[0] and hyou1[0] >= li[i][0] and hyou1[1] >= li[i][1]:
      li[i+1] = hyou1
      HYOU = li[i+1]
#      print(HYOU)
    elif hyou2[0] > hyou1[0] and hyou2[0] >= li[i][0] and hyou2[1] >= li[i][1]: 
      li[i+1] = hyou2
      HYOU = li[i+1]
#      print(HYOU)


print(sum(HYOU))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))

def main():
  import math
  from fractions import Fraction
  n = int(input())
  x = [1,1]
  for i in range(n):
    au,bu = x
    a,b = [int(i) for i in input().split()]
    
    nya = math.ceil(max(Fraction(au,a),Fraction(bu,b)))
    x = [nya*a, nya*b]
  print(int(sum(x)))
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
TA = []
 
for _ in range(N):
    TA.append([int(x) for x in input().split()])
 
x, y = TA[0]
 
for i in range(1, N):
    X, Y = TA[i]
    if X < x or Y < y:
        mul = max(x // X + (x % X != 0), y // Y + (y % Y != 0))
        x, y = X * mul, Y * mul
    else:
        x, y = X, Y
    #print(x, y)
 
print(x + y)

Submission status: Accepted

Solution code:
icase=0
if icase==0:
    n=int(input())
    t=[0]*n
    a=[0]*n

    for i in range(n):
        t[i],a[i]=map(int,input().split())
elif icase==1:
    n=5
    t=[3,48,31,231,3]
    a=[10,17,199,23,2]
    ans=6930

ti=t[0]
ai=a[0]
dt=1
for i in range(n-1):
    if ti/t[i+1]>ai/a[i+1]:
        ii=max((ti-dt)//t[i+1]+1,1)
        ti=ii*t[i+1]
        ai=ii*a[i+1]
    else:
        ii=max((ai-dt)//a[i+1]+1,1)
        ti=ii*t[i+1]
        ai=ii*a[i+1]

print(ai+ti)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
cur_t = 1
cur_a = 1
for i in range(n):
    t, a = map(int, input().split())
    times = max(-(-cur_t // t), -(-cur_a // a))
    cur_t = t * times
    cur_a = a * times
    # print(cur_t, cur_a)
print(cur_t + cur_a)

Submission status: Accepted

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

T=X[0][0]
A=X[0][1]

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

Submission status: Accepted

Solution code:

def func(n,x):
    if n%x!=0:
        return n+(x-n%x)
    else:
        return n
X=[]
n=int(input())
for i in range(n):
    t,a=map(int,input().split())
    X.append([t,a])

T=X[0][0]
A=X[0][1]

for i in range(1,n):
    if T<=X[i][0] and A<=X[i][1]:
        T=X[i][0]
        A=X[i][1]
    elif T>X[i][0] and A<=X[i][1]:
        T=func(T,X[i][0])
        A=T*X[i][1]//X[i][0]
    elif T<=X[i][0] and A>X[i][0]:
        A=func(A,X[i][1])
        T=A*X[i][0]//X[i][1]
    else:
        T=func(T,X[i][0])
        A=func(A,X[i][1])
        if T>A*X[i][0]//X[i][1]:
            A=T*X[i][1]//X[i][0]
        else:
            T=A*X[i][0]//X[i][1]
print(T+A)

Submission status: Accepted

Solution code:
import math

#in1 = '5'
#in2 = ['1 2','2 1','1 1','3 1','1 1']
#n = int(in1)
n = int(input())

tall = 1
aall = 1
for idx1 in range(n):
    t, a = map(int, input().split())
    #t, a = map(int, in2[idx1].split())
    mul = max(-(-tall // t), -(-aall // a))
    tall, aall = t * mul, a * mul
    #print(tall, aall)

print(tall + aall)

Submission status: Accepted

Solution code:
n = int(input())
t = [0] * n
a = [0] * n
for i in range(n):
    tt, aa = map(int, input().split())
    t[i], a[i] = tt, aa

if n == 1:
    print(t[0]+a[0])
else:
    for i in range(1, n):
        for j in range(max(t[i-1]//t[i], a[i-1]//a[i]), 10**18):
            if t[i]*j >= t[i-1] and a[i]*j >= a[i-1]:
                t[i], a[i] = t[i] * j, a[i] * j
                break
    print(t[n-1]+a[n-1])

Submission status: Accepted

Solution code:
N = int(input())

tak = 1
aok = 1

for _ in range(N):
    t, a = map(int, input().split())
    d = max(-(-aok // a), -(-tak // t))
    tak, aok = t * d, a * d

print(tak + aok)

Submission status: Accepted

Solution code:
N = int(input())
T, A = [0]*N, [0]*N

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

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)
a=1
b=1
for i in range(N):
  n=max((a+T[i]-1)//T[i], (b+A[i]-1)//A[i])
  a=n*T[i]
  b=n*A[i]
print(a+b)

Submission status: Accepted

Solution code:
N = int(input())

l = [0, 0]
for _ in range(N):
    t, a = map(int, input().split())
    if t >= l[0] and a >= l[1]:
        l = [t, a]
    else:
        temp = max((l[0] - 1) // t + 1, (l[1] - 1) // a + 1)
        l = [t * temp, a * temp]
    
print(sum(l))

Submission status: Accepted

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

a = 1
b = 1
for ti, ai in zip(T,A):
    #n = max(math.ceil(a/ti),math.ceil(b/ai))
    n = max((a+ti-1)//ti,(b+ai-1)//ai)
    a = n*ti
    b = n*ai
    #print(a,b)
print(a+b)

Submission status: Accepted

Solution code:
n = int(input())
t = 1
a = 1
for i in range(n):
    next_t, next_a = map(int, input().split())
    kake_t = (t + next_t - 1) // next_t
    kake_a = (a + next_a - 1) // next_a
    kake = max(kake_t, kake_a)
    t = next_t * kake
    a = next_a * kake
print(int(a + t))

Submission status: Accepted

Solution code:
n=int(input())
f=lambda:map(int,input().split())
a,b=f()
for _ in range(1,n):
  c,d=f()
  t=max(1,0--a//c,0--b//d)
  a,b=c*t,d*t
print(a+b)

Submission status: Accepted

Solution code:
N=int(input())
T=1
A=1
for i in range(N):
    x,y=map(int,input().split())
    d1=1
    d2=1
    if T>x:
        d1=(T-1)//x+1
    if A>y:
        d2=(A-1)//y+1
    T=max(d1,d2)*x
    A=max(d1,d2)*y

print(T+A)

Submission status: Accepted

Solution code:
n = int(input())
ta = [list(map(int, input().split())) for _ in range(n)]
pt, pa = 1, 1
for i in range(n):
    t, a = ta[i]
    v = max((pt + t - 1) // t, (pa + a - 1) // a)
    pt = v * t
    pa = v * a

print(pt + pa)

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())
curt=t[0]
cura=a[0]
for i in range(1,n):
    if t[i]>=curt and a[i]>=cura:
        curt=t[i]
        cura=a[i]
    else:
        kt=curt//t[i]
        if curt%t[i]:
            kt+=1
        ka=cura//a[i]
        if cura%a[i]:
            ka+=1

        k=max(kt,ka)
        curt=t[i]*k
        cura=a[i]*k
print(curt+cura)

Submission status: Accepted

Solution code:
N = int(input())


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


T, A = 1, 1
for _ in range(N):
    Tt, At = map(int, input().split())
    x = max(ceil(T , Tt), ceil(A , At))
    T, A = Tt * x, At * x
print(T + A)

Submission status: Accepted

Solution code:
t = int(input())
par = [0, 0]
for i in range(t):
	p, t = map(int, input().split())
	if p >= par[0] and t >= par[1]:
		par = [p, t]
	else:
		n = max((par[0]-1)//p + 1, (par[1]-1)//t +1)
		par = [p*n, t*n]
print(sum(par))

Submission status: Accepted

Solution code:
from decimal import Decimal
from math import ceil

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

t_voted = a_voted = 1
for t, a in ratio:
    val = max(ceil(Decimal(t_voted) / Decimal(t)), ceil(Decimal(a_voted) / Decimal(a)))
    t_voted = t * val
    a_voted = a * val

print(t_voted + a_voted)

Submission status: Accepted

Solution code:
import fractions
N=int(input())
T,A=map(int,input().split())
for i in range(1,N):
    nT,nA=map(int,input().split())
    if(nT>=T and nA>=A):
        T,A=nT,nA
        continue
    pT,pA=T//nT,A//nA
    if(T%nT!=0):
        pT+=1
    if(A%nA!=0):
        pA+=1
    T,A=nT*max(pT,pA),nA*max(pT,pA)
print(T+A)

Submission status: Accepted

Solution code:
from sys import stdin
from operator import itemgetter
# stdin = open("sample.txt")

N = int(stdin.readline().rstrip())
hyo = [0,0]
ans = [0,0]

for i in range(N):
    hyo[0],hyo[1] = [int(x) for x in stdin.readline().rstrip().split()]

    if ans[0]<=hyo[0] and ans[1]<=hyo[1]:
        ans[0] = hyo[0]
        ans[1] = hyo[1]
    elif ans[0]>hyo[0] and ans[1]>hyo[1]:
        if ans[0]%hyo[0] == 0:
            which1 = ans[0]//hyo[0]
        else:
            which1 = ans[0]//hyo[0]+1
        if ans[1]%hyo[1] == 0:
            which2 = ans[1]//hyo[1]
        else:
            which2 = ans[1]//hyo[1]+1
        if which1 >= which2:
            which = which1
        else:
            which = which2
        ans[0] = hyo[0] * which
        ans[1] = hyo[1] * which
    elif ans[0]>hyo[0]:
        left = ans[0]//hyo[0]
        if ans[0]%hyo[0] == 0:
            ans[0] = hyo[0]*left
            ans[1] = hyo[1]*left
        else:
            ans[0] = hyo[0]*(left+1)
            ans[1] = hyo[1]*(left+1)
    elif ans[1]>hyo[1]:
        right = ans[1]//hyo[1]
        if ans[1]%hyo[1] == 0:
            ans[0] = hyo[0]*right
            ans[1] = hyo[1]*right
        else:
            ans[0] = hyo[0]*(right+1)
            ans[1] = hyo[1]*(right+1)
    # print(ans)

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

Submission status: Accepted

Solution code:
n = int(input())
before = [0, 0]
for i in range(n):
    t, a = map(int, input().split())
    if t >= before[0] and a >= before[1]:
        before = [t, a]
    else:
        mul = max((before[0]-1)//t+1, (before[1]-1)//a+1)
        before = [t*mul, a*mul]

print(sum(before))

Submission status: Accepted

Solution code:
import math

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

x = l[0]
for i in range(1,n):
    #y = math.ceil(x[0] / l[i][0]) # 'ceil'では 'WA'.
    #z = math.ceil(x[1] / l[i][1]) # 'ceil'では、商が桁の大きなfloatの場合、高次桁で結果に狂いが生じる.
    y = -(-x[0] // l[i][0])
    z = -(-x[1] // l[i][1])
    x = [max(y, z) * j for j in l[i]]

print(sum(x))

Submission status: Accepted

Solution code:
import math

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

x = l[0]
for i in range(1,n):
    #y = math.ceil(x[0] / l[i][0]) # 'ceil'は、商がfloatで桁が大きい場合、高次桁で結果に狂いが生じる.
    #z = math.ceil(x[1] / l[i][1]) # 同上
    y = -(-x[0] // l[i][0])
    z = -(-x[1] // l[i][1])
    x = [max(y, z) * j for j in l[i]]

print(sum(x))

Submission status: Accepted

Solution code:
n = int(input())
ta = [list(map(int,input().split())) for _ in range(n)]
ans = [ta[0][0],ta[0][1]]
for i in range(1,n):
  if ans[0] / ta[i][0] <= 1 and ans[1] / ta[i][1] <= 1:
    ans[0] = ta[i][0]
    ans[1] = ta[i][1]
  else:
    x = max(-(-ans[0]//ta[i][0]),-(-ans[1]//ta[i][1]))
    ans[0] = ta[i][0]*x
    ans[1] = ta[i][1]*x
print(sum(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
a=A[0][0]
b=A[0][1]
import fractions
for i in range(1,N):
  if a<=A[i][0] and b<=A[i][1]:
    a=A[i][0] 
    b=A[i][1]
  else:
    aa=1
    bb=1
    if a>A[i][0]:
      if a%A[i][0]==0:
        aa=a//A[i][0]
      else:
        aa=1+a//A[i][0]
    if b>A[i][1]:
      if b%A[i][1]==0:
        bb=b//A[i][1]
      else:
        bb=1+b//A[i][1]
    c=max(aa,bb)
    a=c*A[i][0]
    b=c*A[i][1]
print(a+b)

Submission status: Accepted

Solution code:
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
a,b=1,1
for i in range(n):
  l=-min(-a//ta[i][0],-b//ta[i][1])
  a=ta[i][0]*l
  b=ta[i][1]*l
print(a+b)

Submission status: Accepted

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)


def main():
    n = int(input())
    senkyo = [tuple(map(int,input().split())) for _ in range(n)]
    
    last_t,last_a = senkyo[-1]
    
    def ok(x):
        t = x * last_t
        a = x * last_a
        flag = True
        for i in range(n - 2, -1, -1):
            ti,ai = senkyo[i]
            y = min(t//ti,a//ai)
            t = y * ti
            a = y * ai
            if a == 0 :
                flag = False
                break
        return flag
    
    r = 10 ** 18
    l = 0
    while r - l > 1:
        mid = (r + l)//2
        if ok(mid):
            r = mid
        else:
            l = mid
    
    print(r * (last_a + last_t))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

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

def main():
	n = int(input())
	a, t = IN()
	for _ in range(n-1):
		ap, tp = IN()
		aa=ww(a,ap)
		ta=ww(t,tp)
		rr=max(aa,ta)
		a,t=ap*rr, tp*rr
	return a+t
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc046/tasks/arc062_a
# 条件を考えよう
# iのときの割合の人数n[i],m[i]を考えると
# n[i]=p*A[i], m[i]=p*B[i] かつ n[i]>=n[i-1], m[i]>=m[i-1] を満たす最小のn[i], m[i]
# このような条件を満たすpを探すのは容易だ
# n[i-1]//A[i] がn[i]をギリギリ超えないpなのだから、ギリギリ超えるpはn[i-1]//A[i] + 1 (ぴったり割り切れるときは注意)
# nについてもmについてもギリギリ越したいのだから大きい方を採用する。(小さい方では片方が超えなくなる)


N = int(input())
ans = 1


def ret_nm(t, a, n, m):
    times_t = (n - 1) // t + 1
    times_a = (m - 1) // a + 1
    times = max(times_t, times_a)
    return times * t, times * a


n = m = 1
for _ in range(N):
    t, a = map(int, input().split())
    n, m = ret_nm(t, a, n, m)


print(n + m)

Submission status: Accepted

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

#print()
T = 0
A = 0
for i in range(n):
    t, a = p[i]
    if t >= T and a >= A:
        T, A = t, a
    else:
        d1 = T // t
        d2 = A // a
        if T % t != 0: d1 += 1
        if A % a != 0: d2 += 1
        d = max(d1, d2)
        T, A = d * t, d * a
    #print(T, A)

print(T+A)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
T = []
A = []
for i in range(N) :
    p, q = map(int,input().split())
    T.append(p)
    A.append(q)

Tak = T[0]
Aok = A[0]
for i in range(1, N) :
    Tb = (Tak + T[i] - 1) // T[i]
    Ab = (Aok + A[i] - 1) // A[i]
    Tak = T[i] * max(Tb, Ab)
    Aok = A[i] * max(Tb, Ab)

print(Tak + Aok)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    NT=1
    NA=1
    for i in range(N):
        T,A=MI()
        xt=(NT+T-1)//T
        xa=(NA+A-1)//A
        x=max(xt,xa)
        NT=T*x
        NA=A*x
    print(NT+NA)
            

main()

Submission status: Accepted

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

T = A = 1
for t, a in TA:
  r = max(A//a, T//t)
  if r*a >= A and r*t >= T:
    A = r*a; T = r*t
  else:
    A = (r+1)*a; T = (r+1)*t

print(T+A)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
# C - AtCoDeerくんと選挙速報
from math import ceil
n=int(input())
t,a=1,1
for i in range(n):
    tt,aa=map(int,input().split())
    min_num=max(-(-t//tt),-(-a//aa))
    # min_num=max(ceil(t/tt),ceil(a/aa))
    t=min_num*tt
    a=min_num*aa
print(t+a)

Submission status: Accepted

Solution code:
import math
n = int(input())
T = [0]*n
A = [0]*n
Tvote = [0]*n
Avote = [0]*n

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

for k in range(n):
    if k == 0:
        Tvote[k] = T[k]
        Avote[k] = A[k]
    else:
        '''
        j = math.ceil(max(Tvote[k-1]/T[k],Avote[k-1]/A[k]))
        print(Tvote[k-1]/T[k])
        print(Avote[k-1]/A[k])
        print(max(Tvote[k-1]/T[k],Avote[k-1]/A[k]))
        print(j)
        print(Avote[k-1], A[k]*j)
        print(bool(Avote[k-1]<A[k]*j))
        print(bool(j>Avote[k-1]/A[k]))
        '''
        j = int(min(Tvote[k-1]//(-T[k]),Avote[k-1]//(-A[k])))*-1
        #普通に割り算やると誤差で死ぬ（floatがむずい。）
        # // は整数の除算で常に負の無限大方向に丸められる
        #一度も float になることがないはずなので、正しい計算結果が出る
        #https://paiza.hatenablog.com/entry/2017/08/01/Python3%E3%81%A7%E5%B7%A8%E5%A4%A7%E3%81%AA%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E8%A8%88%E7%AE%97%E3%81%AE%E7%B5%90%E6%9E%9C%E3%81%8C%E5%A4%89%E3%81%A0%E3%81%A3%E3%81%9F%E3%81%AE%E3%81%A7%E7%90%86
        #正の無限大方向に丸めたいので-1かけてから計算して（丸めて）あとで-1かける。その際Av/AとTv/Tの比較も逆をとるのに注意
#        j = 1
#        while Tvote[k-1]>j*T[k] or Avote[k-1]>j*A[k]:
#            j += 1
#これは投票数が多すぎるのでTLE
        Tvote[k] = j*T[k]
        Avote[k] = j*A[k]
#    print("---input:{}:{}--vote{}:{}--diff{}".format(T[k],A[k],Tvote[k],Avote[k],bool(T[k]/A[k]==Tvote[k]/Avote[k])))   

#print("---Tvote:{}".format(Tvote))
#print("---Avote:{}".format(Avote))
#print('hoge')
#for i in range(n):
#    print(Tvote[i],Avote[i])
print(Tvote[n-1]+Avote[n-1])

Submission status: Accepted

Solution code:
from math import ceil
N = int(input())
T, A = 1, 1
for k in range(N):
    t, a = map(int,input().split())
    b = max(T//t,A//a)
    if t*b < T or a*b < A:
        b += 1
    T, A = t*b, a*b
print(T+A)

Submission status: Accepted

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

n = int(readline())
t,a = 0,0
for i in range(n):
    rt,ra = map(int,readline().split())
    x = max((t-1)//rt+1,(a-1)//ra+1)
    t = rt*x
    a = ra*x
    if a+t == 0:
        t += rt
        a += ra

print(t+a)

Submission status: Accepted

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

N = int(input())
TA = []

for _ in range(N):
    TA.append([int(x) for x in input().split()])

x, y = TA[0]

for i in range(1, N):
    X, Y = TA[i]
    if X < x or Y < y:
        mul = max(x // X + (x % X != 0), y // Y + (y % Y != 0))
        x, y = X * mul, Y * mul
    else:
        x, y = X, Y
    # print(x, y)

print(x + y)

Submission status: Accepted

Solution code:
from math import ceil
 
n = int(input())
a = 1
b = 1
 
for i in range(n):
    s,t = map(int,input().split())
    #x = max([ceil(a/s), ceil(b/t)])
    x = max((a+s-1)//s, (b+t-1)//t)

 
    a = x*s
    b = x*t

print(a+b)

Submission status: Accepted

Solution code:
N = int(input())
T,A = map(int,input().split())
for i in range(N-1):
    t,a = map(int,input().split())
    T1 = (T+t-1)//t*t
    A1 = (T+t-1)//t*a
    T2 = (A+a-1)//a*t
    A2 = (A+a-1)//a*a
    if A1 < A:
        T,A = T2,A2
    else:
        T,A = T1,A1
print(T+A)

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    m = -min(-pret//t,-prea//a)
    pret = m * t
    prea = m * a
print(pret + prea)

Submission status: Accepted

Solution code:
N = int(input())
# 初回は単純に人数として加算
T, A = map(int, input().split())

for _ in range(N - 1):
    t_i, a_i = map(int, input().split())

    # 比率を考えると総人数は T, A = n*t_i, n*a_i の形になる
    # 必ず現在のT, A以上となるnの値を考える
    n = max(-(-T // t_i), -(-A // a_i))

    # 更新
    T, A = n * t_i, n * a_i

print(T + A)

Submission status: Accepted

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

XY = [TA[0]]

for i in range(1, n):
    x0, y0 = XY[i-1]
    x1, y1 = TA[i]
    xq, xr = divmod(x0, x1)
    yq, yr = divmod(y0, y1)
    if xr != 0:
        xq += 1
    if yr != 0:
        yq += 1
    q = max(xq, yq)
    x1, y1 = x1*q, y1*q
    XY.append([x1, y1])
    
print(sum(XY[-1]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

a, b = ta[0]
for i in range(n):
    x, y = ta[i]
    z = max(-(-a//x), -(-b//y))
    a = x * z
    b = y * z

ans = a + b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

N = int(input())
tak, aok = 1, 1
for _ in range(N):
    T, A = map(int, input().split())
    if T == A:
        tak = aok = max(tak, aok)
    else:
        f = (tak + T - 1) // T
        t = f * T
        a = f * A
        if a >= aok:
            tak = t
            aok = a
        else:
            f = (aok + A - 1) // A
            tak = f * T
            aok = f * A
print(tak + aok)

Submission status: Accepted

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

Submission status: Accepted

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

    a = num*c
    b = num*d
print(a+b)

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

chlist = votelist[0]
for i in range(1, n):
    x = max(-(chlist[0]*-1 // votelist[i][0]), -(chlist[1]*-1 // votelist[i][1]))
    chlist[0] = votelist[i][0] * x
    chlist[1] = votelist[i][1] * x
    
print(sum(chlist))

Submission status: Accepted

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

nowt,nowa=TA[0]
for t,a in TA[1:]:
  c=max(-(-nowt//t),-(-nowa//a))
  nowt,nowa=c*t,c*a
print(nowt+nowa)

Submission status: Accepted

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

T, A = TA[0]
answer = T+A
p = 1
prev = p
pT, pA = T, A
for i in range(1,N):
    # (T+A) * p >= prev
    # p >= prev/(T+A)
    T, A = TA[i]
    s = T+A
    p = (answer+s-1)//s
    p1 = (pT+T-1)//T
    p2 = (pA+A-1)//A
    p = max([p,p1,p2])
    pT, pA = p*T, p*A
    answer =  pT+pA
    #print(T, A, p, answer, sep="\t")
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
ta = [list(map(int, input().split())) for _ in range(N)]
t = 1
a = 1
for i in range(N):
    if t % ta[i][0] != 0:
        ttmp = t // ta[i][0] + 1
    else:
        ttmp = t // ta[i][0]

    if a % ta[i][1] != 0:
        atmp = a // ta[i][1] + 1
    else:
        atmp = a // ta[i][1]
    n = max(ttmp, atmp)
    t = (n * ta[i][0])
    a = (n * ta[i][1])

print(t + a)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
t, a = map(int, input().split())
x = gcd(t,a)
pT = t//x
pA = a//x
for i in range(1,N):
  t, a = map(int, input().split())
  mt = pT//t+1 if pT%t!=0 else pT//t
  ma = pA//a+1 if pA%a!=0 else pA//a
  m = max(mt,ma)
  pT = t*m
  pA = a*m

print(pT+pA)

Submission status: Accepted

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

ta_cur = list(ta[0])
for i in range(1, n):
  hi = max(-(ta_cur[0]*-1 // ta[i][0]), -(ta_cur[1]*-1 // ta[i][1]))
  ta_cur[0] = ta[i][0] * hi
  ta_cur[1] = ta[i][1] * hi

print(sum(ta_cur))

Submission status: Accepted

Solution code:
from math import ceil

n = int(input())
a = 1
b = 1

for i in range(n):
    s,t = map(int,input().split())
    #x = max([ceil(a/s), ceil(b/t)])
    x = max((a+s-1)//s, (b+t-1)//t)

    a = x*s
    b = x*t

print(a+b)

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

pre_T=0
pre_A=0

def krag(n,m):
    return -(-n//m)


for _ in range(N):
    T,A=map(int,input().split())
    
    if T<pre_T or A<pre_A:
        k=max(krag(pre_T,T),krag(pre_A,A))
        T*=k
        A*=k
    
    pre_T,pre_A=T,A    
print(T+A)