ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1138. Integer Percentage

var max:array[1..10000] of longint;
    s,d,e,x,j,i,n,m:longint;

function gcd(a,b:longint):longint;
  begin
    if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b)
  end;

begin
  fillchar(max,sizeof(max),0);
  read(n,s);
  if n<s then writeln(0) else begin
  max[s]:=1;
  for i:=s to n-1 do
    begin
      d:=gcd(i,100); e:=100 div d;
      for j:=1 to d do begin
        x:=i+i*j*e div 100;
        if (x<=n)and(max[x]<max[i]+1) then max[x]:=max[i]+1
      end;
    end;
  m:=1;
  for i:=s to n do if max[i]>m then m:=max[i];
  writeln(m)
  end
end.
Li Xun Oh!I've got AC now! [1] // Problem 1138. Integer Percentage 16 Apr 2003 21:26
> var max:array[1..10000] of longint;
>     s,d,e,x,j,i,n,m:longint;
>
> function gcd(a,b:longint):longint;
>   begin
>     if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b)
>   end;
>
> begin
>   fillchar(max,sizeof(max),0);
>   read(n,s);
>   if n<s then writeln(0) else begin
>   max[s]:=1;
>   for i:=s to n-1 do
>     begin
>       d:=gcd(i,100); e:=100 div d;
>       for j:=1 to d do begin
>         x:=i+i*j*e div 100;
>         if (x<=n)and(max[x]<max[i]+1) then max[x]:=max[i]+1
>       end;
>     end;
>   m:=1;
>   for i:=s to n do if max[i]>m then m:=max[i];
>   writeln(m)
>   end
> end.
>
Liszt Re: Oh!I've got AC now! // Problem 1138. Integer Percentage 11 May 2004 21:02
Could you tell me why you got WA at first