Úloha: Párování výrobních linek
Proslulá firma pro výrobu ohebných počítačových komponent FlexiMachineOne (FMO) si pronajala několik standardizovaných výrobních hal, ve kterých hodlá umístit výrobní linky svých produktů.FMO chce instalovat N výrobních linek očíslovaných od 0 do N−1, přičemž N je sudé číslo. V každé hale je prostor pro právě dvě výrobní linky, proto si FMO pronajala právě N/2 hal. Jednotlivé výrobní linky se ale navzájem technologicky liší, a proto dlouhodobé náklady na provoz dvojice linek v jedné hale závisí na tom, které konkrétní linky to budou. Vývojové oddělení FMO spočetlo pro každou dvojici linek dlouhodobé náklady pro případ, že obě linky budou v jedné hale. Výsledek v podobě nákladové tabulky předložilo ředitelství firmy. To se má nyní na základě tohoto podkladu rozhodnout, jak jednotlivé linky spárovat. Nezáleží na tom, ve které hale která dvojice linek nakonec bude umístěna (haly jsou standardizované), záleží však na tom, aby celkové náklady dané součtem nákladů na jednotlivé páry linek v jednotlivých halách byly co nejnižší.
Předložená nákladová tabulka má N×N polí a její položka na r-tém řádku a v s-tém sloupci představuje dlouhodobé sumární náklady na společný provoz linek r a s v jedné hale. Tabulka je symetrická podle hlavní diagonály, na hlavní diagonále má nuly a všechny její další hodnoty jsou celá kladná čísla.
Vstup
První řádek vstupu obsahuje jediné celé kladné sudé číslo N udávající počet výrobních linek. Na dalších N řádcích je uvedená kompletní nákladová tabulka, každý řádek vstupu obsahuje jeden řádek tabulky, údaje na řádku jsou odděleny jednou nebo více mezerami. Předpokládejte, že všechny hodnoty na vstupu jsou zadány korektně podle výše uvedené specifikace, nemusíte nekontrolovat jejich přípustnost.Výstup
Výstup obsahuje dva řádky. Na prvním je celková cena optimálního párování linek. Na druhém řádku je seznam párů linek v následujícím formátu. Každý pár linek je zapsán jako trojice čísel A B C, kde A a B jsou čísla linek a C jsou náklady na jejich společný provoz v jedné hale. Musí platit A < B. Čísla v trojici jsou oddělena jednou mezerou, trojice jsou uzavřeny v kulatých závorkách a trojice jsou oděleny navzájem jednou mezerou. Dále platí, že hodnota A daného páru je vždy menší než hodnota A páru následujícího za ním ve výpisu. Pokud existuje více možností párování, na výstupu se objeví pouze to, jehož výstupní seznam je lexikograficky nejmenší možný.Příklad 1
Vstup:4 0 6 3 8 6 0 3 9 3 3 0 7 8 9 7 0Výstup:
11 (0 3 8) (1 2 3)
Příklad 2
Vstup:6 0 2 2 2 2 4 2 0 9 2 2 2 2 9 0 2 2 2 2 2 2 0 2 2 2 2 2 2 0 2 4 2 2 2 2 0Výstup:
6 (0 1 2) (2 3 2) (4 5 2)Při této dané tabulce nákladů je více možností, jak linky spárovat. Tyto možnosti jsou všechny uvedeny níže, podle pravidel zadání však vystoupí pouze první z nich.
(0 1 2) (2 3 2) (4 5 2) (0 1 2) (2 4 2) (3 5 2) (0 1 2) (2 5 2) (3 4 2) (0 2 2) (1 3 2) (4 5 2) (0 2 2) (1 4 2) (3 5 2) (0 2 2) (1 5 2) (3 4 2) (0 3 2) (1 4 2) (2 5 2) (0 3 2) (1 5 2) (2 4 2) (0 4 2) (1 3 2) (2 5 2) (0 4 2) (1 5 2) (2 3 2)
Příklad 3
Vstup:6 0 1 2 3 4 5 1 0 6 7 8 9 2 6 0 10 11 12 3 7 10 0 13 14 4 8 11 13 0 15 5 9 12 14 15 0Výstup:
23 (0 3 3) (1 4 8) (2 5 12)
Příklad 4
Vstup:10 0 2 1 2 1 1 2 2 1 2 2 0 2 2 2 2 1 1 2 2 1 2 0 1 2 1 2 2 1 1 2 2 1 0 2 1 1 1 1 1 1 2 2 2 0 1 1 1 2 2 1 2 1 1 1 0 2 2 1 1 2 1 2 1 1 2 0 1 1 2 2 1 2 1 1 2 1 0 1 2 1 2 1 1 2 1 1 1 0 1 2 2 1 1 2 1 2 2 1 0Výstup:
5 (0 2 1) (1 6 1) (3 5 1) (4 7 1) (8 9 1)
Příklad 5
Vstup:14 0 12 19 1 19 16 7 15 1 5 9 22 23 24 12 0 2 18 15 19 5 1 23 24 19 3 21 16 19 2 0 14 25 15 1 2 19 16 2 13 1 21 1 18 14 0 6 21 15 15 9 23 2 7 10 6 19 15 25 6 0 25 2 7 4 6 13 25 22 15 16 19 15 21 25 0 21 11 9 11 3 3 1 12 7 5 1 15 2 21 0 8 20 21 1 2 5 2 15 1 2 15 7 11 8 0 14 16 19 20 3 20 1 23 19 9 4 9 20 14 0 22 8 23 6 7 5 24 16 23 6 11 21 16 22 0 3 2 11 9 9 19 2 2 13 3 1 19 8 3 0 19 12 12 22 3 13 7 25 3 2 20 23 2 19 0 9 17 23 21 1 10 22 1 5 3 6 11 12 9 0 22 24 16 21 6 15 12 2 20 7 9 12 17 22 0Výstup:
13 (0 3 1) (1 7 1) (2 10 2) (4 8 4) (5 12 1) (6 13 2) (9 11 2)