福州一中 林尔桢
【数据结构】
考虑到此题的测试数据可能较大，故采用一Record型变量储存数组，其中：Len表示当前数值的位数，Byte型数组Data[1..Maxn]储存数值各位上的数字。
【问题分析】
首先，先计算得到的数a与k相乘后的各位数字和s。因为题目中的k在场整形范围内，故只需将数组a.Data内的各位数字由低至高乘以k后取个位数字，剩余的数进位至下一位，再将此时的a.Data中各位数字相加，之和即为s。
现在，题目变为：已知数A与s，求另一数C，使其各位数字之和为s，并且C是符合此条件的最小的数。考虑用以下算法：
建一Shortint型数组d[0..Maxn]，从此数组的第一位（即d[1]）开始，取a.Data[i]的值（i为此时取的位数），同时把s减去a.Data[i]的值。
当发现s的值小等于零时，将d[i]的值取为d[i]+s-1，并将d[i-1]的值加一，如果di-1]的值大于9则进位（具体操作参看下文加下划线文字），并将数组的下一位置末尾的值都赋为零，再将数组中从第i位至末位的数进行变换。具体操作为：第i位的数与末位数调换位置，第i-1位与倒数第二位调换……即可。
例：A=129945，s=23。
首先对数组d各项赋值，依次为：1，2，9，9，赋值至第5项时，d[5]=4，而s= -2<0，故d[5]=4+s=4+(-2)=2，对d[4]进行进位操作，d[6]取零后得到新数：139910，将"9910"变换操作后得数130199即为正确答案。
当取遍数组后，如果s的值大于零，则将数组的最后一位（即数值的个位）与s相加。如果此时数组的最后一位大于9，则把数组的最后一位赋值为9，将它与9的差与它的前一位相加，一直到某一位不超过9为止（当a[1]>9时，进位至a[0]，并将数组往后移一位）。这里有个技巧：可将数组设为d[-10..Maxn]，再建一变量ｔ，数组需要后移时，把ｔ的值加１，最后根据ｔ的值移位，可减少程序的运算量。
例：A=129945，s=43。
首先对数组d各项赋值，依次为：1，2，9，9，4，5。此时已赋值完毕，而s=13，进位操作后得新数169999即位正确答案。
再将a赋值为求得的数，循环(n-1)次，即可。
【参考程序】
Program number;
Const
inputfilename='numbers.in2';
outputfilename=''{'numbers.out'};
Maxn=5000;
TYPE
num=RECORD
len:integer;
data:array[1..maxn]of 0..9;
end;
Var
a:num;
k,n,h:longint;
Procedure readdata;
var f:text;
c:array[0..maxn] of 0..9;
str,i:longint;
Begin
assign(f,inputfilename);
reset(f);
readln(f,str,k,n);
a.len:=0;
while str>0 do
begin
inc(a.len);
a.data[a.len]:=str mod 10;
str:=str div 10;
end;
for i:=1 to a.len do c[i]:=a.data[a.len-i+1];
for i:=1 to a.len do a.data[i]:=c[i];
close(f);
End;
Procedure gettotal;
var
i,t:longint;
Begin
h:=0;
t:=0;
for i:=a.len downto 1 do
begin
t:=longint(a.data[i])*k+t;
inc(h,t mod 10);
t:=t div 10;
end;
while t>0 do
begin
inc(h,t mod 10);
t:=t div 10;
end;
End;
Procedure doing;
var
i,j,jj,q,t,u,uu:longint;
c:array[-10..maxn] of integer;
d:array[1..50] of integer;
Begin
for t:=2 to n do
begin
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
gettotal;
j:=0; jj:=0; i:=a.len;
while (h>0) and (j<=a.len) do
begin
inc(j);
c[j]:=a.data[j];
h:=h-c[j];
if h<=0 then
begin
c[j]:=c[j]+h;
jj:=j;
end;
end;
if jj>0 then
begin
q:=jj;
inc(c[jj-1]);
dec(c[jj]);
while c[jj-1]>9 do
begin
c[jj-2]:=c[jj-2]+c[jj-1]-9;
c[jj-1]:=9;
dec(q);
dec(jj);
end;
jj:=c[q]; h:=0;
for j:=q to a.len do
begin
inc(h);
d[h]:=c[j];
end;
for j:=h downto 1 do
c[q+h-j]:=d[j];
end
else
begin
c[i]:=c[i]+h;
while c[i]>9 do
begin
c[i-1]:=c[i-1]+c[i]-9;
c[i]:=9;
dec(i);
end;
end;
uu:=-10;
while c[uu]=0 do inc(uu);
u:=a.len-uu+1;
q:=1-uu;
for i:=1 to u do a.data[i]:=c[i-q];
a.len:=u;
end;
End;
Procedure print;
var f:text; i:longint;
Begin
assign(f,outputfilename);
rewrite(f);
for i:=1 to a.len do write(f,a.data[i]);
writeln(f);
close(f);
End;
Begin
readdata;
doing;
print;
End.
|
