Outline · [ Standard ] · Linear+ Okruzno Takmicenje Iz Informatike 2010, i kvalifikacije za isto

[username]

jel radi ovde neko one zadatke sa z-treninga? ja sam manje-vise uradio sve (mada cu za jedan jos da popravim kod), nisu teski


inace, za neupucene, da biste se kvalifikovali na takmicenje iz informatike treba da osvojite "pozitivan broj poena" na bilo kom krugu kvalifikacionih takmicenja na sajtu http://www.z-trening.com. prvi krug ce trajati jos sutra, ali ce posle biti jos jedan

[Andrei]

Zadaci su ove godine teži nego prošle (prošle su bili smešni), možda su i teži od zadataka na prošlogodišnjem okružnom, mada nisu toliki problem da se reše.
Ne znam samo kakvi će biti test primeri, jer čitav prvi može da mi propadne ukoliko budu bili nezgodni. Sa sigurnošću mogu da kažem da sam uradio treći i peti tako da zadovoljavaju vremenska ograničenja u svim slučajevima.
Videću da li ću da napišem kod za ostale, jer rešenja koja mi padaju na pamet su dosta dugačka.

I, da, ove godine imam nameru da se takmičim sa vama.

[username]

onaj sortsre ce sigurno da mi predje sve vremenske limite koliko god da ga ja doradjujem i menjam. sto se tice ovih ostalih testirao sam ih za najvece moguce test primere i brzo se izvrsavaju, mada ne mogu da budem 100% siguran da li se izvrsavaju za 0.1 ili 0.2 ili vise sekundi

mada cu sigurno imati dovoljno za prolaz na gradsko

This post has been edited by username: Jan 24 2010, 08:41 PM

[pyost]

Sortsre i paldrm su takvi da ce proci vremenski cak i ako uradite prvo sto vam padne na pamet... Umetanje se isto jako brzo izvrsava, ako shvatite sta treba da se radi. K-torke nikako ne smeju bruteforce, jer nema sanse da prodje, a sumecif ne bi trebalo brute-om

[username]

kad malo razmislim ja sam sve isao sa brute-force osim k_torki. sumecif mi je samo malo prilagodjen brute, ali se brzo izvrsava

jel zna neko kako da izmerim vreme izvrsavanja programa?

This post has been edited by username: Jan 24 2010, 09:06 PM

[pyost]

Neka praksa koja se koristi na takmicenjima jeste da program za jednu sekundu moze da izvrsi 10 miliona operacija, pa racunaj koliko tvoj program izvrsava u najgorem slucaju... E sad, mislim da moze da se racuna i na vise od toga, posebno na z-treningu.

[username]

neko je na njihovom forumu rekao 80 miliona poredjenja/dodela

mada znam da postoji neka funkcija u C-u i delphi-ju koja uzima stanje CPU takta ili tako nesto, pa moze da se iskoristi za precizno merenje vremena, ali ne mogu nista da nadjem za pascal

[pyost]

Eto... Vise nego dovoljno

[username]

u pravu, sigurno jeste

[Andrei]

Izašli rezultati.

Pošto me je mrzelo da uradim sve zadatke, poslao sam ih samo tri. Rezultat - 235 poena, 75. mesto. Mislim da je to dovoljno za plasman i pristojno za moje prvo takmičenje na Z-Training-u i prvo takmičenje za srednje škole.

Zna li neko gde su "optimalna" rešenja zadataka, odnosno rešenja autora?

Vidimo se na okružnom.

This post has been edited by Andrei: Jan 26 2010, 03:31 PM

[pyost]

Nije ovde bilo puno mesta za optimizaciju: k_torke jednostavna formula sa jednim prolazom kroz niz, sortsre obican quicksort, umetanje bruteforce, paldrm isto tako, a sumecif dinamickim.

[username]

kakvo bre dinamicko za sumecif??? o.O

ja sam okruglo 40. mesto sa okruglo 400 poena

@andrei za plasman je dovoljan pozitivan broj poena => ne brini, prosao si

This post has been edited by username: Jan 26 2010, 08:42 PM

[pyost]

Za sumecif prolazi i brute, ali moze i lepse...

Ja sam uspeo da redefinisem pojam fail U sortsre imam 15 umesto 100 zato sto sam u funkciji za poredjenje dva stringa umesto while-a stavio if

[username]

sortsre mi je stalno nesto bagovao sa quicksortom (ili ne radi kad se string sastoji iz jednog slova ili hvata infinite loop) pa sam ga najprostije napisao sa sortom slozenosti n^2

a 1. sam koristio nesto sto bas i nije najtacnije, iako sam znao tacnu formulu za ono sto se trazilo (mada se onda sporo izvrsavao)

[Turgon]

Kakve bre formule, prvi ne zahteva skoro nikakvo razmisljanje ili znanje teorije...

[SBS]

Reče čovek koji zna svu teoriju i sva razmišljanja

[Turgon]

Kurva o postenju

[maxydelanoche]

Prvi se sortira i onda se redom ubacuje sledeci u k-torku i oduzima prvi iz trenutne k-torke... al' ako je tebi, turgon, to bila prva pomisao bez po muke... ne mroas da se duvakas, znamo da si pametan

Meni sortsre imam valjda 10 bodova, za ostale mi vraca neki segmentation fault, boga pitaj zasto. Sama sam kucala kvik sort, pa ko zna sta je... Ostalo mi je ok. Sumecif ne mora preko dinamickog, moze preko jednog prolaza od A do B, ali prilagodjeno. Naravno, tako se izvrsava znatno duze. Poenta tog lakseg nacina je da izracunas sumu cifara za A, a onda u for-u do B dodajes plus jedan na trenutnu sumu, osim ako je broj deljiv sa 10, a nije sa 100, tada oduzimas osam, ako je deljiv sa 100, a nije sa 1000, oduzimas ne secam se koliko, al' vidis sam pa uocis patern i isto za sledeci stepen 10-ke, a u preostalim slucajevima ponovo racunas zbir cifara. Posto u vecini slucajeva samo dodajes +1 ili oduzimas neku brojku (i to belezis naravno u nekom int niz[64]), a ne racunas sumu cifara celokupnu za tekuci broj, slozenost je dosta manja i prolazi program. Umetanje se ispituju sve kombinacije, ja sam to radila koristeci bitwise & da virnem u binarni zapis jednog brojaca koji mi je predstavljao trenutnu kombinaciju pluseva. U palindromu sam ja trazila najveci moguci palindrom sa desne strane unesenog stringa i onda na desno dodavala preostale karaktere stringa tako da se napravi palindrom.

Eto to su neke ideje koje mogu da pomognu, a da ih lako razumeju pocetnici poput mene

[username]

ma ti se samo hvalis kako si dobro uradila


btw, i ja sam sumecif radio slicno tako, osim sto nisam primetio to za oduzimanje osmice u svakoj novoj dekadi, pa sam racunao sumu cifara svaki put kad nisam imao ni na sta drugo da se pozovem

This post has been edited by username: Jan 27 2010, 02:30 PM

[RZA]

Ja sam uradila jedan zadatak, imam 100
Nisu mi se ostali radili, nisam ni razmisljala preterano o idejama