시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 25 | 12 | 10 | 50.000% |
Pan Wincenty bardzo lubi swój ogród, niestety - bardzo nie lubi w nim pracować. A już szczególnie nie lubi grabić opadłych (jak to jesienią) liści. Po kilku latach (i - co za tym idzie - kilku spędzonych na grabieniu liści jesieniach) pan Wincenty uznał, że miarka się przebrała - jego ogród jest po prostu za duży. Postanowił więc oddać część swojego terenu sąsiadom (i niech oni już sobie grabią liście).
Ogród pana Wincentego jest dość nietypowy - ma (ogród, nie pan Wincenty) kształt prostokąta o wymiarach 1 na N i dzieli się na N kolejnych pól o wymiarach 1 na 1. W każdym z tych pól rośnie albo trawa, albo drzewo kasztanowe. Pan Wincenty chce pozostawić sobie jak największą część ogrodu, z zachowaniem następujących zastrzeżeń:
Jaka jest maksymalna długość fragmentu ogrodu, który pan Wincenty może sobie pozostawić?
W pierwszej linii wejścia podana jest liczba testów L (L <= 5). Następnie podawane są opisy poszczególnych testów.
Jeden test składa się z dwóch linii - w pierwszej znajdują się opisane w treści liczby naturalne N i K (0 < K <= N <= 1000000).
W drugiej znajduje się opis ogrodu pana Wincentego - ciąg znaków długości N. Każdy znak ciągu to 'K' lub 'T', w zależności od tego, czy w danym polu rośnie kasztanowiec, czy tylko trawa.
Dla każdego testu w osobnej linii wypisz maksymalną długość fragmentu ogrodu, jaki pan Wincent może sobie pozostawić.
3 10 1 KTTTTTTTTK 10 3 TKTKTKTKTK 10 5 KTKTTTKKKK
9 7 9
Contest > Spot > FallSpot 2009 1-2번