Zaginanie papieru

25.11.2011

Zaginanie papieru

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Hektor bardzo nudzi się na lekcjach, dlatego wymyślił sobie grę, która ma zapewnić mu zajęcie. Wyciął pasek papieru i napisał na nim ciąg zer i jedynek (np. 10000101011). Teraz planuje zaginać pasek pomiędzy kolejnymi symbolami tak, aby dało się dopasować zagiętą część do części na którą się ją zagina. Zasada jest taka, że zera i jedynki z nakładających się fragmentów muszą się zgadzać. Można więc zagiąć przykładowy pasek 10000101011 pomiędzy trzecim i czwartym symbolem i uzyskać pasek 00101011, lub zagiąć pasek pomiędzy przedostatnim i ostatnim symbolem i uzyskać pasek 1010100001. Zauważmy, że Hektor zawsze zagina pasek z lewej na prawą stronę. 

Hektor pragnie zaginać pasek tak (być może wielokrotnie), aby w rezultacie uzyskać jak najkrótszy pasek. Na przykład z paska 10011001 można uzyskać pasek 01 zginając najpierw pomiędzy czwartym i piątym symbolem (uzyskujemy 1001), po czym między drugim i trzecim.

Hektor zastanawia się jaka jest najkrótsza osiągalna długość paska. Czy potrafisz mu pomóc?

Wejście

W pierwszej linii znajduje się jedna liczba całkowita t - liczba zestawów testowych (1 <= t <= 20). Następuje t opisów kolejnych zestawów testowych

Opis pojedynczego zestawu testowego składa się z jednej linii zawierającej opis paska papieru Hektora. Będzie to ciąg zer i jedynek nieoddzielonych żadnymi znakami. Ciąg będzie składał się z co najmniej jednego symbolu i będzie nie dłuższy niż 100.

Wyjście

Dla każdego zestawu testowego należy w osobnej linii wypisać jedną liczbę całkowitą - długość najkrótszego paska, jaki można uzyskać za pomocą (być może wielokrotnego) zaginania.

Przykład

Wejście Wyjście
3
11111111111
10011001
101
1
2
3
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com