In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Wzdłuż prostej ustawiło się spragnionych mrówek.
Początkowo
-ta mrówka znajduje się w punkcie o współrzędnej
(dla uproszczenia na prostej wprowadzamy oś liczbową), przy czym
.
Na prostą spadają krople rosy.
Wiemy, że -ta kropla rosy spadnie w chwili
na punkt o współrzędnej
(
).
Jeśli w danym momencie na prostej nie ma żadnych kropel, to mrówki stoją w miejscu.
W przeciwnym razie każda z mrówek podąża z jednostkową prędkością
do najbliższej jej kropli rosy - w przypadku, gdy są dwie takie najbliższe krople,
porusza się w lewo.
Gdy jakaś mrówka dotrze do kropli, to natychmiast wypija tę kroplę.
Zauważ, że wypicie kropli może zmienić sposób dalszego poruszania się mrówek. Jeśli do kropli jednocześnie dotrze kilka mrówek, mrówki dzielą się wodą z tej kropli po równo (i natychmiast ją wypijają). W szczególności, w jednym punkcie prostej może znajdować się więcej niż jedna mrówka. Jeśli kropla spadnie bezpośrednio na mrówkę, zostaje wypita dokładnie w momencie spadnięcia i nie wpływa w żaden sposób na ruch mrówek.
Twoim zadaniem jest stwierdzenie, jakie będą położenia wszystkich mrówek na końcu, tzn. w chwili, gdy zostanie wypita ostatnia kropla rosy.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (
)
oznaczającą liczbę mrówek.
Drugi wiersz zawiera niemalejący ciąg
liczb całkowitych
(
) oznaczających położenia kolejnych mrówek wzdłuż prostej.
Trzeci wiersz zawiera jedną liczbę całkowitą
(
) oznaczającą
liczbę zdarzeń.
Każdy z kolejnych
wierszy zawiera dwie liczby całkowite
oraz
(
) oznaczające, że w chwili
na punkt prostej o współrzędnej
spadła kropla rosy.
Zdarzenia będą wymienione w niemalejącej kolejności czasów
.
Twój program powinien wypisać jeden wiersz zawierający ciąg liczb całkowitych
oznaczający położenia poszczególnych mrówek w chwili, gdy skonsumowana zostanie
ostatnia kropla rosy.
Ciąg wynikowy należy wypisać w kolejności niemalejącej.
Dla danych wejściowych:
5 1 3 4 6 7 4 1 2 2 9 4 5 4 1
poprawną odpowiedzią jest:
1 1 2 6 7
Autor zadania: Adam Karczmarz.