| ENG RUS | Timus Online Judge |
Обсуждение задачи 1803. Винтовки белочеховZARHANE Any test cases ? [4] // Задача 1803. Винтовки белочехов 1 ноя 2010 23:32 I have WA for Test #11. Any test case ? Erop [USU] Re: Any test cases ? [3] // Задача 1803. Винтовки белочехов 2 ноя 2010 14:00 2 40 1 2 3 6 4 5 9 12 7 8 11 15 18 10 13 19 14 21 24 25 17 16 20 22 30 26 32 38 23 27 28 31 35 29 34 36 39 33 37 40 10 40 1 2 3 4 8 7 5 9 15 6 13 12 10 19 11 14 22 30 18 25 26 21 28 17 29 16 20 40 24 36 23 27 32 31 33 35 37 34 39 38 mnk Re: Any test cases ? [1] // Задача 1803. Винтовки белочехов 3 ноя 2010 20:43 Both from them are passed, but I still have WA 11. Please, give another test cases. Vasiliy Re: Any test cases ? // Задача 1803. Винтовки белочехов 4 ноя 2010 20:14 Fibonachi digits grow very fast. Even UInt64 is incefficient for fibonachi digit with number 93. luckysundog Re: Any test cases ? // Задача 1803. Винтовки белочехов 17 ноя 2011 08:21 Test 11 beats unstable sorting algorithms like QuickSort. Test "10 40" shows it too. TheMentalist WA in #12 // Задача 1803. Винтовки белочехов 27 май 2011 08:16 oooops! How come? This is the last result that I expected.. What could possibly go wrong? If compeared, the output for case 10,50000 is just the same, as that of my previous version, which got TLE at #12. I can't even think of an algo error.. Ibragim Atadjanov (Tashkent U of IT) TL11 [5] // Задача 1803. Винтовки белочехов 7 ноя 2010 07:04 Edited by author 11.11.2010 07:28 Moonstone [Samara SAU] Re: TL11 [4] // Задача 1803. Винтовки белочехов 7 ноя 2010 13:28 Of course, it's slow! BigIntegers are not allowed in this problem! And replace your precalculations by while cycle and in k-based numeral system! Edited by author 07.11.2010 13:42 Ibragim Atadjanov (Tashkent U of IT) still got tl11 [1] // Задача 1803. Винтовки белочехов 8 ноя 2010 21:04 Edited by author 11.11.2010 07:28 Ibragim Atadjanov (Tashkent U of IT) Re: still got tl11 // Задача 1803. Винтовки белочехов 11 ноя 2010 07:24 AC dont use ArrayList for adding two big numbers just used array (in java) Ibragim Atadjanov (Tashkent U of IT) Re: TL11 [1] // Задача 1803. Винтовки белочехов 11 ноя 2010 07:29 thanks Kolyanich Re: TL11 // Задача 1803. Винтовки белочехов 15 фев 2011 04:52 If you have TLE#11 consider to use not "one byte per one digit" representation, but rather one 16/32 bit int per group of digits. Another hint: when you sum all digits in your next fibonacci number and use 16-24 bits per group approach, you can precalculate sum of digits in every possible of such groups before the main loop. Vasiliy Solving [12] // Задача 1803. Винтовки белочехов 31 окт 2010 16:56 Could you please give me a hint? Do we need to generate a fibonachi digits in any way or there is a better solution? quick(YarSU) Re: Solving // Задача 1803. Винтовки белочехов 31 окт 2010 19:37 same question. I wrote the solution: 1) generate fib one by one and sum digits. 2) very optimize actions and no copy array of digits 3) stable sort or count sort ==> it works on test "2 50000" about 4 - 5 second. TL 12 How did you avoid TL? Moonstone [Samara SAU] Re: Solving [10] // Задача 1803. Винтовки белочехов 1 ноя 2010 09:56 1. Generate all sums of digits for numbers from 0 to k^p-1 (the best p is 6 for my solution) 2. Replace k with k^p 3. Run stupid solution but add precalculated numbers to sum 4. ??????? 5. PROFIT quick(YarSU) Re: Solving [6] // Задача 1803. Винтовки белочехов 1 ноя 2010 12:41 accepted... 72VanVector[SevNTU] Re: Solving [5] // Задача 1803. Винтовки белочехов 4 ноя 2010 20:50 How can i generate Fibonchi num 50000? it is very big! Moonstone [Samara SAU] Re: Solving [4] // Задача 1803. Винтовки белочехов 4 ноя 2010 22:48 Use long arithmetics. 72VanVector[SevNTU] Re: Solving [3] // Задача 1803. Винтовки белочехов 5 ноя 2010 01:57 So in the worst case i must calculate the 50000 Fibonachi numbers, writing them using long arithmetic, at the same time calculating the number of banknotes to pay for them, writing this calculations in separate array. Then i must sort this array and print the bounded numbers of sorted elements from begin to the end. Is this method ok? Moonstone [Samara SAU] Re: Solving [2] // Задача 1803. Винтовки белочехов 5 ноя 2010 13:57 This method gets TLE, but it may be improved (look at my previous messages). 72VanVector[SevNTU] Re: Solving [1] // Задача 1803. Винтовки белочехов 5 ноя 2010 14:52 Thx... Will try to calculate the number of banknotes using precounted values... Vasiliy Re: Solving // Задача 1803. Винтовки белочехов 8 ноя 2010 01:26 Guys, could you please send me your code for investigation? kobchik83@list.ru elkasimi Re: Solving // Задача 1803. Винтовки белочехов 4 дек 2010 21:47 THANKS A LOT FOR YOUR HINT !! elkasimi Re: Solving // Задача 1803. Винтовки белочехов 4 дек 2010 21:51 THANKS A LOT FOR YOUR HINT !! elkasimi Re: Solving // Задача 1803. Винтовки белочехов 4 дек 2010 21:53 Edited by author 04.12.2010 21:54 72VanVector[SevNTU] Will the answer AC?? [3] // Задача 1803. Винтовки белочехов 4 ноя 2010 17:05 72VanVector[SevNTU] Re: Will the answer AC?? [2] // Задача 1803. Винтовки белочехов 4 ноя 2010 17:07 In test case 10 8 we have answer 1 2 3 4 8 7 5 6... But the fist gun can be bought for 1 moneyticket and the 2 also. Will the answer 2 1 3 4 8 7 5 6 be correct?? Moonstone [Samara SAU] Re: Will the answer AC?? [1] // Задача 1803. Винтовки белочехов 4 ноя 2010 22:46 No. If the same quantity of notes was paid for two rifles, then the rifle with the smallest number should go first. 72VanVector[SevNTU] Re: Will the answer AC?? // Задача 1803. Винтовки белочехов 5 ноя 2010 01:58 clear
|