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

Any clue for this problem?
Posted by Vedernikoff Sergey (HSE: АОП) 5 May 2009 04:30
How to solve it? Any hints? Thanks in advance.
Re: Any clue for this problem?
Posted by Al.Cash 5 May 2009 14:10
We must minimize the value of [1000/P1]*Pi1 + [1000/P2]*Pi2 + ... + [1000/Pn]*Pin, where (i1, i2, ... in) - some permutation of (1, 2, ... n), which defines the cycle.
If we forget about the cycle, the minimum value will be reached when i1=1, i2=2, ... in=n (think why).
I obtained the solution using this idea and intuition)
If you need more help, you may e-mail me

P.S. I would be very thankful for any help on 1653 ;)

Edited by author 05.05.2009 14:22
Re: Any clue for this problem?
Posted by Vedernikoff Sergey (HSE: АОП) 5 May 2009 14:17
Thanks, I'll think.

Regarding problem 1653 - I didn't face any troubles with test 16 of the problem, so I don't know what's the reason for such verdict. Check - maybe your program just handles some solids incorrectly? IMHO, it's the only reason. If you still need help - mail me at goryinyich[you-know-what]inbox[you-know-what-again]ru

Edited by author 05.05.2009 14:18