← 返回题目列表

AtCoder · ddcc2020_qual_d

D. 数字和替换

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

N 程序员将参加DDCC 20XX的预赛阶段。不过由于场地的大小,最多 9 参赛者可参加决赛。

预赛由几轮组成,具体如下:

  • 所有 N 参赛者将参加第一轮。
  • 当 X 选手参加某轮比赛,晋级下一轮的选手人数将按如下方式决定:
    • 主办方将选择十进制中连续两位数字 X,并将它们替换为这些数字的总和。得出的数字将是晋级下一轮的参赛者人数。
      例如,当 X = 2378,晋级下一轮的参赛者人数为 578 (如果 选择 2 和 3 ), 选择 2108 (如果 选择 3 和 7 ),或 选择 2315 (如果 选择 7 和 8 )。
      当 X = 100,晋级下一轮的参赛者人数为 10,无论选择哪两位数字。
  • 预赛阶段结束时 9 或更少的参赛者剩余。

首席组织者林戈希望举办尽可能多的比赛。 求出预赛阶段的最大可能回合数。

由于参赛人数较多, N,可以是巨大的,它以两个整数序列的形式提供给您 d_1, \ldots, d_M 和 c_1, \ldots, c_M,其含义如下:十进制表示法 N 包括 c_1 + c_2 + \ldots + c_M 数字,其第一个 c_1 数字全部 d_1,以下 c_2 数字全部 d_2, \ldots,最后一个 c_M 数字全部 d_M.

约束

  • 1 \leq M \leq 200000
  • 0 \leq d_i \leq 9
  • d_1 \neq 0
  • d_i \neq d_{i+1}
  • c_i \geq 1
  • 2 \leq c_1 + \ldots + c_M \leq 10^{15}

输入

输入由标准输入按以下格式给出:

M
d_1 c_1
d_2 c_2
:
d_M c_M

输出

打印初级阶段的最大可能轮数。


示例输入 1

2
2 2
9 1

示例输出 1

3

在这种情况下, N = 229 参赛者将参加第一轮。初步阶段的一种可能的进展如下:

  • 229 参赛者参加回合 1, 49 参赛者参加回合 2, 13 参赛者参加回合 3,和 4 选手晋级决赛。

这里,预赛阶段进行三轮,这是可能的最大数量。


示例输入 2

3
1 1
0 8
7 1

示例输出 2

9

在这种情况下, 1000000007 将参加第一轮。