infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Filip Cristian Buruiana din Ianuarie 20, 2008, 14:12:44



Titlul: 636 Restante
Scris de: Filip Cristian Buruiana din Ianuarie 20, 2008, 14:12:44
Aici puteţi discuta despre problema Restante (http://infoarena.ro/problema/restante).


Titlul: Răspuns: 636 Restante
Scris de: Andrei Purice din Ianuarie 20, 2008, 16:39:40
 :? sunt putin nedumerit... Imi poate explica si mie cineva cum de ia quicku 100 si heapsortu 80 :) ?


Titlul: Răspuns: 636 Restante
Scris de: Andrei Grigorean din Ianuarie 20, 2008, 16:57:15
Quicksort e cel mai rapid algoritm de sortare :).


Titlul: Răspuns: 636 Restante
Scris de: Tataranu Vlad din Ianuarie 20, 2008, 16:59:36
Ce inseamna error: assignment of data-member 'cuvant::orig' in read-only structure (http://infoarena.ro/job_detail/124874)? :?


Titlul: Răspuns: 636 Restante
Scris de: Andrei Purice din Ianuarie 20, 2008, 18:08:05
Multumesc.  :) Eu unul stiam ca heapsortu e cel mai bun... si ca ( , ) quicku trage spre n^2 in caz ca ele sunt deja sortate... eh de-acu in colo daca e fac quick randomizat...


Titlul: Răspuns: 636 Restante
Scris de: Bondane Cosmin din Ianuarie 20, 2008, 18:22:02
Multumesc.  :) Eu unul stiam ca heapsortu e cel mai bun... si ca ( , ) quicku trage spre n^2 in caz ca ele sunt deja sortate... eh de-acu in colo daca e fac quick randomizat...

Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).


Titlul: Răspuns: 636 Restante
Scris de: Stefan Istrate din Ianuarie 20, 2008, 18:26:56
Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).
Ba 'trage' spre O(N^2) pentru ca intotdeauna pivotul e gasit pe prima pozitie. Recurenta e T(N)=O(N)+T(N-1), ceea ce duce la O(N^2). :)


Titlul: Răspuns: 636 Restante
Scris de: Bondane Cosmin din Ianuarie 20, 2008, 18:30:29
Nu are cum sa 'traga' spre O(n^2) cand sunt sortate deja, ci mai degraba 'trage' spre O(n).
Ba 'trage' spre O(N^2) pentru ca intotdeauna pivotul e gasit pe prima pozitie. Recurenta e T(N)=O(N)+T(N-1), ceea ce duce la O(N^2). :)

My bad, m-am grabit aiurea.


Titlul: Răspuns: 636 Restante
Scris de: Andrei Grigorean din Ianuarie 20, 2008, 20:34:38
Invatati C++ si STL. Iata un program care sorteaza un vector in C++:


Cod:
#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int v[1024];

void ReadArray() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", v+i);
}

int main() {
    ReadArray();
    sort(v, v+N);
}


Titlul: Răspuns: 636 Restante
Scris de: Andrei Purice din Ianuarie 20, 2008, 21:00:08
Multumesc de indicatie. Am folosit si eu sortul din stl de cateva ori ( 2 ) dar nu trec de tot in c decat in clasa a 9-a.


Titlul: Răspuns: 636 Restante
Scris de: Andrei Grigorean din Ianuarie 20, 2008, 21:02:13
Ar fi bine sa treci mai repede. Daca te califici la JBOI ai avea un avantaj fata de cei in Pascal ;).


Titlul: Răspuns: 636 Restante
Scris de: Andrei Purice din Ianuarie 20, 2008, 21:11:40
 :peacefingers: Daca JBOI pica in vara ca anu trecut atunci se incadreaza la clasa a 9-a :) .


Titlul: Răspuns: 636 Restante
Scris de: Vene Tian din Ianuarie 26, 2008, 22:32:02
am cateva intrebari.. offtopic
cand vreau sa citesc din fisiere spatiile albe si endline-urile
care e cea mai eficienta metoda?
cea cu resetiosflags sau cu f.get() nu mai stiu cum :/
metoda de sortare din STL e quicksortu' nu ? nam folosit-o niciodata

care e diferenta dintre scanf ("%g", &N)si f<<g


Titlul: Răspuns: 636 Restante
Scris de: Tabara Mihai din Ianuarie 26, 2008, 22:45:27
care e diferenta dintre scanf ("%g", &N)si f<<g[/i]

Pai scanf e mai rapida.E citire specifica limbajului C, pe cand cu f >> g este specifica C++.
Exemplu daca citesti de la tastatura numarul intreg n, atunci o sa ai
Cod:
scanf( "%d", &n )
sau
Cod:
f >> n; // citirea cu streamuri



Titlul: Răspuns: 636 Restante
Scris de: Vene Tian din Ianuarie 28, 2008, 19:47:59
Si raspunsu' la celelalte 2 intrebari?

Citat
cand vreau sa citesc din fisiere spatiile albe si endline-urile
care e cea mai eficienta metoda?
cea cu resetiosflags sau cu f.get() nu mai stiu cum :/
metoda de sortare din STL e quicksortu' nu ? nam folosit-o niciodata
Multumesc  :)


Titlul: Răspuns: 636 Restante
Scris de: Andrei Grigorean din Ianuarie 28, 2008, 20:34:42
Metoda de sortare din STL este un quicksort modificat. Oricum e mai bun decat ar putea sa scrie cineva de mana (in concurs cel putin).


Titlul: Răspuns: 636 Restante
Scris de: Mircea Pasoi din Ianuarie 28, 2008, 20:35:32
Metoda de sortare din STL este un quicksort modificat. Oricum e mai bun decat ar putea sa scrie cineva de mana (in concurs cel putin).

Se numeste introsort (http://en.wikipedia.org/wiki/Introsort) de fapt :P


Titlul: Răspuns: 636 Restante
Scris de: Vene Tian din Februarie 08, 2008, 14:15:31
STL se regăseşte şi în BC 3.1 ? (inafară de DJGPP)


Titlul: Răspuns: 636 Restante
Scris de: Stefan Istrate din Februarie 08, 2008, 14:18:52
Nu


Titlul: Răspuns: 636 Restante
Scris de: Farcasanu Alexandru Ciprian din Februarie 24, 2008, 08:10:04
Imi poate spune si mie cum fac cu sortarea din STL(introsort) sa sortez liniile la matrici? (in cazul de fata matricea e char)


Titlul: Răspuns: 636 Restante
Scris de: Alina Ene din Februarie 24, 2008, 08:39:11
sort(a[ i ], a[ i ] + N) sorteaza primele N elemente pe linia i


Titlul: Răspuns: 636 Restante
Scris de: Farcasanu Alexandru Ciprian din Februarie 24, 2008, 08:50:15
Si eu daca vreau sa sortez liniile?


Titlul: Răspuns: 636 Restante
Scris de: Pripoae Teodor Anton din Februarie 24, 2008, 08:52:57
adica? vrei sa sortezi pe linii sau pe coloane? sau vrei sa sortezi liniile intre ele dupa un anumit criteriu?


Titlul: Răspuns: 636 Restante
Scris de: Sima Cotizo din Februarie 24, 2008, 08:57:05
Faci un vector O[ x ]=y => a x-a linie din matricea ordonata este y. Apoi sortezi pe O, dar functia de comparare de fapt va testa liniile corespunzatoare din matrice. Mai clar:

Cod:
int comp(int a, int b) {
return strcmp( A[a], A[b] ); // compari liniile a si b din matrice
}

int main() {
// citesti matricea, ii faci ce vrei

for (i=0; i<n; ++i) O[i] = i;
sort(O, O+n, comp);

return 0;
}


Titlul: Răspuns: 636 Restante
Scris de: Farcasanu Alexandru Ciprian din Februarie 24, 2008, 09:02:40
adica? vrei sa sortezi pe linii sau pe coloane? sau vrei sa sortezi liniile intre ele dupa un anumit criteriu?

Vreau sa sortez liniile intre ele dupa un anumit criteriu

sima_cotizo nu cred ca ma ajuta ideea ta.....eu vreau sa le sortez sortez:D


Titlul: Răspuns: 636 Restante
Scris de: Sima Cotizo din Februarie 24, 2008, 09:42:39
Pai si in O nu vei avea indicii liniilor sortati dupa criteriul pe care il vrei tu?

Daca de exemplu acum vei afisa matricea in ordinea liniilor din O, vei avea acelasi rezultat cu a interschimba liniile.
Cod:
for (i=0; i<n; ++i) 
      printf("%s\n", A[O[i]]); // ma folosesc de faptul ca matricea e de char

Ca sa folosesti in general matricea sortata, cand vei parcurge de la 0 la n-1 liniile le vei accesa pe O[ i ], nu direct pe i...


Titlul: Răspuns: 636 Restante
Scris de: Farcasanu Alexandru Ciprian din Februarie 24, 2008, 09:48:31
Pai si in O nu vei avea indicii liniilor sortati dupa criteriul pe care il vrei tu?

Daca de exemplu acum vei afisa matricea in ordinea liniilor din O, vei avea acelasi rezultat cu a interschimba liniile.
Cod:
for (i=0; i<n; ++i) 
      printf("%s\n", A[O[i]]); // ma folosesc de faptul ca matricea e de char

Ca sa folosesti in general matricea sortata, cand vei parcurge de la 0 la n-1 liniile le vei accesa pe O[ i ], nu direct pe i...

Da, in fine, eu eram curios cum se sorteaza fizic, dar merge si asa:D, da-mi add pe mes:ciprianfarcasanu sa te mai intreb cate ceva

PS:Am incercat cu varianta ta(am scris identic) si nu vrea, daca am 2 linii identice le interschimba intre ele, altfel nimic.

Cod:
int v[36009];
char m[36009][20];
int comp(int a, int b) {
return strcmp( m[a], m[b] );
int main(){
..........
for(i=0;i<n;i++)
v[i]=i;
sort(v,v+n,comp);
for(i=0;i<n;i++)
printf("%s\n",m[v[i]]);
}
PPS: Si matricea si vectorul incep de pe pozitia 0


Titlul: Răspuns: 636 Restante
Scris de: Andrei Misarca din Martie 14, 2008, 11:15:48
Am incercat si io faza cu sortarea si nu vrea sa sorteze   :?


Titlul: Răspuns: 636 Restante
Scris de: Pripoae Teodor Anton din Martie 14, 2008, 11:42:18
ce sortare ai folosit?


Titlul: Răspuns: 636 Restante
Scris de: Andrei Misarca din Martie 14, 2008, 11:55:19
ce sortare ai folosit?

cea prezentata mai sus de sima cotizo  :)


Titlul: Răspuns: 636 Restante
Scris de: Pripoae Teodor Anton din Martie 14, 2008, 18:15:10
mai bine folosesti qsortu si aproximativ aceeasi functie de comparare (trebe doar facuta conversia de la const void la char*) si aia merge sigur (am luat 100 cu ea din prima)


Titlul: Răspuns: 636 Restante
Scris de: Serban Andrei Stan din Martie 15, 2008, 17:44:12
Mai bun e merge-ul...e sigur in toate cazurile.  :thumbup:


Titlul: Răspuns: 636 Restante
Scris de: Andrei Misarca din Martie 17, 2008, 21:11:04
mai bine folosesti qsortu si aproximativ aceeasi functie de comparare (trebe doar facuta conversia de la const void la char*) si aia merge sigur (am luat 100 cu ea din prima)

mersi... qsortu asta chiar e bun pt ca merge si in borland (fiind in stdlib), desi e mai greu de folosit  :)


Titlul: Răspuns: 636 Restante
Scris de: Fodor Gabor din Aprilie 30, 2008, 05:04:20
Iata o chestie ciudata:

Cod:

...

string K[MAX];
int N,R[MAX];

int comp(int a,int b){   
    return K[b] > K[a];
    }

int comp2(int a,int b){   
    return K[b].compare(K[a]);
    }

...

sort(R,R+N,comp);
// resetare R, R[i] =i;
sort(R,R+N,comp2);

...

prima sortare merge, al doilea pare a nu avea nici un efect asupra arrayului.
ceva idee?


Titlul: Răspuns: 636 Restante
Scris de: Stefan Istrate din Aprilie 30, 2008, 11:06:36
Metoda "compare" a string-ului e pe modelul functiei "strcmp" din C si returneaza -1, 0, sau 1. Pentru sortare descrescatoare incearca
Cod:
int comp2(int a, int b) {
    return K[a].compare(K[b]) > 0;
}


Titlul: Răspuns: 636 Restante
Scris de: Fodor Gabor din Aprilie 30, 2008, 17:33:17
 :D
Mea culpa ... nu ma mai pun la debug 5 AM. Thx.

PS:

Citat
int strcmp ( const char * str1, const char * str2 );
...
A zero value indicates that both strings are equal.
A value greater than zero indicates that the first character that does not match has a greater value in str1 than in str2; And a value less than zero indicates the opposite.

Deci sursa :

Cod:
int comp(int a, int b) {
return strcmp( m[a], m[b] );

..trebuie modificata la fel.


Titlul: Răspuns: 636 Restante
Scris de: Bula Ionut din Octombrie 09, 2008, 17:25:30
avand in vedere ca pentru siruri mici, sortarea prin insertie se descurca destul de bine nu ar fi eficient daca am sorta prin insertie cuvintele si daca am folosi quick-sort, eventual sort din STL, pentru sirul de cuvinte?

sper totusi ca 16 sa nu fie o valoare prea mare...



Titlul: Răspuns: 636 Restante
Scris de: Andrei-Bogdan Antonescu din Octombrie 09, 2008, 20:29:41
ba da e eficient (poate mai rapid) :) si poti pentru restu sa faci cu quicksort .
succes ...


Titlul: Răspuns: 636 Restante
Scris de: Bula Ionut din Octombrie 09, 2008, 21:50:35
a iesit destul de bine, am testat si cu quick randomizat si cu cel ce alege pivot, primul element. daca as folosi sort() din STL ar iesi si mai bine dar nu are rost un algoritm industrial (cel putin pentru problema asta)  :) in fine..
m-am uitat si la rezultatul tau, andrei-alpha, am observat ca ai scos niste timpi foarte buni si memorie deasemenea, ce implementare ai folosit?   =D&gt;


Titlul: Răspuns: 636 Restante
Scris de: A Andrei din Martie 26, 2009, 11:55:27
As dori un test mai dificil pentru aceasta,iau doar 10 puncte si nu reusesc sa`mi dau seama ce gresesc.


Titlul: Răspuns: 636 Restante
Scris de: Romila din Decembrie 20, 2009, 15:53:03
Testul 4 are ceva mai "special" ?


Titlul: Răspuns: 636 Restante
Scris de: Simoiu Robert din Februarie 25, 2010, 19:32:46
Imi da WA la 7 teste. Nu ma puteti ajuta cu niste teste ?


Titlul: Răspuns: 636 Restante
Scris de: Cobzaru Adrian-Andrei din Iulie 02, 2012, 20:35:12
Imi da si mie cineva un test mai mare?Iau 10 puncte si 9 WA...


Titlul: Răspuns: 636 Restante
Scris de: Dan H Alexandru din Iulie 03, 2012, 12:15:06
Iti poti genera tu teste. Generezi un in , iei o sursa de 100 si ai out-ul. Apoi poti sa iti dai seama unde ai gresit. Succes.