InfoCNFB 2024 Mirror - Juniori | Fast

Cerință

Sunteți la un game-show pentru informaticieni ambițioși. Ați ajuns, după mai multe probe grele, în finală. Aici, prezentatorul vă adresează următoarea întrebare:

Pentru un număr natural $n$ și având la dispoziție doar operațiile de adunare cu $1$ și înmulțire cu $2$, care este numărul minim de pași necesari astfel încât, pornind de la numărul $0$ să ajungem $n$?

Veți reuși să luați marele premiu (o placă video de ultimă generație)?

Date de intrare

Programul citește din fișierul fast.in numărul $n$, un număr natural.

Date de ieșire

Programul va scrie în fișierul fast.out numărul minim de pași făcuți pentru a ajunge la numărul $n$.

Restricții și precizări

• $0 \leq n \leq 10^{12}$ ($10$ la puterea a $12$-a).

Exemplul 1

fast.in

4

fast.out

3

Explicație

Pentru a obține numărul $4$, pornind de la $0$, adăugăm $1$ pentru a ajunge la $1$, apoi înmulțim cu $2$ pentru a ajunge la $2$, și din nou înmulțim cu $2$ pentru a ajunge la $4$.

Exemplul 2

fast.in

7

fast.out

5

Exemplul 3

fast.in

13

fast.out

6