Soldiers in row P81846


Statement
 

pdf   zip

“How to arrange 10 soldiers in 5 rows of 4 soldiers each?”

Although this problem looks impossible, this is a solution:

(16,16)

(8,8)8

(8,16)0.40(8,16) (0.3915,10.4721)0.41(0.3915,10.4721) (15.6085,10.4721)0.42(15.6085,10.4721) (3.2977,1.5279)0.43(3.2977,1.5279) (12.7023,1.5279)0.44(12.7023,1.5279)

(8,4.95)0.45(8,4.95) (10.9,7.05)0.46(10.9,7.05) (5.1,7.05)0.47(5.1,7.05) (9.8,10.45)0.48(9.8,10.45) (6.2,10.45)0.49(6.2,10.45)

Input

Input consists of several cases, each with a natural number nn between 2 and 10810^8.

Output

For every case, we must arrange nn soldiers in rows, as follows: In a circumference, we choose xx different points, where xx is odd and at least 3. Then, we draw xx straight segments between different pairs of those xx points. At the end, we can place one soldier on every resulting intersection, those produced at the ends of the segments included.

For every given nn, print the minimum xx that allows arranging at least nn soldiers.

Public test cases

  • Input

    10
11
2
99976869
99976870
99976871

    Output

    5
7
3
14141
14141
14143
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++