DDCC2020 D - Digit Sum Replace

問題原文

D - Digit Sum Replace

問題要旨

が １桁になるまで以下の操作を繰り返す。

• の連続する２桁を選び、 その和に置き換える。

最大で何回操作できるか求めよ。

考えたこと

• 操作の順番は関係なさそう。

難しいこと

• いろんな実験をしても規則性が見えてこない。
• 枠で捉えるのが難しい。

考えるべきこと

• ２桁を選んだ結果は２パターンに大別できる。

  1. 桁数が１減って、桁和は変わらない
  2. 桁数は変わらず、桁和が９減る

• 桁数は１で終わるので、1. のパターンは 回行われる。

• 桁和が９以下になったら 2. のパターンは起こらない。すなわち、2.のパターンは 回行われる。

実装

M = int(input())
digit_num, digit_sum = 0, 0
for i in range(M):
    d, c = map(int, input().split())
    digit_num += c
    digit_sum += d * c

print((digit_num - 1) + ((digit_sum - 1) // 9))

所感

桁和の減る法則性に気づきたかった。