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

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

---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано Locomotive 19 дек 2002 13:14
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
fillchar(m,sizeof(m),-1);
m[0]:=0; k:=0;
repeat
inc(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.
Sincerely
Aidin_n7@hotmail.com

Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано Sid 18 апр 2005 22:53
Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n;

Edited by author 19.04.2005 14:19
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано Machvi 24 фев 2007 18:28
Sid писал(a) 18 апреля 2005 22:53
Cool It's great idea. But i think b[i]=(a[1]+...+a[i])%n;

right!!!
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано Machvi 24 фев 2007 18:29

Edited by author 24.02.2007 18:30
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано iverson_49 28 мар 2007 17:41
that's it
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано qwe (Dmitry) 5 сен 2008 17:46
Thank you so so much ))
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано grandvic 22 апр 2011 03:47
Respect!
Re: ---> Very Simple Way with O(N) and pigeonhole proving! <---
Послано jlcastrillon 19 авг 2011 07:37
amazing, really amazing.