Problem description

Back

Show PDF

.desc_header { margin-bottom: 2em; text-align: center; } .desc_title { font-size: 200%; text-decoration: underline; padding: 0em 0.2em; display: inline-block; } .desc_code { padding: 0em 0.2em; font-weight: bold; display: inline-block; } .desc_meta { margin: 0.5em; } .desc_memlimit { padding: 0em 1.25em; display: inline-block; } .desc_timelimit { padding: 0em 1.25em; display: inline-block; } .desc .example-test { width: 100%; margin-top: 10px; } .desc .example-test td { vertical-align: top; } .desc .example-test pre { margin-top: 5px; } Zderzające kulki (F) Limit pamięci: 256 MB Limit czasu: 1.00 s W wąskiej rurze leży w jednej linii N kulek. Kolejne kulki (patrząc od lewej do prawej) mają początkowe masy M1, M2, …, MN. Uwaga fizyczna: Masy te mogą przyjmować wartości dodatnie, zerowe, a nawet ujemne. Obiekty te składają się z niestabilnej materii kwantowej – w trakcie gwałtownych zderzeń kulka może stracić więcej masy, niż faktycznie posiadała, co powoduje „przejście przez zero” i uzyskanie ujemnej masy (działającej jak egzotyczna antywaga odpychająca otoczenie). W jednym ruchu możesz wybrać dwie sąsiadujące ze sobą kulki i zamienić je miejscami. Zamiana wymaga jednak zderzenia, które zmienia ich masy: Lewa kulka przeskakująca w prawo traci 1 jednostkę masy, natomiast prawa kulka przeskakująca w lewo zyskuje 1 jednostkę masy. Możesz wykonać dowolną liczbę takich ruchów (masy kulek mogą w trakcie lub na końcu stać się zerowe albo ujemne). Twoim zadaniem jest sprawdzenie, czy da się ustawić kulki tak, aby ich ostateczne masy tworzyły ciąg niemalejący (czyli dla każdego i od 1 do N − 1, masa kulki na pozycji i ma być mniejsza lub równa masie kulki na pozycji i + 1). Wejście W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę kulek. Drugi wiersz wejścia zawiera N liczb całkowitych M1, M2, …, MN pooddzielanych pojedynczymi odstępami, określających początkowe masy kolejnych kulek. Wyjście Twój program powinien wypisać jedno słowo — TAK, jeśli da się ustawić kulki w ciąg niemalejący, lub NIE w przeciwnym wypadku. Ograniczenia 1 ≤ N ≤ 200 000, 1 ≤ Mi ≤ 109 Przykład Wejście Wyjście Wyjaśnienie 3 5 2 4 TAK Początkowe masy kulek to [5,2,4]. Zamieniamy pierwszą i drugą kulkę miejscami: pierwsza traci 1 jednostkę masy (5 − 1 = 4), a druga zyskuje 1 jednostkę (2 + 1 = 3). Otrzymujemy układ [3,4,4], który jest ciągiem niemalejącym (3 ≤ 4 ≤ 4). Wejście Wyjście 2 5 4 NIE Ocenianie Podzadanie Warunki Punkty 1 N ≤ 10 20 2 N ≤ 1000 30 3 Brak dodatkowych ograniczeń 50

Wejście	Wyjście	Wyjaśnienie
`3 5 2 4`	`TAK`	Początkowe masy kulek to [5,2,4]. Zamieniamy pierwszą i drugą kulkę miejscami: pierwsza traci 1 jednostkę masy (5 − 1 = 4), a druga zyskuje 1 jednostkę (2 + 1 = 3). Otrzymujemy układ [3,4,4], który jest ciągiem niemalejącym (3 ≤ 4 ≤ 4).

Wejście	Wyjście
`2 5 4`	`NIE`