10239 - The Book-shelver's Problem

[shahriar_manzoor]

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]

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]

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]

But how can I display the result without using float numbers ?

[toomyem]

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]

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]

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]

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]

Oh, my stupidity Of course, now I know! I have to be more careful when solving next problems.

thanx,
tomekM

[xenon]

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
read(books);
read(temp);
shelfwidth:=trunc(10000*(temp+0.00001));
if (books=0) then break;
for i:=1 to books do begin
read(temp);
height:=trunc(10000*(temp+0.00001));
read(temp);
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]

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.]

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]

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?
thanks in advance!

[Larry]

Try thinking of it as a graph problem.. =)

[WanBa]

how to contrive it as graph problem?
thanx in advance ?