I have thought this problem for a long time and i haven't obtained
nothing. In the discussion board says you can do it in O(n); but
simply i don't know :|

> I have thought this problem for a long time and i haven't obtained
> nothing. In the discussion board says you can do it in O(n); but
> simply i don't know :|

This problem on arithmetic theory.

 Let us S be a summa of first i elements.

So,
 s:=0;
 for i:=1 to n do begin
  read(j);
  ..
  ..
  ..
  sum:=sum+j;
  ..
  ..
  ..
 end;

On each step we have two cases:
 1. sum mod n=0
 2. sum mod n=b. If there is a number A in our input data(in first i
elemnts!) so that A mod n=b then we can take number (sum-A) - it is
our answer.

As we take n numbers there is at least one answer.

For more help you can e-mail : nsc2001@rambler.ru

> I have thought this problem for a long time and i haven't obtained
> nothing. In the discussion board says you can do it in O(n); but
> simply i don't know :|

This problem on arithmetic theory.

 Let us S be a summa of first i elements.

So,
 s:=0;
 for i:=1 to n do begin
  read(j);
  ..
  ..
  ..
  sum:=sum+j;
  ..
  ..
  ..
 end;

On each step we have two cases:
 1. sum mod n=0
 2. sum mod n=b. If there is a number A in our input data(in first i
elemnts!) so that A mod n=b then we can take number (sum-A) - it is
our answer.

As we take n numbers there is at least one answer.

For more help you can e-mail : nsc2001@rambler.ru