In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W stolicy Bajtocji, Bajtawie, ulice mają bardzo regularny układ. Wszystkie biegną albo z północy na południe, albo z zachodu na wschód. Łatwo zauważyć, że każda ulica z północy na południe przecina każdą ulicę z zachodu na wschód w dokładnie jednym miejscu. Ponadto, wzdłuż każdej ulicy kolejne skrzyżowania są odległe o dokładnie 1 km.
W Bajtawie jest zabytkowych budynków, z których każdy znajduje się przy jednym ze skrzyżowań. Radzie Miejskiej bardzo zależy na ochronie tych unikalnych zabytków, dlatego postanowiono wybudować w mieście dwa duże posterunki straży pożarnej. Każdy z zabytków będzie chroniony przez posterunek jemu najbliższy; w przypadku równych odległości od każdego z posterunków, budynek będzie pod ochroną ich obu.
Zabudowa w Bajtawie jest bardzo gęsta. Nie należy więc patrzeć na odległość do zabytków w linii prostej. Zamiast tego, jako odległość od posterunku do zabytku należy przyjąć długość najkrótszej trasy biegnącej ulicami.
Rada Miejska przygotowała kilka projektów lokalizacji posterunków straży. Zostałeś poproszony o wyznaczenie, dla każdego z nich, liczby zabytków chronionych: tylko przez pierwszy posterunek, tylko przez drugi posterunek oraz przez oba posterunki.
W pierwszym wierszu standardowego wejścia znajdują się cztery liczby całkowite , , oraz (, ) pooddzielane pojedynczymi odstępami, oznaczające odpowiednio: liczbę ulic biegnących z północy na południe, liczbę ulic biegnących z zachodu na wschód, liczbę zabytkowych budynków w Bajtawie oraz liczbę projektów zaproponowanych przez Radę Miejską. Ulice biegnące z północy na południe są ponumerowane od do , w kierunku z zachodu na wschód. Ulice biegnące z zachodu na wschód są ponumerowane od do , w kierunku z północy na południe. Skrzyżowaniu -tej ulicy biegnącej z północy na południe z -tą ulicą biegnącą z zachodu na wschód dla uproszczenia przypisujemy współrzędne .
W każdym z kolejnych wierszy znajdują się dwie liczby całkowite oraz (, ) oddzielone pojedynczym odstępem i oznaczające współrzędne -tego zabytku. Żadna para zabytków nie znajduje się przy tym samym skrzyżowaniu.
Każdy z kolejnych wierszy zawiera jedną propozycję Rady Miejskiej - cztery liczby całkowite , , , pooddzielane pojedynczymi odstępami, , , . Współrzędne oraz opisują skrzyżowania, przy których mają być umiejscowione posterunki straży zgodnie z -tą propozycją ().
Twój program powinien wypisać na standardowe wyjście wierszy. W -tym wierszu powinny się znaleźć trzy liczby całkowite, oznaczające: liczbę zabytków chronionych tylko przez pierwszy posterunek z -tej propozycji Rady Miejskiej, liczbę zabytków chronionych tylko przez drugi posterunek oraz liczbę budynków chronionych przez oba posterunki. Liczby te powinny być oddzielone pojedynczymi odstępami.
Dla danych wejściowych:
6 5 6 1 1 2 6 5 5 1 3 3 3 4 4 1 2 3 4 3
poprawną odpowiedzią jest:
1 3 2
Na rysunku linie przerywane przedstawiają ulice, kółka - lokalizacje
zabytków, a krzyżyki - proponowane lokalizacje posterunków straży
pożarnej.
Białe kółko przedstawia zabytek chroniony przez pierwszy posterunek,
czarne kółka - przez drugi posterunek, natomiast szare kółka - przez
oba posterunki.
Autorzy zadania: Marian M. Kędzierski, Jakub Radoszewski.