Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP6_2F - Redukcja liczby |
Grześ w przerwach pomiędzy rozwiązywaniem zadań usilnie poszukuje nowych form rozrywki. Wszelkie gry planszowe oraz gra "kamień, papier, nożyce" już dawno znudziły się naszemu bohaterowi i postanowił stworzyć coś zupełnie nowatorskiego. Swój najnowszy pomysł nazwał "redukcją liczby".
Gra polega na tym, że z pewnej liczby zapisanej w postaci binarnej w każdym ruchu usunąć można dowolny spójny podciąg zer lub jedynek, o ile jego długość jest większa od 1. Jeżeli w wyniku usunięcia podciągu powstała luka, Grześ scala ze sobą pozostałe ciągi. Gra kończy się w momencie gdy nie ma możliwości usunięcia kolejnego podciągu albo wszystkie cyfry zostały już usunięte.
Nasz bohater chciałby wiedzieć jaka jest minimalna liczba ruchów niezbędnych do całkowitego zredukowania liczby, o ile jest to w ogóle możliwe. Pomóż Grzesiowi i napisz program, który dla każdej wczytanej liczby binarnej wyznaczy minimalną ilość ruchów potrzebnych do całkowitego jej zredukowania albo wypisze - w przypadku, kiedy jest to niemożliwe.
Wejście
W pierwszej linii wejścia znajduje jedna liczba całkowita n (1 ≤ n ≤ 100) określająca ilość liczb do zredukowania. W kolejnych n liniach znajdują liczby do zredukowania w zapisie binarnym (mogą zawierać wiodące zera). Długość każdej z liczb nie przekracza 25 cyfr.
Wyjście
Na wyjściu dla każdej liczby wypisz minimalną ilość ruchów potrzebną do jej całkowitego zredukowania albo - jeżeli jest to niemożliwe.
Przykład
Wejście
2 01110 0101
Wyjście
2 -
Dodane przez: | Maciej Boniecki |
Data dodania: | 2014-03-14 |
Limit czasu wykonania programu: | 0.5s-3s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |