ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

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

Basic test
Posted by Ekvilon 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"?
Re: Basic test
Posted by Vahan Stepanyan (YSU) 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?
Re: Basic test
Posted by Kasparyanm 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
Re: Basic test
Posted by svr 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
Re: Basic test
Posted by Skyter 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."
Re: Basic test
Posted by Al.Cash 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.