W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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...
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.
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.
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.