10239  The Bookshelver's Problem
Moderator: Board moderators

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
10239  The Bookshelver'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 20020314 14:03 ]</font>
<font size=1>[ This Message was edited by: shahriar_manzoor on 20020314 14:03 ]</font>

 New poster
 Posts: 35
 Joined: Sat Jan 05, 2002 2:00 am
 Contact:

 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???
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???
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!
[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!

 New poster
 Posts: 35
 Joined: Sat Jan 05, 2002 2:00 am
 Contact:
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 liketoomyem 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]
[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.

 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
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
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:=(books1) 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]
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:=(books1) 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]

 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
For details, please refer to http://acm.uva.es/problemset/pascal.html

 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 TimeLimit Exceeded.
What's the idea behind a O(n^2) solution or even a faster one?
thanks in advance!
I've implemented a O(n^3) solution, which obviously leads to a TimeLimit Exceeded.
What's the idea behind a O(n^2) solution or even a faster one?
thanks in advance!