Discussion @ 1368. Goat in the Garden 3 @ Timus Online Judge

Smilodon_am To admins: problem task in Russian and in English [1] // Problem 1368. Goat in the Garden 3 3 Oct 2009 15:16

yuyan What's the answer for k=1000000 [2] // Problem 1368. Goat in the Garden 3 22 May 2009 15:23

Chmel_Tolstiy Very nice problem [-] // Problem 1368. Goat in the Garden 3 6 Jul 2008 02:22

IGOR_Lviv NU no subject // Problem 1368. Goat in the Garden 3 2 Mar 2008 19:28

semiconductor Can someone check my answer? thanks [5] // Problem 1368. Goat in the Garden 3 25 Apr 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] // Problem 1368. Goat in the Garden 3 25 Apr 2005 21:55

No. For example:
10 11
13 12.
Good luck!

zizou Re: Can someone check my answer? thanks [3] // Problem 1368. Goat in the Garden 3 2 May 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] // Problem 1368. Goat in the Garden 3 3 May 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] // Problem 1368. Goat in the Garden 3 24 Dec 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 // Problem 1368. Goat in the Garden 3 24 Dec 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] // Problem 1368. Goat in the Garden 3 23 Apr 2005 20:35

Hamed Ahmadi Nejad How can you solve k=12 with less than 12 fences?? [2] // Problem 1368. Goat in the Garden 3 7 Sep 2005 17:12

Furtuna Dan Emanuel Why do I get Fail (Validator)? [2] // Problem 1368. Goat in the Garden 3 23 Apr 2005 20:57

semiconductor No subject // Problem 1368. Goat in the Garden 3 23 Apr 2005 20:33

Discussion of Problem 1368. Goat in the Garden 3