| ENG RUS | Timus Online Judge |
Обсуждение задачи 1611. Децимацияanisca22 WA #12 // Задача 1611. Децимация 22 фев 2017 23:51 Give me a test or something... TR Sriram WA #22 [1] // Задача 1611. Децимация 8 сен 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 // Задача 1611. Децимация 16 дек 2016 18:58 Try this: 20 1 00000000100000000001 Answer: 0 1 15 Try_to_try WA #22 [2] // Задача 1611. Децимация 30 окт 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] // Задача 1611. Децимация 6 июл 2013 01:05 I have the same problem TR Sriram Re: WA #22 // Задача 1611. Децимация 8 сен 2015 20:26 Even i have the same problem! Can someone tell me what the mistake might be ? Destyon Need Help [4] // Задача 1611. Децимация 30 мар 2008 17:19 Give me some test please i have WA13 Alexander Kouprin Re: Need Help [3] // Задача 1611. Децимация 31 мар 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] // Задача 1611. Децимация 31 мар 2008 21:35 My answer also 5 Denis Koshman Re: Need Help [1] // Задача 1611. Децимация 4 авг 2008 12:36 5 6 1 2 3 4 11 12 Zhang Ye Re: Need Help // Задача 1611. Децимация 26 сен 2012 16:12 me too! marat Recursion // Задача 1611. Децимация 26 апр 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 Sergey What is complexity of your algo? [4] // Задача 1611. Децимация 3 апр 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? KIRILL(ArcSTUpid coder:) Re: What is complexity of your algo? [3] // Задача 1611. Децимация 3 апр 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] // Задача 1611. Децимация 4 авг 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] // Задача 1611. Децимация 19 окт 2008 14:47 I could adopt only O(N*K*10) in DP 198808xc Re: What is complexity of your algo? // Задача 1611. Децимация 21 окт 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 AlMag Also WA13. What to do? Some tricky tests? (-) // Задача 1611. Децимация 28 авг 2008 11:51
|