Page 3 How do I get an unlimited length array from the console so that the test starts? What is the end character of the input? When you use scanf(), generall you can check the return value of scanf(). If the return value is equal to -1, it means that it gets the end of input. Besides, you when you use cin, you can just judge if the input is end by the return value of cin is 0 or not. If it is 0, it means the end. eg: int main(){ int n; while(scanf("%d", &n) != -1){ .... } } and int main(){ int n; while(cin >> n){ .... } } 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. Page 2 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. Does it say it requires a minimum cardinality? For test 34 I have time limit exceeded answer. I have done the problem in Java. May I see the test 34? Thanks. I solved by using int[] instead of ArrayList. The test has only one number: 1 2 Ohhhhhhh,thank youuuuuu! Try also this test: 5 3 1 3 3 3 Answer is, of course: 4 1 3 3 3 The test has only one number: 1 2 This test isn't coorectly because numbers is [1, N] correct testcase is: 1 1 And my program print coorect answer: 1 1 But I still have WA1.. someone can help? P.S. my program pass your testcase too =) No, numbers are in [1, 15000], not [1, N]. :) 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! And I'm interesting how to solve this in 0,015s. well... There's good idea in neighbor thread, which proves that solution always exist. It can help you solve it in O(n). Or... you can think up your own ideas based on remainders... There's up to N remainders only... so I used BFS without considering duplicates... it works fast enough in Java. Yeah, there is a nice idea. =) 0.14 seconds on JAVA, O(nlogn + n) solution 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 you should print any set of numbers/ so, both answers are possible. even 3 1 2 3 Check please test 33. It's very strange that dp ( subset with given sum ) don't work. Maybe there is a bad checker. Both test 33 and checker are correct. Look for a bug in your solution. Good luck! Thank's. Stupid error in my algo. 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? Print numbers from list such that the sum of those numbers is a multiple of n. You can do it yourself! Here's a hint. Consider the sum of the first k integers for k = 1 to n. I got AC now. And I got WA twice only because I forgot a stupid santance "memset(o,0,sizeof(o));". I can run it in FP,but if I put it on,it will showed'Compilation error'. Who can tell me why? var n,i,j,t,l:longint; a:array[0..1000] of longint; c:array[0..1000] of boolean; f:array[0..50000,0..1000] of boolean; begin readln(n); for i:=1 to n do readln(a[i]); c[0]:=true;f[0,0]:=true; for i:=1 to n do for j:=n downto a[i] do if c[j-a[i]] then begin c[j]:=true; for l:=0 to i-1 do if f[j-a[i],l] then f[j,l]:=true; f[j,i]:=true; if j=n then begin for i:=1 to i do if f[n,i] then inc(t); writeln(t); for i:=1 to i do if f[n,i] then writeln(a[i]);halt; end; end; writeln(0); end.
var n,i,j,t,l:longint; a:array[0..1000] of longint; c:array[0..1000] of boolean; f:array[0..50000,0..1000] of boolean; begin readln(n); for i:=1 to n do readln(a[i]); c[0]:=true;f[0,0]:=true; for i:=1 to n do //If you use var i here for j:=n downto a[i] do if c[j-a[i]] then begin c[j]:=true; for l:=0 to i-1 do if f[j-a[i],l] then f[j,l]:=true; f[j,i]:=true; if j=n then begin for i:=1 to i do // then you can not use it inside cycle if f[n,i] then inc(t); writeln(t); for i:=1 to i do if f[n,i] then writeln(a[i]);halt; end; end; writeln(0); end. You can choose "send reply on my email" for explanations Edited by author 23.11.2007 15:59 can the answer contain 2 numbers of equal magnitude?? please help |
|