194AC - ABC046C: AtCoDeer and Election Report

ABC046-C (300 points)

問題

高橋くんと青木くんの二人が出ている選挙で, 二人の得票数の比が表示されている選挙速報を見ている.
回目に画面を見たときに表示されている比が であるとき, 回目に画面を見たときの投票数として考えられるものの最小値を求める.
ただし, 回目の画面を見た時点で, 高橋くん, 青木くんはそれぞれ 票以上を得ており, 得票数が途中で減ることはないものする.

• 
• 
• と は互いに素である.
• 答えは 以下である.

方針

以下の条件を満たすように [k = 1, \ldots, N] について考えられる最小の投票数を順番に求めていく.

• 回目の画面を見た時点で, 高橋くん, 青木くんそれぞれ 票以上を得ている.
• 回目に画面を見たときの高橋くん, 青木くんそれぞれの得票数は, ( は自然数) でなければならない.
• 得票数が途中で減ることはない.
• math.ceilの挙動でハマる. 未解決.

import math

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


T = 1 # 高橋くんの最小得票数
A = 1 # 青木くんの最小得票数
ans = 2

for i in range(0, N):
    # m = max(math.ceil(T / TA[i][0]), math.ceil(A / TA[i][1]))
    m = max(T // TA[i][0] + (T % TA[i][0] != 0), A // TA[i][1] + (A % TA[i][1] != 0))
    T = TA[i][0] * m
    A = TA[i][1] * m
    ans = T + A

print(ans)