W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Rozkładem dwójkowym liczby nazywamy ciąg "cyfr" , taki że
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 są: 10001, 1111 i 10011 (dla wygody cyfrę oznaczyliśmy tu jako 1). Pierwszy z tych rozkładów jest rozkładem optymalnym dla .
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 (). W drugim wierszu podana jest liczba dziesiętna złożona z cyfr. Liczba 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 .
Dla danych wejściowych:
2 15
poprawną odpowiedzią jest:
2