Ordenant paraules P50728


Statement
 

pdf   zip

thehtml

Donat un vector de paraules amb longituds entre 1 i 10, on cada paraula té o bé només lletres minúscules o bé només lletres majúscules, cal obtenir un nou vector amb les mateixes paraules però en aquest ordre:

  • abans, les paraules amb lletres minúscules;
  • en cas d’empat, les paraules més curtes;
  • en cas d’un altre empat, respectant l’ordre relatiu en el vector.

Per exemple, si el vector conté [ HELLO, ivet, anna, HI, BYE, pep ], el resultat ha de ser [ pep, ivet, anna, HI, BYE, HELLO ].

Escriviu un procediment

vector<string> ordena_sense_sort(const vector<string>& V);

que retorni un vector<string> amb el resultat d’ordenar les paraules de V amb els criteris indicats anteriorment.

Precondició

Totes les paraules de V són diferents, i cadascuna té entre 1 i 10 lletres, que són o bé totes minúscules o bé totes majúscules.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La solució esperada no usa el sort() ni cap algorisme similar i té cost O(n), on n és la mida del vector. Amb una solució “raonable” de cost O(n logn) el jutge us donarà 70 punts, i podreu obtenir una nota màxima de 7 en aquest problema.

Information
Author
Salvador Roura
Language
Catalan
Official solutions
C++
User solutions
C++