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