시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1 | 1 | 1 | 100.000% |
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?
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.
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.
3 11111111111 10011001 101
1 2 3
Contest > Spot > FallSpot 2011 3-4번