6. sada domácich zadaní - Backtracking

Najneskorší termín odovzdania: 15.4.2014 (utorok) o 21:00
Odovzdávané súbory: Vagony.java

Doplňujúce požiadavky:

  • riešenia, ktoré nebude možné skompilovať (t.j. riešenia so syntaktickými chybami) nebudú hodnotené,
  • zdrojový kód správne naformátujte (CTRL+SHIFT+F),
  • komentovaný zdrojový kód

Kto pôjde do práce cez víkend? (4b+3b)

Andrej pracuje ako vedúci oddelenia logistiky (okrem iného zabezpečuje zásobovanie) jednej veľkej spoločnosti. Výroba potrebuje k svojej činnosti rôzne suroviny a chemikálie. Každý deň prichádzajú do areálu spoločnosti aj cisternové vagóny, ktorých obsah je treba prečerpať do zásobníkov. Na to slúžia štyri rovnako výkonné prečerpávacie stanice. Samozrejme počas prečerpávania musí byť na stanici neustále prítomná obsluha. Počas pracovného týždňa je k dispozícii dosť pracovníkov, ktorí môžu zabezpečovať prečerpávanie. Problém nastáva cez víkend. Totiž cisternové vagóny (i keď v menšom počte, ale predsa) prichádzajú aj cez víkend a treba ich prečerpávať. Andrej preto musí do práce počas víkendu povolať na dennú zmenu ľudí, ktorí by obsluhovali prečerpávacie stanice. Zamestnanci nie sú veľmi nadšení, keď musia ísť do práce aj cez víkend. Andrej ako dobrý šéf im chce čo najviac vyjsť v ústrety. A tak každý piatok večer rieši dlhé hodiny problém, koľko ľudí potrebuje v práci v sobotu a nedeľu, aby všetky vagóny, ktoré prídu, boli prečerpané počas ich dennej pracovnej zmeny.

Ako to vlastne u Andreja v piatok večer vyzerá? Informačný systém mu pre každý deň (sobotu aj nedeľu) dopredu vytvorí výpis cisternových vagónov, ktoré je potrebné v daný deň prečerpať. Na základe obsahu a objemu vie Andrej určiť, aký čas je potrebný na prečerpanie daného cisternového vagóna v čerpacej stanici (vrátane času na posunovanie vagónov do prečerpávacej stanice). Andrej tak ku každému vagónu priradí čas potrebný na jeho "vybavenie". No a potom kombinuje a kombinuje. Snaží sa nájsť také zaradenie vagónov do jednotlivých prečerpávacích staníc, aby bolo do zmeny potrebné zavolať čo najmenej pracovníkov obsluhy. Jeho deti (jeden z nich študent prvého ročníka na PF UPJŠ) sa už na to nemôžu pozerať. Veď máme predsa počítače, ktoré nám môžu pomôcť. Rozhodli sa preto vytvoriť program, ktorý by na základe Andrejových časov na prečerpanie jednotlivých vagónov vypočítal, aký minimálny počet pracovníkov obsluhujúcich prečerpávacie stanice treba zavolať do práce.

Vstup: Textový súbor vagony.txt obsahuje údaje o jednotlivých vagónoch, ktoré v daný deň treba prečerpať. V každom riadku je medzerou oddelený kód vagónu (jedno slovo) a čas v minútach potrebný na jeho prečerpanie.

Príklad: 

CL-1230-BA 120
H2SO4-KE-1 240
H2SO4-KE-2 140
BENZIN-95-1 300
H2SO4-KE-3 200
BENZIN-95-2 300
[$[Get Code]]

Výstup: Program vytvorí súbor zmena.txt, ktorý

  • v prvom riadku obsahuje číslo k - minimálny počet prečerpávacích staníc, ktoré je treba v daný deň spustiť do prevádzky (=počet potrebných tímov obsluhy čerpacích staníc), aby sa všetky vagóny prečerpali počas pracovnej zmeny, ktorá trvá 450 minút,
  • v druhom riadku obsahuje minimálny čas potrebný na prečerpanie všetkých vagónov pri použití k prečerpávacích staníc (=počet minút od začiatku zmeny, kedy skončí prečerpanie posledného vagóna),
  • v ďalších k riadkoch sa v každom riadku nachádza medzerami oddelený zoznam vagónov, ktoré majú byť zaradené do rovnakej prečerpávacej stanice.

Príklad výstupu: 

3
440
CL-1230-BA BENZIN-95-1
H2SO4-KE-1 H2SO4-KE-3
H2SO4-KE-2 BENZIN-95-2
[$[Get Code]]

Môžete predpokladať, že všetky vagóny je možné prečerpať počas jednej zmeny v prípade použitia všetkých štyroch prečerpávacích staníc.

Hodnotenie:

  • za korektné riešenie sú 4 body
  • ďalšie 3 body môže udeliť opravujúci podľa efektívnosti implementácie