## 10012 - How Big Is It?

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 10012 - How Big Is It?

I think my solution for this problem is correct; I calculate the distance between two circles with pythagoras and check all permutions of the circles. My program gives the right answer for the sample input. Can someone please give me a difficult input line?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I found my problem. Consider this input line:
3 2.0 0.4 2.0
The correct output is 8.000, not 7.578

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### 10012 WA

Why I get WA?

[pascal]Program p10012;

Const MaxM = 7;

Var N,M,i,j : Integer;
R : Array[1..MaxM]of Extended;

Procedure Solve;
Var Ans : Extended;
O,U : Array[1..MaxM]of Byte;
Procedure GetSize;
Var i,j,k : Integer;
a,b : Extended;
d : array[0..MaxM,0..MaxM]of Extended;
begin
for i:=0 to MaxM do
for j:=0 to MaxM do
d[i,j]:=-10;
for j:=1 to M+1 do
for i:=0 to M-j+1 do begin
if (i=0)and(j<=M) then d[0,j]:=R[O[j]] else
if (i+j=M+1)and(i>0) then d[i,M+1]:=R[O] else
if (i>0)and(i+j<=M) then begin
a:=Abs(R[O]-R[O[i+j]]);
b:=R[O]+R[O[i+j]];
d[i,i+j]:=sqrt(b*b-a*a);
end;
for k:=i+1 to i+j-1 do
if d[i,i+j]<d[i,k]+d[k,i+j] then
d[i,i+j]:=d[i,k]+d[k,i+j];
end;
if d[0,M+1]<Ans then Ans:=d[0,M+1];
end;
Procedure Rec(Step : Integer);
Var i : Integer;
begin
if Step=M+1 then begin
GetSize;
Exit;
end;
for i:=1 to M do
if U=0 then begin
U:=1;
O[Step]:=i;
Rec(Step+1);
U:=0;
end;
end;
begin
Ans:=10E10;
FillChar(U,SizeOf(U),0);
Rec(1);
Writeln(Ans:0:3);
end;

begin
for i:=1 to N do begin
for j:=1 to M do Read(R[j]);
if M>0 then Solve else Writeln('0.000');
end;
end.[/pascal]

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia
It is very strange. Then I wrote

Code: Select all

``MaxM = 7``
or

Code: Select all

``MaxM = 8``
my program gets WA. But then I wrote

Code: Select all

``MaxM = 10``
it get Accepted!

Very Strange

Trickster
New poster
Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

### 10012 wa

Hi everyone,

i
"There's a difference between knowing the path, and walking the path."

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm
Your solution, 7.58, is based on putting the big 2.0 circle, then the small one and then the big one again. The problem is that the two big circles overlap in such a layout.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
Can anybody check these input/output. please?

Input:

Code: Select all

``````100
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
3 0.196 0.009 0.735
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
3 0.467 0.889 0.461
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
6 1.419 5.220 1.208 0.714 1.741 8.151
7 0.453 2.879 1.834 3.639 1.361 0.558 1.280
8 10.519 0.553 4.513 0.911 1.170 0.293 0.678 1.463
2 1.069 0.616
5 1.780 3.458 2.220 0.659 0.750
8 0.146 1.085 7.379 0.992 4.334 3.427 0.608 2.375
1 0.155
5 0.119 2.052 0.379 2.150 0.693
4 63.499 0.249 3.666 0.322
5 1.890 4.796 0.583 0.187 0.347
1 1.079
4 0.209 1.862 1.430 5.867
8 3.265 0.590 0.054 1.583 0.074 1.585 0.525 0.989
4 2.232 7.205 150.375 1.467
1 11.740
6 10.779 3.807 1.716 0.428 0.536 1.224
4 1.071 2.685 0.794 0.117
4 0.608 0.486 0.135 4.533
1 0.469
8 2.294 0.756 10.556 3.538 2.250 0.383 0.858 1.160
3 2.463 1.446 1.809
5 2.174 0.154 0.322 0.539 0.847
7 0.429 1.694 2.170 0.214 0.369 0.275 8.182
5 2.159 0.739 1.132 0.733 0.328
3 7.906 3.212 1.724
1 3.759
4 2.750 1.045 1.434 19.391
2 0.241 12.710
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411
3 2.301 1.375 0.298
2 0.376 0.532
4 2.275 0.261 0.087 2.705
5 0.605 1.057 0.257 0.706 0.861
3 0.203 0.627 0.848
1 4.048
5 3.357 0.641 4.038 0.864 0.667
8 0.252 0.416 1.932 0.365 0.621 0.502 8.299 0.318
2 40.436 3.087
7 0.682 2.496 0.322 0.786 0.128 0.625 0.438
4 1.042 2.291 0.724 1.504
8 1.460 5.581 0.001 25.125 1.713 2.704 0.342 0.716
6 0.102 0.469 0.859 4.451 2.170 1.602
8 1.830 14.377 0.517 0.685 1.184 0.001 1.011 1.385
6 0.855 0.000 1.823 0.768 0.426 1.157
5 0.647 2.051 0.537 1.676 0.339
3 3.623 0.364 0.994
8 0.947 1.024 0.263 0.773 1.279 4.074 49.961 0.065
2 6.345 16.925
5 4.651 0.156 1.075 0.480 2.629
5 1.256 0.227 0.054 0.035 1.912
2 1.203 0.751
7 5.175 0.518 1.108 8.091 0.274 1.003 0.555
6 0.291 0.175 0.370 7.216 0.554 1.628
7 0.847 0.676 0.577 0.492 1.407 0.868 10.257
2 0.812 1.108
6 1.286 19.802 0.499 0.333 0.598 13.306
3 0.688 0.263 21.964
1 0.748
8 0.203 1.499 23.346 1.314 2.114 0.833 1.757 14.082
7 7.280 0.942 0.389 1.521 1.467 0.963 2.634
6 0.588 0.239 0.647 2.450 1.536 0.291
8 22.087 1.160 10.010 0.527 1.168 0.720 0.184 0.670
7 3.225 1.402 1.486 2.549 1.023 1.008 2.263
2 0.955 1.202
5 3.073 7.774 6.587 8.906 1.282
6 0.301 0.835 4.213 0.848 5.414 1.315
4 0.731 2.590 2.308 0.235
1 1.250
8 0.383 3.919 0.738 0.429 0.663 0.698 1.331 1.531
7 1.280 0.356 0.686 1.039 0.680 0.058 0.490
6 1.031 0.174 1.945 0.773 0.680 0.466
8 0.413 0.689 4.510 0.694 1.453 3.161 0.971 0.283
3 0.781 1.030 1.666
3 0.061 1.953 1.654
3 0.036 0.741 0.477
3 1.826 2.268 2.851
7 0.319 2.537 1.363 35.278 0.172 6.054 4.533
2 5.517 1.447
2 0.226 0.493
8 2.559 0.443 4.470 1.445 1.162 0.258 0.193 1.644
4 0.563 3.274 1.186 0.803
8 0.303 7.870 17.105 0.734 1.000 6.424 3.592 2.105
7 1.028 2.475 1.486 0.505 0.480 0.133 1.702
2 0.528 1.190
4 8.753 0.326 0.944 0.843
2 0.870 1.001
4 0.324 0.899 0.772 5.190
8 0.182 2.026 12.486 2.303 1.066 4.099 0.923 1.286
7 2.644 0.931 0.367 0.779 0.618 0.190 11.166
8 1.903 0.002 1.174 3.766 0.789 1.874 7.221 0.830
8 0.579 0.657 0.518 0.567 19.806 0.080 0.186 2.428
6 0.778 3.006 5.973 8.024 0.042 0.268
7 0.148 0.226 3.190 0.146 1.708 0.398 0.317
5 2.595 0.559 0.306 1.292 1.908
``````
My output:

Code: Select all

``````20.334
3.170
21.870
3.497
9.809
28.015
20.397
28.812
3.308
14.987
32.716
0.608
9.063
126.998
12.707
2.158
15.695
14.333
300.750
150.375
27.398
8.177
9.066
0.938
31.701
11.251
10.556
19.737
8.877
22.398
7.518
38.782
25.420
6.718
17.124
7.233
2.301
9.941
6.453
3.018
8.096
14.976
18.239
80.872
8.694
10.299
54.389
15.754
28.754
14.377
8.777
8.412
99.922
43.996
15.114
6.267
3.855
26.208
15.699
20.514
3.817
65.572
43.928
1.496
73.691
23.309
9.041
61.835
23.824
4.300
49.918
20.044
10.248
2.500
15.232
8.357
8.829
18.325
6.712
7.202
2.407
13.743
70.560
12.615
1.387
20.281
9.581
61.570
13.133
3.303
17.506
3.737
10.409
34.572
24.677
27.367
39.612
32.294
9.566
11.336
``````
@+!
DitriX

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Code: Select all

``````knoppix@ttyp0[p10012.cpl]\$ diff test2.joa test2.out
2c2
< 1.690
---
> 3.170
12c12
< 0.310
---
> 0.608
20c20
< 23.480
---
> 150.375
27c27
< 6.269
---
> 10.556
37c37
< 1.802
---
> 2.301
50c50
< 9.145
---
> 14.377
knoppix@ttyp0[p10012.cpl]\$``````

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris
Thank you! Your data was very helpfull, I found the bug and got accespted.
It was a some particular interference with previously calculated values...
@+!
DitriX

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### 10012. Is there any non-exhaustive algorithm?

This is my algorithm which gets WA:

Code: Select all

``````First, put the biggest circle in the box.
Then put the 2th biggest circle into the box, insert it at the place which makes the smallest width of the 2 circles.
Then put the 3rd biggest circle into the box, insert it at the place which makes the smallest width of the 3 circles.
Then...... Until All circles are in the box.``````
But I get WA.
This is my test IO. I think my output is wrong.
Input

Code: Select all

``````5
8 1.344 0.852 0.269 1.472 3.170 1.329 0.579 2.847
7 0.030 3.821 1.368 1.545 5.434 0.934 0.105
7 0.744 1.173 1.035 0.354 0.300 1.102 0.708
4 0.900 0.978 0.568 0.968
7 1.056 0.084 1.089 3.910 0.114 1.221 2.411``````
Output

Code: Select all

``````20.632 (the sequence of circles: 6 8 7 4 3 2 5 1)
22.188 (7 1 6 2 4 5 3)
10.082 (6 5 1 4 2 7 3)
6.733 (4 1 3 2)
17.265 (5 2 1 7 6 4 3)``````
Must I use exhaustive search? Is there any non-exhaustive algorithm?
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
I stay home. Don't call me out.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Hi, you will have to use exhaustive search. notice that since all circles have to touch the bottom of the box, and there are a maximum of 8 circles, for 8 circles the number of permutations is at most 8! = 40320. you can prune this by half due to symmetry, or ceil(0.5 * number of permutations of the circles). Note the ceil, because, suppose there are 3 circles with diameters 1.0, 1.0, 2.0, then number of permutations = 3! / 2! = 3, or the orders 1.0, 1.0, 2.0 and 1.0, 2.0, 1.0 and 2.0, 1.0, 1.0. Considering 1.0, 1.0, 2.0 and 2.0, 1.0, 1.0 is the same, we are left with 2 orders to consider or ceil(3/2) = 2.

Example input:

3 1.0 2.0 3.0

Considering the order 1.0 2.0 3.0 is the same as considering the order 3.0 2.0 1.0.

Hope this helps. Do look for test cases to this problem using the search option. There is one particular tricky one.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Ok. Now I am really stuck. In the given sample IO:

Sample input:

3
3 2.0 1.0 2.0
4 2.0 2.0 2.0 2.0
3 2.0 1.0 4.0

Sample output:
9.657
16.000
12.657

I can understand why outputs for the first two cases are 9.657 and 16.000.

But after reading the problem description many times, I couldn't understand why output for the third case is 12.657.

Because the total area of the three circles in the third case is: pi*2/2*2/2 + pi*1/2*1/2 + pi*4/2*4/2 = 5.25*pi where pi = 3.14159... and 5.25*pi > 12.657. But the size of the rectangular box required should be greater than the total area of the circles right? Then how come the output for the third case is 12.657? Could anyone explain please? Thanks for any help.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Finally found the problem. The input data is indeed the radii of the circles.

From the output description:

For each data line of input, excluding the first line of input containing n, your program must output the size of the smallest rectangle which can pack the circles. Each case should be output on a separate line by itself, with three places after the decimal point. Do not output leading zeroes unless the number is less than 1, e.g. 0.543.

The keyword is size, which I interpreted as the area of the rectangular box required, but the output given is the length of the box required. The output description is confusing and wrong and should be corrected.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Thank you, chunyi81. You have helped me many times.
I will try exhaustive search.
I stay home. Don't call me out.