Zadanie: AUT
Autostrada 2 [A]Potyczki Algorytmiczne 2024, runda piąta. Limity: 1024 MB, 4 s.

15.03.2024

Bajtocja i Bitocja po latach bezsensownych wojen wreszcie podpisały traktat pokojowy. Na znak ostatecznejzgody pomiędzy stolicami państw została wybudowana autostrada. Ty zaś zostałeś wyznaczony na zarządcęnitki autostrady prowadzącej z Bajtocji w kierunku Bitocji.∗
Na autostradzie aktualnie znajduje się m bramek poboru opłat, ponumerowanych kolejno liczbami od 1
do m. Pierwsza z nich znajduje się na początku autostrady, a ostatnia – na końcu. Koszty przejazdu przez danąbramkę mogą być różne o różnych porach dnia. Doba jest podzielona na n godzin, ponumerowanych liczbami
od 1 do n. Aktualnie koszt przejazdu przez bramkę j o godzinie i wynosi ci,j bajtalarów. Niektóre spośród tychkosztów mogą być równe 0 (przejazd przez bramkę jest wtedy darmowy) lub nawet ujemne (kierowca wtedy
otrzymuje −ci,j bajtalarów za przejazd bramką).
Cała autostrada jest na tyle krótka, że można przejechać ją w przeciągu jednej godziny. Jednak oczywiścienie trzeba się tak śpieszyć – w trakcie przejazdu można zrobić dowolnie wiele postojów. Nie można jednak
nocować na autostradzie; przez wszystkie bramki trzeba przejechać tego samego dnia.
Oczywiście kierowcy chcą przejechać autostradę możliwie małym kosztem. Przez f (i, j) dla 1 ≤ i ≤ j ≤ noznaczamy minimalny możliwy koszt przejechania całej autostrady, jeśli przez pierwszą bramkę kierowca przejedzie w godzinie i, a przez ostatnią bramkę w godzinie j. Wszystkie wartości f (i, j) zostały ustalone w traktacie
pokojowym przez rządy obu państw, więc jako zarządca autostrady nie możesz ich zmienić. Możesz jednak
dowolnie modyﬁkować cenniki przejazdu przez poszczególne bramki lub nawet zupełnie zamknąć część bramek,o ile pierwsza i ostatnia bramka pozostaną otwarte, wartości f (i, j) nie ulegną zmianie oraz wszystkie ustaloneprzez Ciebie koszty będą całkowitymi wielokrotnościami jednego bajtalara.
Aby zminimalizować koszty utrzymania autostrady, chciałbyś zamknąć jak najwięcej bramek. Wyznacz
minimalną liczbę bramek, jakie muszą pozostać otwarte, aby nadal spełniać warunki traktatu.
Projekt reorganizacji schematu poboru opłat będzie składał się z dwóch faz. W pierwszej fazie – wstępnym
projekcie – wystarczy, że znajdziesz samą optymalną liczbę bramek. Jednak w drugiej fazie – fazie wdrożenia
projektu – musisz dodatkowo podać cały przykładowy cennik dla pozostawionych bramek.

WejścieW pierwszym wierszu wejścia znajdują się trzy liczby całkowite n, m oraz q (2 ≤ n, m ≤ 30 000; n·m ≤ 300 000;q ∈ {0, 1}), oznaczające odpowiednio liczbę godzin w jednej dobie, aktualną liczbę bramek poboru opłat naautostradzie oraz bit opisujący fazę projektu. Wartość q = 0 oznacza pierwszy etap projektu (wstępny projekt),natomiast wartość q = 1 oznacza, że projekt jest już w fazie wdrożenia.
Kolejnych n wierszy zawiera opis aktualnych opłat; i-ty z nich zawiera m liczb całkowitych ci,1 , ci,2 , . . . , ci,m(−106 ≤ ci,j ≤ 106 ). Wartość ci,j oznacza koszt przejazdu przez bramkę j o godzinie i wyrażony w bajtalarach.
Jeśli wartość ci,j jest ujemna, to za przejazd przez j-tą bramkę o godzinie i kierowca otrzymuje −ci,j bajtalarów.

WyjścieW pierwszym wierszu wyjścia powinna znaleźć się jedna liczba całkowita k (2 ≤ k ≤ m), oznaczająca minimalną
liczbę bramek, jaką trzeba pozostawić na autostradzie, aby żadna wartość f (i, j) się nie zmieniła. Jeśli q = 0,wyjście powinno składać się tylko z jednego wiersza, zawierającego tylko tę jedną liczbę.
Jeśli q = 1, w kolejnych n wierszach powinien znaleźć się przykładowy optymalny cennik opłat spełniający warunki zadania. W i-tym z tych wierszy powinno znaleźć się k liczb całkowitych di,1 , di,2 , . . . , di,k(−1012 ≤ di,j ≤ 1012 ). Wartość di,j oznacza nowy koszt przejazdu przez j-tą z pozostawionych bramek o godzinie i.
Można udowodnić, że dla ograniczeń z zadania zawsze jest możliwe wyznaczenie kosztów będących liczbami
całkowitymi, których wartości bezwzględne nie przekraczają 1012 .
∗ Kierunek z Bitocji do Bajtocji Cię nie interesuje; jest on zarządzany przez wysłannika wrogiego przyjaznego państwa.

1/2Autostrada 2 [A]Przykład
Dla danych wejściowych:
3 6 1-1 0 4 0 -3 0
-4 1 5 2 -5 2
-5 2 3 0 -2 2
poprawnym wynikiem jest na przykład:
3
0 0 0
0 1 0
0 0 0

Natomiast dla danych wejściowych:
5 7 0
0 0 0 8 0 0 0
0 7 6 5 9 7 0
0 0 0 5 9 6 0
9 4 0 4 4 7 0
0 0 0 9 8 6 0
poprawnym wynikiem jest:
3Wyjaśnienie przykładu: W pierwszym teście przykładowym poszczególne minimalne koszty przejazdów
przez autostradę są następujące:f (1, 1) = (−1) + 0 + 4 + 0 + (−3) + 0 = 0,f (1, 2) = (−1) + 0 + 4 + 0 + (−5) + 2 = 0,f (1, 3) = (−1) + 0 + 4 + 0 + (−5) + 2 = 0,f (2, 2) = (−4) + 1 + 5 + 2 + (−5) + 2 = 1,f (2, 3) = (−4) + 1 + 3 + 0 + (−2) + 2 = 0,f (3, 3) = (−5) + 2 + 3 + 0 + (−2) + 2 = 0.
Takich samych kosztów przejazdu nie da się zrealizować przy użyciu dwóch bramek. Zwróć uwagę na to, żepierwsza i ostatnia bramka nie mogą zostać zamknięte, mimo że przy zaproponowanych kosztach di,j na tych
bramkach nie są pobierane żadne opłaty.
W drugim teście przykładowym wyjście nie zawiera propozycji nowego cennika, gdyż projekt reorganizacji
schematu poboru opłat jest dopiero we wstępnej fazie.

Podzadania• W testach wartych połowę punktów zachodzi warunek q = 0.
• W pozostałych testach zawsze zachodzi warunek q = 1.

2/2

Autostrada 2 [A]