Globglogabgalab P48500
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