Soldiers in row P81846


Statement
 

pdf   zip

thehtml

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



Although this problem looks impossible, this is a solution:



unit=0.40cm (16,16)

[linestyle=dashed,linewidth=0.5pt](8,8)8

[fillstyle=solid](8,16)0.40(8,16) [fillstyle=solid](0.3915,10.4721)0.41(0.3915,10.4721) [fillstyle=solid](15.6085,10.4721)0.42(15.6085,10.4721) [fillstyle=solid](3.2977,1.5279)0.43(3.2977,1.5279) [fillstyle=solid](12.7023,1.5279)0.44(12.7023,1.5279)

[linewidth=2pt]-03 [linewidth=2pt]-04 [linewidth=2pt]-12 [linewidth=2pt]-14 [linewidth=2pt]-32

[fillstyle=solid](8,4.95)0.45(8,4.95) [fillstyle=solid](10.9,7.05)0.46(10.9,7.05) [fillstyle=solid](5.1,7.05)0.47(5.1,7.05) [fillstyle=solid](9.8,10.45)0.48(9.8,10.45) [fillstyle=solid](6.2,10.45)0.49(6.2,10.45)

Input

Input consists of several cases, each with a natural number n between 2 and 108.

Output

For every case, we must arrange n soldiers in rows, as follows: In a circumference, we choose x different points, where x is odd and at least 3. Then, we draw x straight segments between different pairs of those x 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 n, print the minimum x that allows arranging at least n 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++