Komplement auf 0 – Fortgeschritten
Wir können jede Zahl in ihrer Binärdarstellung auf 0 reduzieren, indem wir wiederholt eine Komplement-Operation anwenden:
5 = 101 → 10 → 1 → 0 ⇒ 3 Komplement-Operationen.
Diesmal sollen wir ermitteln, wie viele solcher Operationen nötig sind, um sehr große Bitstrings auf 0 zu bringen.
Eingabe
Die Eingabe besteht aus einer einzelnen Zeile, die den Bitstring
s repräsentiert (1 ≤ |s| ≤ ).Ausgabe
Die Ausgabe soll eine einzelne ganze Zahl enthalten – die Anzahl der Komplement-Operationen, die benötigt werden, um
s in 0 zu verwandeln.Beispiele
Eingabe | Ausgabe |
111111000111110011100 | 6 |
Erklärung
111111000111110011100 → 111000001100011 → 111110011100 → 1100011 → 11100 → 11 → 0
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB