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: Wrong Answer

Solution code:
from sys import stdin

n = int(stdin.readline())

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

p_t, p_a = t_votes, a_votes

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

print(t_votes + a_votes)

Submission status: Wrong Answer

Solution code:
import math
N = input()

t = []
a = []

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

t_get = 1
a_get = 1

for i in range(N):
    times = max(math.ceil(float(t_get)/t[i]),math.ceil(float(a_get)/a[i]))
    t_get = t[i]*times
    a_get = a[i]*times

print int(t_get + a_get)

Submission status: Wrong Answer

Solution code:
from sys import stdin

n = int(stdin.readline())

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

p_t, p_a = t_votes, a_votes

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

print(t_votes + a_votes)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n=i()
t=[0]*n
a=[0]*n
for j in range(n):
    t[j],a[j]=ii()

tt,aa=1,1
for j in range(n):
    if t[j]>=tt and a[j]>=aa:
        tt,aa=t[j],a[j]
    else:
        k=max(int(math.ceil(1.*tt/t[j])),int(math.ceil(1.*aa/a[j])))
        tt,aa=t[j]*k,a[j]*k

print tt+aa

Submission status: Wrong Answer

Solution code:
from math import ceil

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

while n:
    n -= 1
    a, t = map(int, input().split())
    if sa <= a:
        if st <= t:
            sa, st = a, t
        else:
            r = ceil(st / t)
            sa, st = a * r, t * r
    else:
        ra = ceil(sa / a)
        if st <= t:
            sa, st = a * ra, t * ra
        else:
            rt = ceil(st / t)
            r = max(ra, rt)
            sa, st = a * r, t * r

print(sa + st)

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n=i()
t=[0]*n
a=[0]*n
for j in range(n):
    t[j],a[j]=ii()

tt,aa=1,1
for j in range(n):
    if t[j]>=tt and a[j]>=aa:
        tt,aa=t[j],a[j]
    else:
        k=max(math.ceil(1.*tt/t[j]),math.ceil(1.*aa/a[j]))
        tt,aa=t[j]*k,a[j]*k

print int(tt+aa)

Submission status: Wrong Answer

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [input().split() for _ in range(n)]
ans = [0,0]
for i in range(n):
    ref_1 = int(l[i][0])
    ref_2 = int(l[i][1])
    for j in range(2,10**18-1):
        if (ans[0]>ref_1) or (ans[1]>ref_2):
            ref_1 = int(l[i][0])
            ref_2 = int(l[i][1])
            ref_1 *= j
            ref_2 *= j
        else:
            break

    ans[0], ans[1] = ref_1, ref_2
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

f, a0 = map(int, input().split())

for i in range(n-1):
    t1, a1 = map(int, input().split())
    
    if f % t1 != 0:
        f += t1 - f % t1
    while (f // t1) * a1 < a0:
        f += t1
    a0 = (f // t1) * a1
print(f + a0)

Submission status: Time Limit Exceeded

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

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

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (T, A) != (tg, ag):
        sum_t, sum_a = T * max_ta, A * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= T
            sum_a -= A
            if sum_t < t or sum_a < a:
                sum_t += T
                sum_a += A
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)

Submission status: Time Limit Exceeded

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

t = 0
a = 0
for i in range(N):
    if i == 0:
        t += L[i][0]
        a += L[i][1]
        continue
    if (L[i][0] >= t and L[i][1] >= a):
        t = L[i][0]
        a = L[i][1]
        continue

    max_ta = max(t, a)
    g = math.gcd(t, a)
    tg, ag = t // g, a // g
    if (L[i][0], L[i][1]) != (tg, ag):
        sum_t, sum_a = L[i][0] * max_ta, L[i][1] * max_ta
        # print(sum_t, sum_a)
        while True:
            sum_t -= L[i][0]
            sum_a -= L[i][1]
            if sum_t < t or sum_a < a:
                sum_t += L[i][0]
                sum_a += L[i][1]
                break
        t = sum_t
        a = sum_a
        continue

print(t + a)

Submission status: Time Limit Exceeded

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

x, y = 1, 1
for t, a in query:
    T, A = t, a
    while not (T >= x and A >= y):
        T += t
        A += a
    x = T
    y = A
print(x + y)

Submission status: Time Limit Exceeded

Solution code:
import math
N=int(input())
ans=0
nowT=0
nowA=0
beforeT=0
beforeA=0
T,A=map(int,input().split())
beforeA=A
beforeT=T
ans=A+T
for i in range(1,N):
    T,A=map(int,input().split())
    sumTA=T+A
    kouho=math.ceil(ans/sumTA)*sumTA
    ans=kouho
    while(1):
        nowT=(ans*T)//sumTA
        nowA=(ans*A)//sumTA
        #print(nowT,nowA)
        if nowA>=beforeA and nowT>=beforeT :
            beforeA=nowA
            beforeT=nowT
            break
        else:
            ans+=sumTA
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x,y = map(int,input().split())
for i in range(n-1):
    t,a = map(int,input().split())
    o = t
    p = a
    while x > o or y > p:
        o += t
        p += a
    x = o
    y = p
print(x+y)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
bt,ba=1,1
for t,a in l:
    tt,ta=t,a
    i=2
    while bt>tt or ba>ta:
        tt=t*i
        ta=a*i
        i+=1
    bt,ba=tt,ta
print(bt+ba)

Submission status: Time Limit Exceeded

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

    elif x > t and y <= a:
        i = 1
        while x > t:
            t //= i
            i +=1
            t *= i
        y = i*a
        x = t

    elif x > t and y > a:
        i = 1
        while x > t or y > a:
            t //= i
            a //= i
            i += 1
            t *= i
            a *= i
        x = t
        y = a

print(x+y)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T,A = (int(T) for T in input().split())
for TN in range(1,N):
    TNext,ANext = (int(T) for T in input().split())
    Cnt = 1
    while TNext*Cnt<T or ANext*Cnt<A:
        Cnt += 1
    T = TNext*Cnt
    A = ANext*Cnt
print(A+T)

Submission status: Time Limit Exceeded

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

for _ in range(n):
    t,a=map(int,input().split())
    n=1
    while p>n*t or q>n*a:
        n+=1
    p,q=n*t,n*a

print(p+q)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N = int(input())
x, y = map(int, input().split())
s = x + y
for i in range(N - 1):
    t, a = map(int, input().split())
    if s % (t + a) == 0:
        x2 = t * (s // (t + a))
        y2 = a * (s // (t + a))
        while x2 < x or y2 < y:
            x2 += t
            y2 += a
        x, y = x2, y2
    else:
        s += (t + a) - s % (t + a)
        x2 = t * (s // (t + a))
        y2 = a * (s // (t + a))
        while x2 < x or y2 < y:
            x2 += t
            y2 += a
        x, y = x2, y2
    s = x + y
print(s)

Submission status: Time Limit Exceeded

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

c = [0] * n
d = [0] * n

c[0] = a[0]
d[0] = b[0]

for i in range(n-1):
    for j in range(10**18):
        if (a[i+1]+b[i+1])*(j+1) >= c[i]+d[i] and a[i+1]*(j+1) >= c[i] and b[i+1]*(j+1) >= d[i]:
            c[i+1] = a[i+1]*(j+1)
            d[i+1] = b[i+1]*(j+1)
            break

print(c[n-1]+d[n-1])

Submission status: Time Limit Exceeded

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

    for i in range(1,N):
        j = ceil(now_t / T[i])
        mul_t = T[i] * j
        mul_a = A[i] * j
        while now_t > mul_t or now_a > mul_a:
            j += 1
            mul_t = T[i] * j
            mul_a = A[i] * j
        else:
            now_t = mul_t
            now_a = mul_a
    
    print(now_t + now_a)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

    for i in range(1,N):
        mul_t = T[i]
        mul_a = A[i]
        j = 2
        while now_t > mul_t or now_a > mul_a:
            mul_t = T[i] * j
            mul_a = A[i] * j
            j += 1
        else:
            now_t = mul_t
            now_a = mul_a
    
    print(now_t + now_a)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = (T // t) * t
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = (A // a) * a
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)

Submission status: Time Limit Exceeded

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

T, A = 0, 0
for t, a in TA:
    if T == 0 and A == 0:
        T = t
        A = a
        continue
    if t == a:
        M = max(T, A)
        T = M
        A = M
    elif t < a:
        n = 0
        while n < T or a * (n // t) < A:
            n += t
        T = n
        A = a * (T // t)
    else:
        n = 0
        while n < A or t * (n // a) < T:
            n += a
        A = n
        T = t * (A // a)
print(A + T)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	x, y = LI()
	for _ in range(n-1):
		t, a = LI()
		if x <= t and y <= a:
			x, y = t, a
		else:
			l = 1
			xl, yl = l*t, l*a
			while xl < x or yl < y:
				l += 1
				xl, yl = l*t, l*a
			x, y = xl, yl
	print(x+y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
#import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
pairs=[LI() for i in range(n)]
def pair_revise(x,y,a,b):
    global p
    global q
    #print(x,y,a,b)
    for i in range(max(1,min(floor(x/a),floor(y/b))),max(ceil(x/a),ceil(y/b))+1):
        p,q=a*i,b*i
        if p>=x and q>=y:
            break
    return [p,q]
    #return [x*max(ceil(x/a),ceil(y/b)),y*max(ceil(x/a),ceil(y/b))]
    #for i in range(max(ceil(x/a),ceil(y/b)),):
u,v=pairs[0]
for i in range(n-1):
    u,v=pair_revise(u,v,pairs[i+1][0],pairs[i+1][1])
print(u+v)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# hello worldと表示する
import sys
import numpy
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
from copy import deepcopy
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
pairs=[LI() for i in range(n)]
def pair_revise(x,y,a,b):
    global p
    global q
    #print(x,y,a,b)
    for i in range(max(1,min(floor(x/a),floor(y/b))),max(ceil(x/a),ceil(y/b))+1):
        p,q=a*i,b*i
        if p>=x and q>=y:
            break
    return [p,q]
    #return [x*max(ceil(x/a),ceil(y/b)),y*max(ceil(x/a),ceil(y/b))]
    #for i in range(max(ceil(x/a),ceil(y/b)),):
u,v=pairs[0]
for i in range(n-1):
    u,v=pair_revise(u,v,pairs[i+1][0],pairs[i+1][1])
print(u+v)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import math

def main():
    N = int(input())
    T, A = map(int, input().split())
    for _ in range(N-1):
        t, a = map(int, input().split())
        tmpT, tmpA = t,a
        while 1:
            if T <= tmpT and A <= tmpA:
                T,A = tmpT, tmpA
                break
            else:
                tmpT += t
                tmpA += a
    print(T+A)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a, b = map(int, input().split())
for _ in range(n - 1):
    x, y = map(int, input().split())
    xx, yy = x, y
    while xx < a or yy < b:
        xx += x
        yy += y
    a, b = xx, yy
print(a + b)

Submission status: Time Limit Exceeded

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

t, a = 1, 1
for ti, ai in pairs:
    mul = 1
    while ti * mul < t or ai * mul < a:
        mul += 1
    t, a = ti * mul, ai * mul

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
M=[list(map(int,input().split())) for _ in range(N)]
T=M[0][0]
A=M[0][1]

def search(M0,M1,T,A):
    i=min(T//M0,A//M1)
    while True:
        a=M0*i
        b=M1*i
        if a>=T and b>=A:
            return a,b
        i+=1

for i in range(1,N):
    T,A=search(M[i][0],M[i][1],T,A)
print(T+A)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
M=[list(map(int,input().split())) for _ in range(N)]
T=M[0][0]
A=M[0][1]

def search(M0,M1,T,A):
    i=1
    while True:
        a=M0*i
        b=M1*i
        if a>=T and b>=A:
            return a,b
        i+=1

for i in range(1,N):
    T,A=search(M[i][0],M[i][1],T,A)
print(T+A)

Submission status: Time Limit Exceeded

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

t = 1
a = 1

for i in range(N):
    T, A = TA[i]
    mul = 2
    while t > T or a > A:
        T = TA[i][0] * mul
        A = TA[i][1] * mul
        mul += 1
    t = T
    a = A
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	num = 1
	while True:
		tnow = num*t
		anow = num*a
		if tnow >= tvote and anow >= avote:
			tvote = tnow
			avote = anow
			break
		num += 1
	
print(tvote+avote)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mt = 0
ma = 0
for i in range(n):
    t , a = map(int, input().split())
    if t>=mt and a>=ma:
        mt = t
        ma = a
    elif t<mt or a<ma:
        k=1
        while t*k<mt or a*k<ma:
            k+=1
        mt=t*k
        ma=a*k
print(mt+ma)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    TA = [list(map(int, input().split())) for i in range(N)]
    t, a = TA[0]
    for i in range(1, len(TA)):
        t_next, a_next = TA[i]
        mul = 1
        while True:
            if t_next*mul >= t and a_next*mul >= a:
                t = t_next*mul
                a = a_next*mul
                break
            mul += 1
    print(t+a)


if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ta=[list(map(int,input().split())) for _ in range(n)]
ans=ta[0]
for i in range(1,n):
  if (ta[i-1][0]<ta[i][0]) and (ta[i-1][1]<ta[i][1]):
    pass
  else:
    r=ta[i][0]
    l=ta[i][1]
    while (ta[i-1][0]>ta[i][0]) or (ta[i-1][1]>ta[i][1]):
      ta[i][0]+=r
      ta[i][1]+=l
print(sum(ta[-1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t,a=[0]*n,[0]*n
for i in range(n):
  t[i],a[i]=map(int,input().split())
tt,aa=t[0],a[0]
for i in range(1,n):
  j=0
  while 1:
    j+=1
    if t[i]*j>=tt and a[i]*j>=aa:
      tt=t[i]*j
      aa=a[i]*j
      break
print(aa+tt)

Submission status: Time Limit Exceeded

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

for i in range(1,N):
	Cnt_pre = Cnt[i-1]
	while T[i]*Cnt[i]<T[i-1]*Cnt_pre:
		Cnt[i] += 1
	while A[i]*Cnt[i]<A[i-1]*Cnt_pre:
		Cnt[i] += 1
print(Cnt[N-1]*(T[N-1]+A[N-1]))

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
t, a = [0] * n, [0] * n
for i in range(n):
    t[i], a[i] = map(int, input().split())
ans = a[0] + t[0]
j_pre = 1
for i in range(1, n):
    j = 1
    vote = t[i] + a[i]
    while vote * j < ans or (t[i] * j < t[i - 1] * j_pre or a[i] * j < a[i - 1] * j_pre):
        j += 1
    ans = vote * j
    j_pre = j
    #print(t[i] * j, a[i] * j)
    #print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t, a = map(int, input().split())
for i in range(1, n):
    x, y = map(int, input().split())
    i = 1
    c, d = x, y
    while c < t or d< a:
        c = x * i
        d = y * i
        i += 1
    t, a = c, d
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

for i in range(N - 1):
    nt, na = map(int, input().split())
    pt, pa = nt, na
    while pt < t or pa < a:
        pt += nt
        pa += na
    t = pt
    a = pa
print(t + a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=1
b=1
for i in range(n):
    ti,ai=map(int,input().split())
    m=1
    while a>m*ti or b>m*ai:
        m=m+1
#        print(m,a,m*ti,b,m*ai)
#    print(m,a,m*ti,b,m*ai)
    a=m*ti
    b=m*ai
#    print(a,b,m)
print(a+b)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil


n = int(input())

votes = [0, 0]

for i in range(n):
    a, b = map(int, input().split())
    if i == 0:
        votes = [a, b]
    else:
        if a == b:
            x = max(votes)
            votes = [x, x]
        else:
            num = min(ceil(votes[0]/a), ceil(votes[1]/b))
            for i in range(num, 10000000):
                x = a * i
                y = b * i
                if x >= votes[0] and y >= votes[1]:
                    votes = [x, y]
                    break

print(sum(votes))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    if N <=1000:
        t = [0] * N
        a = [0] * N
        A = B = 1
        for i in range(N):
            tt, aa = map(int, input().split())
            t[i], a[i] = tt, aa

        for ii in range(N):
            A, B = prop(ii, t, a, A, B)
            
        answercheck(A, B)
    else:
        pass


def prop(a, T, A, x, y):
    while not x / y == T[a] / A[a]:
        if x / y >= T[a] / A[a]:
            y += 1
        elif x / y <= T[a] / A[a]:
            x += 1
    return x, y
    


def answercheck(a, b):
    if a + b < 10 ** 18 +1:
        print(a+b)
    else:
        pass


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    t = [0] * N
    a = [0] * N
    A = B = 1
    
    for i in range(N):
        tt, aa = map(int, input().split())
        t[i], a[i] = tt, aa

    for ii in range(N):
        A, B = prop(ii, t, a, A, B)
        
    answercheck(A, B)


def prop(a, T, A, x, y):
    while not x / y == T[a] / A[a]:
        if x / y >= T[a] / A[a]:
            y += 1
        elif x / y <= T[a] / A[a]:
            x += 1
    return x, y
    


def answercheck(a, b):
    if a + b < 10 ** 18 +1:
        print(a+b)
    else:
        pass


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    t = [0] * N
    a = [0] * N
    A = B = 1
    
    for i in range(N):
        tt, aa = map(int, input().split())
        t[i], a[i] = tt, aa

    for ii in range(N):
        A, B = prop(ii, t, a, A, B)
        
    answercheck(A, B)


def prop(a, T, A, x, y):
    while not x / y == T[a] / A[a]:
        if x / y >= T[a] / A[a]:
            y += 1
        else:
            x += 1
    return x, y
    


def answercheck(a, b):
    if a + b < 10 ** 18 +1:
        print(a+b)
    else:
        pass


main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
table=[[int(i) for i in input().split()] for j in range(0,N)]

for i in range(0,N-1):
    for j in range(0,10**9):
        if table[i][0]<=j*table[i+1][0]:
            for l in range(j,10**9):
                if table[i][1]<=l*table[i+1][1]:
                    table[i+1][1]=l*table[i+1][1]
                    table[i+1][0]=l*table[i+1][0]
                    break
            break

print(table[N-1][0]+table[N-1][1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
table=[[int(i) for i in input().split()] for j in range(0,N)]

for i in range(0,N-1):
    for j in range(0,10**9):
        if table[i][0]<=j*table[i+1][0]:
            for l in range(j,10**9):
                if table[i][1]<=l*table[i+1][1]:
                    table[i+1][1]=l*table[i+1][1]
                    table[i+1][0]=l*table[i+1][0]
                    break
                else:
                    pass
            break
        else:
            pass

print(table[N-1][0]+table[N-1][1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
table=[[int(i) for i in input().split()] for j in range(0,N)]

for i in range(0,N-1):
    for j in range(0,10**9):
        if table[i][0]<=j*table[i+1][0] and table[i][1]<=j*table[i+1][1]:
            table[i+1][0]=j*table[i+1][0]
            table[i+1][1]=j*table[i+1][1]
            break
        else:
            pass

print(table[N-1][0]+table[N-1][1])

Submission status: Time Limit Exceeded

Solution code:
ls = list()
lt = list()
la = list()
LT = list()
LA = list()
N = int(input())
for i in range(1, N+1):
    T, A = map(int, input().split())
    X = T + A
    ls.append(X)
    lt.append(T)
    la.append(A)
    LT.append(T)
    LA.append(A)
for j in range(1, N):
    while lt[j] < lt[j-1] or la[j] < la[j-1]:
        lt[j] += LT[j]
        la[j] += LA[j]
print(lt[N-1] + la[N-1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
t=[]
a=[]

for i in range(n):
    ti,ai=map(int,input().split())
    t.append(ti)
    a.append(ai)
    
ti=t[0]
ai=a[0]

for i in range(n-1):
    ta=a[i+1]*t[i+1]
    for ii in range(1,10000000):
        if ta*ii//a[i+1]>=ti and ta*ii//t[i+1]>=ai:
            ti=ta*ii//a[i+1]
            ai=ta*ii//t[i+1]
            break
            
print(ai+ti)