10012 - How Big Is It?

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10012 - How Big Is It?

Post by Adrian Kuegel » Fri Jan 18, 2002 4:54 pm

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?

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

Post by Adrian Kuegel » Sun Jan 20, 2002 10:17 pm

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

Post by Revenger » Thu Jun 20, 2002 11:12 pm

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

Please, help me !

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

Post by Revenger » Thu Jun 20, 2002 11:17 pm

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 :wink:

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

10012 wa

Post by Trickster » Mon Nov 24, 2003 1:41 am

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

Post by david » Tue Apr 06, 2004 6:31 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

Post by ditrix » Tue Oct 19, 2004 2:44 pm

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

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

Post by little joey » Tue Oct 19, 2004 7:05 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

Post by ditrix » Wed Oct 20, 2004 9:08 pm

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

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

10012. Is there any non-exhaustive algorithm?

Post by ImLazy » Sun Jun 26, 2005 4:01 pm

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.

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

Post by ImLazy » Tue Jun 28, 2005 10:32 am

What about your algorithms? Do you use exhaustive search?
I stay home. Don't call me out.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Fri Jul 01, 2005 5:08 am

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

Post by chunyi81 » Sat Jul 02, 2005 2:52 pm

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

Post by chunyi81 » Sun Jul 03, 2005 8:14 am

Finally found the problem. The input data is indeed the radii of the circles. :oops:

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.

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

Post by ImLazy » Mon Jul 04, 2005 6:27 pm

Thank you, chunyi81. You have helped me many times.
I will try exhaustive search.
I stay home. Don't call me out.

Post Reply

Return to “Volume 100 (10000-10099)”