/ Vijos / 题库 /

电子表

电子表

背景

计数问题

描述

我们有一个N位数字的电子表,当时间到达10^N-1时,下一秒就归0。下面我们给出数字0 到 9的模拟图。

        +   +---+   +---+   +   +   +---+
        |       |       |   |   |   |
        +   +---+   +---+   +---+   +---+
        |   |           |       |       |
        +   +---+   +---+       +   +---+

    +---+   +---+   +---+   +---+   +---+
    |           |   |   |   |   |   |   |
    +---+       +   +---+   +---+   +   +
    |   |       |   |   |       |   |   |
    +---+       +   +---+       +   +---+

对于每个数字,相邻两个+之间会有一根电子管,当显示该数字时,这些电子管就会发亮。如上图所示:数字0到9,它们的电子管数量分别是:6、2、 5、 5、 4、 5、 6、 3、 7、 5。

设现在的时刻是X, 那么可以算出该时有多少根电子管是亮的。比如:现在时刻是:99,那么共有5 + 5= 10根电子管是亮的。假如从现在时刻开始,再过Y秒后,时刻显示为Z, 我们的问题是:求最小的Y,使得时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等。如:现在X = 99 ,那么再过Y = 5 秒后, 时刻变成了Z = 04, 而时刻Z发亮的电子管数量 = 6 + 4 = 10。于是Y = 5就是你要求的数。

格式

输入格式

第一行:一个整数N,表示电子表是10^N进制的。1 <= N <= 15。

对于30%数据,N < 7.
第二行:一个整数X, 表示现在的时刻,可能有前导0。X有N位数字。

输出格式

一行:最小的整数Y, 表示从现在X时刻开始,再过Y秒,得到的时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等

样例1

样例输入1

3
007

样例输出1

11

限制

1s

提示

11(因为数字007有6+6+3 =15根电子管发亮,所以过11秒后,电子表显示数字018时,才能满足发亮的电子管数量相等。018时刻发亮的电子管数量 = 6 + 2 + 7 = 15)

信息

ID
1374
难度
6
分类
动态规划 | 搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
132
已通过
36
通过率
27%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库