DDCC2020予選D Digit Sum Replace

はじめに

全問題の一覧はこちらです

実際にて計算をしてみると、どのような順で予選ラウンドを開催しても開催の回数が変わらないと分かります。

ただし、愚直に先頭からシミュレーションを行うと処理が間に合わないため、計算量を削減する方法を考えます。

予選を行うことで、桁数、全体の和がどのように変化するかに着目します。

これらの情報を元に、全体の和を一桁にするために何度、予選ラウンドを開催すれば良いかを計算できます。

解法がわかりさえすれば、実装はとてもシンプルです。

M = int(input())
S = 0 # 全体の和
C = 0 # 桁数
for m in range(M):
    d, c= map(int, input().split())
    S += d*c
    C += c
print ((C-1)+(S-1)//9)