Lizak
Limit pamięci: 64 MB
Bajtazar prowadzi w Bajtogrodzie sklep ze słodyczami. Wśród okolicznych dzieci najpopularniejszymi słodyczami są lizaki waniliowo-truskawkowe. Składają się one z wielu segmentów jednakowej długości, z których każdy ma jeden smak - waniliowy lub truskawkowy. Cena lizaka jest równa sumie wartości jego segmentów; segment waniliowy kosztuje jednego bajtalara, a truskawkowy dwa bajtalary.
Rys. 1: Przykładowy lizak o pięciu segmentach,
trzech truskawkowych i dwóch waniliowych, ułożonych na przemian.
Cena tego lizaka wynosi bajtalarów.
Obecnie Bajtazarowi został na składzie tylko jeden (za to być może bardzo długi) lizak. Sprzedawca zdaje sobie sprawę, że być może nikt nie będzie chciał go kupić w całości, dlatego dopuszcza możliwość łamania go na granicach segmentów w celu uzyskania lizaka o mniejszej długości. Fragment lizaka przeznaczony ostatecznie do sprzedaży musi pozostać niepołamany.
Doświadczenie pokazuje, że klienci najczęściej chcą kupić lizaka za całe swoje kieszonkowe.
Bajtazar zastanawia się, dla wielu możliwych wartości , jak przełamać posiadany lizak tak,
aby otrzymać lizak o cenie równej dokładnie
bajtalarów.
Ponieważ zadanie nie jest wcale proste, poprosił Cię o pomoc.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz
(
) oddzielone pojedynczym odstępem.
Oznaczają one odpowiednio liczbę segmentów ostatniego pozostałego w sklepie lizaka oraz liczbę rozpatrywanych wartości
.
Segmenty lizaka są ponumerowane kolejno od 1 do
.
W drugim wierszu znajduje się
-literowy opis lizaka, złożony z liter T i W,
przy czym T oznacza segment truskawkowy, zaś W - waniliowy;
-ta z tych liter opisuje smak
-tego segmentu.
W kolejnych
wierszach znajdują się kolejne wartości
do rozpatrzenia
(
), po jednej w wierszu.
Wyjście
Twój program powinien wypisać na standardowe wyjście dokładnie wierszy
zawierających wyniki dla kolejnych wartości
, po jednym wyniku w wierszu.
Jeśli dla danej wartości
nie da się wyłamać z lizaka spójnego fragmentu o wartości równej
bajtalarów,
należy wypisać słowo NIE.
W przeciwnym przypadku należy wypisać dwie liczby
oraz
(
) oddzielone pojedynczym
odstępem, takie że fragment lizaka złożony z segmentów o numerach od
do
włącznie ma wartość dokładnie
bajtalarów.
Jeśli istnieje wiele możliwych odpowiedzi, Twój program może podać dowolną z nich.
Przykład
Dla danych wejściowych:
5 3 TWTWT 5 1 7
poprawną odpowiedzią jest:
1 3 2 2 NIE
Wyjaśnienie do przykładu: Przykład opisuje lizak z rys. 1. Segmenty o numerach od 1 do 3 tworzą lizak postaci TWT, wart 5 bajtalarów. Segment numer 2 ma smak waniliowy i kosztuje 1 bajtalara. Z tego lizaka nie da się w żaden sposób uzyskać lizaka wartego 7 bajtalarów.
Autor zadania: Jakub Pachocki.