10239 - The Book-shelver's Problem

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

Moderator: Board moderators

Post Reply
shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

10239 - The Book-shelver's Problem

Post by shahriar_manzoor » Thu Mar 14, 2002 4:24 am

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 :smile: but may be not :sad: . 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:

Post by Alexander Denisjuk » Thu May 23, 2002 11:20 am

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

Shih-Chia Cheng
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:

Post by Shih-Chia Cheng » Fri May 24, 2002 4:35 am

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

Post by toomyem » Thu Jun 06, 2002 1:23 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

Post by toomyem » Thu Jun 06, 2002 1:36 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:

Post by Alexander Denisjuk » Tue Jun 11, 2002 11:00 am

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

Post by toomyem » Tue Jun 11, 2002 11:32 am

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:

Post by Alexander Denisjuk » Tue Jun 11, 2002 12:28 pm

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

Post by toomyem » Tue Jun 11, 2002 12:49 pm

Oh, my stupidity :o 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

Post by xenon » Sat Aug 10, 2002 2:23 pm

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

Post by Alexander Denisjuk » Mon Sep 02, 2002 2:57 pm

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?

Post by Whinii F. » Wed Sep 25, 2002 5:48 am

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.

:D

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

Efficient Implementation

Post by uzioriluzan » Tue Oct 15, 2002 3:28 am

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Nov 18, 2002 2:20 am

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

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

graph?

Post by WanBa » Fri May 23, 2003 3:03 pm

how to contrive it as graph problem?
thanx in advance ?
destiny conditioned by past

Post Reply

Return to “Volume 102 (10200-10299)”