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
import math
from decimal import Decimal


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
from decimal import Decimal

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import ceil
from decimal import *

N = int(input())
A,B = 1,1

for i in range(N):
	nums = [int(x) for x in input().split()]
	x,y = nums[0],nums[1]
	n = Decimal(max(ceil(A/x),ceil(B/y)))
	A,B = x*n, y*n
print(A+B)

Submission status: Accepted

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

votes = rates[0]
for i in range(1,N):
    rate_t = rates[i][0]
    rate_a = rates[i][1]
    min_t = votes[0] / rate_t + (1 if votes[0] % rate_t > 0 else 0)
    min_a = votes[1] / rate_a + (1 if votes[1] % rate_a > 0 else 0)
    mag = max(min_t, min_a)
    votes = (rate_t * mag, rate_a * mag)

print sum(votes)

Submission status: Accepted

Solution code:
N = int(raw_input())
p, q = 1, 1
for i in range(N):
    T, A = map(int, raw_input().split())
    k = max((T+p-1) / T, (A+q-1) / A)
    p, q = k*T, k*A
print (p+q)

Submission status: Accepted

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

n = input()
vote_t = 1
vote_a = 1
for i in range(n):
    t,a = map(int,raw_input().split())
    multiple_t = (vote_t+t-1) / t
    multiple_a = (vote_a+a-1) / a
    multiple = max(multiple_t,multiple_a)
    vote_t = t*multiple
    vote_a = a*multiple
print(vote_t + vote_a)

Submission status: Accepted

Solution code:
import sys
import math
 
"n = list(map(int,input().split()))[0] // WA"
n = int(input())
T,A = 1,1
for i in range(n):
    t,a = map(int,input().split(" "))
    coef = max((T+t-1)//t,(A+a-1)//a)
    T,A = coef * t, coef * a 
print(T+A)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N = int(input())
    s, b = 0, 0

    for loop in range(N):
        t, a = map(int, sys.stdin.readline().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

    ans = s + b
    print(ans)



if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
    
t_num , a_num = 1, 1
for t, a in [map(int, input().split()) for _ in range(n)]:
    pre_t_num, pre_a_num = t_num, a_num
    t_num, a_num = t, a
    if t_num < pre_t_num or a_num < pre_a_num:
        t_k = (pre_t_num + t - 1) // t
        a_k = (pre_a_num + a - 1) // a
        m = max(t_k, a_k)
        t_num, a_num = t * m, a * m

ans = t_num + a_num
print()
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

t_num , a_num = 1, 1

for t, a in [map(int, input().split()) for _ in range(n)]:
    pre_t_num, pre_a_num = t_num, a_num
    t_num, a_num = t, a
    if t_num < pre_t_num or a_num < pre_a_num:
        # m = m + 1
        t_k = (pre_t_num + t - 1) // t
        a_k = (pre_a_num + a - 1) // a
        m = max(t_k, a_k)
        t_num, a_num = t * m, a * m

ans = t_num + a_num
print()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
T = []
A = []
Nb = 0
for i in range(N):
    a, b = map(int,input().split())
    T.append(a)
    A.append(b)
Tn = 1
An = 1
for i in range(N):
        tmp = max((Tn+T[i]-1) // T[i], (An+A[i]-1) // A[i])
        Tn = T[i] * tmp
        An = A[i] * tmp
print(Tn + An)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
n=int(input())
t,a=1,1
for i in range(n):
    ti,ai=map(int,input().split())
    m=max(math.ceil(t/ti), math.ceil(a/ai))
    while t > ti*m or a > ai*m:
        m+=1
    while t <= ti*(m-1) and a <= ai*(m-1):
        m-=1
    t,a=ti*m,ai*m
print(t+a)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import math
from decimal import *
N = int(input())
A, B = (1, 1)
for tmp in range (N):
    t, a = map(int,input().split())
    n = Decimal(max([math.ceil(A/t),math.ceil(B/a)]))
    A = n*t
    B = n*a
print(A+B)

Submission status: Accepted

Solution code:
import math
from decimal import Decimal
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())

minT = T[0]
minA = A[0]

for i in range(1, N):
	tmpT = T[i]
	tmpA = A[i]
	# rate = 1
	rate = Decimal(max(math.ceil(minT/tmpT), math.ceil(minA/tmpA)))
	# if tmpT<minT or tmpA<minA:
		# rate = max(int((minT-1)/tmpT)+1, int((minA-1)/tmpA)+1)
		# rate = max(math.ceil(minT/tmpT), math.ceil(minA/tmpA))
	minT = tmpT*rate
	minA = tmpA*rate
print(minT+minA)

Submission status: Accepted

Solution code:
N = int(raw_input())
TA = [map(int, raw_input().split()) for _ in range(N)]
nt, na = 1, 1
for t, a in TA:
    xt = nt / t
    if nt % t != 0:
        xt += 1
    xa = na / a
    if na % a != 0:
        xa += 1
    x = max(xt, xa)
    nt, na = t*x, a*x
print nt + na

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import count
from math import ceil
from fractions import Fraction

def main():
    n = int(input())
    A, B = map(int, input().split())
    for _ in range(n - 1):
        t, a = map(int, input().split())
        n = ceil(max(Fraction(A, t), Fraction(B, a)))
        A, B = n * t, n * a

    print(A + B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(raw_input())

T = []
A = []

for n in range(N):
	t,a = [int(x) for x in raw_input().split(" ")]
	T.append(t)
	A.append(a)

cntA = A[0]
cntT = T[0]

for i in range(N-1):
	if A[i+1] < cntA or T[i+1] < cntT:
		x = -(-cntA // A[i+1]) 
		y = -(-cntT // T[i+1])

		cntA = max(x,y) * A[i+1]
		cntT = max(x,y) * T[i+1]


	else:
		cntA = A[i+1]
		cntT = T[i+1]

print cntA + cntT

Submission status: Accepted

Solution code:
import math

n = int(input())
ta = [[int(i) for i in input().split()] for j in range(n)]

a = 1
b = 1
for i in range(n):
    #n = max(math.floor(a/ta[i][0]), math.floor(b/ta[i][1]))
    n = max(~-a//ta[i][0] + 1, ~-b//ta[i][1] + 1)
    a = n * ta[i][0]
    b = n * ta[i][1]

print(a+b)

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline())

A = B = 1

for _ in xrange(n):
    a, b = map(int, sys.stdin.readline().split())
    k = max(B/b,A/a)
    while k * a < A or k * b < B:
        k += 1
    A= k*a
    B= k*b
print A+B

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8
import math

def f(n,m):
    return n//m + (0 if n%m==0 else 1)

N=int(input())
T,A=1,1
for i in range(N):
    t_i,a_i=list(map(int,input().split()))

    if T<=t_i and A<=a_i:
        T,A=t_i,a_i
    else:
        raito=max(f(T,t_i),f(A,a_i))
        T,A=t_i*raito,a_i*raito

print(T+A)

Submission status: Accepted

Solution code:
N = int(input())
l = 1
r = 1

for k in range(N):
	T, A = map(int, input().split())
	if l % T != 0:
		l += (T - l % T)
	if r % A != 0:
		r += (A - r % A)

	if l//T == r//A:
		()
	elif l//T > r//A:
		r = (l//T) * A
	else:
		l = (r//A) * T
print(l+r)

Submission status: Accepted

Solution code:
from math import ceil
from fractions import Fraction


def main():
    N = int(input())
    t, a = 1, 1
    for _ in range(N):
        _t, _a = map(int, input().split())
        n = ceil(max(Fraction(t, _t), Fraction(a, _a)))
        t, a = _t * n, _a * n
    print(t + a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from decimal import Decimal


def main():
    N = int(input())
    t, a = 1, 1
    for _ in range(N):
        _t, _a = map(int, input().split())
        n = Decimal(max(math.ceil(t / _t), math.ceil(a / _a)))
        t, a = _t * n, _a * n

    print(t + a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#abc046_c

def f(n,d):
 if n%d==0:
  return n/d
 else:
  return n/d+1
 
n=int(raw_input())
t0,a0=map(int,raw_input().split())
for i in range(n-1):
 tt,aa=map(int,raw_input().split())
 m=max(f(t0,tt),f(a0,aa))
 t0=tt*m
 a0=aa*m
print t0+a0

Submission status: Accepted

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

from math import *
from decimal import Decimal

N = int(input())
T, A = 1, 1

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

print(T + A)

Submission status: Accepted

Solution code:
def f(t2,t1):
    return t2//t1 + (1 if t2 % t1 > 0 else 0)

n = int(input())
t,a = map(int,input().split())
for i in range(n-1):
    tn,an = map(int,input().split())
    k = max(f(t,tn), f(a, an))
    t,a = k*tn, k*an
print(t+a)

Submission status: Accepted

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

Tn=1
An=1

for i in range(N):
    T_res=Tn%T[i]
    A_res=An%A[i]
    if T_res==0:
        T_q=Tn/T[i]
    else:
        T_q=(Tn+T[i]-T_res)/T[i]
    if A_res==0:
        A_q=An/A[i]
    else:
        A_q=(An+A[i]-A_res)/A[i]

    q=max(T_q,A_q)

    Tn=q*T[i]
    An=q*A[i]
        
        
print Tn+An

Submission status: Accepted

Solution code:
t, a = 1, 1
for i in range(input()):
    tn, an = map(int, raw_input().split())
    mlt = max(-(-t // tn), -(-a // an))
    t, a = tn * mlt, an * mlt
print t + a

Submission status: Accepted

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

def main():
	n = int(raw_input())
	tmp = raw_input().split()
	tmpt = int(tmp[0])
	tmpa = int(tmp[1])
	for i in range(1, n):
		inpt = raw_input().split()
		inptt = int(inpt[0])
		inpta = int(inpt[1])
		trate = tmpt / inptt
		if tmpt % inptt != 0:
			trate += 1
		arate = tmpa / inpta
		if tmpa % inpta != 0:
			arate += 1
		rate = larger(trate, arate)
		tmpt = inptt * rate
		tmpa = inpta * rate

	print (tmpt + tmpa)

main()

Submission status: Accepted

Solution code:
p=q=1
for i in range(0,int(raw_input())):
 r,s=map(int,raw_input().split())
 t=max((p+r-1)/r,(q+s-1)/s)
 p=r*t
 q=s*t
print p+q

Submission status: Accepted

Solution code:
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1.0
ah = 1.0

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

while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(f1(th,x),f1(ah,y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(int(th+ah))

Submission status: Accepted

Solution code:
import math
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1
ah = 1
while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max((th+x-1)//x, (ah+y-1)//y)
     th = m*x
     ah = m*y
     h += 1
print(th+ah)

Submission status: Accepted

Solution code:
import math
from decimal import Decimal
n = int(input())
i = 0
list = []
while i < n:
   list.append(input().split())
   i += 1
h = 0
th = 1
ah = 1
while h < n:
     listh = list[h]
     x = int(listh[0])
     y = int(listh[1])
     m = max(math.ceil(th/x),math.ceil(ah/y))
     th = Decimal(m*x)
     ah = Decimal(m*y)
     h += 1
print(th+ah)

Submission status: Accepted

Solution code:
n = input()

t, a = 1, 1

for i in range(n):
    xs = map(int, raw_input().split())
    m = max((t + xs[0] - 1) / xs[0], (a + xs[1] - 1) / xs[1])
    t, a = xs[0] * m, xs[1] * m

print t + a

Submission status: Accepted

Solution code:
# C
from math import ceil
N = int(input())
T = [[int(i) for i in input().split()] for n in range(N)]
m = T[0]

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

for n in range(1, N):
    a = max(hoge(m[0],T[n][0]), hoge(m[1],T[n][1]))
    m = [T[n][0] * a, T[n][1] * a]
print(sum(m))

Submission status: Accepted

Solution code:
#!/usr/bin/python2

import sys

n = int(sys.stdin.readline())
A = B = 1

for _ in xrange(n):
    a, b = map(int, sys.stdin.readline().split())
    k = max(B/b, A/a)
    while k * b < B or k * a < A:
        k += 1
    A = k * a
    B = k * b
print A + B

Submission status: Accepted

Solution code:
try:
    N = int(raw_input())
    ab = map(int, raw_input().split(" "))
    a = ab[0]
    b = ab[1]
    for i in range(N-1):
      ab = map(int, raw_input().split(" "))
      A = ab[0]
      B = ab[1]
      if (a < A and b < B):
        a = A
        b = B
      else:
        if (-(-a/A) > -(-b/B)):
          a = A*(-(-a/A))
          b = B*(-(-a/A))
        else:
          b = B*(-(-b/B))
          a = A*(-(-b/B))
    print a+b
except EOFError:
    pass

Submission status: Accepted

Solution code:
n = int(input())

t, a = map(int,input().split())
vote1 = t
vote2 = a

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

    num1 = (vote1 + t - 1) // t
    num2 = (vote2 + a - 1) // a

    if num1 >= num2:
        vote1 = num1 * t
        vote2 = num1 * a
    else:
        vote1 = num2 * t
        vote2 = num2 * a

print(vote1 + vote2)

Submission status: Accepted

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

tmp_t = T[0]
tmp_a = A[0]
ans = tmp_t + tmp_a
for i in range(1, N):
    n_t = tmp_t // T[i] if tmp_t % T[i] == 0 else tmp_t // T[i] + 1
    n_a = tmp_a // A[i] if tmp_a % A[i] == 0 else tmp_a // A[i] + 1
    n = max(n_t, n_a)
    tmp_t = T[i] * n
    tmp_a = A[i] * n
    ans = tmp_t + tmp_a

print(ans)

Submission status: Accepted

Solution code:
n = int(raw_input())
ta_list = []
x, y = 1, 1
for i in range(n):
    # ta_list.append(map(int, raw_input().split()))
    t, a = map(int, raw_input().split())
    k = max((x+t-1)/t, (y+a-1)/a)
    x = k*t
    y = k*a

print x + y

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(raw_input())
t = a = 1
for _ in xrange(N):
    T, A = map(int, raw_input().split())
    q = max((t + T - 1) / T, (a + A - 1) / A)
    t, a = T * q, A * q
print t + a

Submission status: Accepted

Solution code:
import math
n = int(input())
c_t = 0
c_a = 0
for i in range(n):
    t, a = [int(x) for x in input().split(" ")]
    #print(min(c_t / t, c_a / a))
    init = int(max(c_t // t, c_a // a, 1))
    for j in range(init,10**18):
        if t*j >= c_t and a*j >= c_a:
            c_t = t*j
            c_a = a*j
            #print("->" + str(j))
            break
print(c_t + c_a)

Submission status: Accepted

Solution code:
from math import ceil

n = int(input())
data = []
for i in range(n):
    elems = input().split()
    t, a = int(elems[0]), int(elems[1])
    data.append((t, a))

t, a = data[0]

def calcn(r, x):
    n = int(x / r)
    while n * r > x:
        n -= 1
    while n * r < x:
        n += 1
    return n

for i in range(1, n):
    rt, ra = data[i][0], data[i][1]
    na = int(calcn(ra, a))
    nt = int(calcn(rt, t))
    n = max(na, nt)
    t = n * rt
    a = n * ra

print(t + a)

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
a = []
b = []
for _ in xrange(n):
 x,y = map(int,stdin.readline().split())
 a.append(x)
 b.append(y)
x = a[0]
y = b[0]
for i in xrange(1,n):
 fir = a[i]
 sec = b[i]
 if fir>=x and sec >= y:
  x = fir;y=sec
 elif fir>=x:
  k = y/sec
  if y%sec:
   k+=1
  x = fir * k
  y = sec * k
 elif sec>=y:
  k = x/fir
  if x%fir:
   k += 1
  x = fir * k
  y = sec * k
 else:
  u = x/fir
  if x%fir:
   u+=1
  v = y/sec
  if y%sec:
   v+=1
  k = u
  if v > k:
   k = v
  x = fir * k
  y = sec * k



print x + y

Submission status: Accepted

Solution code:
n = int(raw_input())
t = 1
a = 1
for i in range(n):
    x, y = map(int, raw_input().split())
    tmp = max(
        t / x if t % x == 0 else t / x + 1,
        a / y if a % y == 0 else a / y + 1
    )
    t = x * tmp
    a = y * tmp
print t+a

Submission status: Accepted

Solution code:
N = int(input())
vote = [1,1]
for i in range(N):
    ratio = list(map(int, input().split()))
    for j in range(2):
        while(vote[j] % ratio[j] != 0):
            vote[j] += 1
    if vote[0] * ratio[1] < vote[1] * ratio[0]:
        vote[0] = vote[1] // ratio[1] * ratio[0];
    if vote[0] * ratio[1] > vote[1] * ratio[0]:
        vote[1] = vote[0] // ratio[0] * ratio[1];
print(vote[0] + vote[1])

Submission status: Accepted

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

n=int(input())
t=1
a=1
for i in range(n):
    ti,ai = map(int,input().split())
    k=max(f1(t,ti),f1(a,ai))
    t=ti*k
    a=ai*k
print(t+a)

Submission status: Accepted

Solution code:
import math                                             
from decimal import Decimal                             
                                                        
N = input()                                             
t = []                                                  
a = []                                                  
for i in range(int(N)):                                 
    t_n, a_n = input().split()                          
    t.append(Decimal(t_n))                              
    a.append(Decimal(a_n))                              
                                                        
t_ans = 0                                               
a_ans = 0                                               
for t_n, a_n in zip(t, a):                              
    k = max(math.ceil(t_ans/t_n), math.ceil(a_ans/a_n)) 
    if not k:                                           
        k = 1                                           
    t_ans = Decimal(k*t_n)                              
    a_ans = Decimal(k*a_n)                              
print(t_ans+a_ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import math
from decimal import Decimal

N = int(input())

votes = []

for _ in range(N):
    votes.append([Decimal(n) for n in input().split()])

befa = 1
befb = 1

for a, b in votes:
    kakeru = Decimal(max(math.ceil(befa / a), math.ceil(befb / b)))
    befa = a * kakeru
    befb = b * kakeru

print(int(befa)+int(befb))

Submission status: Accepted

Solution code:
def f(x,y):
    return x//y + (1 if x%y > 0 else 0)
n = int(input())
a,b = list(map(int,input().split()))
for i in range(n-1):
    c,d = list(map(int,input().split()))
    e = max(f(a,c),f(b,d))
    a,b = c*e,d*e
print(a+b)

Submission status: Accepted

Solution code:
n=int(raw_input())
t=a=1

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

Submission status: Accepted

Solution code:
def f(x,y):
    return x//y + (1 if x%y > 0 else 0)
n = int(input())
a,b = list(map(int,input().split()))
for i in range(n-1):
    c,d = list(map(int,input().split()))
    e = max(f(a,c),f(b,d))
    a,b = c*e,d*e
print(a+b)

Submission status: Accepted

Solution code:
p=q=1
for i in[0]*input():t,a=map(int,raw_input().split());k=max(~-p/t,~-q/a)+1;p=t*k;q=a*k
print p+q

Submission status: Accepted

Solution code:
N = int(raw_input())
X = [map(int, raw_input().split()) for i in range(N)]

def update(n, x):
    t, a = x
    n1, n2 = n
    c = 1
    i0 = max(n1/t, n2/a)
    for i in xrange(i0, 10**18):
        if i * t >= n1 and i * a >=n2:
            c = i
            break
    return c * t, c* a

n = (1, 1)
for x in X:
    n = update(n, x)
print(sum(n))

Submission status: Accepted

Solution code:

ans = 0

for i in range(int(input())):
    t_i, a_i = list(map(lambda x: int(x), input().split()))

    if i == 0:
        t, a = t_i, a_i

    else:
        n = max((t + t_i - 1) // t_i, (a + a_i - 1) // a_i)
        t = n*t_i
        a = n*a_i

    ans = t + a

print(ans)

Submission status: Accepted

Solution code:
import math
from decimal import Decimal

N = int(input())
T, A = [Decimal(x) for x in input().split()]

for i in range(1,N):
        T2, A2 = [Decimal(x) for x in input().split()]
        n = Decimal(max(math.ceil(T/T2),math.ceil(A/A2)))
        T = T2 * n
        A = A2 * n

print(T+A)

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return int(a)
def lcm(a,b):
    return int(a*b/gcd(a,b))

lines = sys.stdin.readlines()
n = int(lines[0])
ret = [1,1]
before_sum = 2
before_ret = [ret[0],ret[1]]
for line in lines[1:]:
    line = line.rstrip().split(" ")
    for l in range(len(line)):
        line[l] = int(line[l])
    #print ("line=",line)
    #print ("ret=",ret)
    #print ("before_sum=",before_sum)
    #print ("before_ret=",before_ret)
    a,b = int(line[0]),int(line[1])
    #before_ret = [ret[0],ret[1]]
    if (ret[0]<=a) and (ret[1]<=b):
        ret[0]=a
        ret[1]=b
    else:
        check_a = Decimal(ret[0])/Decimal(a)
        check_b = Decimal(ret[1])/Decimal(b)
        if (check_a>check_b):
            ret[0]=math.ceil(check_a)*line[0]
            ret[1]=math.ceil(check_a)*line[1]
        elif (check_a<=check_b):
            ret[0]=math.ceil(check_b)*line[0]
            ret[1]=math.ceil(check_b)*line[1]
    #g = gcd(ret[0],ret[1])
    #print (ret[0],ret[1],g)
    #ret[0]=int(ret[0]/g)
    #ret[1]=int(ret[1]/g)
    """
    if (before_sum>(ret[0]+ret[1])):
        #print ("before_sum=",before_sum,ret)
        check_ret = [ret[0],ret[1]]
        i=2
        print ("check:",check_ret,before_ret)
        while((check_ret[0]+check_ret[1])<before_sum):
            check_ret[0]=ret[0]*i
            check_ret[1]=ret[1]*i
            i+=1
        i=2
        while(check_ret[0]<before_ret[0] or check_ret[1]<before_ret[1]):
            check_ret[0]=ret[0]*i
            check_ret[1]=ret[1]*i
            i+=1
        ret[0] = check_ret[0]
        ret[1] = check_ret[1]
        before_sum=ret[0]+ret[1]
    else:
        before_sum=ret[0]+ret[1]
    """


#print (ret)
print (ret[0]+ret[1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())
T, A = 1, 1 
for loop in xrange(N):
    t, a = map(int, raw_input().split())
    n = max((T + t - 1)/t, (A + a - 1)/a)
    T, A = n*t, n*a
print T + A

Submission status: Accepted

Solution code:
time=input()

aok=1
tak=1

for i in range(time):
	l=map(int, raw_input().split())
	if aok<tak:
		if tak%l[1]!=0:
			tak=(tak/l[1]+1)*l[1]
		if aok>tak/l[1]*l[0]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			aok=tak/l[1]*l[0]
	elif aok==tak:
		if l[0]<=l[1]:
			if aok%l[0]!=0:
				aok=(aok/l[0]+1)*l[0]
			tak=aok/l[0]*l[1]
		else:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
	else:
		if aok%l[0]!=0:
			aok=(aok/l[0]+1)*l[0]
		if tak>aok/l[0]*l[1]:
			if tak%l[1]!=0:
				tak=(tak/l[1]+1)*l[1]
			aok=tak/l[1]*l[0]
		else:
			tak=aok/l[0]*l[1]
print aok+tak

Submission status: Accepted

Solution code:
N = int(raw_input())
t = [[0,0] for i in range(N)]
for i in range(N):
    l = []
    l = raw_input().split()
    t[i][0] = int(l[0])
    t[i][1] = int(l[1])
min_ = [0,0]
min_[0] = t[0][0]
min_[1]= t[0][1]
for i in range(1,N):
#    cnt = max(int(math.ceil(1.0*min_[0]/t[i][0])),int(math.ceil(1.0*min_[1]/t[i][1])))
    cnt_0 = min_[0]/t[i][0]
    if min_[0]%t[i][0]!=0:
        cnt_0+=1
    cnt_1 = min_[1]/t[i][1]
    if min_[1]%t[i][1]!=0:
        cnt_1+=1
    cnt = max(cnt_0,cnt_1)
    min_[0] = cnt*t[i][0]
    min_[1] = cnt*t[i][1]
print min_[0]+min_[1]

Submission status: Accepted

Solution code:
from math import ceil
from fractions import Fraction

n = int(input())
sa, st = 1, 1

for a, t in (map(int, input().split()) for _ in range(n)):
    r = ceil(max(Fraction(sa, a), Fraction(st, t)))
    sa, st = a * r, t * r

print(sa + st)

Submission status: Accepted

Solution code:
import math
from fractions import Fraction

n = int(input())
t, a = [int(x) for x in input().split()]
for i in range(1, n):
    t2, a2 = [int(x) for x in input().split()]
    x = math.ceil(max(Fraction(t, t2), Fraction(a, a2)))
    t, a = x * t2, x * a2

print(t + a)

Submission status: Accepted

Solution code:
N  = int(raw_input())

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

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

    if i != 0 and T[i - 1] - T[i] > 0 or A[i - 1] - A[i] > 0:

        if (T[i  - 1] / T[i]) > (A[i - 1] / A[i]):
            m  = T[i  - 1] / T[i]
            if T[i - 1] % T[i] != 0:
                m += 1 

        else:
            m = A[i - 1] / A[i]
            if A[i - 1] % A[i] != 0:
                m += 1

        T[i] *= m
        A[i] *= m

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

print sum(ans)

Submission status: Accepted

Solution code:
from random import random
import math
import re
from fractions import Fraction

N = int(input())
ca, cb = 0, 0
for _ in range(N):
    a, b = map(int, input().split(" "))
    if ca == 0 and cb == 0:
        ca, cb = a, b
    else:
        r = int(math.ceil(max(Fraction(ca, a), Fraction(cb,b))))
        # print a, b, Fraction(ca, a), math.ceil(Fraction(ca,a))
        ca, cb = a*r, b*r
        # print ca, cb, x
print (ca + cb)

Submission status: Accepted

Solution code:
import math
N = input()
datas = []
for _ in range(N):
	data = map(long, raw_input().split(" "))
	datas.append(data)

t_min = datas[0][0]
o_min = datas[0][1]
for _ in range(N-1):
	t = datas[_+1][0]
	o = datas[_+1][1]
	t_mul = t_min/t + 1 if t_min%t != 0 else t_min/t
	o_mul = o_min/o + 1 if o_min%o != 0 else o_min/o
	if t_mul < o_mul:
		t_min = o_mul*t
		o_min = o_mul*o
	else:
		t_min = t_mul*t
		o_min = t_mul*o

print t_min+o_min

Submission status: Accepted

Solution code:
#coding=UTF-8
#最小公倍数の要素を増やすときみたいに、上手くいかなくなったときにk倍す
#る感じかな

N=int(input())

hihyo=[]
for idx in range(0,N,1):
    mojir=input()
    hyo=mojir.split(' ')
    hihyo.append((int(hyo[0]),int(hyo[1])))

taka=hihyo[0][0]
aoki=hihyo[0][1]

for idx in range(1,N,1):
#    print('高橋 {} 青木 {}'.format(taka,aoki))
    takahi= taka//hihyo[idx][0]  + (0 if  taka%hihyo[idx][0]==0 else 1)
    aokihi= aoki//hihyo[idx][1]  + (0 if  aoki%hihyo[idx][1]==0 else 1)
#    print('比 高橋 {} 青木 {}'.format(takahi,aokihi))

    k=max(takahi,aokihi)
    taka=k*hihyo[idx][0]
    aoki=k*hihyo[idx][1]

ans=taka+aoki
print(ans)
#テストケースが優しい

Submission status: Accepted

Solution code:
N = input()
T,A = map(int,raw_input().split(' '))
for i in xrange(N-1):
    t,a = map(int,raw_input().split(' '))
    s1 = T/t
    if T%t != 0:
        s1+=1
    s2 = A/a
    if A%a != 0:
        s2+=1
    s = max(s1,s2)
    T = s*t
    A = s*a
print T+A