Titlul: 467 Orase Scris de: Adrian Diaconu din Iunie 25, 2007, 16:20:41 Aici puteţi discuta despre problema Orase (http://infoarena.ro/problema/orase).
Titlul: Răspuns: 467 Orase Scris de: Gabriel Bitis din Iunie 26, 2007, 14:40:01 Ce complexitate trebuie sa aiba solutia?
Titlul: Răspuns: 467 Orase Scris de: Bondane Cosmin din Iunie 26, 2007, 15:31:14 Eu am reusit sa scot un O(n*logn), pe total, si am luat 100 pcte.
Titlul: Răspuns: 467 Orase Scris de: Ionescu Vlad din Iunie 26, 2007, 22:44:21 in exemplu, strazile sunt:
5 6 2 2 (1) 0 3 2 7 (2) distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile? Titlul: Răspuns: 467 Orase Scris de: Florian Marcu din Iunie 27, 2007, 07:38:28 Pai..dupa cum vezi in explicatie [ in desen ] strazile au fost desenate una in sus si una in jos, asta pentru a simplifica probabil intelegerea. Cred k se pot suprapune, insa calculul distantei va ramane la fel [ dist (i,j)=li+ lj <=>asta doat in cazul suprapunerii]. Sau...mai simplu:considera orice pereche i,j kare s-ar "suprapune" k fiind opuse [ k in desen] si s-a rezolvat tot. :thumbup:
Titlul: Răspuns: 467 Orase Scris de: Ionescu Vlad din Iunie 27, 2007, 12:21:16 pai si daca am:
2 2 2 3 2 4 cum mai consider ca sunt opuse? :-' probabil ca-i asa cum spui, n-am rezolvat inca problema, dar nu prea e logic... Titlul: Răspuns: 467 Orase Scris de: Andrei Purice din Iunie 27, 2007, 12:31:29 Din moment ce nu este precizat modul lor de asezare atunci ramane de datoria ta sa il alegi... si pentru a obtine maximul te duci cu max1 intr-o directie si cu max2 in cealalta ;) . In cazul tau rezultatul va fi 7 :)
Titlul: Răspuns: 467 Orase Scris de: Sima Cotizo din Iunie 27, 2007, 19:32:58 Am facut un program N log N, imi ia 30 cu TLE si un WA... nu asta conteaza... ci faptul ca am facut in main
Cod: return 50; Titlul: Răspuns: 467 Orase Scris de: Bondane Cosmin din Iunie 27, 2007, 19:38:42 N <= 50000. Pentru ca eu mi-am declarat astfel sirurile pe care le-am folosit si a mers fara probleme.
Titlul: Răspuns: 467 Orase Scris de: Sima Cotizo din Iunie 27, 2007, 19:42:09 Tocmai scriam un reply in care sa sustin ca nu e asa, dar am gresit ... :) citeam (n,m) nu (m,n)... Greseala mea, scuze! :oops:
Titlul: Răspuns: 467 Orase Scris de: Sebastian Crisan din Iunie 27, 2007, 21:46:39 [..] distanta dintre orasele de la capatul strazilor (1) si (2), care este? 7+2 = 9, sau 7-2 = 5? Se pot suprapune strazile? Probabil ca atunci cand vrei sa mergi dintr-un oras in altul trebuie sa treci si pe strada principala: dist(i, j)=L[ i]+L[j]+|D[ i]-D[j]|. Titlul: Răspuns: 467 Orase Scris de: Florian Marcu din Iunie 27, 2007, 21:54:46 Cum se face asta in N logN? Care e idea care sta la baza algoritmului..? k nu ma prind :oops: Am o rezolvare N^2 cu care prind numa` 40 de puncte...
Titlul: Răspuns: 467 Orase Scris de: Florin Pogocsan din Iunie 27, 2007, 23:38:10 Pai N*logN vine de la sortare :P , dupa care liniar determini maximul . Mai mult nu zic ca deja e mare spoiler ce am zis :)
Titlul: Răspuns: 467 Orase Scris de: Sebastian Crisan din Iunie 29, 2007, 16:42:52 Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva?
Titlul: Răspuns: 467 Orase Scris de: Cezar Mocan din Iunie 29, 2007, 16:59:09 Pai probabil ca te ajuta daca faci sortare de aia in timp liniar ca sa nu mai trebuiasca sa afli maximu din sir... alta utilizare nu-i vad...
Titlul: Răspuns: 467 Orase Scris de: Andrei Homorodean din Iunie 29, 2007, 20:37:59 In articol e:
Cod: distanta care trebuie parcursa intre doua orase i < j: Li+Di+Lj-Dj cred ca e j < i.. Titlul: Răspuns: 467 Orase Scris de: Mircea Pasoi din Iunie 29, 2007, 21:19:13 Asa e.
Titlul: Răspuns: 467 Orase Scris de: Bozianu Ana din Iulie 05, 2007, 13:55:10 Am rezolvat problema, insa nu m-am folosit nicaieri de M (lungimea strazii principale). Voi ati folosit-o undeva? Eu nu. Doar ca am vazut ca solutia este <=3.000.000 deci intra pe long int. In rest in m-a "ajutat" ca pe altii sa fac citirea in ordine gresita a lui m si n :? Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 10:55:47 Am incercat solutia oficiala, dar iau numai 50 de puncte, restul sunt TLE-uri
ce sortare ar trebui sa folosesc?(cu insertion sort fac acum) http://infoarena.ro/job_detail/329952 cred ca se blocheaza undeva, dif de timp e uriasa! Titlul: Răspuns: 467 Orase Scris de: Emanuel Cinca din Iulie 08, 2009, 11:04:15 Foloseste quicksort. Desi ar trebui sa intre si cu mergesort, ambele avand complexitatea O(nlogn).
Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 11:10:13 nu am invatat quicksort, chiar daca stiu ca e cel mai rapid :'(
oricum, caut pe net Titlul: Răspuns: 467 Orase Scris de: Cezar Mocan din Iulie 08, 2009, 11:27:17 Foloseste sort-ul din STL. Incluzi libraria <algorithm> si apoi scrii sort(sir + 1, sir + N + 1);
Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 11:50:33 adica pentru vectorul a[50000] scriu sort(a+1,a+n+1)?
Titlul: Răspuns: 467 Orase Scris de: Popescu Marius din Iulie 08, 2009, 12:11:29 Da, unde n reprezinta numarul de elemente din vectorul a[50001] . Daca ai elemente in vector de la 1 atunci scri sort(a+1,a+n+1) , iar daca ai de la 0 scri sort(a,a+n);
Uite aici un exemplu , sper sa te ajute : Cod: #include<fstream.h> Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 12:12:24 multumesc mult!! karma plus la toti
Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 12:25:51 Cod: #include<fstream.h> 2.elementele din v1 intra in long dupa ce *100000? Titlul: Răspuns: 467 Orase Scris de: Emanuel Cinca din Iulie 08, 2009, 12:49:40 Cod: #include<algorithm> Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 13:03:36 Cod: #include<fstream.h> http://infoarena.ro/job_detail/330015 am ramas blocat la 50 de puncte! Titlul: Răspuns: 467 Orase Scris de: Emanuel Cinca din Iulie 08, 2009, 13:27:22 Vezi ca ti-am trimis PM! :peacefingers:
Titlul: Răspuns: 467 Orase Scris de: zloteanu adrian nichita din Iulie 08, 2009, 13:35:32 n-am primit nimic inca, dar sunt dispus sa astept :weightlift:
LE: trebuie sa dau click pe "mesaje"(meniul de sus) si apoi "mesaje primite"? nu primesc nimic! Titlul: Răspuns: 467 Orase Scris de: George Popoiu din Noiembrie 21, 2009, 17:58:33 Imi da cineva un hint cum sa calculez maximul Liniar?
Titlul: Răspuns: 467 Orase Scris de: irimias robert din Noiembrie 28, 2009, 11:40:51 probabil asta ar trebui sa te ajute, george http://infoarena.ro/problema/ssm
apropo, imi puteti va rog spune de ce metoda asta nu ia 100 de puncte: Cod: void program() daca nu trebuia sa pun solutia asta rog un admin sa stearga, ms Titlul: Răspuns: 467 Orase Scris de: George Popoiu din Noiembrie 29, 2009, 12:28:46 ceva de genu fac si eu robert, nu cred ca e corect. Cred ca e o chichita...
P.S. : Citisem articolul si rezolvasem inaite sa postez :P Titlul: Răspuns: 467 Orase Scris de: Paval Cristi Onisim din Decembrie 28, 2010, 14:14:09 Am rezolvat problema in O(M) fara nici o sortare :yahoo:
[editat] am modificat mesajul ca sa evitam postatul consecutiv... Titlul: Răspuns: 467 Orase Scris de: UAIC.VlasCatalin din August 22, 2011, 23:25:12 Am trimis numai citirea in pascal si am TLE pe 6 teste, stie cineva ce inseamna asta ca eu deja nu mai inteleg ce se intimpla ](*,)
LE: S-a rezolvat, nu era problema in algoritm dar am incurcat m cu n la citire #-o :aha: Nu posta consecutiv, ci editeaza mesajele anterioare. Titlul: Răspuns: 467 Orase Scris de: UAIC.VlasCatalin din August 24, 2011, 18:06:56 Sucuze pentru post consecutiv, dar nu stiu cum se reediteaza mesajele anterioare, as fi recunoscator daca mi-ati spune cum se face asta, ce sunt incepator pe aici :)
Titlul: Răspuns: 467 Orase Scris de: Jack ONeill din Februarie 17, 2015, 11:20:23 Puteti pune testul 3 va rog? Nu stiu de ce nu-mi ruleaza acolo...
|