ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1138. Целочисленные проценты

HELP!!! I always get "TIME EXCEEDED!"
Послано turkeys 4 мар 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 апр 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 фев 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.