Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info Ranking

Contest problemset description

Show PDF Back
Stok narciarski
(A)
Limit pamięci: 512 MB
Limit czasu: 2.00 s

W tegorocznej Bitockiej Olimpiadzie Zimowej wprowadzono nową kategorię sportową: narciarstwo przełajowe. Wyznaczony został górski teren, którego można przedstawić jako siatka N × M pól, każde z nich położone na pewnej wysokości. Zadaniem uczestników będzie manewrować na stoku, zaczynając w dowolnym punkcie i przemieszczając się w dowolnym z czterech kierunków, północy, południa, wschodu i zachodu. Celem zawodów jest odwiedzić pewien zbiór pól na stoku wyznaczony przez organizatorów.

Organizatorzy olimpiady chcieliby określić trudność zawodów. Stok ma trudność K, jeżeli istnieje możliwość przejazdu między każdą parą wyznaczonych pól stoku, przejeżdżając jedynie między sąsiednimi polami o maksymalnej różnicy wysokości K. Organizatorzy szukają minimalnego K spełniającego tę wartość. Znalezienie tej wartości przypadło Tobie!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby N oraz M oznaczające wymiary stoku. W następnych N wierszach następuje opis stoku. Każdy wiersz składa się z M liczb. j-ta Liczba w i-tym wierszu to wi, j i oznacza wysokość pola (i,j). Następnie, w następnych N wierszach następuje opis wyznaczonych przez organizatorów pól do odwiedzenia. Każdy wiersz składa się z M liczb, j-ta liczba w i-tym wierszu, xi, j, jest równa 1, gdy pole (i,j) jest wyznaczone do odwiedzenia oraz 0 w przeciwnym przypadku.

Wyjście

W jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą oznaczającą minimalne K takie, że między każdą parą wyznaczonych pól można przejechać zjeżdżając jedynie między polami o różnicy wysokości co najwyżej K.

Ograniczenia

1 ≤ N ⋅ M ≤ 200 000, 0 ≤ wi, j ≤ 109, xi, j ∈ {0, 1} dla 1 ≤ i ≤ N, 1 ≤ j ≤ M. Możesz założyć, że co najmniej jedno pole zostało wyznaczone, tj. że istnieją takie i, j, że xi, j = 1.

Podzadania

Podzadanie Warunki Punkty
1 N = 1. 15
2 xi, j = 1 dla każdego 1 ≤ i ≤ N, 1 ≤ j ≤ M. 35
3 0 ≤ wi, j ≤ 20 dla każdego 1 ≤ i ≤ N, 1 ≤ j ≤ M. 28
4 Brak dodatkowych ograniczeń. 22

Przykład

Wejście Wyjście Wyjaśnienie 
3 5
16 6 0 10 13
9 15 17 10 12
4 0 4 24 15
1 1 0 0 1
0 0 0 0 0
0 0 0 1 0

9

Mimo tego, że pola w lewym górnym rogu sąsiadują ze sobą, lepiej jest początkowo pojechać z pola (1,1) na południe, później na wschód i dopiero na północ.
Poczta
(B)
Limit pamięci: 512 MB
Limit czasu: 1.00 s

Zarządzasz kolejką na poczcie i musisz decydować o tym, kto w danym momencie ma podejść do okienka. Jeżeli w danym momencie oczekuje pewna liczba osób, to oczywiście wiesz, że najpierw do okienka powinna podejść osoba, która przyszła jako pierwsza najstarsza oczekująca osoba. Jeżeli jest wiele oczekujących osób w tym samym wieku – wtedy wpuszczana jest pierwsza, która przyszła, a jeżeli przyszły w tym samym momencie, wpuszczana jest ta, która przy okienku ma stać najkrócej. W momencie, kiedy aktualna osoba zostaje obsłużona, to natychmiast zaczyna być obsługiwana następna (o ile ktokolwiek oczekuje na obsłużenie). W jednym momencie przy okienku może być obsługiwana tylko jedna osoba.

Jesteś już doświadczony, także doskonale wiesz, że dzisiaj na pocztę przyjdzie N osób w wieku w1, …, wN, w momentach dnia c1, …, cN, a każde spędzi pewien czas t1, …, tn przy (oczywiście jedynym otwartym) okienku. Napisz program, który znajdzie kolejność, w jakiej klienci będą obsługiwani.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba N, oznaczająca liczbę osób, które przyjdą na pocztę. W następnych N wierszach znajduje się opis każdej osoby. Opis i-tej osoby składa się z trzech liczb wi, ci, ti, oznaczające odpowiednio wiek, czas przybycia oraz czas spędzenia w okienku i-tej osoby.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać N liczb: kolejność, w jakiej osoby będą podchodzić do okienka.

Ograniczenia

1 ≤ N ≤ 200 000, 0 ≤ wi, ti, ci ≤ 109. Możesz założyć, że żadne dwie osoby nie mają jednocześnie tego samego wieku, czasu przybycia i czasu przy okienku.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 2 000. 20
2 wi = 0 dla każdego 1 ≤ i ≤ N. 25
3 wi ≤ 20 dla każdego 1 ≤ i ≤ N. 30
4 Brak dodatkowych ograniczeń. 25

Przykład

Wejście Wyjście Wyjaśnienie 
4
60 2 5
30 3 3
45 2 4
10 1 2

4 1 3 2

Jako pierwsza na pocztę przyjdzie czwarta osoba, więc jako pierwsza stanie w okienku i będzie tam stała przez 2 minuty. W tym czasie na pocztę przyjdą wszystkie pozostałe osoby. Kiedy czwarta osoba przestanie być obsługiwana, do okienka będą podchodzić pozostałe osoby w kolejności wieku (niezależnie od tego, która była pierwsza).
Pingwiny
(C)
Limit pamięci: 512 MB
Limit czasu: 6.00 s

Wszyscy kochają pingwiny! Pingwiny też kochają pingwiny. W szczególności, pingwiny lubią zbierać się blisko siebie, dzięki czemu lepiej utrzymują ciepło. Jako największy miłośnik pingwinów wyruszyliście wraz z grupą badawczą na Bitorktydę, największe skupisko pingwinów na ziemi. Obserwujecie pewien obszar, który podzielony jest na N × M komórek. W każdej komórce może stać co najwyżej jeden pingwin. Obserwację zaczynacie, kiedy żaden pingwin nie znajduje się na obserwowanym obszarze, jednakże pingwiny są ruchliwe, zatem przychodzą i odchodzą z różnych pól obszaru.

Zauważyłeś, że pingwinek, który stoi w danym polu, jest zadowolony, jeżeli w dokładnie trzech z czterech sąsiadujących z nim pól również stoją pingwiny (dzięki temu pingwinkowi jest ciepło, ale nie za ciepło). Zastanawiasz się, ile pingwinów jest zadowolonych w każdym momencie obserwacji?

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby N, M oraz Q, oznaczających odpowiednio wymiary obserwowanego obszaru oraz liczbę wydarzeń. i-te z wydarzeń opisane jest przez liczby wi, xi, yi. Jeżeli wi to +, to znaczy, że w polu (xi,yi) stanął pingwin. Jeżeli wi to - to oznacza, że z pola (xi,yi) odszedł pingwin. Możesz założyć, że wydarzenia mają sens, tzn. w danym polu może stanąć tylko pingwin, jeżeli to pole było wolne, oraz z danego pola może odejść pingwin tylko wtedy, kiedy jakiś stał tam w tym momencie.

Wyjście

Należy wypisać Q wierszy, i-ty wiersz powinien określać liczbę zadowolonych pingwinów po i-tym zdarzeniu.

Ograniczenia

1 ≤ N, M ≤ 2 000, 1 ≤ Q ≤ 1 000 000, 1 ≤ xi ≤ N, 1 ≤ yi ≤ M.

Podzadania

Podzadanie Warunki Punkty
1 N ⋅ M ⋅ Q ≤ 1 000 000 30
2 Brak dodatkowych ograniczeń. 70

Przykład

Wejście Wyjście 
3 3 12
+ 3 3
+ 1 1
+ 3 1
+ 1 2
+ 1 3
+ 2 1
+ 2 2
+ 2 3
- 3 3
- 2 2
+ 3 3
- 1 2

0
0
0
0
0
0
2
4
3
0
0
0