Discussion @ 1138. Integer Percentage @ Timus Online Judge

HELP!!! I always get "TIME EXCEEDED!" turkeys 4 Mar 2002 19:00

program URAL1138;
const
    max=10000;
var
    opt:array[1..max] of integer;
    i,j,n,s,t:integer;
begin
    read(n,s);
    fillchar(opt,sizeof(opt),0);
    opt[s]:=1;
    for i:=s to n do
            if opt[i]<>0 then
                 for j:=i+1 to n do
                        if (opt[j]<opt[i]+1) and (j*100 mod i=0) then
                           opt[j]:=opt[i]+1;
    t:=0;
    for i:=s to n do if opt[i]>t then t:=opt[i];
    writeln(t);
end.

Re: HELP!!! I always get "TIME EXCEEDED!" Bighead 19 Apr 2002 07:57

This way be useful:
First, add a integer k in the Var Part.
Second, change

for j:=i+1 to n do
    if (opt[j]<opt[i]+1) and (j*100 mod i=0) then
       opt[j]:=opt[i]+1;

into:

if n>i*2 then k:=i*2 else k:=n;
for j:=i+1 to k do
    if (opt[j]<opt[i]+1) and (j*100 mod i=0) then
       opt[j]:=opt[i]+1;

I have used this way to get AC.

My program is quite similar to yours, but TLE. Koala 14 Feb 2003 13:59

program p1138;

const
maxn=10000;

var
c:array [1..maxn] of longint;
ans,n,s,i,high,j:longint;

begin
read(n,s);

fillchar(c,sizeof(c),0);
c[s]:=1;
for i:=s to n-1 do
    if c[i]>0 then
    begin
      if n>i+i then high:=i+i else high:=n;
      for j:=i+1 to high do
        if (c[i]+1>c[j]) and (j*100 mod i=0)
          then c[j]:=c[i]+1;
    end;

ans:=0;
for i:=s to n do
    if c[i]>ans then ans:=c[i];
writeln(ans);
end.

Discussion of Problem 1138. Integer Percentage