Hop-Frog P78101


Statement
 

pdf   zip

html

“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.



unit=0.20cm (64,16)

(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.

Public test cases
  • Input

    1
    3
    4
    11
    1000000000000000
    

    Output

    Case #1: 3
    Case #2: 3
    Case #3: 4
    Case #4: 5
    Case #5: 35
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Final