Zkouška 28.5.2012

Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
janbok
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 21. 5. 2012 22:52
Typ studia: Informatika Bc.

Zkouška 28.5.2012

Příspěvek od janbok »

Zadání:
Začíná volební kampaň a vy, jakožto předseda, musíte objet co nejvíc mítinků, přičemž na každém musíte zůstat po celou jeho dobu a samo sebou na něj musíte dojet včas. Kolik nejvíce mítinků se lze zůčastnit a jaké to jsou? Pokud je řešení více, vypište jen jedno z nich.

Na vstupu dostanete seznam měst, popis silniční sítě a seznam mítinků (detaily viz dále). Máte zaručeno, že mezi každými dvěmi městy vede cesta, ale nemusí být přímá. Hrany jsou neorientované a ohodnocené časem přejezdu.

Omezeni:
počet měst N <= 1000
délka názvu města <= 30
nejdelší cesta mezi dvěmi městy <= 500 minut
počet mítinků P <= 50000
nejdelší doba mítinku <= 3,5 dne
doba kampaně <= 31 dní

Operační paměť pro úlohu: 2,5 MB
Program by měl seběhnout v rozumném čase (můžete počítat s počítačem zvládajícím 10^9 instrukcí za sekundu)
Můžete si ukládat data na HDD. Pro účely úlohy předpokládejte, že je nekonečně velký.

Formát vstupu:
N
dále N řádek s názvem města
M
dále M řádek s cestami ve formátu: město město čas_přejezdu
P
dále P řádek ve formátu: město minuta hodina den měsíc rok

Formát výstupu:
I (délka nejdelší mítinkové "šnůry")
I řádek ve formátu: město minuta hodina den měsíc rok
cestu je přirozeně nutno vypsat chronologicky vzestupně podle času začátku mítinku

Řešení:
Floyd-Warshall a následně dynamika. Paměť stačí s velkou rezervou. Časová složitost je O(N^3 + P^2).

Průběh zkoušky:
Na začatku se vysvětluje zadání. Následně máte 2 hodiny času. Samo sebou se nevyžaduje psát kód, ale popsat algoirtmus.
Po napsání písemky se jdete zapsat na papír o dvou sloupečcích, kde řádky odpovídají půl hodině přibližně od 13 do 17 hodin. Kdo dřív napíše písemku, dřív si vybírá.
Jeden ze sloupců (což předem nevíte, ale IMHO je to jedno, ačkoliv okolo toho někteří nadělají) je pan Holan, druhý pan Töpfer.
Při ústním nejdříve obhajujete své řešení, následně dostanete několik lehkých otázek z přednášek Programování I a II.

A to je vše. Tak hodně štěstí u zkoušky a ať řešení sypete z rukávu!
Odpovědět

Zpět na „PRG031 Programování II“