Hop-Frog P78101
“What is the diversion?” “We call it the Eight Chained Ourang-Outangs”…A long chain was now procured. First, it was passed about the waist of the king, and tied, then about another of the party, and also tied; then about all successively, in the same manner…The party stood as far apart from each other as possible, they formed a circle…Hop-Frog passed the residue of the chain in two diameters, at right angles, across the circle…
The rest of the story is well-known: Hop-Frog burnt alive the cruel king and his seven ministers with the help of Trippetta, and afterwards they escaped home. Now Hop-Frog is wondering if he could have tied those nobles differently. He is considering situations where n nobles are tied in a circle, and where each noble may be additionally tied to exactly another noble (different from the one to his left or to his right), with a straight chain that crosses at most another straight chain. Below, on the left you can see the original situation of the story. On the center you can see another possibility for n = 8. On the right you can see one of the many possibilities for n = 16. Note that for n ≤ 3 there is just one possibility, namely no additional chains at all.
(0,8)0.40(0,8) (2.3431,13.6569)0.41(2.3431,13.6569) (8,16)0.42(8,16) (13.6569,13.6569)0.43(13.6569,13.6569) (16,8)0.44(16,8) (13.6569,2.3431)0.45(13.6569,2.3431) (8,0)0.46(8,0) (2.3431,2.3431)0.47(2.3431,2.3431)
-01 -12 -23 -34 -45 -56 -67 -70
-04 -26
(24,8)0.410(24,8) (26.3431,13.6569)0.411(26.3431,13.6569) (32,16)0.412(32,16) (37.6569,13.6569)0.413(37.6569,13.6569) (40,8)0.414(40,8) (37.6569,2.3431)0.415(37.6569,2.3431) (32,0)0.416(32,0) (26.3431,2.3431)0.417(26.3431,2.3431)
-1011 -1112 -1213 -1314 -1415 -1516 -1617 -1710
-1013 -1117 -1416
(48,8)0.420(48,8) (50.3431,13.6569)0.421(50.3431,13.6569) (56,16)0.422(56,16) (61.6569,13.6569)0.423(61.6569,13.6569) (64,8)0.424(64,8) (61.6569,2.3431)0.425(61.6569,2.3431) (56,0)0.426(56,0) (50.3431,2.3431)0.427(50.3431,2.3431)
(63.391,11.0614)0.430(63.391,11.0614) (48.609,11.0614)0.431(48.609,11.0614) (63.391,4.9386)0.432(63.391,4.9386) (48.609,4.9386)0.433(48.609,4.9386) (59.0614,15.391)0.434(59.0614,15.391) (59.0614,0.609)0.435(59.0614,0.609) (52.9386,15.391)0.436(52.9386,15.391) (52.9386,0.609)0.437(52.9386,0.609)
-2031 -2136 -2234 -2330 -2432 -2535 -2637 -2733
-3121 -3622 -3423 -3024 -3225 -3526 -3727 -3320
-2032 -2125 -2230 -2633 -2735
Hop-Frog plans to keep killing the maximum number of nobles, but he could be bewildered by too many possible ways to tie them. To help Hop-Frog with his exquisite purpose, please compute the maximum number of nobles n for which there are at most x ways to tie them.
Input
Input consists in several test cases, each one with an integer number x between 1 and 1018.
Output
For every case, print its number followed by the maximum number of nobles n for which there are at most x ways to tie them.
Input
1 3 4 11 1000000000000000
Output
Case #1: 3 Case #2: 3 Case #3: 4 Case #4: 5 Case #5: 35
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++