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 1172. Ship Routes

Who can explain the sample for me? Thank you very much!
Posted by charles.king 12 Apr 2004 19:07
I can only find 5 routes when there are 2 cities on each island : 1 2 1 3 2 3
         1 2 3 1 2 3
         1 2 3 1 3 2
         1 2 3 2 1 3
         1 3 2 1 2 3
Who can tell me the other 11 routes?

Edited by author 13.04.2004 06:02

Edited by author 13.04.2004 06:02
Re: Who can explain the sample for me? Thank you very much!
Posted by sloboz 13 Apr 2004 05:23
there are 3N -> 6 cities (2 on each island) not just 3...
eight solutions are
1 3 5 4 6 2
1 3 6 4 5 2
1 4 5 3 6 2
1 4 6 3 5 2
1 5 3 6 4 2
1 5 4 6 3 2
1 6 3 5 4 2
1 6 4 5 3 2
the other 8 are simetrical

hope I was useful.
Re: Who can explain the sample for me? Thank you very much!
Posted by charles.king 13 Apr 2004 06:00
thank you very much! Now I understand the problem.And I found the 16 routes:(2k and 2k-1 are on the same island,k=1,2,3)
1 3 5 2 4 6
1 3 5 2 6 4
1 3 6 2 4 5
1 3 6 2 5 4
1 4 5 2 3 6
1 4 5 3 2 6
1 4 6 2 3 5
1 4 6 3 2 5
1 5 2 4 6 3
1 5 3 2 4 6
1 5 3 6 2 4
1 5 4 6 2 3
1 6 2 4 5 3
1 6 3 2 4 5
1 6 3 5 2 4
1 6 4 5 2 3
And I think your routes are not correct:the tourist must go back but he can't travel from 2 to 1.Thank you all the same!