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.
Koncern GazBit zamierza zdominować rynek gazowy w Bajtocji. Specjaliści umiejscowili już na mapie Bajtocji optymalne położenia punktów wydobycia gazu oraz stacji dystrybucji gazu - pozostało jeszcze tylko przyporządkować stacje do punktów wydobycia. Każda stacja dystrybucji ma być połączona z dokładnie jednym punktem wydobycia i odwrotnie, każdy punkt wydobycia z dokładnie jedną stacją.
GazBit specjalizuje się w budowie gazociągów prowadzących z punktów wydobycia do stacji dystrybucji w kierunku południowym i wschodnim - dokładniej, każdy wybudowany gazociąg ma (patrząc z lotu ptaka) kształt łamanej, której każda kolejna część biegnie w kierunku południowym lub wschodnim i jest prostopadła do poprzedniej. Zarząd koncernu zastanawia się, jak przyporządkować punktom wydobycia gazu stacje dystrybucji tak, by zminimalizować łączną długość koniecznych do wybudowania gazociągów. Przy planowaniu można pominąć problem przecinania się gazociągów - ich kolidujące fragmenty zostaną umieszczone na różnych głębokościach pod ziemią.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę punktów wydobycia (równą liczbie stacji dystrybucji). Kolejne wierszy zawiera po dwie liczby całkowite i ( dla ), oddzielone pojedynczym odstępem i oznaczające współrzędne na mapie punktów wydobycia gazu. Przyjmujemy, że wraz z rosnącą współrzędną poruszamy się na wschód, a wraz z rosnącą współrzędną poruszamy się na północ. Następne wierszy zawiera po dwie liczby całkowite i ( dla ), oddzielone pojedynczym odstępem i oznaczające współrzędne na mapie stacji dystrybucji gazu. Zarówno punkty wydobycia, jak i stacje dystrybucji numerujemy liczbami naturalnymi od 1 do w kolejności występowania na wejściu. Żadna para współrzędnych nie powtórzy się w jednym zestawie danych wejściowych. Ponadto dla każdych danych wejściowych istnieje jakieś przyporządkowanie punktom wydobycia stacji dystrybucji, które można zrealizować za pomocą gazociągów idących tylko na południe i wschód.
Pierwszy wiersz wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą minimalną sumaryczną długość wszystkich koniecznych do wybudowania gazociągów. Dalej na wyjściu powinien wystąpić przykładowy opis przyporządkowania stacji punktom wydobycia, który realizuje to minimum. Każdy z kolejnych wierszy powinien zawierać dwie liczby całkowite, oddzielone pojedynczym odstępem i oznaczające numery punktu wydobycia i stacji dystrybucji, które powinny być połączone gazociągiem. Kolejność wypisywania przyporządkowań może być dowolna. Jeżeli istnieje wiele poprawnych rozwiązań, Twój program powinien wypisać jakiekolwiek z nich.
Dla danych wejściowych:
3 3 5 1 2 4 3 6 3 5 2 2 1
poprawną odpowiedzią jest:
9 2 3 1 2 3 1
Autor zadania: Jakub Radoszewski.