Operacije
Duletu je bilo jako dosadno na času matematike (ne zato što ga gradivo ne interesuje već zato što je većinu prešao kada se pripremao za takmičenje) tako da je rešio da se malo poigra. Naime, rekao je svom drugu da napiše veliki prirodni broj n na papiru i tvrdio da može samo uz pomoć operacija: dodavanja broja 1 datom broju, oduzimanja broja 1 od datog broja i njegovim deljenjem sa 2 (ukoliko je paran) - dobiti broj 0. Kako njegovo rešenje mora stati na jednom papiru, Dule mora da nađe najmanji broj operacija koje dovode broj n na 0.
Kako je Dule uvideo da ovo nije toliko jednostavan problem, zamolio vas je da napišete program koji nalazi traženi minimalni broj operacija.
Kako je Dule uvideo da ovo nije toliko jednostavan problem, zamolio vas je da napišete program koji nalazi traženi minimalni broj operacija.
InputU prvom i jedinom redu nalazi se prirodni broj n. Broj n neće imati više od 1000 cifara. Broj neće imati vodećih nula.
OutputU prvi i jedini red upisati minimalni broj operacija potrebnih da se prirodni broj n svede na nulu. Operacije su dodavanje ili oduzimanje jedinice i deljenje sa dva, ukoliko je broj paran.
Input
Output
Input
Output
5Output
4Input
30Output
7Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.