Lollobrygida
Limit pamięci: 32 MB
W fabryce poduszkowców do budowy torów testowych używa się standardowych
bloków o różnych wysokościach, ustawianych jeden za drugim.
W idealnie zbudowanym torze, zwanym lollobrygidą, nigdy nie
występują obok siebie
dwa bloki jednakowej wysokości, nigdy też trzy kolejne bloki nie mają
kolejno coraz większych, albo coraz mniejszych wysokości.
Mówiąc bardziej formalnie, niech oznacza ciąg
wysokości kolejnych bloków należących do toru. Jeśli
dla każdego zachodzi:
to taki tor można nazwać
lollobrygidą.
Przykład
Z zestawu bloków o wysokościach nie da się
zbudować lollobrygidy, gdyż albo musiałyby stać w niej
obok siebie dwa bloki
wysokości , albo musi się w niej pojawić jedna z niedozwolonych
sekwencji lub .
A oto przykład lollobrygidy, poprawnie zbudowanej z innego
zestawu bloków:
. Z tego zestawu można też zbudować inne
lollobrygidy.
Zadanie
Napisz program, który wczyta ze standardowego wejścia liczbę
zestawów danych i dla każdego zestawu:
- wczyta liczbę bloków oraz wysokości poszczególnych bloków,
- stwierdzi, czy z podanego zestawu można zbudować lollobrygidę,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się
liczba całkowita , ,
równa liczbie zestawów danych.
W następnym wierszu standardowego wejścia zaczyna się pierwszy zestaw
danych.
W pierwszym wierszu każdego zestawu danych znajduje się
liczba całkowita , . Jest to liczba bloków
w tym zestawie.
W kolejnych wierszach znajdują się wysokości bloków.
Każdy z tych wierszy zawiera jedną liczbę całkowitą równą
wysokości odpowiedniego bloku, .
Kolejne zestawy danych następują bezpośrednio po sobie.
Wyjście
Standardowe wyjście powinno zawierać dokładnie wierszy,
po jednym dla każdego zestawu danych.
W -tym wierszu standardowego wyjścia powinien być zapisany jeden wyraz:
- TAK, jeżeli z -tego zestawu bloków można
zbudować lollobrygidę,
- NIE, w przeciwnym przypadku.
Przykład
Dla danych wejściowych:
2
5
3
3
3
5
2
6
3
3
1
5
2
2
poprawną odpowiedzią jest:
NIE
TAK
Autor zadania: Piotr Chrząstowski-Wachtel