Afişează mesaje
Pagini: 1 ... 6 7 [8]
176  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 671 Joc7 : Mai 04, 2008, 12:38:09
trebuie sortate datele de intrare? Think
177  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int : Mai 03, 2008, 12:16:06
Citat
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:

Citat
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
Citat
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
179  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int : Mai 03, 2008, 11:00:02
gata, am scos 100.  Yahoo! mishu, poti incerca si ideea mea de mai sus... scoti timpi faini, 70 ms cel mai mare Very Happy suuces! Ok
180  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 294 Zeap : Mai 02, 2008, 23:22:39
Citat
Fisierul de intare va contine maxim 300 000 linii

o mica gresala Tongue
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  Thumb up
182  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int : Mai 02, 2008, 16:16:21
deci vrei sa spui ca trebuie sa aflu nr maxim de intervale disjuncte, si nu intervalele disjuncte cu numarul maxim de elemente Huh
183  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 279 Int : Mai 02, 2008, 15:48:40
Citat
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:

Citat
-11 -7
0 30

poate nu am inteles eu bine problema...va rog o explicatie mai detaliata
184  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 126 Lungimi de interval : Aprilie 25, 2008, 11:28:22
am reusit pana la urma sa o rezolv.. merci mult Ok
185  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 126 Lungimi de interval : Aprilie 25, 2008, 00:14:32
da, aia am inteles, dar daka eu mai pun un test...pica...o sa imi citesca n=-700000 ceva pe acolo...si din aia nu eram lamurit Smile
186  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 126 Lungimi de interval : Aprilie 24, 2008, 23:36:02
am observat ca in exemplul tau, mi-ai dat 546 de intervale... acuma ce sa inteleg: ca trebuie eleminate doua intervale de acolo, sau n=544  Cry lamureste-ma plz
187  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 126 Lungimi de interval : Aprilie 24, 2008, 17:40:20
tot timpul asta mi se intampla...cand nu imi iasa o problema cer teste Whistle asa ca indraznesc la bunovointa voasta pt un test mai mare.. Very Happy

P.S.: pt testele mici imi iasa sad
188  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 359 Vecini : Aprilie 23, 2008, 17:52:25
imi dati un exemplu pt N mai mare sa vad cum de imi cade exeplu? Very Happy merci anticipat
189  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 543 Dk : Aprilie 13, 2008, 21:28:40
dar zice ca n<=400.000 ...deci nu cred ca ar fi o problema in a genera ciurul...
190  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 543 Dk : Aprilie 13, 2008, 20:55:10
si daca aplic ciurul lui eratostene, si dupa citesc fiecare element, verific daca e prim, si daka e, incrementez ceva...daka ati putea sa imi dati un contra exemplu... peacefingers
191  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Aprilie 06, 2008, 17:30:00
defapt nu, daca k este mai mare decat numarul de ecuatii formate, afiseaza -1...chiar nu stiu unde gresesc la implementare din moment ce mie imi intra pe toate testele...
P.S: am pus si conditia aia, dar tot 0 iau...  Fighting
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...  sad 
193  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Aprilie 06, 2008, 15:26:58
da Brick wall
194  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Aprilie 06, 2008, 12:11:02
imi poate spune si mie care ar fi cauza din care iau 0 puncte, cu totul ca mie imi merge programul pe toate testele, inclusiv alea pe care mi le-a postat bogdan... nu stiu ce sa mai fac... daka vrea unu cu 100 de pct pe prob asta sa ma ajute, ii explic ce am facut la id de mes: gabor_oliviu1991 ...merci anticipat
195  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Martie 30, 2008, 19:28:54
exact...si zimi si mie...ai folosit sortare?
196  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Martie 30, 2008, 19:00:23
si cam cum arata conditia aia??? Think
197  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Martie 26, 2008, 17:49:05
sigur sunt bune toate exemplele? si la ecuatia 8x^2+35x+12=0 , nu pentru fiecare divizor a lui 8 sunt doua posibilitati de scriere???...mai sunt si alte conditii de care eu nu m-am prins?
198  Comunitate - feedback, proiecte si distractie / Off topic / Răspuns: Probleme cu site-ul : Martie 22, 2008, 21:43:56
de ce nu merge compilatorul??? Angry Angry Angry
199  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Martie 22, 2008, 15:24:49
rog pe cineva sa verifice testele la problema aceasta. Brick wall..si daca a facut-o cineva sa posteze o ecuatie de gr.2 si raspunsul Cry...merci anticipat peacefingers


[Edit] : merci Bogdan;)
200  infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 609 Ecuatie : Ianuarie 24, 2008, 20:17:30
din cate vad, nimeni nu este interesat sa ne ajute in rezolvarea acestei ecuatii...vorbesc de cei cu punctaj de 100... Mad... si o explicatie la "Killed by signal 8(SIGFPE)." va rog Confused
Pagini: 1 ... 6 7 [8]
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines