{"id":1982,"date":"2011-07-26T22:50:00","date_gmt":"2011-07-26T22:50:00","guid":{"rendered":"https:\/\/zrstest.zrs.hr\/index.php\/2011\/07\/26\/programerski-osvrt-na-drugo-kolo-ljetne-lige-c-2011-za-kadete\/"},"modified":"2011-07-26T22:50:00","modified_gmt":"2011-07-26T22:50:00","slug":"programerski-osvrt-na-drugo-kolo-ljetne-lige-c-2011-za-kadete","status":"publish","type":"post","link":"https:\/\/zrs.hr\/index.php\/2011\/07\/26\/programerski-osvrt-na-drugo-kolo-ljetne-lige-c-2011-za-kadete\/","title":{"rendered":"Programerski osvrt na drugo kolo Ljetne lige C++ 2011 za kadete"},"content":{"rendered":"

\n\tDanas je završeno 2. kolo ljetne lige C++ za kadete. Zadaci su ovog puta malo poja\u010dani, što mo\u017eemo i pro\u010ditati iz samih rezultata<\/a> :-).<\/p>\n

\n\tPonovno smo naišli na razli\u010dite i zanimljive pristupe, posebice u tre\u0107em zadatku "otoci". \ud83d\ude42
\n\tIsto tako, drago nam je da su nekim natjecateljima svi "pravci" uvijek paralelni :-P, iako nam nije drago da se još uvijek pokušava dijeliti s nulom \ud83d\ude41
\n\tŠto se ti\u010de sortiranja stringova, ono je leksi\u010dko, te duljina niza nije primarni kriterij (zadatak "Max-suma"), tako da bi poravnanje sa prefiksnim nulama bilo od pomo\u0107i, a ne bi bio niti veliki problem uvesti vlastiti kriterij usporedbe…<\/p>\n

\n\tSlijedi nekoliko dobrih praksi i pravila kojih bi se trebali pridr\u017eavati svi natjecatelji pri riješavanju zadataka i predaji rješenja:<\/strong><\/p>\n

\n\t1) Valja pripaziti na imenovanje datoteka, ime datoteke s rješenjem se uvijek nalazi pri samom dnu teksta zadatka.
\n\t2) Preporuka je radi uniformnosti, prije predavanja rješenja zakomentirati ili obrisati svaku pojavu system("pause"); <\/strong>
\n\t3) Ispis valja završiti u novom retku, dakle zadnji znak koji bi trebalo ispisati je endl. <\/strong>Drugim rije\u010dima korisite cout << endl;<\/strong> ili printf("\n");<\/strong>
\n\t4) U svakom zadatku su zadana ograni\u010denja (tipovi podataka i veli\u010dina podataka), te iste uvijek valja uzeti u obzir.
\n\t5) Memorijsko ograni\u010denje je u pravilu 32 MB po zadatku, a vremensko je do 30 sekundi po test primjeru. <\/p>\n

\n\tEvo i nekoliko prijedloga koji se ti\u010du tipova podataka te njihovog unosa i ispisa:<\/strong>
\n\t– Za cijele brojeve koristimo int <\/strong>(%d)
\n\t– Za racionalne brojeve koristiom float <\/strong>(%f), a za racionalne brojeve dvostruke preciznosti double <\/strong>(%lf), koristimo izraz "racionalni", jer realni brojevi ne mogu biti pokriveni budu\u0107i sadr\u017ee i iracionalne brojeve koje u stvarnosti i ne mo\u017eemo to\u010dno zapisati u ra\u010dunalu (ograni\u010deni smo veli\u010dinom registra …), a niti na papiru (izuzev simboli\u010dkih zapisa)
\n\t– za formatirani ispis valja koristiti printf <\/strong>naredbu: npr za racionalni broj zaokru\u017een na 2 decimale pišemo printf("%.2f");
\n\t– <\/strong>kada \u017eelimo napraviti desno poravnanje brojeva (npr. na 10 mjesta) onda pišemo printf("%10f");<\/strong> ili printf("%10d");<\/strong><\/p>\n

\n\tZa semdaše, a pogotovo osmaše, bilo bi dobro da prou\u010de i izvje\u017ebaju odre\u0111ene algoritme, <\/strong>
\n\tposebice su zanimljivi BFS: http:\/\/en.wikipedia.org\/wiki\/Breadth-first_search<\/a> i DFS: http:\/\/en.wikipedia.org\/wiki\/Depth-first_search<\/a><\/p>\n

\n\tOd ostalih, svakako bi trebalo poznavati sljede\u0107e strukture podataka i algoritme:
\n\t– <\/strong>Apsolutno sve što se ti\u010de stringova i charova
\n\t– Stack, Queue, FIFO i LIFO, vezane liste, cirkularne liste, …
\n\t– Longest Common Substring (algoritam za najdulji zajedni\u010dki podniz)
\n\t– Euklidov algoritam najve\u0107e zajedni\u010dke mjere
\n\t– Eratostenovo sito za mapiranje prostih brojeva od 2 – N.
\n\t– Rastav brojeva na proste faktore
\n\t– Binarno pretra\u017eivanje i binarna stabla
\n\t– Formule za sumu i pronalazak \u010dlanova aritmeti\u010dkih i geometrijskih nizova
\n\t– Algoritam za pronalak te\u017eišta poligona
\n\t– Algoritmi za izra\u010dun presjeka, unije i razlike realnih intervala
\n\t– Algoritmi za ra\u010dunanje s velikim brojevima, odnosno zbrajanje, oduzimanje i mno\u017eenje "stringova"
\n\t– Algoritmi za kriptiranje podataka, barem oni najosnovniji – bazirani na XOR-u \ud83d\ude42
\n\t– Dvodimenzionalne matrice su uvijek posebno zanimljive, kretanje \u010dovje\u010duljka i izbjegavanje prepreka je \u010desta pojava \ud83d\ude42
\n\t– C++ strukture pair<\/strong>, vector<\/strong> i map<\/strong> te pripadne metode i iteratore nad tim objektima
\n\t– zatim uporaba funkcija sort<\/strong> i reverse<\/strong> (i ostalo iz <algorithm>), kod sort funkcije svakako obratiti pa\u017enju na mogu\u0107nost uvo\u0111enja vlastite funkcije za usporedbu elemenata (compare function)
\n\t– uvo\u0111enje vlastitih struktura podataka (typedef struct { .. }<\/strong> )
\n\t– kod rekurzivnih rješenja, valja se zapitati da li postoji dinami\u010dki pristup (mapiranje izra\u010duna)
\n\t– kada sve ostalo zaka\u017ee, valja krenuti heuristi\u010dkim putem :-), a kada i to zaka\u017ee, uvijek preostaje brute force i mapiranje rješenja \ud83d\ude42
\n\t…<\/p>\n

\n\t <\/p>\n

\n\tEvaluacija na ovoj Ljetnoj ligi te na IBT-u za mla\u0111e kadete se vrši pomo\u0107nim evaluatorom, koji radi sljede\u0107e zada\u0107e:<\/strong><\/p>\n

\n\t1) Prevodi natjecateljska riješenja sa g++ compiler-om
\n\t2) Poziva natjecateljske izvršne verzije (.exe) sa preusmjerenim ulazom na test primjere, te nakon toga se poziva u istom re\u017eimu slu\u017ebeno rješenje
\n\t3) Test primjeri se izmišljaju ru\u010dno ili sa pomo\u0107nim programom koji ih generira, a tada su oni posve nasumi\u010dni te u granicama zadanim u tekstu zadatka.
\n\t4) Provjera ispravnosti rješenja se radi ru\u010dnim putem: usporedbom natjecateljskih izlaza sa slu\u017ebenim izlazima
\n\t5) Bodovi se mogu dijeliti na na\u010din da se priznaju samo potpuno ispravni izlazi, ili se mogu dijeliti djelomi\u010dni bodovi za djelomi\u010dna rješenja, a to ovisi isklju\u010divo o prirodi samog zadatka. Tako recimo za zadatke koji tra\u017ee 3 izlaza, mo\u017ee se davati po tre\u0107ina ili polovina bodova za djelomi\u010dna rješenja. <\/p>\n

\n\tToliko u ovom osvrtu, puno sre\u0107e na preostalim kolima!<\/p>\n

\n\tAutor zadataka C++<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Danas je završeno 2. kolo ljetne lige C++ za kadete. Zadaci su ovog puta malo poja\u010dani, što mo\u017eemo i pro\u010ditati iz samih rezultata :-). Ponovno smo naišli na razli\u010dite i zanimljive pristupe, posebice u tre\u0107em zadatku "otoci". \ud83d\ude42 Isto tako, drago nam je da su nekim natjecateljima svi "pravci" uvijek paralelni :-P, iako nam nije […]<\/p>\n","protected":false},"author":1,"featured_media":1983,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14,23],"tags":[],"class_list":["post-1982","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-obavijesti","category-ljeto-u-zagrebu"],"_links":{"self":[{"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/posts\/1982","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/comments?post=1982"}],"version-history":[{"count":0,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/posts\/1982\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/media\/1983"}],"wp:attachment":[{"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/media?parent=1982"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/categories?post=1982"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zrs.hr\/index.php\/wp-json\/wp\/v2\/tags?post=1982"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}