UPJŠ ŠVK 2008: Programátorská súťaž

Moderátor: FeroG

<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Apr 10, 2008 7:01 pm

UPJŠ ŠVK 2008: Programátorská súťaž

Keďže sa už asi o ŠVK všelikde veľa hovorilo, pridávam doplňujúce informácie pre tých, ktorí sa súťaže rozhodnú zúčastniť.

Do súťaže sa treba prihlásiť, viac informácií nájdete tu: http://www.ics.upjs.sk/~krajci/skola/ine/SVK/SVK.html

V princípe treba doc. Stanovi Krajčimu zaslať e-mailom meno, priezvisko, ročník a správu, že sa chcete zúčastniť programátorskej súťaže organizovanej počas ŠVK. Na stránke uvedený termín je dobré dodržať (výnimočne sa dá prihlásiť aj neskôr). Úlohy z minulých rokov nájdete v systéme Palma - takže, ak máte chuť, môžete aj trénovať.

Extra bonusy (prémiové body k cvičeniam):
    3 body za účasť
    7 bodov za každú vyriešenú úlohu

Pripomínam, že v prípade vyriešenia aspoň 2 úloh máte "uznanú" praktickú časť skúšky z PAZ1b.
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Štv Apr 24, 2008 8:22 pm

Na uvod sa chcem podakovat vsetkym, ktori sa zucastnili programatorskej sutaze SVK. Verim, ze to bola pre Vas zaujimava a poucna skusenost.

Zial, nie vsetkym sa podarilo vyriesit 2 ulohy potrebne na akceptovanie praktickej casti skusky z PAZ1b. Z vysledkov vsak netreba byt sklamany. Je to len programatorska sutaz, kde neraz klucovym faktorom uspechu su bohate skusenosti z riesenia uloh podobneho typu. A istotne pre vacsinu z vas to bola prva skusenost s programatorskou sutazou. Tiez treba povedat, ze realny zivot programatora s riesenim takychto uloh v "casovej tiesni" nema vela spolocneho (i ked ludia zdatni v rieseni tychto uloh hravo zvladaju aj "realne" programovanie ...).

Vzhladom na iste posutazne reakcie, mozno by bolo zaujimave na tomto fore (ci niektorom cviceni) prediskutovat mozne riesenia uloh: pochvalit sa so svojimi rieseniami, zistit preco odoslane riesenia nepresli, ake idey islo pouzit na tu-ktoru ulohu ...
<<

johny

Príspevky: 132

Registrovaný: Pia Feb 22, 2008 6:37 pm

Bydlisko: Košice

Poslať Štv Apr 24, 2008 8:38 pm

(Niektoré) vzorové riešenia:
C - Zbierka: http://mo.mff.cuni.cz/p/57/reseni-3b.html
D - Obojsmerný text: http://www.ioinformatics.org/locations/ ... andout.txt
E - Pluky: http://www.ksp.sk/mop/archiv/2005/sl-2005-1-vzo.pdf

D - popis približne môjho riešenia (trochu iné ako na vyššie uvedenom linku, ale tiež dynamické programovanie):
Išlo o dynamické programovanie. Teda označme si "vstup" reťazec zo vstupu a nech X[a][b] je minimálny počet znakov, ktoré musíme doplniť do podreťazca vstupu začínajúceho na vstup[a] a končiacom na vstup[b], aby z neho vznikol palindróm. Zjavne nás zaujíma X[0][vstup.length-1]. Potrebujeme "kúzelný vzorec", ako spočítať X[a][b], keď poznáme X[a][b] pre všetky menšie podreťazce. A to takto:

  1. ak b-a <= 1 (jeden znak alebo nič), tak už máme palindróm, takže X[a][b] = 0
  2. ak vstup[a] == vstup[b] (na začiatku aj na konci je ten istý znak), tak tieto dva znaky už sú "v poriadku" a potrebujeme získať palindróm medzi nimi. Teda X[a][b] = X[a+1][b-1]
  3. inak: Potrebujeme, aby na začiatku aj na konci bol ten istý znak. To môžeme dosiahnuť tak, že
    1. pridáme nejaký rovnaký znak na začiatok aj na koniec, čiže dokopy pridáme dva znaky.
    2. znak zo začiatku pridáme aj na koniec, teda tieto dva znaky už sú v poriadku a opäť nás zaujíma to, čo je medzi nimi. Teda X[a][b] = 1 + X[a+1][b]
    3. analogicky, znak z konca pridáme na začiatok, teda X[a][b] = 1 + X[a][b-1]
    Možnosť a zjavne nebude dobrá, keďže pridávame dva znaky, zatiaľ čo v ostatných len jeden, okrem toho, ďalej by sme hľadali to isté X[a][b] a tak by to šlo donekonečna. Výsledkom teda bude lepšia z možností b a c, teda X[a][b] = min(1 + X[a+1][b], 1 + X[a][b-1])
E-mail/Jabber: jan[zavináč]jergus.eu
<<

Azteq

Príspevky: 147

Registrovaný: Ned Feb 24, 2008 11:02 am

Bydlisko: Prešov

Poslať Pia Apr 25, 2008 8:38 am

a ja som si myslel, ze su to uplne nove vymyslene ulohy...
<<

FeroG

Príspevky: 1290

Registrovaný: Uto Máj 29, 2007 11:25 am

Poslať Pia Apr 25, 2008 8:49 am

Pokial viem, tak ulohy A a B, ktore mal na starosti Jano Katrenic, by mali byt uplne nove.
<<

Azteq

Príspevky: 147

Registrovaný: Ned Feb 24, 2008 11:02 am

Bydlisko: Prešov

Poslať Pia Apr 25, 2008 11:41 am

FeroG píše:Pokial viem, tak ulohy A a B, ktore mal na starosti Jano Katrenic, by mali byt uplne nove.

tak aspon daco:)

ja som sa snazil riesit prvu a druhu ulohu
druhu som vyriesil, aj ked to vyzera ze to trvalo dlho, ale riesenie som mal pomerne skoro...

k vyrieseniu druhej ulohy mi chybalo asi este 5min casu :D
<<

lochness42

Príspevky: 40

Registrovaný: Uto Feb 26, 2008 8:46 pm

Poslať Pia Apr 25, 2008 12:00 pm

Ano prve dve ulohy boli nove, zvysne boli prevzate.
<<

Cavour

Príspevky: 15

Registrovaný: Pon Feb 25, 2008 1:38 pm

Poslať Pia Apr 25, 2008 2:10 pm

SVK

Ja si myslim ze to nebolo az take tazke, tu zbierku som ani neskusal robit ale napr. tie pluky a strelec boli lahke a aj ten obdlznik ktory som nestihol lebo som sa dost zdrzal pri tom retazci ktory mi aj siel pre ten priklad aj pre ine co som si vymyslel, ale asi niekde som mal chybu, lebo celkovo to slo zle. ku obdlzniku mi stacila uz iba jedna podmienka a bolo by to hotove. skoda ze upozornil na cas 2 minuty pred koncom. cas som vobec nevnimal. rano som tu podmienku doplnil a poslal a co cert nechcel, islo to. chcel som urobit 2 ulohy co sa podarilo ale dalo sa v pohode aj viac. Dobra skusenost zo sutaze.

Späť na PAZ1b

Kto je on-line

Užívatelia prezerajúci fórum: Žiadny registrovaný užívateľ nie je prítomný a 2 hostia

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software.
Slovenský preklad.