Fusió i suma dels elements de dos llistes doblement encadenades X99017

Donada la classe Llista que permet guardar seqüències d’enters amb una llista doblement encadenada, sense fantasma i no circular, cal implementar el mètode

que fusiona els elements del paràmetre implícit i de l2 agafant n elements del paràmetre implícit i n elements de l2 alternativament (o els que quedin si n’hi ha menys de n). Al principi del paràmetre implícit s’afegeix un nou element que conté la suma de tots els elements del paràmetre implícit i l2. La llista l2 queda buida.

Per exemple, si inicialment tenim aquestes dues llistes:

  p.i. [2 5 3 8 4]
  l2   [1 6 9]    

desprès de cridar fusiona_suma amb n=2, les dues llistes quedaran així:

  p.i. [38 2 5 1 6 3 8 9 4]
  l2   []

Pots veure més exemples en els jocs de prova públics. Cal enviar a jutge.org només la implementació del mètode fusiona_suma. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements n1 de la llista del p.i. i nombre d’elements n2 de la llista l2.

Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe Llista i un programa principal que processa línies d’enters amb els que crea dues llistes i desprès crida vàries vegades el mètode fusiona_suma amb diferents valors de n.

Entrada

L’entrada conté dues línies formades per seqüències d’enters, són els elements que tindran les dues llistes inicials. A continuació segueix una seqüència d’enters que representen diferents valors de n.

Sortida

Per a cada valor n d’entrada es fusionen i es sumen els elements de les dues llistes inicials agafant alternativament n elements de cadascuna i s’escriu tres línies: El valor n, el contingut de la primera llista i el contingut de la segona llista. Per cada llista s’escriu el nombre d’elements de la llista seguit d’un espai, els elements de la llista entre claudàtors i separats per espais, i finalment aquests mateixos elements però amb ordre invers, també entre claudàtors i separats per espais.

Observació

Cal enviar la solució (el fitxer solution.cpp) comprimida en un fitxer .tar:

tar cvf solution.tar solution.cpp

Només cal enviar la implementació del mètode fusiona_suma i el seu cost en funció del nombre d’elements n1 i n2 de les dues llistes inicials. Segueix estrictament la definició de la classe de l’enunciat.