Úloha: Účty za užití dálnice

Chystaný systém placení za použití dálnice je v principu velmi jednoduchý. Každý vjezd na dálnici a každý výjezd z dálnice je opatřen kamerou, která neustále sleduje provoz. Každému vjíždějícímu nebo vyjíždějícímu vozidlu kamera přečte jeho SPZ a do centrální databáze odešle informační záznam, který obsahuje identifikaci dálnice, vzdálenost kamery v km od začátku dálnice, hodinu a minutu pořízení záznamu, pořadové číslo dne v roce, v němž byl záznam pořízen, údaj indikující, zda jde o vjezd nebo výjezd vozidla, a nakonec SPZ vozidla. Každá dálnice má svůj tarif. Tarif se skládá ze 24 položek, jednotlivé položky odpovídají postupně denním dobám 00:00 - 00:59, 01:00 - 01:59, atd., až 23:00 - 23:59. Vozidlu, které použije dálnici, je počítána cena za použití dálnice, která je číselně rovna počtu ujetých kilometrů po dálnici vynásobenému tou položkou tarifu, která odpovídá hodině a minutě vjezdu vozidla na dálnici. Položka tarifu je celé číslo představující setiny Kč. Například hodnota 40 znamená, že za 10 km na dálnici zaplatí majitel vozidla 4 Kč. Počet ujetých kilometrů na dálnici je roven absolutní hodnotě rozdílu vzdálenosti od začátku silnice kamer v místě vjezdu a výjezdu vozidla. Kromě tarifu se za každé použití dálnice platí jednorázový paušál, který se uvádí v celých korunách. Paušál stejně jako tarif se pro různé dálnice liší.

Úlohou je pro zadané období roku vypočítat účet pro každé vozidlo, které použilo v tomto období alespoň jednu dálnici.

Vstup

Nejprve je uveden řádek s celým číslem d určujícím počet dálnic, ty jsou identifikovány čísly 1, 2, ..., d.
Dále následuje d řádků, první z nich odpovídá první dálnici, druhý druhé atd. Na řádku je uveden nejprve paušál a za ním všech 24 položek tarifu příslušné dálnice. Údaje na řádku jsou odděleny jednou mezerou.
Dále následuje nespecifikovaný ale nenulový počet řádků, každý z nich odpovídá jednomu záznamu kamery. Formát řádku je
ID KM HH:MM DD Y SPZ
přičemž ID je identifikace dálnice, KM je vzdálenost kamery od začátku dálnice v celých kilometrech, HH:MM je hodina a minuta pořízení záznamu (tento údaj vždy obsahuje všech pět znaků), DD je pořadové číslo dne (z intervalu 1..366) pořízení záznamu, Y představuje znak 'e' znamenající vjezd (entry ) nebo znak 'x' znamenající výjezd (exit ). SPZ je posloupnost alfanumerických znaků o délce nejvýše 10, bez mezer. Záznamy nejsou uvedeny v žádném specifickém pořadí, kalendářním ani časovém ani jiném.
Za seznamem všech záznamů následuje řádek s jedním celým číslem, které představuje manipulační poplatek v korunách za vytvoření účtu.
Za tímto řádkem následuje poslední řádek vstupu, který obsahuje dvě celá čísla oddělená mezerou určující pořadové číslo prvního a posledního dne účtovacího období.

Výstup

Na výstupu jsou účty pro jednotlivá vozidla uvedené v lexikografickém pořadí SPZ. Účet je zapsán na jediném řádku a obsahuje nejprve SPZ vozidla, pak mezeru a pak celkovou cenu včetně všech paušálů, která je tomuto vozidlu za dané období účtována za veškeré registrované jízdy po dálnicích. Cena je vždy zaokrouhlena dolů na celé koruny a uvádí se jako celé číslo bez znaménka. Jízdy, které byly započaty před účtovacím obdobím nebo ukončeny po účtovacím období se do celkového účtu nezapočítávají.
Předpokládáme, že pro provoz vozidla platí zřejmá pravidla: Po vjezdu vozidla na některou dálnici musí v čase následovat jeho výjezd z téže dálnice a mezitím nemůže toto vozidlo vjíždět na jinou dálnici nebo z ní vyjíždět a stejně tak nemůže opakovaně na tutéž dálnici pouze vjíždět. Po výjezdu vozidla z dálnice může následovat pouze jeho vjezd na některou (případně tutéž) dálnici. Pro vozidlo, jehož provoz splňuje tato pravidla a které v daném období na žádnou dálnici nevjelo, se účet negeneruje.
Díky různým okolnostem (nehoda, výpadek kamery, únos UFO apod.) se může stát, že k záznamu o vjetí vozidla na dálnici neexistuje párový záznam registrující jeho vyjetí nebo naopak je k dispozici jen záznam o vyjetí. Pro takové vozidlo se vždy generuje prázdný účet neávisle na tom, zda tento osamocený záznam spadá do sledovaného období. Stejně tak se vždy generuje prázdný účet pro vozidlo, které by vykázalo nějakou jinou nekonzistenci vůči uvedeným pravidlům. Prázdný účet obsahuje nejprve SPZ vozidla a pak za mezerou jediný znak 'P'.
Pokud je seznam vygenerovaných účtů prázdný, vystoupí pouze řetězec [Empty list].

Příklad 1

Vstup:
2
25 2 2 2 2 2 2 5 5 5 5 5 3 3 3 4 5 5 5 3 2 2 2 2 2
5 10 10 10 10 10 10 15 15 15 15 15 15 15 15 15 15 15 15 10 10 10 10 10 10 
1 411 23:11 320 e UO2313
2 14 10:06 330 x CB8022A
2 126 08:54 330 e CB8022A
1 622 01:11 321 x UO2313
1 411 11:44 320 e KTA5548F
35
315 342 
Výstup:
CB8022A 56
KTA5548F P
UO2313 64

Příklad 2

Vstup:
1
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 10:00 365 e AAAAAA
1 100 12:00 365 x AAAAAA
20
1 365
Výstup:
AAAAAA 121

Příklad 3

Vstup:
1
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 20 23:59 199 e BBBB
1 80 01:00 200 x BBBB
1 20 00:00 200 e AAAAAA
1 80 01:00 200 x AAAAAA
1 20 23:59 200 e CCCC
1 120 01:00 201 x CCCC
1 20 00:00 201 e DDDDD
1 80 01:00 201 x DDDDD
10
200 200
Výstup:
AAAAAA 110
CCCC 111

Testovací 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