| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| To admins: problem task in Russian and in English | Smilodon_am | 1368. Пусти козла в огород 3 | 3 окт 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. Пусти козла в огород 3 | 22 май 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. Пусти козла в огород 3 | 6 июл 2008 02:22 | 1 |
|
| no subject | IGOR_Lviv NU | 1368. Пусти козла в огород 3 | 2 мар 2008 19:28 | 1 |
Edited by author 02.03.2008 19:53 |
| Can someone check my answer? thanks | semiconductor | 1368. Пусти козла в огород 3 | 24 дек 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. Пусти козла в огород 3 | 21 дек 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. Пусти козла в огород 3 | 25 сен 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. Пусти козла в огород 3 | 28 апр 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. Пусти козла в огород 3 | 23 апр 2005 20:33 | 1 |
|
