Afişează mesaje
|
Pagini: 1 ... 6 7 [8]
|
177
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int
|
: Mai 03, 2008, 12:16:06
|
Este o solutie si O (n log n), destul de usor de inteles si de implementat. Consta in a sorta intervalele dupa limita din stanga, iar cele care o au egala, dupa limita din dreapta. Dupa aia se alege pur si simplu primul interval, si trebuie sa vezi care este intervalul cu limita din stanga mai mare decat limita din dreapta a celui ales. Il alegi pe primul care il intalnesti, si tot asa. Asta o sa-ti iasa in timp liniar. N log N vine de la sortare... Spor! daca am inteles eu bine explicatie, pentru exemplul: 6 ---nr de intervale -2 5 1 2 2 3 3 4 4 5 7 10
acesta imi ia intervalul -2 5 si cauta primu interval disjunct, adica 7 10. si afiseaza 2. rapunsul este gresit pt ca trebuie afisat 5, intervalele disjuncte incepand de pe pozitia a 2-a pana la final.
|
|
|
178
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int
|
: Mai 03, 2008, 12:10:36
|
Pai ideea asta e in O(N^2), si am incercat-o si scot 40 de puncte ideea mea de mai sus a survenit niste modificari, fiindca si eu tot 40 de puncte luam. mai ai o conditie inainte sa cauti primul interval disjunct in dreapta. daca intervalul curent este disjunct cu intervalul maximului din v[].daca da atunci v[curent]=max+1, ("max" care e prima valoare maxima din v), iar daca intervalul curent nu e disjunct cu intervalul maximului din v[], atunci cauta la dreapta primul interval disjunt. PS: nu prea le am in a calcula complexitatea algoritmului, dar cu un quicksort scoti timpi de maxim 80 ms
|
|
|
181
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int
|
: Mai 02, 2008, 18:05:38
|
deci ideea mea e in felul urmator: am un vector v[] care la inceput e initializat cu 0. parcurg intervalele de la sfarsit la inceput. si pentru fiecare interval verific toate intervalele din dreapta lui daca sunt disjuncte cu el. cand am ajuns la primu interval disjunct, atribui la v[interval_curent]=v[interval disjunct]+1...iar daka nu exista interval disjuct cu el atunci v[interval_curent]=1. si caut maximul din v[] si il afisez... daca ati putea sa imi dati un contra exemplu la aceasta rezolvare
|
|
|
183
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int
|
: Mai 02, 2008, 15:48:40
|
Determinati o submultime de intervale cu numar maxim de elemente, cu proprietatea ca intersectia oricaror 2 intervale din submultime este vida. in exemplul dat, daca ne luam dupa ce spune enuntul problemei, trebuie sa cautam intervalele cu un numar de exemente maxim... deci nu trebuia selectate intervalele: -11 -7 0 30
poate nu am inteles eu bine problema...va rog o explicatie mai detaliata
|
|
|
192
|
infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie
|
: Aprilie 06, 2008, 16:30:54
|
nu prea am inteles ce sa fac, dar oricum...o intrebare...pot sa spun in principiu cum am facut? ...am luat toti divizorii lui a (distincti) dupa formula din articol si am bagat un quicksort. si dupa am generat intr-un vector doua solutii (iarasi cu formulele din articol )...am verificat ca p1*p2==a si ca q1*q2==c...si daka era buna una din solutii o bagam intro matrice, si dupa afisam a k solutie... iau incorect pe testele de la 2 la 8...pe primele doua presupun ca trebe afisat -1... P.S: am verificat ca delta sa fie patrat perfect...
|
|
|
|