10269 - Adventure of Super Mario

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
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

10269

Post by Observer »

This question looks quite interesting to me.

However, I don't have the slightest idea of how to solve this qq...... :p


Do I have to consider ALL paths before arriving at the answer?
Or are there any better ways to do this qq?

Thx!


_________________________
Beginner............

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

10269 - Adventure of Super Mario

Post by Jan »

Can anyone verify the i/o set?

Input:

Code: Select all

8

1 4 4 61 1
1 2 20
2 3 1
3 4 40
5 4 51

4 1 4 61 1
1 2 20
2 3 1
3 4 40
5 4 51

1 1 1 20 1
1 2 20

6 1 6 100 1
7 6 1
6 5 20
5 4 20
4 3 20
3 2 20
2 1 20

5 2 6 100 1
7 5 1
5 4 20
4 3 20
3 6 20
6 2 20
2 1 20

3 3 5 100 1
6 5 10
6 4 20
5 4 3
4 2 1
2 1 100

4 2 6 5 1
4 6 1
5 6 10
4 5 5
3 5 4
2 3 4
1 2 3

4 2 6 9 1
4 6 1
5 6 10
4 5 5
3 5 4
2 3 4
1 2 3
Output:

Code: Select all

61
51
0
1
40
14
12
9
Is there any tricky case?

Thanks in advance.
Ami ekhono shopno dekhi...
HomePage

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Re: 10269 - Adventure of Super Mario

Post by greve »

My solution returns the same output (you can test other sets for the problem on http://www.uvatoolkit.com).
For help with problems, visit http://www.uvatoolkit.com/

warenix
New poster
Posts: 5
Joined: Sun Aug 12, 2007 1:17 pm

Re: 10269 - Adventure of Super Mario

Post by warenix »

Can anyone explain why uva toolkit gives the following output?

intput

Code: Select all

2

2 1 2 10 1
1 2 8
2 3 10

1 2 2 10 1
1 2 8
2 3 10
output

Code: Select all

8
8
my program gives:

Code: Select all

8
10
From my understanding, Mario won't wear boot when the next node is a castle. I wonder why uva toolkit gives 10 for both cases.

greve
New poster
Posts: 27
Joined: Tue May 29, 2007 8:52 pm
Contact:

Re: 10269 - Adventure of Super Mario

Post by greve »

I thought about the case for some time, and initially thought that there was a bug in my solution, but now I believe that my solution (i.e. the one on uvatoolkit) is correct. The explanation for the second case is as follows. First we go from village 1 to castle 2 for at cost of 8 and then we use the boot from castle 2 to castle 3 for a cost of 0. This gives the total cost of 8. After having reread the problem statement a couple of times I believe that it is allowed to use the boot from a castle to another castle as long as we do not go through an intermediate castle on the way.
For help with problems, visit http://www.uvatoolkit.com/

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10269 - Adventure of Super Mario

Post by Shafaet_du »

try this case,you may find your bug

Code: Select all

2

1 2 2 10 2
1 2 9
2 3 10

2 1 2 10 2
1 2 10
2 3 9
output:

Code: Select all

0
0
You can start or stop running at any node,but you cant run THROUGH a castle.

Post Reply

Return to “Volume 102 (10200-10299)”