原题：
我们有一个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。
第二行：一个整数X, 表示现在的时刻，可能有前导0。X有N位数字。
输出：
一行：最小的整数Y, 表示从现在X时刻开始，再过Y秒，得到的时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等。
样例输入：
3
007
样例输出：
11
样例说明：
因为数字007有6+6+3 =15根电子管发亮，所以过11秒后，电子表显示数字018时，才能满足发亮的电子管数量相等。018时刻发亮的电子管数量 = 6 + 2 + 7 = 15
数据说明：
对于30%数据，N < 7.
分析：
对于这道题目，很容易的一的想法就是不断+1，然后判断是否和原数相等，最后相减就是答案，但是这样肯定会超时，因为数字的位数最大有15，那么再来看仔细看题目，我们需要找的就是第一个比x大的并且电子管数量相同的数字(先不考虑超过上限回到0)，那么要比x大并且电子管数量相同这要怎么做呢？其实可以发现，从后一位开始改变(改大)，看是否可以变成数量相同的，如果当前位不可以，继续同时改后两位，直到可以改变成功。那么如何快速知道是否可以改变呢？需要一个辅助布尔型函数f[len,light,i]表示长度为len(从后往前数)，有Light个电子管，且最前面一个数字为i时 是否可以构成。递推而来就可以f[len,light,i]:=f[len,light,i]or f[len-1,light-e[i],j]（e是构成数字所需要的电子管数量，j需要枚举，是len-1时的数字）
举个例子，对于98765 我们先从最后一位开始找，发现不行，然后找后两位，也就是找98766-98799，看是否可以构成相同电子管数量，发现不行，再看第二位9868-9869，还是不行，然后继续，发现988**成立，那么第三个数字就改成8，然后往回推，继续改原先的数字，直到改完，可以递归进行，然后把改变的字符串和之前的字符串变成数字相减就得出答案了
对于超出n位的那么只需要判断一下，然后把答案字符串清0，从头开始继续上面所做，当然前面部分的答案最后要加上去
实现：
const
e:array[0..9]of longint=(6,2,5,5,4,5,6,3,7,5);
var
s,x:string;
i,j,k,l,n:longint;
bz:boolean;
a,b,ans,q:int64;
f:array[0..17,0..107,0..11]of boolean;
sum:array[0..17]of longint;
procedure dg(x,t:longint);
var
i:longint;
begin
if x=0 then exit;
for i:=0 to 9 do
if f[x,t,i] then break;
s[n-x+1]:=chr(i+48);
dg(x-1,t-e[i]);
end;
begin
readln(n);
readln(x);
s:=x;
for i:=0 to 9 do f[1,e[i],i]:=true;
for i:=2 to n do
for j:=0 to 9 do
for k:=e[j] to 7*i+1 do
for l:=0 to 9 do f[i,k,j]:=f[i,k,j] or f[i-1,k-e[j],l];
sum[0]:=0;
for i:=1 to n do sum[i]:=sum[i-1]+e[ord(s[n-i+1])-48];
bz:=false;
for i:=1 to n+1 do
begin
if bz or (i>n) then break;
for j:=ord(s[n-i+1])-48+1 to 9 do
if f[i,sum[i],j] then
begin
bz:=true;
break;
end;
end;
if bz then
begin
dec(i);
s[n-i+1]:=chr(j+48);
dg(i-1,sum[i]-e[j]);
val(s,a);
val(x,b);
writeln(a-b);
end
else
begin
s:='';
for i:=1 to n do s:=s+'0';
val(x,b);
q:=1;
for i:=1 to n do q:=q*10;
ans:=q-b;
for i:=1 to n+1 do
begin
if bz or (i>n) then break;
for j:=0 to 9 do
if sum[n]-(n-i)*e[0]>=0 then
if f[i,sum[n]-(n-i)*e[0],j] then
begin
bz:=true;
break;
end;
end;
dec(i);
s[n-i+1]:=chr(j+48);
dg(i-1,sum[n]-(n-i)*e[0]-e[j]);
val(s,a);
writeln(ans+a);
end;
end.
网友评论