| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贪心正确性个人理解首先自己可以数学归纳法证明:多位数的各数位乘积一定小于原数
所以我们知道输出的数一定是一步乘成读入的数
然后因为数的位数越小越好,并且我们希望大的数排在小的数的后面
所以从个位往上枚举每位的数的大小
对于个位数直接特判即可
代码:
var
a,ans,b:array[0..1010] of longint;
n,m,i,j,k,l,s:longint;
st:ansistring;
f:boolean;
function check:boolean;
begin
exit((a[0]=1)and(a[1]=1));
end;
function zc(x:longint):boolean;
var i,k:longint;
begin
k:=0;
for i:=1 to a[0] do
begin
b[i]:=(k*10+a[i]) div x;
k:=(k*10+a[i]) mod x;
end;
if k<>0 then exit(false);
if b[1]=0 then k:=2 else k:=1;
for i:=k to a[0] do a[i-k+1]:=b[i];
a[0]:=a[0]-k+1;
exit(true);
end;
begin
readln(st);
while st<>'-1' do
begin
l:=length(st); a[0]:=l;
for i:=1 to l do a[i]:=ord(st[i])-48;
if l=1 then begin writeln(1,st); readln(st); continue; end;
ans[0]:=0;
while not check do
begin
f:=false;
for i:=9 downto 2 do
if zc(i) then begin f:=true; break; end;
if not f then break;
inc(ans[0]);
ans[ans[0]]:=i;
end;
if not f then write('There is no such number.')
else for i:=ans[0] downto 1 do write(ans[i]);
writeln;
readln(st);
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator