Globglogabgalab P48500


Statement
 

pdf   zip

thehtml
Una biblioteca té n passadissos, numerats en ordre de l’1 a l’n. A un dels passadissos s’amaga en Globglogabgalab (Glob, per abreujar). Sense mirar, des de fora de la biblioteca, i repetidament, podeu triar un número de passadís i preguntar a crits al Glob si es troba allà. Si encerteu, ja heu acabat. Altrament, en Glob es mourà a un dels (com a molt) dos passadissos adjacents al que es troba actualment. El vostre objectiu és triar una seqüència de números de la mínima longitud ℓ(n) que us garanteixi que encertareu en algun moment on està en Glob.

Per exemple, tenim ℓ(3) = 2, perquè per a n = 3 la seqüència 2 2 és òptima: Si en Glob estava inicialment al passadís 2, a la primera ja estem. Altrament, al principi en Glob estava al passadís 1 o 3, per la qual cosa en el segon moment estarà segur en el 2. I és trivial veure que no es pot aconseguir trobar amb seguretat en Glob amb un sol intent.

Per a cada n donada, quant val ℓ(n)?

Entrada

L’entrada consisteix en una línia amb un natural m entre 0 i 104, seguit d’m línies, cadascuna amb una n entre 1 i 106.

Sortida

Per a cada n, cal escriure una línia amb ℓ(n).

Public test cases
  • Input

    4
    1
    2
    3
    4
    

    Output

    1
    2
    2
    4
    
  • Information
    Author
    Víctor Martín
    Language
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python