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: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd

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=gcd(t[i+1],a[i+1])*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]
#            print(i,ii,ti,ai,ta)
            break
            
print(ai+ti)

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 = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0 and (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
               ans += j
               break

print(ans)

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 = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)

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 = T[0]+A[0]

for i in range(N-1):
    for j in range(10**8):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)

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 = T[0]+A[0]

for i in range(N-1):
    for j in range(10**18):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
f=lambda:map(int,input().split())
a,b=f()
for _ in range(1,n):
  s,t=f(); x=y=0
  while x<a or y<b: x+=s; y+=t
  a,b=x,y
print(a+b)

Submission status: Time Limit Exceeded

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

t_voted, a_voted = ratio[0][0], ratio[0][1]
for t, a in ratio[1:]:
    tt, aa = t, a
    while tt < t_voted or aa < a_voted:
        tt += t
        aa += a
    t_voted, a_voted = tt, aa

print(t_voted + a_voted)

Submission status: Time Limit Exceeded

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())
    m,p=nT,nA
    while(nT<T or nA<A):
        nT+=m;nA+=p
    T,A=nT,nA
print(T+A)

Submission status: Time Limit Exceeded

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:
        i=2
        _t=t
        _a=a
        while _t<before[0] or _a<before[1]:
            _t=t*i
            _a=a*i
            i+=1
        before=[_t,_a]
print(sum(before))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
la = 0
lb = 0
for i in range(0,n):
    a,b = map(int, input().split())
    for bei in range(1,10000000):
        if(a * bei >= la and b * bei >= lb):
            la = a * bei
            lb = b * bei
            break

print(la+lb)

Submission status: Time Limit Exceeded

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:
        c = 1
        while  t * c < T or a * c < A:
            c += 1
            # print(t * c, a * c)
        T, A = t * c, a * c
    # print(T, A)

print(T+A)

Submission status: Time Limit Exceeded

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
        xa=NA//A
        x=min(xt,xa)
        tempT=T*x
        tempA=A*x
        while tempT<NT or tempA<NA:
            tempT+=T
            tempA+=A
        NT=tempT
        NA=tempA
    print(NT+NA)
            

main()

Submission status: Time Limit Exceeded

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()
        tempT=T
        tempA=A
        while tempT<NT or tempA<NA:
            tempT+=T
            tempA+=A
        NT=tempT
        NA=tempA
    print(NT+NA)
            

main()

Submission status: Time Limit Exceeded

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

T = A = 0
for t, a in TA:
  _t, _a = t, a
  while t<T or a<A:
    t += _t; a += _a
  T = t; A = a
print(T+A)

Submission status: Time Limit Exceeded

Solution code:

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 = 1
        while Tvote[k-1]>j*T[k] or Avote[k-1]>j*A[k]:
            j += 1
        Tvote[k] = j*T[k]
        Avote[k] = j*A[k]

#print("---Tvote:{}".format(Tvote))
#print("---Avote:{}".format(Avote))
print(Tvote[n-1]+Avote[n-1])

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
ans = 0
pret = 0
prea = 0
for x in range(n):
    t, a = map(int, input().split())
    if ans == 0 : 
        ans = t + a 
        pret = t
        prea = a
    else:
        sum = t + a
        ans = math.ceil(ans / sum) * sum
        while (pret > (ans * t // sum) or prea > (ans * a // sum)):
            ans += sum
        pret = ans * t // sum
        prea = ans * a // sum
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
T,A = map(int,input().split())
if n == 1:
    print(T+A)
for _ in range(n-1):
    t,a = map(int,input().split())
    i = 1
    while t*i<T or a*i<A:
        i += 1
    T,A = t*i,a*i
if n!= 1:
    print(T+A)

Submission status: Time Limit Exceeded

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

PQ = [TA[0]]

for i in range(1, n):
    p0, q0 = PQ[i-1]
    p1, q1 = TA[i]
    t, a = TA[i]
    while p1 < p0 or q1 < q0:
        p1 += t
        q1 += a
    PQ.append([p1, q1])
    
print(sum(PQ[-1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a,b = map(int,input().split())
for _ in range(n-1):
    c,d = map(int,input().split())
    deltaA = 0
    deltaB = d/c * (a + deltaA) - b 
    #print(deltaA,deltaB)
    while deltaB < 0 or int(deltaB) != deltaB:
        deltaA += 1
        deltaB = d/c * (a + deltaA) - b 
        #print(deltaA,deltaB)
    a += int(deltaA)
    b += int(deltaB)
#print(a,b)
print(a+b)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
TT=0
AA=0
for k in range(N):
    T,A = map(int,input().split())
    k=min(TT//T,AA//A)
    for k in range(100000000000000000):
        k+=1
        if T*k>=TT and A*k>=AA:
            TT=T*k 
            AA=A*k
            break
print(TT+AA)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
TT=0
AA=0
for k in range(N):
    T,A = map(int,input().split())
    k=0
    for k in range(100000000000000000):
        k+=1
        if T*k>=TT and A*k>=AA:
            TT=T*k 
            AA=A*k
            break
print(TT+AA)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: "List[int]", A: "List[int]"):

    a0, a1 = T[0], A[0]
    for t, a in zip(T, A):
        while a0*a != a1*t:
            if a0/a1 - t/a > 0:
                a1 += 1
            else:
                a0 += 1
        # print(a0, a1)
    print(a0+a1)
    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for _ in range(N):
	t, a = map(int, input().split())
	T.append(t)
	A.append(a)
	
t_v = 0
a_v = 0
	
for i in range(N):
	t_r = T[i]
	a_r = A[i]
	for j in range(1, 10 ** 18):
		if j * t_r >= t_v and j * a_r >= a_v:
			t_v = j * t_r
			a_v = j * a_r
			break
			
print(t_v + a_v)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n-1):
    s,t = map(int,input().split())
    while float(a/b) != float(s/t):
        if float(a/b) > float(s/t):
            b += 1
        elif float(a/b) < float(s/t):
            a += 1

print(a+b)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


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

    now = TA[0]
    for t, a in TA[1:]:
        i = 1
        while now[0] > t * i or now[1] > a * i:
            i += 1
        now[0] = t * i
        now[1] = a * i

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

a, b = 1, 1
for i in range(N):
    T, A = map(int, input().split())
    tmp_T = T
    tmp_A = A
    while True:
        if a <= tmp_T and b <= tmp_A:
            a = tmp_T
            b = tmp_A
            break
        tmp_T += T
        tmp_A += A
        
print(a+b)

Submission status: Time Limit Exceeded

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

result1 = rList[0][0]
result2 = rList[0][1]
for i,j in enumerate(rList):
  if i  == 0:
    pass
  else:
    if rList[i][0] == rList[i][1]:
       if result1 > result2:
          result2 = result1
       elif result1 < result2:
          result1 = result2 
    else:
      r_sum = result1+result2
      ra = rList[i][0]+rList[i][1]
      while True: 
          r_sum += (ra - (r_sum % ra))
          if (r_sum//ra) * rList[i][0] >= result1 and  (r_sum//ra) * rList[i][1] >= result2:
            result1= (r_sum//ra) * rList[i][0]  
            result2= (r_sum//ra) * rList[i][1]  
            break
#  print(i,result1,result2)
print(result1+result2)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
cura, curb = MAP()
for i in range(N-1):
    a, b = MAP()
    tmpa, tmpb = a, b
    # 比をそのままで、現在の票数より大きくする
    while a < cura or b < curb:
        a += tmpa
        b += tmpb
    cura, curb = a, b
ans = cura + curb
print(ans)

Submission status: Time Limit Exceeded

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

curr_a, curr_b = 0, 0

for v1, v2 in votes:
    a, b = v1, v2
    i = min(curr_a // v1, curr_b // v2)

    while a < curr_a or b < curr_b:
        a = v1 * i
        b = v2 * i
        i += 1

    curr_a, curr_b = a, b

print(curr_a + curr_b)

Submission status: Time Limit Exceeded

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

curr_a, curr_b = 0, 0

for v1, v2 in votes:
    a, b = v1, v2
    i = 2

    while a < curr_a or b < curr_b:
        a = v1 * i
        b = v2 * i
        i += 1

    curr_a, curr_b = a, b

print(curr_a + curr_b)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

tkhs = 1
aoki = 1

for _ in range(n):
    t, a = map(int, input().split())
    k = 1
    while not(tkhs <= k*t and aoki <= k*a):
        k += 1
    tkhs = k*t
    aoki = k*a

print(tkhs+aoki)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import sys
import numpy as np
from collections import deque as deq

N = int(input())
T = [list(map(int, input().split())) for i in range(N)]
T = [ t[0] / t[1] for t in T ]

t0, t1 = 1, 1
for i in range(N):
    while t0 / t1 != T[i]:
        if t0 / t1 < T[i]:
            t0 += 1
        else:
            t1 += 1

print(t0 + t1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import sys
import numpy as np
from collections import deque as deq

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

t0, t1 = 1, 1
for i in range(N):
    while t0 / t1 != T[i][0] / T[i][1]:
        if t0 / t1 < T[i][0] / T[i][1]:
            t0 += 1
        else:
            t1 += 1

print(t0 + t1)

Submission status: Time Limit Exceeded

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

ans_a = 0
ans_t = 0
ratio = ratios.pop(0)
ans_a = ratio[0]
ans_t = ratio[1]

for ratio in ratios:
  
  i = min(ans_a // ratio[0], ans_t // ratio[1])
  
  while True:
    temp_a = ratio[0]*i
    temp_t = ratio[1]*i
    if temp_a >= ans_a and temp_t >= ans_t:
      ans_a = temp_a
      ans_t = temp_t
      break
    i += 1
    
print(ans_a + ans_t)

Submission status: Time Limit Exceeded

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

ans_a = 0
ans_t = 0
ratio = ratios.pop(0)
ans_a = ratio[0]
ans_t = ratio[1]

for ratio in ratios:
  i = 1
  while True:
    temp_a = ratio[0]*i
    temp_t = ratio[1]*i
    if temp_a >= ans_a and temp_t >= ans_t:
      ans_a = temp_a
      ans_t = temp_t
      break
    i += 1
    
print(ans_a + ans_t)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())
ab = map(int, sys.stdin.read().split())
ab = list(zip(ab, ab))

def main():
    c_a = ab[0][0]
    c_b = ab[0][1]
    for a, b in ab[1:]:
        ratio = a / b
        while c_a / c_b != ratio:
            if c_a / c_b < ratio:
                c_a += 1
            else:
                c_b += 1
    
    ans = c_a + c_b
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T, A = 1, 1
for i in range(N):
  t, a = map(int, input().split())
  i = 1
  while t * i < T or a * i < A:
    i += 1
  T = t * i
  A = a * i
print(T + A)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T = 0
A = 0
for _ in range(N):
    t, a = map(int, input().split())
    i = 1
    while T > i*t or A > i*a:
        i += 1
    T = i*t
    A = i*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)]
Taka=1
Aoki=1

def UP(V1,V2,R1,R2):
    r1,r2=R1,R2
    while V1>R1 or V2>R2:
        R1+=r1
        R2+=r2
    return [R1,R2]

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t_and_a = []
for _ in range(n) :
    t_and_a += [list(map(int, input().split()))]
if n == 1 :
    print(sum(t_and_a[-1]))
else :
    for i in range(n - 1) :
        k = 1
        while True :
            memo0 = k * t_and_a[i + 1][0]
            memo1 = k * t_and_a[i + 1][1]
            if memo0 >= t_and_a[i][0] and memo1 >= t_and_a[i][1] :
                t_and_a[i + 1][0] = memo0
                t_and_a[i + 1][1] = memo1
                break
            else :
                k += 1
    #answer
    print(sum(t_and_a[-1]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t=ta[0][0]
a=ta[0][1]
for i in range(1,n):
    T,A=ta[i]
    s,b=T,A
    while T<t or A<a:
        T+=s
        A+=b
    t,a=T,A
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

N = int(input())
prv_t, prv_a = map(int,input().split())
ans = prv_t + prv_a
for _ in range(N-1):
  t,a = map(int,input().split())
  
  x = ceil(ans/(t+a))
  while prv_t > t*x or prv_a > a*x:
    x+=1
  ans = (t+a)*x
  prv_t, prv_a = t*x, a*x
print(ans)

Submission status: Time Limit Exceeded

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


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while True:
        if TA[n][0] * coeff >= t_votes and TA[n][1] * coeff >= a_votes:
            break
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)

Submission status: Time Limit Exceeded

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


t_votes = TA[0][0]
a_votes = TA[0][1]
for n in range(1, N):
    coeff = 1
    while TA[n][0] * coeff < t_votes or TA[n][1] * coeff < a_votes:
        coeff += 1
    t_votes = coeff * TA[n][0]
    a_votes = coeff * TA[n][1]

print(t_votes + a_votes)

Submission status: Time Limit Exceeded

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


def solve(N: int, T: "List[int]", A: "List[int]"):
    current = [T[0],A[0]]
    for i in range(1,N):
        t = T[i]
        a = A[i]
        while current[0]>t or current[1]>a:
            t+=T[i]
            a+=A[i]
        
        current[0]=t
        current[1]=a
    print(sum(current))

    return


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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

x = 0
y = 0
for t, a in TA:
    if x <= t and y <= a:
        x = t
        y = a
    else:
        if t >= a:
            while(1):
                if (x*a) % t == 0 and (x*a) // t >= y:
                    y = (x*a) // t
                    break
                else:
                    x += 1
        else:
            while(1):
                if (y*t) % a == 0 and (y*t) // a >= x:
                    x = (y*t) // a
                    break
                else:
                    y += 1

print(x+y)

Submission status: Time Limit Exceeded

Solution code:
# C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report

# 比がa:bとなる合計最小の票分布はa,b
# 次にc:dになったとき、a<=cかつb<=dを満たすまでc,dを2倍、3倍、と増やしていく

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

a, b = TA[0]
ans = a + b

for idx in range(1,N):
    c, d = TA[idx]
    ori_c, ori_d = c, d
    while c < a or d < b:
        c += ori_c
        d += ori_d
    ans = c+d
    a,b = c,d
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
now = (0,0)

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

    i=1
    while True:
        if t*i>=now[0] and a*i>=now[1]:
            now = (t*i,a*i)
            break
        i +=1

print(sum(now))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=[list(map(int, input().split())) for i in range(n)]
a=0
b=0
for i in range(n):
    x=l[i][0]
    y=l[i][1]
    while l[i][0]<a or l[i][1]<b:
        l[i][0]+=x
        l[i][1]+=y
    a=l[i][0]
    b=l[i][1]
print(sum(l[-1]))

Submission status: Time Limit Exceeded

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

x = 1
y = 1
for i in range(n):
    a = ab[i][0]
    b = ab[i][1]
    for j in range(2, 10**18):
        if x <= a and y <= b:
            x = a
            y = b
            break
        else:
            a = ab[i][0] * j
            b = ab[i][1] * j
print(x + y)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

t = 1 
a = 1 

for i in range(n):
    tr,ar = map(int,input().split())
    tc,ac = tr,ar 
    while(tc<t or ac<a):
        tc += tr
        ac += ar
    t = tc
    a = ac 
    
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
suji=[]
for i in range (n):
	suji=suji+list(map(int,input().split()))
tlist=[]
alist=[]
for i in range(2*n):
	if i%2==0:
		tlist.append(suji[i])
	else:
		alist.append(suji[i])

for i in range(n-1):
	k=1
	while tlist[i]>tlist[i+1]*k or alist[i]>alist[i+1]*k:
		k+=1
	tlist[i+1]=tlist[i+1]*k
	alist[i+1]=alist[i+1]*k

print(int(tlist[n-1]+alist[n-1]))

Submission status: Time Limit Exceeded

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

def compare(A,B):
    if A[0]>=B[0] and A[1]>=B[1]:
        return A
    else:
        A0=copy.copy(A[0])
        A1=copy.copy(A[1])
        while A0<B[0] or A1<B[1]:
            A0+=A[0]
            A1+=A[1]
        return [A0,A1]
st=inp[0]
for i in range(1,N):
    st=compare(inp[i],st)
print(sum(st))

Submission status: Time Limit Exceeded

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

for i in range(1, N):
  dt, da = map(int, input().split())
  for j in range(max(A[i-1]//da, T[i-1]//dt)+3):
    if A[i-1] <= j * da and T[i-1] <= j * dt:
      n = j
      break
      
  T[i], A[i] = dt * n, da * n

print(A[N-1] + T[N-1])

Submission status: Time Limit Exceeded

Solution code:
import math

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

for i in range(1, N):
  dt, da = map(int, input().split())
  for j in range(10**9):
    if A[i-1] <= j * da and T[i-1] <= j * dt:
      n = j
      break
      
  T[i], A[i] = dt * n, da * n

print(A[N-1] + T[N-1])

Submission status: Time Limit Exceeded

Solution code:

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

lcms = TA[0]

for t,a in TA[1:]:
    tmp = [t,a]
    
    while tmp[0] < lcms[0]:
        tmp[0] += t
        tmp[1] += a
    while tmp[1] < lcms[1]:
        tmp[0] += t
        tmp[1] += a
    lcms = tmp

print(sum(lcms))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a,b=map(int,input().split())
if n!=1:
	for _ in range(n-1):
		A,B=map(int,input().split())
		c=0
		d=0
		k=1
		while a>c or b>d:
			c=k*A
			d=k*B
			k+=1
		a=c
		b=d
print(a+b)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]
ansT = TA[0][0]
ansA = TA[0][1]
for i in range(N):
    j = 1
    while  TA[i][0]*j<ansT or TA[i][1]*j<ansA:
        j += 1
    ansT = TA[i][0]*j
    ansA = TA[i][1]*j
print(ansT + ansA)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

def f(a,c,b,d):
    if a >= A and b >=B :
        return a,b
    return f(a+c,c,b+d,d)

n = int(input())
a = [list(map(int,input().split()))for _ in range(n)]
A,B = a[0][0],a[0][1]
for i in range(1,n):
    A,B = f(a[i][0],a[i][0],a[i][1],a[i][1])
print(A+B)

Submission status: Time Limit Exceeded

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

# def gcd(x, y):
#     #print(x, y)
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

# def lcm(x, y):
#     return x * y // gcd(x, y)

# for i in range(1, n):
#     lcms = [0] * 2
#     for j in range(2):
#         lcms[j] = lcm(A[i][j], A[i-1][j])
#     print("lcms", lcms)
#     st = 0
#     op = 1
#     if lcms[0] > lcms[1]:
#         st = 1
#         op = 0
#     new_1 = (lcms[st] // A[i][st]) * A[i][op]
#     print(new_1)
#     if new_1 >= A[i-1][op]:
#         A[i][op] = new_1
#         A[i][st] = lcms[0]
#     else:
#         new_0 = lcms[op] // A[i][op] * A[i][st]
#         A[i][st] = new_0
#         A[i][op] = lcms[op]
#     print(A[i])

# print(sum(A[-1]))

for i in range(1, n):
    s = A[i][0]
    t = A[i][1]
    while not (A[i][0] >= A[i-1][0] and A[i][1] >= A[i-1][1]):
        A[i][0] += s
        A[i][1] += t
        # print(A[i-1], A[i])

print(sum(A[-1]))

Submission status: Time Limit Exceeded

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

x = 1
y = 1
for i in range(N):
    n = 1
    while not (x <= n * T[i] and y <= n * A[i]):
        n += 1
    else:
        x = n * T[i]
        y = n * A[i]
else:
    print(x + y)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
pairs = deque()

for _ in range(n):
    pairs.append([int(x) for x in input().split()])
T, A = pairs.popleft()
for Ti, Ai in pairs:
    a = 0
    while (Ti*(A+a))%Ai or (Ti)*(A + a)//Ai - T < 0:
        a += 1
    t = (Ti)*(A + a)//Ai - T
    A += a
    T += t
print(A+T)

Submission status: Time Limit Exceeded

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

for i in range(1, N):
  dt, da = map(int, input().split())
  t, a = dt, da
  
  while t < T[i-1] or a < A[i-1]:
    t += dt
    a += da
  
  T[i], A[i] = t, a
  
print(A[-1] + T[-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
B=[]


for i in range(N):
    a,b, = map(int, input().split())
    B.append([a,b])

a=B[0][0]
b=B[0][1]

for i in range(1,N):
    a1=B[i][0]
    b1=B[i][1]
    if a>B[i][0] or b>B[i][1]:
        while a>a1 or b>b1:
            a1+=B[i][0]
            b1+=B[i][1]
        a=a1
        b=b1
    else:
        a=B[i][0]
        b=B[i][1]
print(a+b)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
ratio_list = [list(map(int, input().split(' '))) for i in range(N)]
#print(ratio)

Tnum = 0
Anum = 0

for ratio in ratio_list:
    k = 1
    while Tnum > ratio[0] * k or Anum > ratio[1] * k:
        k = max(math.ceil(Tnum / ratio[0]), math.ceil(Anum / ratio[1]))
    Tnum = ratio[0] * k
    Anum = ratio[1] * k
    #print('Tnum = ', Tnum)
    #print('Anum = ', Anum)
print(Tnum + Anum)

Submission status: Time Limit Exceeded

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

Tnum = 0
Anum = 0

for ratio in ratio_list:
    k = 1
    while Tnum > ratio[0] * k or Anum > ratio[1] * k:
        k += 1
    Tnum = ratio[0] * k
    Anum = ratio[1] * k
    #print('Tnum = ', Tnum)
    #print('Anum = ', Anum)
print(Tnum + Anum)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ratios = [tuple(int(x) for x in input().split()) for i in range(n)]

t_votes = 1
a_votes = 1
for ratio in ratios:
    count = 0
    while t_votes > ratio[0]*count or a_votes > ratio[1]*count:
        count += 1
    t_votes = ratio[0] * count
    a_votes = ratio[1] * count
print(t_votes+a_votes)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def adjust(a, b, va, vb):
  if a == 0 and b == 0:
    return va, vb
  if vb == 1:
    return a, b
  while a / b != va / vb:
    if a / b < va / vb:
      a += 1
    elif a / b > va / vb:
      b += 1
  return a, b

t = 0
a = 0
for n in range(N):
  ti, ai = [int(x) for x in input().split()]
  if ti < ai:
    t, a = adjust(t, a, ti, ai)
  else:
    a, t = adjust(a, t, ai, ti)

print(t + a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

t = ta[0][0]
a = ta[0][1]
for i in range(1, n):
    p = ta[i][0] / (ta[i][0] + ta[i][1])
    while True:
        if p == t / (t + a):
            break
        if p < t / (t + a):
            a += 1
        else:
            t += 1

print(t + a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
TA = [0] * N

vote = 0
t, a = 0, 0
for i in range(N):
    T, A = map(int, input().split())
    if vote == 0:
        t, a = T, A
        vote = t+A
        continue
    t1, a1 = T, A
    while not (t <= t1 and a <= a1):
        t1 += T
        a1 += A
    t, a = t1, a1
print(t+a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
T, A = map(int, input().split())
num = T + A
for _ in range(N-1):
  t, a = map(int, input().split())
  while True:
    if num%(t+a) == 0 and (num*t)//(t+a) >= T and (num*a)//(t+a) >= A:
      T = (num*t)//(t+a)
      A = (num*a)//(t+a)
      break
    num += num%(t+a)
print(num)