Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024
Problem description
Generał Sherman wygrał właśnie arcyważną bitwę z Pułkownikiem Leopardem. Kolumna jego czołgów wraca teraz do bazy aby świętować zwycięstwo. Jednakże ocalałe czołgi Pułkownika Leoparda zastawiły zasadzkę na oddział Generała Shermana. Pomóż centrali rozsztrzygnąć kto wygra to ostateczne starcie.
Wszystkie czołgi możemy prezentować jako punkty w kartezjańskim
ukłądzie współrzędnych. Generał Sherman posiada N czołgów o współrzędnych
(x1, 1,y1), (x1, 2,y1), …, (x1, N,y1).
Podobnie Pułkownik Leopard ma M czołgów o współrzędnych (x2, 1,y2), (x2, 2,y2), …, (x2, M,y2).
Zachodzi y2 > y1.
Ponieważ czołgi Generała Shermana wracają do bazy, to ich lufy początkowo są skierowane w prawo. Pułkownik Leopard dobrze przygotował swój atak i lufy jego czołgów są skierowane w kierunku czołgów przeciwnika, w dół. Początkową przykładową sytuajcę ilustruje obrazek.
Gdy rozpocznie się walka, wszystkie czołgi będą mogły zacząć obracać swoje lufy, każdy z tą samą prędkością kątową. Jeśli lufa czołgu jest aktualnie skierowana na inny czołg, to może on go zniszczyć. Nawet jeżeli ma on sam zostać zniszczony w tym samym momencie. W szczególności jeśli dwa czołgi celują w siebie nawzajem to mogą oba siebie zniszczyć.
Pomóż centrali dowiedzieć się, który z przywódców pierwszy zniszczy wszystkie czołgi przeciwnika przy optymalnym postępowaniu obu stron. Może się zdarzyć, że na koniec bitwy wszystkie czołgi zostaną zniszczone, w takim przypadku ogłoś remis.
Wejście
W pierwszym wierszu wejścia znajdują się cztery liczby: N, M, y1 i y2.
W drugim wierszu wejścia znajduje się N liczb: x1, 1, x1, 2, …, x1, N.
W trzecim i ostatnim wierszu wejścia znajduje się M liczb: x2, 1, x2, 2, …, x2, M.
Wyjście
Twój program powinien wypisać dokładnie jeden wiersz.
Jeśli wygrał Generał Sherman powinno się w nim znajdować słowo
Sherman
.
W przypadku wygranej Pułkownika Leoparda powinno to być słowo
Leopard
.
A w przypadku remisu słowo Remis
.
Ograniczenia
1 ≤ N, M ≤ 100 000
1 ≤ y1 < y2 ≤ 1 000 000
1 ≤ x1, 1 < x1, 2 < … < x1, N ≤ 1 000 000
1 ≤ x2, 1 < x2, 2 < … < x2, M ≤ 1 000 000
Podzadania
Podzadanie | Warunki | Punkty |
---|---|---|
1 | N, M ≤ 2 | 10 |
2 | N, M ≤ 10 | 20 |
3 | walka nie skończy się remisem | 30 |
4 | brak dodatkowych ograniczeń | 40 |
Przykład
Wejście | Wyjście | Wyjaśnienie |
|
|
Jest to test z obrazka z treści. |