| ENG RUS | Timus Online Judge |
Обсуждение задачи 1381. Тараканы в зданииxurshid_n I solve with simple recursion!!!! // Задача 1381. Тараканы в здании 13 авг 2012 14:47 after 2 days, found DP solution, and AC with 0.046 s. Edited by author 15.08.2012 16:07 Vedernikoff Sergey (HSE: АОП) WA 38. Something special? (-) [1] // Задача 1381. Тараканы в здании 23 май 2009 20:05 Erop [USU] Re: WA 38. Something special? (-) // Задача 1381. Тараканы в здании 16 мар 2012 01:36 I think in this test there is some big loop with small weight. So u need go through cicle many times to decrease (increase) population of cockroaches. EfremovAleksei I don't understand, why this simple problem, solved only 25 coders! [10] // Задача 1381. Тараканы в здании 14 фев 2007 22:39 svr Re: I don't understand, why this simple problem, solved only 25 coders! // Задача 1381. Тараканы в здании 14 фев 2007 22:46 I will try tomorrow and will be in one of two parties Kit Re: I don't understand, why this simple problem, solved only 25 coders! // Задача 1381. Тараканы в здании 15 фев 2007 01:16 As for me, this problem has quite unusual idea. BTW, I heard what famous "hard life" has fairly simple solution :) KIRILL(ArcSTU) Re: I don't understand, why this simple problem, solved only 25 coders! [7] // Задача 1381. Тараканы в здании 15 фев 2007 01:53 May be you one of the best coders:) an it's simple for you? Dmitry 'Diman_YES' Kovalioff The solution is really easy, but it is not that easy to think it out (-) [6] // Задача 1381. Тараканы в здании 15 фев 2007 09:12 svr Re: The solution is really easy, but it is not that easy to think it out (-) [5] // Задача 1381. Тараканы в здании 16 фев 2007 00:08 Could'n found very simple solution. In final version calcul z1(k)= min [F(0,0,a1)+F(0,a1,a2)+ F(a1,a2,a3)+...+F(ak-1,ak,0)+F(ak,0,0)- a1-...-ak] for all [a1....ak] k=1,.... z2(k)=min [-F(0,0,a1)-F(0,a1,a2)+ -F(a1,a2,a3)+...-F(ak-1,ak,0)+F(ak,0,0)+ a1-...+ak] if (z1<0)&&(z2<0) <> and so on. k from 1 to 10000 but functional depend only ak-1,ak and z1(k-2). History fogotten this is "fishka" in my prog Ac(1.3 cek) Ho make 0.015 don't now . diver[rus] Re: The solution is really easy, but it is not that easy to think it out (-) [4] // Задача 1381. Тараканы в здании 16 фев 2007 02:23 AC(0.109) using DP, but i was really surprised, when my program got AC EfremovAleksei Re: The solution is really easy, but it is not that easy to think it out (-) [3] // Задача 1381. Тараканы в здании 8 мар 2007 17:01 dp with bfs - i think it is very standart algo svr Re: The solution is really easy, but it is not that easy to think it out (-) [2] // Задача 1381. Тараканы в здании 8 мар 2007 17:24 My method also standart. It is Bellman-method for shortest path when functional of length rather specific but have main property of fogotten history [SPbSU ITMO] WiNGeR Re: The solution is really easy, but it is not that easy to think it out (-) [1] // Задача 1381. Тараканы в здании 9 мар 2007 00:22 I think, this method is DP Denis Koshman Re: The solution is really easy, but it is not that easy to think it out (-) // Задача 1381. Тараканы в здании 24 авг 2008 17:57 It's quite obvious DP. Search for positive/negative loop around (0,0) in graph with transfers (i,j) -> (j,k) Sandro Sample#2 // Задача 1381. Тараканы в здании 24 сен 2005 18:01 Be careful! Sample input and output #2 have changed. F(0,0,0)=0 in all tests in this problem.
|