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.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke mino.in.) U prvom i jednom redu ulazne datoteke nalazi se prirodni broj n. Broj n neće imati više od 1000 cifara. Broj neće imati vodećih nula.

Izlaz.

(Izlazne podatke upisati u datoteku mino.out) U prvi i jedini red izlazne datoteke 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.

Primer 1.

5

4

Objašnjenje.

Minimalni broj operacija potrebnih da se broj 5 dovede na nulu je 4. Jedini algoritam koji sadrži 4 operacija je:

5 → 4 → 2 → 1 → 0

Primer 2.

30

7

/*
  Author: Andreja Ilic, PMF Nis
  e-mail: ilic_andrejko@yahoo.com
*/ 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_N 1005

// d - broj pamtimo u nizu d po ciframa u obrnutom redosledu
// n - broj trenutnih cifara u broj
int n, d[MAX_N], sol;

  // Unos podataka
  void input()
  {
    FILE *in = fopen ("mino.in", "r");
    char tmp [MAX_N];
    fscanf (in, "%s", &tmp);
    n = strlen(tmp);
    for (int i = 0; i < n; i++)
      d [n - i] = (int)(tmp [i] - '0');
    fclose(in);
  }

  void output()
  {
    FILE *out = fopen ("mino.out", "w");
    fprintf (out, "%d\n", sol);
    printf ("%d\n", sol);
    fclose(out);
  }

  // Funckija koja deli trenurni broj sa 2
  void divide(int c)
  {
    int tmp = 0;
    for (int i = n; i >= 1; i--)
    {
      tmp = tmp * 10 + d [i];
      d [i] = tmp / c;
      tmp = tmp % c;
    }
    if (d [n] == 0)
      n--;
  }

  // Metoda koja trenutnom broju dodaje 1
  void add()
  {
    d [1] = d [1] + 1;
    int index = 1;
    while (d [index] == 10)
    {
      d [index] = 0;
      d [++index]++;
    }
  }

  // Metoda koja trenutnom broju oduzima 1
  void sub()
  {
    d [1] = d [1] - 1;
    int index = 1;
    while ((d [index] == -1) && (index < n))
    {
      d [index] == 9;
      d [++index]--;
    }
    if (d [n] == 0)
      n--;
  }

  void printN()
  {
    printf ("%d: ", sol);
    for (int i = n; i >= 1; i--)
      printf("%d", d [i]);
    printf ("\n");
  }

  int solve()
  {
    //printN();

    // [1] Ispitivanje kraja rekurzije
    if (n == 1)
    {
      switch (d [1])
      {
        case 0:
          return 0;
        case 1:
          return 1;
        case 3:
          return 3;
        default:
          break;
      }
    }

    int tmp = d [2] * 10 + d [1];

    // [2] Ukoliko je broj deljiv sa 2, delimo ga
    if (tmp % 4 == 2)
    {
      divide(2);
      return (1 + solve());
    }

    if (tmp % 4 == 0)
    {
      divide(4);
      return (2 + solve());
    }

    // [3] Ispitujemo da li treba dodati 1 ili oduzeti 1
    if ((tmp + 1) % 4 == 0)
      add();
    else
      sub();

    return (1 + solve());
  }

  int main()
  {
    input();
    d [n + 1] = 0;
    sol = solve();
    output();

    return 0;
  }