Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

贪心正确性个人理解

Posted by wukewen at 2014-11-02 17:38:49 on Problem 2325
首先自己可以数学归纳法证明:多位数的各数位乘积一定小于原数
所以我们知道输出的数一定是一步乘成读入的数
然后因为数的位数越小越好,并且我们希望大的数排在小的数的后面
所以从个位往上枚举每位的数的大小
对于个位数直接特判即可

代码:
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator