ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1368. Goat in the Garden 3

Can someone check my answer? thanks
Posted by semiconductor 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

Re: Can someone check my answer? thanks
Posted by Kit 25 Apr 2005 21:55
No. For example:
10 11
13 12.
Good luck!
Re: Can someone check my answer? thanks
Posted by zizou 2 May 2005 16:44
Can u tell me how to put the fence?
Re: Can someone check my answer? thanks
Posted by Cybernetics Team 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
Re: Can someone check my answer? thanks
Posted by svr 24 Dec 2007 14:28

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
Re: Can someone check my answer? thanks
Posted by svr 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]);
}

}
}