Imam predosjecaj da je ovaj primjer kriv: ____________________________ Ulaz: 5 Jato:Beograd->Nis Soko:Cuprija->Jagodina Espreso:Nis->Aleksinac Simpleks:Jagodina->Beograd Raketla:Aleksinac->Cuprija
Izlaz: Nis ____________________________
"U prvom redu standardnog ulaza nalazi se broj karata koje je Ðura prikupio posle putovanja (N <= 20000), a nakon toga, posle razmaka, sledi ime Ðurinog rodnog grada. U narednih N redova sledi opis svake od karata. Svaki red je zapisan na sledeci nacin:"
Pa gdje je ime toga grada poslije N???
"Na standardni izlaz u jednom redu ispisati N+1 ime, tako što ce prvo i poslednje ime biti ime Ðurinog rodnog grada. Izmedu svaka dva imena obavezno staviti ,,->''. Ne treba dodavati razmake, niti druge znakove."
Ovo sigurno nije dobro.
Nesto se pobrkalo.
Pretpostavljam da je ovako trebalo ispasti: ____________________ Ulaz: 5 Nis Jato:Beograd->Nis Soko:Cuprija->Jagodina Espreso:Nis->Aleksinac Simpleks:Jagodina->Beograd Raketla:Aleksinac->Cuprija
kako se resava ovaj zadatak ? Ja sam probao da nalazim grad po grad ali izgleda da ja sporo(na nekim primerima daje "pogresno resenje"). Prolazi mi samo prvi test primer.
int main() { int i,j; int N; string grad; string karta[20001]; bool used[20001]; memset(used,false,sizeof used); cin>>N; cin>>grad;
Ja sam radio ovako: Imas 2 niza - niz stringova (gradova) i niz integera (brojevi koji pokazuju koji po redu u nizu stringova je sljedeci grad). Ucitas broj gradova i rodni grad. Ucitas sljedeci red u string i iz njega izvuces 2 grada. Provjeris postoji li koji od ta 2 grada vec u nizu gradova koje si dosad ucitao, ako postoji, u niz integera upisujes di se taj grad nalazi (na kojem mjestu). Kad nadjes glavni grad, njega posebno obiljezis na kojem mjestu u nizu gradova se nalazi nekom posebnom varijablom. Na kraju ispisujes i mices se po gradovima u for petlji i:= 1-n: glavni_grad = pok[glavni_grad];
Upravo tako sam radio i opet je sporo. Prolaze prvih 4 test primera i poslednji . Drugi prekorace vremenski limit. Ako hoce neko da pogleda moj kod i da mi kaze kako da optimiziram? Ili mozda neka bolja ideja. Hvala
Sta je map ili mapa? Ja sam resio zadatak tako sto imam 2 niza stringova:grad1 i grad2, grad1 je polazni grad na karti a grad2 odrediste. uveo sam treci niz u koji sam smestao redom elemente, a redosled sam dobio tako sto kad mi grad2 iz predhodne karte bud jednak gradu1 sa ove karte tada u niz u koji smestam gradove redom dodam grad 2 ove karte. Medjutim, to traje predugo pa mi primeri od 5-9 ne budu izvrseni na vreme.
Pa mapa ti je hash na neki nacin, bar se za to cesto koristi. Ako imas takva pitanja, najbolje ti je da posavetujes google. Google is your friend :) http://www.cprogramming.com/tutorial/stl/stlmap.html http://www.cplusplus.com/reference/stl/map/ http://www.cppreference.com/cppmap/index.html
Aha, pa onda ti mapa ne znaci puno za c++. U c++-u postoji stl biblioteka koja implementira neke standardne strukture/algoritme. Medju njima su recimo sort, permutacije, heap, queue, stack, hash itd. A evo ukratko oko hash-a Recimo da imas stringove baba, dom, kuca, deda, sestra, kisobran, muzika, abrakadabra Ako u ovom nizu trazis kamion (pretpostavimo da nije sortirano) moras proci kroz sve reci, a recimo da podelis reci po broju karaktera u njima (na taj nacin si definisao hash funkciju. onda moze recimo da bude zbir ascii vrednosti svih karaktera po nekom modulu, ili proizvod ili neka mesavina, znaci to je kako odredis da ce biti najbolje) po hash funkciji imaces nizove dom baba, kuca, deda sestra, muzika kisobran abrakadabra
sada kad budes trazio kamion, trazices u nizu gde su sestra i muzika cime ces prilicno ustedeti na vremenu. Eto, to je ukratko o hashovanju.
Zvuci lepo, ali mislim da cu imati manjih problema sa realizacijom istog u paskalu, ali vredi probati. Nesto tako mi je palo na pamet kad sam pisao program ali sam mislio da cu se zapetljati previse.
Kao sto sam i rekao, imao sam problema sa realizacijom toga, prvo sam hteo da ih razvrstam po pocetnom slovu pa sam napravio 2d niz 'A'..'Z',1..20000 medjutim, nisam mogao da napravim da mi pocetno slovo bude char , tj. kad uradim a:=copy(grad,1,1), a bude string[1] cija je vrednost prvo slovo od tog grada, a onda mi treba niz recimo b[a,4] a tu a mora da mi bude char a ne string, pa sam morao da odustanem od te ideje. Onda sam ih razvrstao po broju slova ali ni to nije uspelo jer su, predpostavljam, imena slicnih duzina pa je opet trajalo predugo, jel imas neki savet?
Pa evo shta recimo mozes da radis nevezano za bilo kakvu strukturu: Ucitas ulaz, ali i zapamtis shta si chitao. Sva imena koja si prosao stavis u jedan niz, znaci iz primera niz ce ti imati Beograd, Cuprija, Nis, Jagodina, Aleksinac a potom to sortiras. Ubacujes u niz samo polazna mesta. Kad to uradis, ponovo se vratis kroz ulaz (zato ga pamtis) i radis sledece odredis ta dva grada GradA->GradB binarnim pretrazivanjem nadjes index grada GradA onom sortiranom nizu, tako isto i za GradB postavis vezu graph[idx za GradA] = index za GradB svaki cvor ti ima jednog suseda, pa nema potrebe da pamtis nesto vise. Posle svega nadjes koji ti je pocetni grad - to mozes i binarnim, a mozes i prosto jednim prolazom kroz ceo sortiran niz. To neka ti je index polazniIdx i tada bi trebalo vec da je ocigledno :)
Hvala ti sto se trudis da mi objasnis, ali je to previse za mene, ne kapiram ti pola odgovora. Zanima me samo jedna stvar: Jel mogu da prevedem string[1] u char nekako? Mislim da bi mi to resilo problem.
string[1] ti je char ord(string[1]) ti daje ASCII kod tog karaktera. Ne znam shta ti je previse. To sto sam ti napisao da uradis nije ni malo tesko. Binarno pretrazivanje bi trebao da znas, a i sortiranje. Ostalo je sve samo kuckanje
Nije isto string i char jer mi daje type mismatch kad stavim a:array['A'..'Z'] pa kasnije za neko b:string[1] stavim a[b], dok za c:char i a[c] ne daje type mismatch, ali resio sam to, medjutim opet mi daje prekoraceno vremensko ogranicenje iako sam razvrstao gradove po pocetnim slovima i onda pretrazujem samo u onoj grupi gde je to pocetno slovo. Medjutim to kao da traje duze jer mi daje prekoracenje vremena za svih 10 primera a kad ih nisam razvrstavao 5 primera mi je bilo u odgovarajucem vremenu.
Inace nisam razumeo ni sta su grafovi, a ni ne znam sta je binarno pretrazivanje, takodje ne vidim zasto bih sortirao niz gradova, a ni ne kapiram ideju koju si izneo u tom postu.
Btw, jel se ti takmicis, tj. jel ides jos u srednju skolu ili si na faksu? Odakle si?
E, sad gledam tvoje postove i vidim da spominjes dosta meni nepoznatih termina i nacina resavanja zadataka, kao sto su neka stabla, binarno i dinamicko(nesto, nije ni bitno sta), mape, match, hash(ili kako vec) i sve tako nesto. E sad meni nije cudno sto ja to ne znam jer sam jos nov u ovome, a najtezi zadatak koji smo radili u skoli bio je izracunati neki izraz koji u sebi sadrzi stepen i faktorijel ili naci najmanji od unetih n brojeva i tako to, cak nismo radili ni while i repeat vec samo for, dok sam ostalo morao sam da ucim(teoriju) a za nacine resavanja zadataka sam morao sam da smisljam bez koriscenja tih neki stabala i svega toga sto spominjes. Mene u stvari zanima da li postoji neka knjiga ili tutorijal(o paskalu(iskljucivo)) NA SRPSKOM koji mozes da mi preporucis a da tamo, na jednom mestu mogu naci sve o tome ili se bar vise upoznati sa tim terminima i njihovim nacinom koriscenja tj. njihovom primeno.
Ok. Mozda jos neko bude hteo da skine, pa cu ostaviti jos neko vreme. Nisam siguran bas da li smem da drzim, zato se dvoumim... Nego, kad budes bolje naucio engleski, moj savet ti je da pogledas Introduction To Algorithms ili kako se jos popularno zove CLRS (po imenima autora i mislim da je tako) ili ITA.
ja :) nadam se da znas da tekst na z-treningu nije bas kako treba. Evo ti c/p pravog teksta :)
Mornar Äura je veliki avanturista i nakon zavrÅ¡ene karijere, odluÄio je da krene na put oko sveta. Krenuo je iz svog rodnog mesta, obiÅ¡ao veliki broj gradova i na kraju se vratio kući. PoÅ¡to je Äura Äovek u penziji, poÄeo je da zaboravlja. Želeo je da rekonstruiÅ¡e redosled gradova koje je posećivao, meÄ‘utim, sve Å¡to mu je ostalo su bile autobuske, avionske i karte za brodove kojima se prevozio. Pomozite Äuri da rekonstruiÅ¡e svoje puteÅ¡estvije koje će prepriÄavati unucima.
Na svakoj karti se nalazi ime kompanije koja prevozi, ime polaziÅ¡ta i odrediÅ¡ta. Poznato je da Äura, avanturista u duÅ¡i, nikada ne posećuje isti grad dva puta (ako to nije njegov rodni grad, naravno).
Ulaz:
U prvom redu tekstualne datoteke mornar.in se nalazi broj karata koje je Äura prikupio posle putovanja (N ≤ 20000), a nakon toga, posle razmaka, sledi ime Äurinog rodnog grada. U narednih N redova sledi opis svake od karata. Svaki red je zapisan na sledeći naÄin:
Ime1:Ime2->Ime3
Ime1 je ime kompanije, Ime2 je ime polaznog grada, dok je Ime3 destinacija. Svako ime (ukljuÄujući i ime rodnog grada) se sastoji iskljuÄivo od slova engleskog alfabeta. Prvo slovo imena je veliko, dok su ostala mala. Redosled pojavljivanja karata u ulazu ne mora biti isti kao i redosled kojim je Äura putovao.
Izlaz:
U prvom i jedinom redu izlazne datoteke mornar.out ispisati N+1 ime, tako Å¡to će prvo i poslednje ime biti ime Äurinog rodnog grada. IzmeÄ‘u svaka dva imena obavezno staviti ,,->''. Ne treba dodavati razmake, niti druge znakove.
Znam da u tekstu ima greska, i nije mi problem da dobijem tacno resenje vec sto to ne mogu da uradim za zadato vreme. Probao sam 3-4 nacina i max mi je 5 test primera.
Obrati paznju na ogranicenje za N. Posto moze da ide i do 20000, ne mozes da imas resenje koje radi u N^2 nego u N log N... Hint: quick sort, binarna pretraga.
inace, podelim gradove u nizove sa istim posetnim slovom i (quick)sortiram svaki od njih i radim binarnu pretragu u nizu sa istim pocetnim slovom ali mi pada na vremenu.
n^2 i n log n je slozenost programa, u neku ruku vrlo gruba procena broja iteracija. Recimo, ako ti imas samo jednu for petlju od 1 do n koja radi nesto, slozenost je n, ako imas for i:=1 to n pa unutar nje for j:=1 to n, slozenost je n^2. Verujem da Boba ume sve ovo bolje da objasni :)
Sto se ideje tice, nisam bas sigurna da ti je potrebno ovo deljenje u nizove, cini mi se da je dovoljno samo da sortiras ceo niz, pa po njemu ides binarnom pretragom :)
[quote author=Sanja Popovic link=topic=10198.msg12679#msg12679 date=1206191795] Verujem da Boba ume sve ovo bolje da objasni :) [/q] Hvala ;), ali mislim da si ti sasvim korektno objasnila. Ipak, da ponovim sto si napisala Ako posmatras neke ulazne parametre i broj iteracija koji ti program napravi sa tim ulaznim parametrima, u ovom slucaju ulazni parametar je samo n, onda ti je f(n) = broj_iteracija slozenost algoritma, znaci to ti je f(n), kao sto je Sanja napisala, za QS je u srednjem slucaju n logn, sto znaci da ako je n = 20 000, onda je broj iteracija (kao sto je Sanja napisala :), to je gruba procena) 20 000 * log (20 000). Eto, to je to. Inace, najbolje je ako racunas da 10 000 000 iteracija radi za 1 sekundu, mada naravno da isti broj iteracija tipa INC(a) i a := a / 123.345 nije nikako isti vremensi i to je jedan od razloga zasto je ta procena gruba.
Mislim da imam isti problem kao Vasja., bar po primjerima koji nam prolaze.
Radio sam u principu nako, kao i "unknownhero", ali kad koristim map, onda jasno mi je da mogu naci brzo da li sam taj grad vec unio, ali kako onda odrediti na kojem se broju odnosno poziciju nalazi taj grad.
po principu :
A -> B B -> C D -> A C -> D
uzmimo da je D, rodni grad, njega oznacim sa 0 bit ce pozicije slj.
1 -> 2 2 -> 3 0 -> 1 3 -> 0
Pa ako ja vidim u mapi da li njega vec ima, kako onda da znam koja mu je i pozicija pomocu mape.
Ne prolazi mi NI JEDAN test primer na graderu, iako kuci sve radi kako treba, cak sam testirao na zvanicnim primerima....da li bi neki od admina ili moderatora mogao da mi pogleda kod, jer ocigledno nesto kod unosa ne radim kako treba
Meni prolazi 1 / 10 a siguran sam da mi je tacan kod. Da li moze neko da pogleda ? http://www.z-trening.com/new/www/html/submit.php?submit=7100049589&subm_code=1
