Polish version    English version  
  Historia OI -> VII OI 1999/2000 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 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