8562번 - Rozkłady dwójkowe 다국어

Rozkładem dwójkowym liczby n nazywamy ciąg "cyfr" a_ka_k-1...a₁a₀, taki że

1. każda z cyfr a₀, a₁, ..., a_k jest równa 1, 0 lub -1;
2. najbardziej znacząca cyfra w rozkładzie, czyli a_k, jest różna od zera;
3. n = a_k·2^k + a_k-1·2^k-1 + ... + a₁·2 + a₀.

Można łatwo zauważyć, że liczba może mieć wiele różnych rozkładów dwójkowych. Spośród tych wszystkich rozkładów, optymalnymi nazwiemy te, które mają najmniejszą liczbę cyfr niezerowych. Na przykład, rozkładami dwójkowymi liczby 15 są: 10001, 1111 i 10011 (dla wygody cyfrę -1 oznaczyliśmy tu jako 1). Pierwszy z tych rozkładów jest rozkładem optymalnym dla 15.

Twoim zadaniem jest napisanie programu, który obliczy, jaka jest liczba cyfr niezerowych w optymalnym rozkładzie dwójkowym podanej liczby.

Program powinien czytać dane ze standardowego wejścia. W pierwszym wierszu danych podana jest liczba r (1 ≤ r ≤ 500). W drugim wierszu podana jest liczba dziesiętna n złożona z r cyfr. Liczba n jest zapisana począwszy od najbardziej znaczących cyfr (tzn. tradycyjnie) i rozpoczyna się od cyfry różnej od zera.

Program powinien pisać wynik na wyjście standardowe. Wynikiem powinna być liczba oznaczająca liczbę cyfr niezerowych w optymalnym rozkładzie dwójkowym liczby n.