Runda 1: Zbijanie Klocków

27.10.2009 - Piotr Młynarczyk
Trudność

Limit czasowy: 1 sekunda
Limit pamięciowy: 32 MB

Bob podczas wakacji bardzo dużo czasu spędzał grając w różne gry (o czym się niebawem przekonacie). Jedną z gier, jakie Bob sobie upodobał, była gra o nazwie "Zbijanie klocków". Gra polega, jak sama nazwa wskazuje, na zbijaniu klocków piłeczką - tak jak na rysunku.

 

Bob już nabrał wprawy w graniu, ale bardzo chciałby mieć program, który pomoże  mu w grze. Prosi więc Ciebie o napisanie następującego programu:

 

  • na wejściu podana jest liczba klocków w pionie i poziomie,
  • następnie liczba zapytań, jakie Twój program musi przetworzyć,
  • każde zapytanie to albo informacja o zbitych klockach - od kolumny X do kolumny Y, oraz N ilość pionków zbitych w pionie (zbijanie działa tak, że po zbiciu N klocków w kolumnie, w której było ich M pozostanie ich max(0, M-N) i tak dla każdej kolumny z zakresu od X do Y włącznie),
  • albo zapytaniem jest pytanie czy jakaś kolumna jest pusta. Twój program powinien na to pytanie odpowiedzieć TAK/NIE, oraz jeżeli fragment pustych kolumn jest spójny, to powinien podać zakres kolumn odkąd dokąd ciągnie się ten spójny fragment pustych kolumn.

 

Wejście

W pierwszej linii wejścia znajduje się pojedyncza liczba T (1<=T<=10), oznaczająca liczbę zestawów testowych. W pierwszej linii każdego zestawu danych znajdują się trzy liczby naturalne A, B oraz C (1<=A, B<=1000; 1<=C<=100), oznaczające odpowiednio szerokość i wysokość początkowego bloku klocków, oraz liczbę zapytań. W kolejnych C liniach zestwu danych znajdują się opisy zapytań. Opis pojedyńczego zapytania składa się z jednego znaku 'Z' lub 'P', gdzie 'Z' oznacza, że jest to zapytanie informujące program o zbitych klockach, natomiast 'P' jest to zapytanie proszące o informację o pustych kolumnach. W przypadku zapytania 'Z' po pojedynczym odstępie za literką 'Z' znajdują się trzy liczby X, Y, N (1<=X<=Y<=A, 0<=N<=1000), również oddzielone pojedyńczymi odstępami, oznaczające odpowiednio zakres zbitych kolumn(od X do Y włącznie), oraz ilość zbitych klocków w tych kolumnach.

 

Wyjście

Dla każdego zapytania należy wypisać pojedynczą linię. Dla zapytań typu 'Z' w linii tej należy wypisać słowo 'OK', natomiast dla zapytania typu 'P' należy wypisać słowo 'NIE', jeżeli nie ma pustej kolumny, lub słowo 'TAK' jeżeli jest przynajmniej jedna pusta kolumna. Dodatkowo jeżeli wszystkie puste kolumny tworzą spójny fragment (nie ma niepustej kolumny, po której prawej i lewej stronie, nie koniecznie w bezpośrednim sąsiedztwie, znajdują się jakieś puste kolumny) to należy wypisać dwie liczby X, Y oznaczające, że pusty ciąg kolumn zaczyna się w kolumnie X, a kończy w kolumnie Y.

 

Przykład

 

Dla danych wejściowych:

 

1
10 5 6
Z 1 10 1
P
Z 2 5 5
P
Z 7 8 4
P


poprawną odpowiedzią jest:

 

OK
NIE
OK
TAK 2 5
OK
TAK
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak
ZałącznikWielkość
klocki.png7.01 KB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com