## 10239 - The Book-shelver's Problem

Moderator: Board moderators

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### 10239 - The Book-shelver's Problem

The Book Shelver's Problem has been fixed. Now you can submit it. The reason for its not being accepted was floating point precision error. So when you write a solution try to avoid use of floats and doubles. May be you will get lucky and get accepted but may be not . If you are intelligent enough you will surely find a way to do the calculations only using long int.

<font size=-1>[ This Message was edited by: shahriar_manzoor on 2002-03-14 14:03 ]</font>

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
shahriar_manzoor wrote:If you are intelligent enough you will surely find a way to do the calculations only using long int.
I believe, every TeXnician should know

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
Well, though I used long int and got an AC for this problem,
I still don't know what the trick is about using long int.
I also found that I got many wrong answers for some problems due to precision error like problem 10236(The Fibonacci Primes).
Can someone explain how to avoid floating point precision error for
this kind of problem???

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm
But how can I display the result without using float numbers ?

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm
What is wrong with this solution? I have no idea :-(

[c]
#include <stdio.h>

int main()
{
double _sw, _w, _h;
long int sw, w, h;
int n, i;
long int cw, mh, sh;

while( scanf( "%d %lf", &n, &_sw ) && n > 0 )
{
sw = _sw * 10000;
cw = 0; mh = 0; sh = 0;
for( i = 0; i < n; ++i )
{
scanf( "%lf %lf", &_h, &_w );
h = _h * 10000; w = _w * 10000;
if( cw + w <= sw )
{
cw += w;
if( h > mh ) mh = h;
}
else
{
sh += mh;
mh = h;
cw = w;
}
}
sh += mh;
printf( "%0.4lf\n", (double)(sh / 10000.0) );
}

return 0;
}
[/c]

Thanx!

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
toomyem wrote:What is wrong with this solution? I have no idea

[c]
...
double _sw, _w, _h;
long int sw, w, h;
...
scanf( "%lf %lf", &_h, &_w );
h = _h * 10000; w = _w * 10000;
...

[/c]
The bold line is incorrect. I had the same error, so I can share my experience. The typecasting double->long int is NOT rounding, but only truncating. That is why you can obtain an equality like
[c] (long int) (0.1871*10000) ==1870 [/c] as I obtained.

I fixed it by rewriting my program in Pascal, using
[pascal] h=round(_h*10000)[/pascal] But you, of course, can try [c] h=(long int) (_h*10000+0.5)[/c] which is the same.

Thanks to Shahriar Manzoor for his help.

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm
Unfortunately your proposal didn't help. Still got WA. I have no idea, what to do about this. Mayby someone can send me some tricky input data which is sensitive for rounding problem. It could help me to verify what's wrong.

regards,
tomekM

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
Well,
I am sure, you have no more problems with input. Try to check your algorithm. What will it output for the following data:
3 2.5000
10.0000 1.0000
20.0000 1.0000
20.0000 1.0000
?

The right answer is 30.000 as one can see: the first book on the first shelf, the others on the second. It seems to me, that your algorithm will output 40.0000

toomyem
New poster
Posts: 6
Joined: Tue Jun 04, 2002 5:48 pm
Oh, my stupidity Of course, now I know! I have to be more careful when solving next problems.

thanx,
tomekM

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
Well, I think it's a great problem, but I can't get past the WA stage.
I think I avoid the rounding problem sufficiently, so something else must be wrong. Can you help me?
[pascal]var
books:integer;
width,height,best:array[1..1001] of longint;
shelfwidth:longint;
temp:double;
i,j,k,l:integer;
w,h:longint;
begin
repeat
shelfwidth:=trunc(10000*(temp+0.00001));
if (books=0) then break;
for i:=1 to books do begin
height:=trunc(10000*(temp+0.00001));
width:=trunc(10000*(temp+0.00001));
end;
best[books+1]:=0;
best[books]:=height[books];
for i:=(books-1) downto 1 do begin
best:=1000000000000;
w:=width;
j:=i+1;
while ((j<=books) and (w<=shelfwidth)) do begin
w:=w+width[j];
inc(j);
end;
dec(j);
if (w>shelfwidth) then dec(j);
for k:=i to j do begin
h:=0;
for l:=i to k do if (height[l]>h) then h:=height[l];
if (best>(h+best[k+1])) then best:=h+best[k+1];
end;
end;
write(best[1] div 10000,'.');
write((best[1] mod 10000) div 1000,(best[1] mod 1000) div 100,(best[1] div 100) mod 10);
writeln(best[1] mod 10);
until false;
end.[/pascal]

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:
Well, first of all try to replace all your [pascal] write(Integer); writeln(Integer) [/pascal] with [pascal] write(Integer:1); writeln(Integer:1) [/pascal] since the first variant may cause additional spaces after the decimal point, before the decimals.

For details, please refer to http://acm.uva.es/problemset/pascal.html

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

### eh?

I got an AC for this problem, yesterday, using doubles!

when I was using floats it gave me WAs.. but replacement to doubles earned an AC.

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

### Efficient Implementation

Hi all!
I've implemented a O(n^3) solution, which obviously leads to a Time-Limit Exceeded.
What's the idea behind a O(n^2) solution or even a faster one?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Try thinking of it as a graph problem.. =)

WanBa
New poster
Posts: 14
Joined: Mon Apr 28, 2003 11:21 am

### graph?

how to contrive it as graph problem?