3600: 计数-训练套题T2T3

计数 DigitalCounter

n       数字0到9，它们的电子管数量分别是：6、2、 5、 5、 4、 5、 6、 3、 7、 5。

n       设现在的时刻是X, 那么可以算出该时有多少根电子管是亮的。

n       假如从现在时刻开始，再过Y秒后，时刻显示为Z, 我们的问题是：求最小的Y，使得时刻Z发亮的电子管数量与时刻X发亮的电子管数量相等。

n       统计一个数X有多少根电子管是亮的很容易

n       如果每次1秒增加，模拟现实过程，则因为最多有15位数，显然要超时。(1 <= N <= 15)

n       怎样做呢？
二分法？
找规律？
递推或DP？

n       没有单调性，不能二分。

n       找规律也好像不可能。

n       递推之类的？
不能按时间，那样会超时
按什么呢？

n       题目中的其它可能“变量”：
1）数X的位数len---15位
2）亮的电子管个数light---也不大<=15*7

n       设函数f(a)表示数a的有多少电子管是亮的。

n       初始数是X，则要找Y，使f(Y)=f(X)

n       假设Y>X，则Y尽量小：
1）开头数dig尽量小
3）开头数也一样？比较第二位数
…..

n       问题与长度、开头数、电子管数的判断有关。

n       工具函数g( len,  light) 判断问题。（没dig?）

n       g( len, light) 函数推算：

n       g(len, light) = or  g(len-1,light-f(i) )  i=0~9

即开头数字是0~9中任何一个成立都可以。

n       显然个g数组比较容易DP出来。

n       g( len, light) 函数推算：

n        g[0,0]:=true;

n            for i:=1 to N do

n              for j:=1 to 120 do

n                 for k:=0 to 9 do

n                   g[ i,j ] := g[i,j] or g[i-1, j - c[k] ];

n       有了g( len, light) 要求最接近X的Y

n       先看Y>X的情况:

n       考察例子：X =98675  f(x) = 26

  1）先看最后一位：

   y = 98676~98679  看有没有f(y)=26的

  2）再看第二位：

   y =9868*~9869*   如果有f(y)=26，再定*

  3）同理看 y=987**~989**

n       即先从低位到高位，从小到大，先看能否有一个类似： 988**成立，再推算最小的数**。

n       什样推算？
例如: 988**中，如果**还要7个电子管发亮，则只要从高位到低位试，看：0*~9*那些可行，比如1*可行，则看*中电子管为7-f(1)=7-2=5的，即0~9中选最小的电子管是5的数字2即可。最后答案为98812

n       Y<=X的情况只要推算最小的*****即可。

n       function getBig( var len, dig :integer) :boolean;

n       begin

n             fx:=0;

n             for i:=1  to N do                   //从低位到高位

n             begin

n                 fx := fx + c[ d[ i ]  ];          //原X的前i位电子管数

n           for j:=d[ i ]+1 to 9 do       //比原X第i位大的数，从小到大

n             if (fx>=c[j]) and (g[ i-1, fx - c[ j ] ] ) then

n                  begin  len:=i; dig:=j;  exit( true);           //找到最小的

n                       end;

n             end;

n             exit (false);

n       end;

n       procedure getMin(len, fx:integer);

n       begin

n           for i:=len downto 1 do    //从高位到低位

n           begin

n                 for j:=0 to 9 do        //尽量小数字

n              if  (fx>=c[j]) and (g[ i -1, fx - c[j] ] ) then

n                       break;

n           ans[ i ] := j;

n           fx := fx-c[j];               //后面还有多少电子管

n           end;

n       end;

procedure calc();

var  len, dig :integer;

begin

     ans:=d;

     if getBig(len,dig) then

     begin                  //如果在>X的Y，即不“环绕”

          ans[len]:=dig;

          getMin(len-1, fx-c[dig]);

         yy:=0;

         for i:=N downto 1 do yy := yy*10 + ans[i];

         Y:= yy - X;

     end

     else  begin               //如果“环绕”了

              getMin(N, fx);   //求一个尽量小的     

             yy:=0; Y:=1;

            for i:=N downto  1 do begin

                yy := yy*10 + ans[i];

                 Y := Y*10;    //求10^N

            end;

            Y:= Y-X + yy;

     end;

end;