8. sada domácich zadaní

Najneskorší termín: 15.5.2013 (štvrtok) o 21:00

Pri tejto sade sú body pridelené len riešeniam, ktoré Palma akceptovala. Namiesto skúšania všetkých úloh odporúčame zvoliť stratégiu dotiahnutia riešenia celej úlohy.

Vzhľadom na to, že sa pri 7. sade objavilo odovzdanie cudzieho kódu, si pri 8. sade vyhradzujeme právo podmieniť získanie bodov "obhajobou" riešenia.

Odovzdávanie úloh:

  1. zaregistrujte sa na stránke http://palma.strom.sk/?sub=13&type=personal pričom uveďte svoje skutočné meno a priezvisko,
  2. pozrite si poznámky k odovzdávaniu úloh v Jave:
  3. vyriešte niektoré zo zadaných úloh do stanovenému termínu,
  4. e-mailom oznámte Ferovi Galčíkovi svoj login (=prihlasovacie meno) a to, ktoré úlohy ste úspešne vyriešili - vďaka týmto údajom v Palme overíme, či úlohy boli skutočne vyriešené a zapíšeme body do Moodle.

Poznámky:

  • E-mailom zašlite len svoj login, NIE HESLO!
  • Rozhodujúci je čas odoslania riešenia cez systém Palma, nie odoslanie notifikačného e-mailu cvičiacim - tento e-mail môžete pokojne poslať aj po termíne.

Úlohy na riešenie

  • Jednosmerky (6 bodov): https://palma.strom.sk/SVK2013/A/
    • grafové algoritmy pre neohodnotené orientované grafy (najkompaktnejší kód ale dáva jednoduchá úprava jedného z algoritmov pre ohodnotené grafy).
  • Nuly (5 bodov): https://palma.strom.sk/SVK2014/C/
    • vzhľadom na vstupy backtracking postačuje. Treba si ale dať pozor na to, že len násobiť zadané čísla nie je vhodné. Už vynásobením pár z nich sa rýchlo prekročí rozsah long-u. Pri type double sa stráca presnosť a nie je možné testovať deliteľnosť desiatimi. Riešenie spočíva vo využití algebry (rozklad na prvočísla) a uvedomenie si, kedy je číslo deliteľné 10.
    • pre fajnšmekrov: pre väčšie vstupy je možné použiť dynamické programovanie zovšeobecnením úlohy o vyplatení sumy zadanými platidlami.
  • Kvadrant (4 body): https://palma.strom.sk/SVK2014/Q/
    • treba si uvedomiť, že zápis vlastne kóduje nejaký strom a podiel farby súvisí s hlbokou v strome (stromy ale vytvárať netreba).

Pre fajnšmekrov:

  • Most (12 bodov): https://palma.strom.sk/SVK2014/Most/
    • prehľadávanie stavového priestoru - hľadá sa najkratšia cesta z východiskového stavu do cieľového stavu. Pozor, hrany v grafe modelujúcom stavový priestor sú orientované a ohodnotené.

Testovacie vstupy: Sada8.zip