|
Titlul: 11-12 Subiecte Scris de: Bindea Calin din Martie 14, 2005, 18:00:26 Citat 1 - Domino Se considera n dominouri din care se pot construi siruri respectand urmatoarele reguli : - Prima piesa face obligatoriu parte din sir - Urmatoarele piese se iau in ordinea data (se decide dc o piesa se va pune sau nu in sir) - Fiecare piesa se pune la un capat al sirului deja format in pozitia in care a fost data sau invartita cu 180, sau se arunca si nu se mai revine la ea - O piesa poate fi pusa la un capat al sirului daca numarul de pe dominoul din capat (pe jum nealipita deja) si numarul de pe dominoul care se alipeste la pasul curent sunt egale. Determinati cel mai lung sir de dominouri. Domino.in : n si pe urm n linii xi, yi - fetele unui domino Domino.out : lungimea Restrictii : 1 <= n <= 100.000 0 <= x,y <= 9 ex: Domino.in 6 1 2 1 5 2 3 1 4 2 3 4 3 Domino.out 5 Titlul: 11-12 Subiecte Scris de: Bindea Calin din Martie 14, 2005, 18:09:17 Citat 2 - luna Firmele de pe pamant doresc construirea unor cladiri de forma dreptunghiulara pe luna. Evident fiecare firma va putea construi doar pe teritoriul alocat ei. Pe prima linie a fisierului de intrare luna.in se da n, m : dimensiunile suprafetei lunii (care e o matrice cu elemente naturale maxim 100, de dimensiuni maxim 50 x 50 ) Pe urmatoarele linii e descrisa matricea Apoi pe urm linie se da k <= 100.000 (nr de cereri) Pe urmatoarele k linii sunt 3 numere reprezentand numarul de ordine al tarii si dimensiunile l x c a cladirii drept. pe care vrea sa o construiasca firma. Pe fiecare linie din fisierul de iesire luna.out(corespunzatoare unei cereri) se va scrie Cererea poate fi satisfacuta! - dc tara poate construi cladirea Cererea nu poate fi satisfacuta! - dc tara nu poate construi Tara de provenienta nu exista! - dc tara nu are pe luna proprietate ex : luna.in 5 10 1 1 1 2 2 2 2 3 3 4 1 1 1 2 2 2 2 3 3 4 5 5 5 2 2 2 2 7 7 4 5 5 5 6 6 6 6 7 7 4 5 5 5 6 6 6 6 7 7 4 6 1 2 3 2 3 4 1 3 2 7 20 20 8 44 luna.out Cererea poate fi satisfacuta! Cererea poate fi satisfacuta! Cererea nu poate fi satisfacuta! Cererea poate fi satisfacuta! Cererea nu poate fi satisfacuta! Tara de provenienta nu exista! Eu am facut 99 din 200 in total.. Busind ](*,) implementarile ... si am fost al 2-lea.. Titlul: 11-12 Subiecte Scris de: Ionel Corneliu Gog din Martie 14, 2005, 19:09:23 Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic.. :-({|=
Titlul: 11-12 Subiecte Scris de: Tiberiu-Lucian Florea din Martie 14, 2005, 19:16:56 Mda.... si ce ai reusit sa busesti? :mrgreen:
Titlul: 11-12 Subiecte Scris de: Bindea Calin din Martie 14, 2005, 19:31:48 Pai nush sigur.. cred ca recurenta la prima.. :-'
Si la a 2-a la precomputare.. :oops: Titlul: 11-12 Subiecte Scris de: P3riutz@ din Martie 15, 2005, 14:42:40 Pt ParrAzitU.
Ce ai facut la concurs? Cum ti so parut baia mare? Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 15:49:31 Citat din mesajul lui: DeadStar Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic.. :-({|= ...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele... Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000 Titlul: 11-12 Subiecte Scris de: cristi8 din Martie 15, 2005, 17:02:25 Citat din mesajul lui: SleepyOverlord Citat din mesajul lui: DeadStar Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic.. :-({|= ...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele... Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000 ...pai nu intra usor "pd clasic" cu n<=100000 si Xi,Yi <=9 ? ..poate am inteles eu gresit problema... dar pare O(n) ... cu o constanta destul d mare, dar ar trebui sa intre "lejer" in timp.. Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 17:21:28 Citat din mesajul lui: Fr3eM4n Citat din mesajul lui: SleepyOverlord Citat din mesajul lui: DeadStar Pfuai.. ce probleme usoare.... prima ii si in cartea lui Mihai Oltean. pd clasic.. :-({|= ...Totusi nu s-a luat nici un punctaj maxim, la nici una din ele... Pe de alta parte, tratare superficiala rulez, gl hf la pd clasica pt n<=100000 ...pai nu intra usor "pd clasic" cu n<=100000 si Xi,Yi <=9 ? ..poate am inteles eu gresit problema... dar pare O(n) ... cu o constanta destul d mare, dar ar trebui sa intre "lejer" in timp.. Prin "pd clasic" eu am inteles O(n^2)... Titlul: 11-12 Subiecte Scris de: Bindea Calin din Martie 15, 2005, 17:38:11 Complexitatea oficiala la Domino era O(n).. bine O(40*n)
se parcurgeau domniourile, luand a[j] = best, pt prima piesa cu fata libera i si ultima piesa cu fata libera j.. Titlul: 11-12 Subiecte Scris de: cristi8 din Martie 15, 2005, 18:08:27 hmmm.. stau si ma gandesc... nu merge O(n) curat ? fara constante mari.. si doar cu un vector a[10] .. care se tot inbunatateste la fiecare pas.. (se parcurg dominourile de la sfarsit la inceput)
..intelegeti ce vreau sa spun ? Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 18:31:48 Citat din mesajul lui: Fr3eM4n hmmm.. stau si ma gandesc... nu merge O(n) curat ? fara constante mari.. si doar cu un vector a[10] .. care se tot inbunatateste la fiecare pas.. (se parcurg dominourile de la sfarsit la inceput) ..intelegeti ce vreau sa spun ? Poti pune la ambele capete asa ca ai nevoie de matrice Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 18:32:28 Citat din mesajul lui: ParrAzitU Complexitatea oficiala la Domino era O(n).. bine O(40*n) se parcurgeau domniourile, luand a[j] = best, pt prima piesa cu fata libera i si ultima piesa cu fata libera j.. Am uitat sa zic, eu sunt autorul, banuiesc cu tine am vb pe coridor :D Titlul: 11-12 Subiecte Scris de: Mircea Pasoi din Martie 15, 2005, 19:38:36 Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred. :-s
Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 19:41:08 Citat din mesajul lui: domino Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred. :-s Runda 10, cu limite mult mai mici. Titlul: 11-12 Subiecte Scris de: Mircea Pasoi din Martie 15, 2005, 20:50:42 Citat din mesajul lui: SleepyOverlord Citat din mesajul lui: domino Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred. :-s Runda 10, cu limite mult mai mici. Da, dar problema era cam aceeasi ca la GInfo n-au pus limita pt K deci trebuia sa faci cat mai bine... Titlul: 11-12 Subiecte Scris de: Cosmin Negruseri din Martie 15, 2005, 21:33:41 Mi-a zis sleepy acuma ca sursa oficiala mergea in O(n^2*m^2+k) , e nasol ca nu s-a luat maxim ... prima mea idee era de O(n^2*m + k) si e destul de banala ... O sa fie naspa pt ardeleni la ONI.
Titlul: 11-12 Subiecte Scris de: Patcas Csaba din Martie 15, 2005, 23:36:25 Citat din mesajul lui: domino Citat din mesajul lui: SleepyOverlord Citat din mesajul lui: domino Au fost usoare problemele, ma mir ca nu s-a luat maxim.. Apropo, a doua a fost si la GInfo runda 8 parca.. si asta inainte de concurs cred. :-s Runda 10, cu limite mult mai mici. Da, dar problema era cam aceeasi ca la GInfo n-au pus limita pt K deci trebuia sa faci cat mai bine... Banuiesc, ca ai vazut testele de la Ginfo... intra shi cu n^2*m^2 pt fiecare query... Titlul: 11-12 Subiecte Scris de: Kelemen Stelian din Martie 21, 2005, 15:22:07 hhyhyhy acuma dupa ce ati vazut textele , toti spune-ti ca a fost tare usor , ca a fost un fleac, da lasati-o mai moale, ca "dupa razboi multi viteji se arata " si " poate mor de gripa "
" everything that has a begining has an end " Titlul: 11-12 Subiecte Scris de: cristi8 din Martie 21, 2005, 15:32:30 Citat din mesajul lui: Matrix hhyhyhy acuma dupa ce ati vazut textele , toti spune-ti ca a fost tare usor , ca a fost un fleac, da lasati-o mai moale, ca "dupa razboi multi viteji se arata " si " poate mor de gripa " " everything that has a begining has an end " n-am citit prea atent postul, dar pare amuzant :lol: :lol: Titlul: 11-12 Subiecte Scris de: Cosmin Negruseri din Martie 21, 2005, 15:35:25 Stai linistit .. pt cineva care vrea premiu la nationala chiar au fost lejere, mai ales ca ai avut posibilitatea sa vezi o problema similara la ginfo si alta similara intr-o carte clasica.
|