Show all threads Hide all threads Show all messages Hide all messages |
To admins: problem task in Russian and in English | Smilodon_am | 1368. Goat in the Garden 3 | 3 Oct 2009 17:21 | 2 |
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?!! "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 |
What's the answer for k=1000000 | yuyan | 1368. Goat in the Garden 3 | 22 May 2009 18:06 | 3 |
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! |
Very nice problem [-] | Chmel_Tolstiy | 1368. Goat in the Garden 3 | 6 Jul 2008 02:22 | 1 |
|
no subject | IGOR_Lviv NU | 1368. Goat in the Garden 3 | 2 Mar 2008 19:28 | 1 |
Edited by author 02.03.2008 19:53 |
Can someone check my answer? thanks | semiconductor | 1368. Goat in the Garden 3 | 24 Dec 2007 15:07 | 6 |
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 No. For example: 10 11 13 12. Good luck! Can u tell me how to put the fence? when k=10,the answer=11. 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 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 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]); } } } |
What a strange problem! Give me some hint ,thanks! | semiconductor | 1368. Goat in the Garden 3 | 21 Dec 2007 11:36 | 3 |
If I suggest, you don't get a pleasure:) 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 |
How can you solve k=12 with less than 12 fences?? | Hamed Ahmadi Nejad | 1368. Goat in the Garden 3 | 25 Sep 2005 20:09 | 3 |
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? No, for k == 12 U require exactly 12 fences. My AC program gets output very similar to yours. Perhaps, WA is at another test. 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! |
Why do I get Fail (Validator)? | Furtuna Dan Emanuel | 1368. Goat in the Garden 3 | 28 Apr 2005 17:19 | 3 |
What does this mean? Can you tell me? Found out: It's a bug that when you don't output then entire sequence of squares, you don't get WA, but this. |
No subject | semiconductor | 1368. Goat in the Garden 3 | 23 Apr 2005 20:33 | 1 |
|