Soldados en fila P81846

Statement

“¿Cómo colocar 10 soldados en 5 filas de 4 soldados por fila?”

Aunque parezca un problema imposible, he aquí una solución:

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

Entrada

La entrada consiste en diversos casos, cada uno con un número natural $n$ entre 2 y $10^8$ .

Salida

Para cada caso, se deben colocar $n$ soldados en filas, como sigue: En una circunferencia, hay que escoger $x$ puntos diferentes, para $x$ impar y al menos 3. Después, hay que trazar $x$ segmentos rectos entre pares diferentes de esos $x$ puntos. Al final, se puede colocar un soldado en cada intersección resultante, incluyendo las producidas en los extremos de los segmentos.

Para cada $n$ dada, escribid la mínima $x$ que permite colocar al menos $n$ soldados.

Public test cases

Input

Output

Information

Author: Salvador Roura
Language: Spanish
Other languages: English
Official solutions: C++
User solutions: C++