| ENG RUS | Timus Online Judge |
Обсуждение задачи 1368. Пусти козла в огород 3Smilodon_am To admins: problem task in Russian and in English [1] // Задача 1368. Пусти козла в огород 3 3 окт 2009 15:16 The problem task in Russian isn't equal to the problem task in English. The English text have following sentence: "You have to put the fence in the minimum number of squares so that the goat will be able to visit exactly K squares." It means that our region built could contain only K squares and something else, for example halves squares (as in example). But in the problem task in Russian this sentence is as follows: "Требуется, поставив минимальное число секций, предоставить козлу участок ровно из K квадратов." It means that the region contains only K squares and nothing else. I think that this sentence should be rewritten as follows: "Требуется, поставив минимальное число секций, предоставить козлу возможность посетить ровно K квадратов." And something else. English sentence contains phrase: "to put the fence in the minimum number of squares". But how should we count number of squares if the fence is put on the bound of two squares?!! Sandro (USU) Re: To admins: problem task in Russian and in English // Задача 1368. Пусти козла в огород 3 3 окт 2009 17:21 "You can build a fence in some of the garden's elementary squares." (English version) "Хозяева козла умеют ставить секции забора в отдельных элементарных квадратах на поле." (Russian version) So the fence consists of the unit squares, not of line segments. Sample test can be written as follows: ..X. .X.X X..X .XX. Edited by author 03.10.2009 17:22 yuyan What's the answer for k=1000000 [2] // Задача 1368. Пусти козла в огород 3 22 май 2009 15:23 Is it 2831? yuyan Re: What's the answer for k=1000000 [1] // Задача 1368. Пусти козла в огород 3 22 май 2009 18:05 Yes,you are right! yuyan Re: What's the answer for k=1000000 // Задача 1368. Пусти козла в огород 3 22 май 2009 18:06 Oh!Thank you very much.I got AC now! By the way,if someone have WA on TEST#14 Please try K=14 , the answer is 13! Chmel_Tolstiy Very nice problem [-] // Задача 1368. Пусти козла в огород 3 6 июл 2008 02:22 IGOR_Lviv NU no subject // Задача 1368. Пусти козла в огород 3 2 мар 2008 19:28 Edited by author 02.03.2008 19:53 semiconductor Can someone check my answer? thanks [5] // Задача 1368. Пусти козла в огород 3 25 апр 2005 21:17 Is it right? K minimum fence 10 13 11 13 12 14 13 15 14 15 15 15 16 16 17 17 18 17 19 17 20 18 21 19 22 19 23 19 24 19 25 20 26 21 27 21 28 21 29 21 30 22 31 23 32 23 33 23 34 23 35 23 36 24 37 25 38 25 39 25 40 25 41 25 42 26 43 27 44 27 45 27 46 27 47 27 48 27 49 28 50 29 Kit Re: Can someone check my answer? thanks [4] // Задача 1368. Пусти козла в огород 3 25 апр 2005 21:55 No. For example: 10 11 13 12. Good luck! zizou Re: Can someone check my answer? thanks [3] // Задача 1368. Пусти козла в огород 3 2 май 2005 16:44 Can u tell me how to put the fence? when k=10,the answer=11. Cybernetics Team Re: Can someone check my answer? thanks [2] // Задача 1368. Пусти козла в огород 3 3 май 2005 21:33 N = 10 -> 11 fences (_ space, * fence, 0 goat square) ___*__ __*0*_ _*000* *0000* _*00*_ __**__ Edited by author 04.05.2005 19:59 Edited by author 04.05.2005 20:00 svr Re: Can someone check my answer? thanks [1] // Задача 1368. Пусти козла в огород 3 24 дек 2007 14:28 Make someone verification,please, for: 1 4 2 6 3 7 4 8 5 8 6 9 7 10 8 10 9 11 10 11 11 12 12 12 13 12 14 13 15 13 16 14 17 14 18 14 19 15 20 15 21 15 22 16 23 16 24 16 25 16 26 17 27 17 28 17 29 18 30 18 31 18 32 18 33 19 34 19 35 19 36 19 37 20 38 20 39 20 40 20 41 20 42 21 43 21 44 21 45 21 46 22 47 22 48 22 49 22 50 22 51 23 52 23 53 23 54 23 55 23 56 24 57 24 58 24 59 24 60 24 61 24 62 25 63 25 64 25 65 25 66 25 67 26 68 26 69 26 70 26 71 26 72 26 73 27 74 27 75 27 76 27 77 27 78 27 79 28 80 28 81 28 82 28 83 28 84 28 85 28 86 29 87 29 88 29 89 29 90 29 91 29 92 30 93 30 94 30 95 30 96 30 97 30 98 30 99 31 100 31 Edited by author 24.12.2007 14:30 svr Re: Can someone check my answer? thanks // Задача 1368. Пусти козла в огород 3 24 дек 2007 15:07 Here my testing program which makes full search for K<=100 and use DP. z[i][j]- minimal value when i=K and 1<=j<=i-size of last row; z[i]=min(z[i][j]),j=1,...,i I have WA8 for which K<=100 with my real quick prog but in range [1,100] results are coinsise. int zz[100][100],z[100]; void help() { int i,k,j,h; zz[0][0]=0; for (i=1;i<=100;i++) { z[i-1]=10000; for (j=1;j<=i;j++) { if (j==i) zz[i-1][j-1]=2*j+2; else { zz[i-1][j-1]=10000; for (k=1;k<=i-j;k++) { h=zz[i-j-1][k-1]; if (j<=k-2) zz[i-1][j-1]=min(zz[i-1][j-1],h); else if (j<=k-1) zz[i-1][j-1]=min(zz[i-1][j-1],h+1); else if (j==k)zz[i-1][j-1]=min(zz[i-1][j-1],h+2); else if (j==k+1)zz[i-1][j-1]=min(zz[i-1][j-1],h+3); else zz[i-1][j-1]=min(zz[i-1][j-1],h-k+j+2+j-k-2); } } z[i-1]=min(z[i-1],zz[i-1][j-1]); } } } semiconductor What a strange problem! Give me some hint ,thanks! [2] // Задача 1368. Пусти козла в огород 3 23 апр 2005 20:35 Kit Re: What a strange problem! Give me some hint ,thanks! [1] // Задача 1368. Пусти козла в огород 3 23 апр 2005 22:18 If I suggest, you don't get a pleasure:) svr Re: What a strange problem! Give me some hint ,thanks! // Задача 1368. Пусти козла в огород 3 21 дек 2007 11:36 I think that displeasure to be confused stronger and that prediscussion is helphull. It is variational Didona problem and it's solution sircle in continious case.Circle is solution of necessary condition in form of differential eqution. In discrete case must be something similar. I think differential eqution cooresponds difference eqution and Dp-method. AC! Optimal form is'n sircle but square: 1 1 1 1 1 1 1 1 1 1 1 1 1 For it and for middle row 1 1 1 1 1 it is necessary the same number 12 of blocs. Value K=1000000 make impossible DP and recursion. We must accept some hypothesis about structure of optimal solution. On this way we can go to 0.001c. Edited by author 24.12.2007 16:23 Hamed Ahmadi Nejad How can you solve k=12 with less than 12 fences?? [2] // Задача 1368. Пусти козла в огород 3 7 сен 2005 17:12 Hello, This is my output for k=12: 12 0 2 1 2 2 1 3 0 2 -1 1 -2 0 -3 -1 -2 -2 -1 -3 0 -2 1 -1 2 But I don't understand why I get "Wrong Answer" for the k=12 test. Is it really possible to solve 12 with less than 12 fences? GaLL Re: How can you solve k=12 with less than 12 fences?? [1] // Задача 1368. Пусти козла в огород 3 11 сен 2005 11:20 No, for k == 12 U require exactly 12 fences. My AC program gets output very similar to yours. Perhaps, WA is at another test. Hamed Re: How can you solve k=12 with less than 12 fences?? // Задача 1368. Пусти козла в огород 3 25 сен 2005 20:09 Yes, I submitted the same program again today and I got accepted! Maybe they took out one of the tests? Or perhaps I had been submitting to the wrong problem! Furtuna Dan Emanuel Why do I get Fail (Validator)? [2] // Задача 1368. Пусти козла в огород 3 23 апр 2005 20:57 What does this mean? Can you tell me? Furtuna Dan Emanuel Re: Why do I get Fail (Validator)? // Задача 1368. Пусти козла в огород 3 23 апр 2005 21:05 Found out: It's a bug that when you don't output then entire sequence of squares, you don't get WA, but this. Vladimir Yakovlev (USU) The problem is fixed now // Задача 1368. Пусти козла в огород 3 28 апр 2005 17:19 semiconductor No subject // Задача 1368. Пусти козла в огород 3 23 апр 2005 20:33
|