W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Nadszedł długo oczekiwany dzień: do bram Bajtocji w końcu zapukał Internet. Pierwszym etapem modernizacji będzie okablowanie stolicy. Zadania tego bardzo chętnie podejmie się Pewna Znana Firma Telekomunikacyjna, jednak nie jest to takie proste z powodu obowiązujących w Bajtocji przepisów oraz ograniczeń infrastrukturalnych.
W stolicy znajduje się wieżowców, każdy z nich na skrzyżowaniu jednej z ulic i jednej z alej. Ulice biegną z północy na południe, a aleje ze wschodu na zachód. Odległość pomiędzy sąsiednimi alejami oraz sąsiednimi ulicami wynosi jeden bajtometr. Ulice są ponumerowane liczbami całkowitymi, ich numery rosną w kierunku wschodnim. Analogiczną numerację stosujemy dla alej, przy czym numery rosną w kierunku północnym.
Kable łączące budynki można kłaść tylko pod ulicami i alejami. Aby połączyć budynek znajdujący się w punkcie () (tj. na skrzyżowaniu ulicy numer z aleją numer ) z budynkiem w punkcie () trzeba zużyć bajtometrów kabla. Co więcej długość pojedynczego kabla nie może przekraczać bajtometrów i nie można ich łączyć poza budynkami.
Aby nie dopuścić do monopolu, każdy z dostawców może zainstalować na dachu dokładnie jednego z budynków antenę odbiorczo-nadawczą. Będzie ona dostarczać Internet do tych wieżowców, które są bezpośrednio lub pośrednio połączone kablami z budynkiem z anteną.
Prezes PZFT zastanawia się jaka jest maksymalna liczba odbiorców, do których może dostarczyć Internet, oraz co najmniej ilu innych dostawców będzie działać w bajtockiej stolicy, jeśli Internet ma być dostarczony do każdego wieżowca.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ) oznaczające odpowiednio liczbę wieżowców oraz maksymalną długość kabla. Wieżowce dla uproszczenia numerujemy kolejnymi liczbami całkowitymi, począwszy od . W kolejnych wierszach znajdują się pozycje wieżowców. Każdy z tych wierszy zawiera dwie liczby całkowite i (), które oznaczają, że -ty wieżowiec znajduje się w punkcie o tych współrzędnych.
Na standardowe wyjście należy wypisać dwie liczby oznaczające odpowiednio minimalną liczbę innych dostawców Internetu, z którymi będzie musiała konkurować PZFT, oraz maksymalną liczbę odbiorców, do których będzie mogła dostarczać Internet.
Dla danych wejściowych:
4 2 1 1 3 3 2 2 10 10
poprawną odpowiedzią jest:
1 3
Autor zadania: Richard Ho (zapożyczenie z USACO: Bartosz Górski).