Quando il Dr. Bruce Banner si trasforma nell’incredibile Hulk, acquista sempre più forza con l’andare del tempo.
Al tempo t=0 riesce a saltare un solo metro, al tempo t=1 ne salta due, al tempo t=2 ne salta quattro e così via: in generale, al tempo t ≥ 0, riesce a saltare 2t metri.
Tuttavia l’incredibile Hulk può saltare sempre e solo nella stessa direzione: dunque ad ogni istante t può decidere se saltare in avanti alla distanza permessagli in quel momento oppure stare fermo.
Hulk deve percorrere una certa distanza D > 0, espressa in metri, e vuole effettuare il minor numero di salti.
- Per esempio, per D=9, Hulk salta due volte (effettua un salto da 1 e uno da 8);
- per D=7, Hulk salta tre volte (un salto da 1, uno da 2 e uno da 4);
- per D=16, Hulk effettua il solo salto da 16.
Aiuta Hulk a calcolare quale è il minimo numero di salti che deve effettuare per coprire la distanza D.
Dati in Input
Il file input.txt è composto da una sola riga contenente un intero positivo D, che rappresenta la distanza da percorrere.
Dati in Output
Il file output.txt è composto da una sola riga che contiene il numero di salti che Hulk deve effettuare per coprire la distanza D.
Assunzioni
- 1 <= D <= 230
Esempi
input.txt | output.txt | |
---|---|---|
1 | 9 | 2 |
2 | 7 | 3 |
3 | 16 | 1 |
Note
- Per ogni input, esiste una sola risposta da fornire in output.