| ENG RUS | Timus Online Judge |
Discussion of Problem 1611. Decimationanisca22 WA #12 // Problem 1611. Decimation 22 Feb 2017 23:51 Give me a test or something... TR Sriram WA #22 [1] // Problem 1611. Decimation 8 Sep 2015 20:27 I am getting WA in 22nd case! I cant find my mistake. Can someone help me ? Tolstobrov Anatoliy[Ivanovo SPU] Re: WA #22 // Problem 1611. Decimation 16 Dec 2016 18:58 Try this: 20 1 00000000100000000001 Answer: 0 1 15 Try to try WA #22 [2] // Problem 1611. Decimation 30 Oct 2011 15:59 I couldn't understand why my program got WA in test 22. Can anyone give me some help. Thanks moji Re: WA #22 [1] // Problem 1611. Decimation 6 Jul 2013 01:05 I have the same problem TR Sriram Re: WA #22 // Problem 1611. Decimation 8 Sep 2015 20:26 Even i have the same problem! Can someone tell me what the mistake might be ? Destyon Need Help [4] // Problem 1611. Decimation 30 Mar 2008 17:19 Give me some test please i have WA13 Alexander Kouprin Re: Need Help [3] // Problem 1611. Decimation 31 Mar 2008 01:58 Try: 90 6 111110111110111110111110111110111110111110111110111110111110111110111110111110111110111110 One of correct answers is: 5 6 78 79 86 87 88 89 Destyon Re: Need Help [2] // Problem 1611. Decimation 31 Mar 2008 21:35 My answer also 5 Denis Koshman Re: Need Help [1] // Problem 1611. Decimation 4 Aug 2008 12:36 5 6 1 2 3 4 11 12 Zhang Ye Re: Need Help // Problem 1611. Decimation 26 Sep 2012 16:12 me too! marat Recursion // Problem 1611. Decimation 26 Apr 2011 15:12 It's not difficult to prove that if you optimally solved the problem with n conductors, n-1 conductors should be solved optimally too. Let a(n,k) be minimal total number of fined fare dodgers and good conductors. Then a(n,k) = MIN i FROM 0 TO k OF { a(n-1,i) + (n+k-[n is not a good conductor])/10 - (n-1+i)/10 } Details: Given k friends we should divide them into two parts. The first part should go and safe n-1 conductors and the second should stay between n-1 and n conductors. All we have to do is to count amount of fined friends in the second part + a(n-1,the first part) + whether n-th conductors is fined(1 or 0). [logical expression A] = 1, if A is true 0, otherwise What concerns test try these ones: ------------------------ 10 2 1110001011 possible answer: 0 2 2 1 ------------------------ 10 3 0001111111 possible answer: 1 0 ------------------------ 10 0 0001110001 possible answer: 1 0 ------------------------ 20 5 11111001110001110001 possible answer: 0 3 3 2 1 Vedernikoff 'Goryinyich' Sergey (HSE: АОП) What is complexity of your algo? [4] // Problem 1611. Decimation 3 Apr 2008 01:44 During the OpenCup I've accepted the problem with complexity O(N*K^2), but here, on timus, only optimizations helped me to beat timelimit with this algo. At the same time, some people have AC-times 0.015 or something like that. Is it possible to solve the problem with more efficient algo? KirillB(Arkhangelsk - PomorSU) Re: What is complexity of your algo? [3] // Problem 1611. Decimation 3 Apr 2008 02:53 O(N*K) my implementation is not so fast because of recursion Denis Koshman Re: What is complexity of your algo? [2] // Problem 1611. Decimation 4 Aug 2008 12:33 O(N*K). Are you sure it's still O(N*K) with recursion? svr Re: What is complexity of your algo? [1] // Problem 1611. Decimation 19 Oct 2008 14:47 I could adopt only O(N*K*10) in DP 198808xc Re: What is complexity of your algo? // Problem 1611. Decimation 21 Oct 2010 23:18 I got confused. My program is very short and the complexity is O(N*K). I didn't find anything hard when solving this. I think you must have made it harder in thought. BTW, not O(N*K*M), but O(N*K). M is the modulo(10 here). Edited by author 21.10.2010 23:19 Edited by author 21.10.2010 23:19 exwRabbits_AlMag(VNTU) Also WA13. What to do? Some tricky tests? (-) // Problem 1611. Decimation 28 Aug 2008 11:51
|