67788


# 問題文

<https://atcoder.jp/contests/arc062/tasks/arc062_a>

> シカのAtCoDeerくんは選挙速報を見ています。 選挙には二人の候補高橋くんと青木くんが出ています。  
>  速報では、現在の二人の得票数の比が表示されていますが、得票数そのものは表示されていません。 AtCoDeerくんは N 回画面を見て、  
>  i(1≦i≦N) 回目に見たときに表示されている比は Ti:Aiでした。  
>  ここで、AtCoDeerくんが選挙速報の画面を1回目に見た段階で既にどちらの候補にも少なくとも一票は入っていたことがわかっています。  
>  N回目に画面を見たときの投票数(二人の得票数の和)として考えられるもののうち最小となるものを求めてください。  
>  ただし、得票数が途中で減ることはありません。

# 回答方針

現在の人数を`t_num`, `a_num`とする。  
`t_num`と`a_num`を、i回目にみた時点での比率Ti:Aiにするために、

`t_num <= T[i] * n かつ a_num <= A[i] * n`

を満たすnを見つける。

### ソースコード

[code]

    from math import ceil
    
    N = int(input())
    T = []
    A = []
    
    for _ in range(N):
        t, a = list(map(int, input().split()))
        T.append(t)
        A.append(a)
    
    t_num = T[0]
    a_num = A[0]
    for i in range(1, N):
        tn = ceil(t_num / T[i])
        an = ceil(a_num / A[i])
        n = max(tn, an)
        t_num = T[i] * n
        a_num = A[i] * n
    
    print(t_num + a_num)
    
[/code]


CC BY-SA 4.0
2020-06-18T12:26:20.567
67786
2020-06-18T12:54:31.800
9616
question
python python3
AtCoder Regular Contest 062 C問題で不正解が発生


答えが10^18と大きくなるので浮動小数点演算を使うと誤差が出ます。


CC BY-SA 4.0
2020-06-18T12:54:31.800
67788
2020-06-18T12:54:31.800
33033
67786
answer