Discussion @ 1663. The Hobbit or There and Back Again 2 @ Timus Online Judge

Ekvilon Basic test [5] // Problem 1663. The Hobbit or There and Back Again 2 20 Dec 2008 13:56

If Hobbit moves in order 1->4->2->3 (like in basic test answer), he will pay 2816. But if he moves in order 1->3->4->2, he will pay only 2050.
So why minimal price way is "1 4 2 3"?

Vahan Stepanyan (YSU) Re: Basic test [3] // Problem 1663. The Hobbit or There and Back Again 2 20 Dec 2008 14:55

1->4->2->3

10*1000/4 + 4*1000/3 + 3*1000/5 = 4433

1->3->4->2

10*1000/5 + 5*1000/4 + 4*1000/3 = 4583

So?

Kasparyanm Re: Basic test [2] // Problem 1663. The Hobbit or There and Back Again 2 20 Dec 2008 15:04

1->3->2->4
10*1000/5+5*1000/3+3*1000/4==4415

Edited by author 20.12.2008 15:07

Edited by author 20.12.2008 15:07

svr Re: Basic test [1] // Problem 1663. The Hobbit or There and Back Again 2 21 Dec 2008 20:20

Why not so!
1-4-3-2
4*[1000/10]+5*[1000/4]+3*[1000/5]+10*[1000/3]=
4*100+5*250+3*200+10*333=400+1250+600+3330=5580
and
1-4-2-3
4*[1000/10]+3*[1000/4]+5*[1000/3]+10*[1000/5]=
400+750+5*333+10*200=1150+2000+1665=4815
and 1-4-3-2 is better!

Edited by author 10.01.2010 05:25

Edited by author 10.01.2010 05:28

Skyter Re: Basic test // Problem 1663. The Hobbit or There and Back Again 2 2 Jan 2009 16:06

Read the task carefuly! "Remember that Bilbo starts his travel from the city with number 1, visits each city exactly once and returns to the city with number 1 only in the end."

Al.Cash Re: Basic test // Problem 1663. The Hobbit or There and Back Again 2 18 Jan 2009 16:38

Bilbo will return to city 1 in the end, so we must calculate the cost of 1->4->2->3->1 and it is equal to:

4*[1000/10] + 3*[1000/4] + 5*[1000/3] + 10*[1000/5] =
= 4*100 + 3*250 + 5*333 + 10*200 = 4815.

Discussion of Problem 1663. The Hobbit or There and Back Again 2