Prihlásenie Registrácia  

V - Výber peňazí

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Mladý pár PAĽo a MÁria už vedia, kde postavia dom a preto začali výstavbu. Po poskytnutí stavebných materiálov znalcovi zistili, že geodét im zle určil hranice pozemku a časť základu domu leží mimo ich pozemku. Keď sa o tom dopočul ich sused, tak hneď začal zúriť a chcel peniaze naruku za časť pozemku, na ktorom ležia základy domu. Paľo si spomenul, že pobočky banky majú svoje striktné pravidlá medzi ktoré patrí: zákazník bez ohlásenia aspoň 3 dni dopredu nedostane viac peňazí ako istá čiastka, aj keď nimi disponuje. Aby Paľo vybral potrebné peniaze potrebuje prejsť niekoľko pobočiek.

Úloha

Implementujte program, ktorý nájde najkratšiu cestu od stavby cez pobočky a naspäť tak, aby vybral dostatočnú sumu peňazí.

Vstup

Prvý riadok obsahuje potrebnú sumu peňazí S (1 ≤ S ≤ 1024) a počet miest N (1 ≤ N ≤ 15). Miesto s označením 0 je miesto stavby a ostatné miesta sú pobočky banky.

Nasleduje riadok pozostávajúci z N čísel reprezentujúci nenulové sumy peňazí, ktoré sa dajú vybrať bez oznámenia okrem prvej hodnoty (môže byť aj 0), ktorá reprezentuje peniaze, ktoré majú Paľo a Mária na ruke.

Nasleduje N riadkov po N stĺpcov reprezentujúcich maticu susednosti vzdialenosti miest (v i-tom riadku sa nachádzajú vzdialenosti od i-teho miesta k ostatným).

Výstup

Výstupom programu je riadok s 2 medzerou oddelenými číslami - počet pobočiek, ktoré treba navšťíviť, a vzdialenosť, ktorú treba prejsť autom. Nech vzdialenosť je najmenšia možná. V prípade, ak je takých ciest viac, vyberte tú, v ktorej sa navštívi nejmenej pobočiek.

Príklad

Vstup:

15 4
5 6 8 8
0 2 5 6
2 0 6 4
7 6 0 2
6 4 2 0

Výstup:

2 12

Poznámka: Paľo sa zastaví v pobočkách v poradí 1, 3 a prejde vzdialenosť 12.