How do I get an unlimited length array from the console so that the test starts? What is the end character of the input?

Let suppose there is prefix sum array with mod n is pre1,pre2,......,pren. Since there can be only n-1 numbers present except zero. If zero is one of elements in prefix sum array then answer is already 0 to i. Else If zero is not present then some number should repeat because prefix array is of size n but only 1,2.... n-1 numbers are present. So there should be particular i,j => prei==prej. Therefore from i+1 to j segment will be divisible by n.

Edited by author 08.12.2020 00:01

Pigeonhole principle: It will always be possible and the answer will always be a continuous sequence.
How to solve:
Consider N = 7:
1 2 50 3 4 0 0
The sum of the segment 1, 2, 50 is 53 and that of 1,2,50,3,4 is 60
53 % 7 = 4
60 % 7 = 4
if a % x = 1
and b % x =1
then (a-b)%x is always 0
So the segment between those two prefix sums will give 0 as modulo which is (3,4) = 7

random_shuffle and check prefix sums for division.

The test has only one number:
1
2

Could someone help me. I've tried to solve the problem
using a classical Lee approach and for the worst case
when the numbers are very small (eg. 1 or 2), the program
takes about 4 secs on my PII-350.

The Dirichlet method of solving isn't a better solution
because it has the same complexity.

Could someone give me a hint on optimizing my algorithm or
if you got a better solution could you please forward it.

Thankz.

There is a typo in statement in the first part of it. The sentence:
"This numbers are not necessarily different"
should be written as:
"These numbers are not necessarily different".

Try this test (it helped me, but real test #36 has N = 10000):
7
4
4
4
5
5
5
5
Answer, of course, is for example
3
5
4
5

Hi,
Does the solution require the set having the minimum cardinality having numbers that sums to k*n? I am getting a WA, but the solution appears pretty right to me.
If so, the question makes it appear that you can get by with any set. @Mods can this be updated in that case?

Thanks.

For test 34 I have time limit exceeded answer. I have done the problem in Java. May I see the test 34? Thanks.

What is test no. 3 ?

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

This is ridiculous!!
My AC solution (ACed twice) works in 0.950 seconds. Which is actually O(n^2). The code is long and nasty... After some "improvements" - ie changing ArrayList to LinkedList/getting rid off BitSet/etc - the running time should decrease drastically!! but it gives me TL... WTF?
I was sure, that my "better" code works FASTER, since there is much less operations to perform...
Can anyone help me with it? I can send the code to get feedback.
Thanks!

What is the answer to
3
1
2
3

According to the question, the answer should be
1
3
isn't it? But why the correct answer is
2
1
2


What is exactly the sentence below mean?
"Your task is to choose a few of given numbers (1 ≤ few ≤ N) so that the sum of chosen numbers is multiple for N"

Is it already correct that the answer to the above question is {1, 2} where as the minimum set which its sum divisible by 3 is {3}. (I'm not English native)

Edited by author 07.02.2010 23:20

Check please test 33.
It's very strange that dp ( subset with given sum ) don't work.
Maybe there is a bad checker.

Solution with DP (minimal summand count) gets WA3.
Changing 1 line (eliminating miminizing) makes it AC.

My solution gives the minimal possible answer ? and yet it still gets WA#1. I tried many times but the result remained unchanged ? Why?

Can the sample output be
4
1
2
3
4 ???

Edited by author 17.03.2007 00:19