Polish version    English version  
  O olimpiadzie -> Zadania -> VII OI 1999/2000


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: LOL
Autor: Piotr Chrząstowski-Wachtel
Lollobrygida

Zawody III stopnia, dzień próbny 11 kwietnia 2000
Plik źródłowy: LOL.??? (np. pas, c, cpp)
Plik wykonywalny: LOL.exe
Plik wejściowy: LOL.in
Plik wyjściowy: LOL.out

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 h1,...,hn oznacza ciąg wysokości kolejnych bloków należących do toru. Jeśli dla każdego 1 <= i <= n-2 zachodzi:

  • hi < hi+1 i hi+1 > hi+2 lub
  • hi > hi+1 i hi+1 < hi+2,

to taki tor można nazwać lollobrygidą.

Przykład

Z zestawu 5 bloków o wysokościach 3, 3, 3, 5, 2 nie da się zbudować lollobrygidy, gdyż albo musiałyby stać w niej obok siebie dwa bloki wysokości 3, albo musi się w niej pojawić jedna z niedozwolonych sekwencji (2, 3, 5) lub (5, 3, 2).

A oto przykład lollobrygidy, poprawnie zbudowanej z innego zestawu bloków: (3, 2, 5, 2, 3, 1). Z tego zestawu można też zbudować inne lollobrygidy.

Zadanie

Napisz program, który wczyta z pliku tekstowego LOL.IN 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ę,
  • zapisze wynik w pliku tekstowym LOL.OUT.

Wejście

W pierwszym wierszu pliku tekstowego LOL.IN znajduje się liczba całkowita d, 1 <= d <= 100, równa liczbie zestawów danych. W następnym wierszu pliku LOL.IN zaczyna się pierwszy zestaw danych.

W pierwszym wierszu każdego zestawu danych znajduje się liczba całkowita n, 3 <= n <= 1000000. Jest to liczba bloków w tym zestawie.

W kolejnych n wierszach znajdują się wysokości bloków. Każdy z tych wierszy zawiera jedną liczbę całkowitą h równą wysokości odpowiedniego bloku, 1 <= h 10^9.

Kolejne zestawy danych następują bezpośrednio po sobie.

Wyjście

Plik tekstowy LOL.OUT powinien zawierać dokładnie d wierszy, po jednym dla każdego zestawu danych. W i-tym wierszu pliku LOL.OUT powinien być zapisany jeden wyraz:

  • TAK, jeżeli z i-tego zestawu bloków można zbudować lollobrygidę,
  • NIE, w przeciwnym przypadku.

Przykład

Dla pliku wejściowego LOL.in:

2
5
3
3
3
5
2
6
3
3
1
5
2
2

poprawną odpowiedzią jest plik wyjściowy LOL.OUT

NIE
TAK



Wersja do druku