11284 - Shopping Trip

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

Moderator: Board moderators

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

11284 - Shopping Trip

Post by ziliang » Sun Sep 16, 2007 5:45 am

i use floyd to calculate distance between each store
and build a new graph that contains only store node and home node
then I use a bit DP to find the max profit

is this algorithm wrong?

can someone give me some test data ?

btw, what is the range of the cost of road and money saved in stoer? could it be very large?
不鸣则已,一鸣惊人.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Sep 16, 2007 6:30 am

That's what I did. But I got WA for using doubles, and got AC by just modifying my code to work only with integers.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Sep 16, 2007 8:44 pm

I am getting WA. My idea is almost similar and I am using only integers. Here are some cases..

Input:

Code: Select all

3

4 5
0 1 1
1 2 3.00
0 3 1.00
3 2 1.50
3 4 3.25
3
1 1.50
1 7.00
2 9.00

4 5
0 1 1
1 2 3.00
0 3 1.00
3 2 1.50
3 4 3.25
4
1 1.50
2 7.00
3 9.00
4 11.00

5 6
0 1 1
1 2 3.00
0 3 1.00
3 2 11.50
3 4 3.25
4 5 8
4
3 1.50
3 7.00
4 1.00
5 20
Output:

Code: Select all

Daniel can save $11.00
Daniel can save $15.50
Daniel can save $6.50
Are these correct? Can anyone post some more cases? Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Sun Sep 16, 2007 10:17 pm

Your output is right. Note that the input is not valid, values are guaranteed to have two digits after the decimal point.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

more datasets ....

Post by baodog » Sun Sep 16, 2007 11:53 pm

More datasets is really appreciated.
Does the (sum of prices)*100 fit inside
a 32 bit integer? Are all prices positive?
Thanks.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Sep 17, 2007 12:21 am

The prices are positive, and everything fits in 32bit signed integer.
Remember to output don't leave the house if the lowest cost is 0.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Sep 17, 2007 12:34 am

100*(sum) more than comfortably fits into 32-bit integer.
Costs are non-negative.

There is one more thing that might cause WA, it is a small implementation detail, read the problem statement carefully.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Mon Sep 17, 2007 1:05 am

Darko wrote: There is one more thing that might cause WA, it is a small implementation detail, read the problem statement carefully.
thanks for the hint , after getting too many wa in contest and online-judge, while reading the description again, i thought about multiple edges between two nodes. after checking that it got accepted. unfortuantely i assumed that there will be no multiple edges :(
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 17, 2007 2:44 am

Well, my code handles duplicate edges. And I have tried many cases, but couldnt find the error. So, I am posting my code.

Code: Select all

code removed by Darko
Can anyone show where it fails? Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Sep 17, 2007 4:47 am

You forgot to comment out the freopen line.

Jan, sorry, I removed your otherwise AC code.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 17, 2007 6:27 am

No no, I removed the freopen before submitting. But got WA. I submitted it and got WA again. Would you please submit it? Thanks. [If you dont have the code I will PM it, just inform me]
Ami ekhono shopno dekhi...
HomePage

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Sep 17, 2007 7:04 am

Very interesting - I checked it against the judge's input and it produces correct answer. But it gets WA on OJ. My compiler is 3.4.6, I am not sure why it would matter.

Maybe it's some C++ thing, maybe you want to repost your code, sorry again for removing it.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Sep 17, 2007 8:27 am

What to do now? Should I report it in Bugs and suggestions?
Ami ekhono shopno dekhi...
HomePage

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sun Sep 23, 2007 4:54 am

Jan wrote:What to do now? Should I report it in Bugs and suggestions?
I get WA all the tiime.
And I passed the input/output above.
Could someone give more tricky input/output?
Thanks in advance

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Mon Sep 24, 2007 6:59 pm

windows2k wrote:
Jan wrote:What to do now? Should I report it in Bugs and suggestions?
I get WA all the tiime.
And I passed the input/output above.
Could someone give more tricky input/output?
Thanks in advance
Edited.

I found my error :
I forgot to add eps when I change all double to int. (*100)
studying @ ntu csie

Post Reply

Return to “Volume 112 (11200-11299)”