F002B. Vectors comprimits P16175

Statement

thehtml

A vegades cal manipular vectors numèrics que tenen un 0 a la majoria de posicions. En aquests casos, es pot estalviar memòria i temps de càlcul usant la tècnica dels vectors comprimits, que consisteix a guardar només els valors diferents de 0, juntament amb la posició on es troben.

Per exemple, per representar el vector

v = (0,3,0,0,8,0,0,−3,5,0,0,0,0)

s’utilitza el vector comprimit amb quatre parells següent:

3;1

8;4

−3;7

5;8

Aquest vector comprimit indica que hi ha un 3 a la posició 1 del vector v, un 8 a la posició ‍4, un −3 a la posició 7, un 5 a la posició 8, i que a la resta de posicions hi ha un 0.

Fixeu-vos que en els vectors comprimits només es guarden les posicions que tenen un valor diferent de 0, i que la taula es troba ordenada creixentment segons les posicions.

Les definicions següents permeten utilitzar vectors comprimits d’enters:

struct Parell { int valor; // Diferent de zero int pos; // Més gran o igual que zero }; typedef vector<Parell> Vec_Com; // Ordenat per pos!

Utilitzant aquestes definicions, implementeu la funció

Vec_Com suma(const Vec_Com& v1, const Vec_Com& v2);

que retorna la suma, component a component, de dos vectors comprimits |v1| i |v2| donats.

Implementeu també l’acció

void llegeix(Vec_Com& v);

que llegeix, d’acord amb el format dels exemples, un vector comprimit, i el desa a |v|.

El programa principal ja se us dóna implementat; no el canvieu. Aquest llegeix primer un natural k. Després llegeix k parelles de vectors comprimits, els suma i n’escriu el resultat. L’acció que escriu vectors comprimits també se us dóna implementada; queda estrictament prohibit cambiar-la. Fixeu-vos que tant a l’entrada com a la sortida apareix explícitament el nombre de valors diferents de 0 del vector. Fixeu-vos també que la llargada que tenia el vector original (no comprimit) és irrellevant en aquest problema.

Observació

Useu algun mètode eficient per implementar |suma()|. Altrament, el Jutge rebutjarà la vostra solució per ser massa lenta. Inspireu-vos en algun dels algorismes fonamentals vistos a classe.

Public test cases

Input

5

4 3;1 8;4 -3;7 5;8
4 3;1 8;4 -3;7 5;8

3 4;0 8;5 6;6
2 3;0 -6;6

3 2;3 3;18 5;21
3 -2;3 -3;18 -5;21

1 1;1000000000
1 1000000000;1

1 999;666
0

Output

4 6;1 16;4 -6;7 10;8
2 7;0 8;5
0
2 1000000000;1 1;1000000000
1 999;666

Information

Author: Professorat de P1
Language: Catalan
Other languages: English
Official solutions: C++
User solutions: C++