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

Обсуждение задачи 1032. Найдите кратное

Моя программа ЗДАЛАСЬ за O(n)
Послано OSPU 10 мар 2003 21:06
program a1032;
var mas,a:array[0..10001] of integer;
    i,j,n:integer;
    s:longint;
begin
for i:=0 to 10001 do
   mas[i]:=0;
readln(n);
s:=0;
for i:=1 to n do
   begin
   readln(a[i]);
   s:=(s+a[i]) mod n;
   if s=0 then
       begin
       writeln(i);
       for j:=1 to i do
           writeln(a[j]);
       halt;
       end;
   if mas[s]<>0 then
       begin
       writeln(i-j-1);
       for j:=mas[s]+1 to i do
       writeln(a[j]);
       halt;
       end;
   mas[s]:=i;
   end;
writeln(0);
end.
plz write just English..
Послано Pasha 10 мар 2003 21:51
?
Послано Locomotive 10 мар 2003 21:52
As you know i can prove that there is 1<=i<j<=n that:
( a[i]+a[i+1]+...+a[j-1]+a[j] ) mod n =0
because as box-principle(or pigeonhole) if we define
b[i]:=a[i] mod n
and b[0]:=0;

we see b[x] es should be in range [0..n-1] but they are n+1 b(b[0] to
b[n])
and it means there is two b (like (b[i],b[j]) that hey are equal
b[i]=b[j]
so
we see:
P1=a[1]+a[2]+a[3]+..a[j]=l*n+b[j]
and
P2=a[1]+a[2]+a[3]+..a[i]=k*n+b[i]
so if we calculate p1-p2 we see:
P3=a[j]+a[j-1]+a[j-2]+..a[i+2]+a[i+1]=
  (l-k)*n+b[j]-b[i]
and we knew b[i]=b[j] so
P3=(l-k)*n ----> p3 mod n =0!!!!
so we should calcualte all b(s) and find I and J
so:
(with this algorithm we dont need to read all numbers!)
here is my code:

Var
  n,i,k               :integer;
  a                   :array[0..10000] of integer;
  m                   :array[0.. 9999] of integer;
begin
  readln(n);
  fillchar(m,sizeof(m),-1);
  m[0]:=0; k:=0;
  repeat
    inc(a[0]);
    readln(a[a[0]]);
    k:=(k+a[a[0]]) mod n;
    if m[k]=-1 then
      m[k]:=a[0]
    else
    begin
      writeln(a[0]-m[k]);
      for i:=m[k]+1 to a[0] do
        writeln(a[i]);
      break;
    end;
  until false;
end.


~~~~~~~~~~~~~~~~~~~~~~
Please tell me if you dont understand it at all.
and your notice about it
Sincerely
Aidin_n7@hotmail.com
OSPU stated: my program's ACCEPTED with O(n) complexity (-)
Послано Dictionary :) 17 мар 2003 21:35