Permutacja [B]
Limit pamięci: 32 MB
Dany jest ciąg liczb naturalnych (dodatnich) , , ..., .
Chcielibyśmy ustawić liczby od do w ciąg w takiej kolejności, żeby
-ta liczba w ciągu była nie większa niż (dla każdego ).
Innymi słowy, szukamy permutacji liczb od do , która
spełnia warunek dla każdego .
Jest jeszcze jeden problem; otóż ciąg może zmieniać się
w czasie...
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę
całkowitą (), oznaczającą liczbę elementów
ciągu .
Drugi wiersz zawiera ciąg liczb naturalnych
(), pooddzielanych pojedynczymi odstępami.
Trzeci wiersz zawiera jedną liczbę całkowitą
(), oznaczającą liczbę modyfikacji, jakim ma zostać
poddany ciąg .
Następne wierszy zawiera opisy kolejnych modyfikacji ciągu;
każdy z nich składa się z dwóch liczb całkowitych oraz
( dla ), oddzielonych pojedynczym
odstępem i oznaczających, że -ty wyraz ciągu uzyskuje nową wartość
.
Uwaga: zmiany wartości w ciągu następują kolejno, czyli -ta zmiana
wykonywana jest w ciągu, który uległ już modyfikacjom od pierwszej
do -szej.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
Każdy z nich powinien zawierać jedno słowo TAK lub NIE.
Słowo znajdujące się w pierwszym wierszu powinno oznaczać, czy istnieje
jakaś permutacja spełniająca dla każdego nierówność
dla początkowej postaci ciągu , natomiast słowa z wierszy
od drugiego do -szego - czy istnieją jakieś (potencjalnie
różne) permutacje spełniające podane nierówności dla ciągów powstałych
po kolejnych modyfikacjach.
Przykład
Dla danych wejściowych:
5
3 4 3 2 5
2
5 4
1 5
poprawną odpowiedzią jest:
TAK
NIE
TAK
Wyjaśnienie do przykładu.
Dla początkowej postaci ciągu wymagane nierówności spełnia
m.in. permutacja .
Po pierwszej modyfikacji ciąg ma postać
- dla takiego ciągu szukana permutacja nie istnieje.
Po drugiej modyfikacji ciąg ma postać .
Przykładem permutacji spełniającej podane nierówności dla tego
ciągu jest .
Autor zadania: Jakub Radoszewski.