In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
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.
Wicehrabia de Bajteaux jest właścicielem znanej na całym świecie kolekcji głazów. Dotychczas utrzymywał ją w piwnicach swojego pałacu, lecz teraz postanowił wyeksponować kolekcję w swoim ogromnym ogrodzie.
Ogrody wicehrabiego mają kształt kwadratu o bokach długości jednostek. Boki kwadratu leżą w kierunkach wschód-zachód i północ-południe. Dla każdego głazu wicehrabia wyznaczył współrzędne punktu, w którym chciałby, żeby został on umiejscowiony (współrzędne te to odległości od południowego i zachodniego boku ogrodu), a następnie przekazał te informacje służącym. Niestety jednak zapomniał im powiedzieć, w jakiej kolejności podał współrzędne poszczególnych punktów. Dokładniej, współrzędne niektórych punktów mógł podać w kolejności odcięta-rzędna, a niektórych rzędna-odcięta. Nieświadomi tego faktu służący rozmieścili głazy zakładając, że kolejność podawania współrzędnych jest standardowa (odcięta-rzędna).
Wicehrabia postanowił zadbać o bezpieczeństwo swojej kolekcji i ogrodzić ją płotem, tworząc skalniak. Płot ze względów estetycznych ma mieć kształt prostokąta o bokach równoległych do boków ogrodu. Wicehrabia tak rozplanował uporządkowania współrzędnych punktów, żeby łączna długość potrzebnego płotu była jak najmniejsza (czyli spośród wszystkich uporządkowań par współrzędnych podanych punktów, uporządkowanie wicehrabiego wymaga minimalnej łącznej długości płotu). (Przyjmujemy przy tym, że prostokąt może mieć boki zerowej długości.)
Aby nie wyszła na jaw omyłkowa realizacja planu wicehrabiego, służący muszą poprzestawiać głazy tak, by długość potrzebnego do ich ogrodzenia płotu była najmniejsza możliwa. Każdy głaz mogą przestawić tylko tak, by jego nowe położenie miało takie same współrzędne jak aktualne, tylko w odwrotnej kolejności. Chcą się przy tym jak najmniej napracować, gdyż głazy są ciężkie. Chcieliby więc zminimalizować łączny ciężar przestawianych głazów.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę głazów w kolekcji wicehrabiego. Kolejnych wierszy zawiera po trzy liczby całkowite , i (, ), pooddzielane pojedynczymi odstępami i oznaczające współrzędne aktualnego położenia i ciężar -tego głazu. Żadna para nieuporządkowana współrzędnych nie pojawi się na wejściu więcej niż raz.
Pierwszy wiersz wyjścia powinien zawierać dwie liczby całkowite, oddzielone pojedynczym odstępem - najmniejszą możliwą do osiągnięcia długość płotu i minimalny ciężar kamieni, jakie trzeba przemieścić, by taki wynik osiągnąć. Drugi wiersz powinien zawierać ciąg zer i/lub jedynek - -ty znak powinien być jedynką, jeżeli w optymalnym rozwiązaniu przemieszczamy -ty kamień, a zerem w przeciwnym przypadku. Jeżeli istnieje wiele poprawnych rozwiązań, Twój program powinien wypisać jedno z nich.
Dla danych wejściowych:
5 2 3 400 1 4 100 2 2 655 3 4 100 5 3 277
poprawną odpowiedzią jest:
10 200 01010
Autorzy zadania: Marek Cygan i Jakub Radoszewski.