Filmová mánie
Petr se těší na premiéru dlouho očekávaného filmu. Aby si film co nejvíce užil, chce jej sledovat v kinech co nejvícekrát. Má k dispozici programy všech kin ve městě a také zná časy potřebné pro přesun mezi jednotlivými kiny. Pro zjednodušení převedl všechny časy a datumy jednotlivých představení a přesunů na celočíselné násobky vhodné časové jednotky (může se jednat například o 30 minut nebo 1 hodinu). Rád by sestavil optimální plán návštěv kin podle následujících kritérií:
- Maximalizovat počet shlédnutí filmu.
- Mezi všemi plány optimálními z hlediska první podmínky, upřednostnit plán, který minimalizuje celkový čas potřebný na všechny přesuny mezi kiny.
Obrázek 1. Předpokládejme, že film trvá 2 časové jednotky a že je promítán ve 4 kinech očíslovaných 1, 2, 3 a 4. Doba cestování mezi kinem 1 a 3 nechť je 1 časová jednotka, mezi kinem 2 a 3 nechť je 2 časové jednotky a jinak 3 časové jednotky pro zbývající dvojice kin. Každý řádek na obrázku znázorňuje seznam počátků promítání filmu v kině označeném číslem v kroužku. Například v kině 4 začíná promítání filmu v časech 6, 20, 30, 35, 45, 50 a 56. Optimální plán je vyznačen pomocí růžově vybarvených obdélníčků. Potřebné přesuny mezi kiny jsou reprezentovány červenými úsečkami, přičemž u každé úsečky je uveden počet časových jednotek, které daný přesun vyžaduje. Optimální plán zahrnuje sledování filmu 15-krát a příslušná celková doba cestování je 14 časových jednotek. |
Úloha
Je dána délka filmu, doba potřebná na přesun pro každou dvojici kin a seznam začátků promítání filmu v každém z kin, vše vyjádřeno jako násobky zvolené
časové jednotky.
Úkolem je určit počet shlédnutí filmu a celkový čas strávený při přesunech mezi kiny v případě optimálního plánu.
Vstup
První vstupní řádek obsahuje dvě celá kladná čísla K a D oddělená mezerou. Číslo K je počet kin, číslo D je
délka filmu.
Dalších K řádků vstupu reprezentuje řádky matice M, která udává časy potřebné na přesuny mezi kiny.
Každý řádek matice sestává z K nezáporných celých čísel oddělených mezerou.
Pro všechna 1 ≤ i, j, k ≤ K, prvek Mi,j reprezentuje dobu přesunu mezi kiny
i a j. Platí Mi,i = 0,
Mi,j = Mj,i (symetrie) a
Mi,j ≤ Mi,k + Mk,j (trojúhelníková nerovnost).
Následuje posledních 2×K vstupních řádků reprezentujících seznamy začátků filmu v jednotlivých kinech, počínaje kinem 1 a konče
kinem K.
Seznam pro jedno kino je uložen na dvou po sobě jdoucích řádcích, kde první řádek obsahuje celé kladné číslo L, což je délka
seznamu,
a druhý řádek obsahuje L nezáporných čísel oddělených mezerou a uspořádaných vzestupně.
V tomto případě každé číslo odpovídá začátku jednoho promítání filmu. Pokud S a U jsou dva po sobě jdoucí začátky, potom platí
|S − U| ≥ D (promítaní filmu se v jednom kině nikdy nepřekrývají).
Buď Li délka seznamu začátků promítání filmu v kině i.
Platí K ≤ 700, 1 ≤ D ≤ 6, TL=L1+ ... + LK ≤ 4 × 105.
Výstup
Výstup sestává z jednoho řádku, který obsahuje dvě celočíselné hodnoty C a T oddělené mezerou. C je počet shlédnutí filmu a T je celková doba strávená cestováním mezi kiny, obojí v případě, kdy Petr postupuje podle optimálního plánu návštev kin.
Příklad 1
Vstup3 2 0 3 1 3 0 2 1 2 0 4 1 4 16 22 5 2 7 12 14 21 5 2 10 19 22 24Výstup
7 2
Příklad 2
Vstup4 2 0 3 1 3 3 0 2 3 1 2 0 3 3 3 3 0 8 1 4 16 22 30 40 60 62 8 2 7 12 14 21 40 42 44 5 2 10 19 22 24 7 6 20 30 35 45 50 56Výstup
15 14Data a řešení Příkladu 2 jsou znázorněny na Obrázku 1.
Veřejná data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy
dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.
Veřejná data