Punt mig d'una llista X60047

Escriviu un programa que simuli el manteniment d’una llista d’enters, a base de llegir instruccions que la van actualitzant, i instruccions que la van consultant. La llista d’enters se suposa inicialment buida, i les instruccions son dels següents tipus: afegir elements al principi o final de la llista, treure elements del principi o final de la llista, o consultar el valor que hi hagi exactament en el punt mig de la llista. En cas que la llista tingui mida parell, no hi ha punt mig i s’escriurà error quan es demani consultar el punt mig.

És obligatori utilitzar només el constructor de tipus list com a mecanisme d’emmagatzemament massiu de dades. En particular, no es pot usar ni vector, ni stack, ni queue. Podeu declarar tants list com volgueu i del tipus que volgueu (que no sigui cap altre mecanisme d’emmagatzemament massiu), i podeu usar iteradors sobre llistes.

Entrada

La entrada consisteix en un nombre arbitrari de linies, cadascuna amb una instrucció. Les instruccions poden ser de la següent forma:

push_front x
push_back x
pop_front
pop_back
get_mid_value

Sortida

Les instruccions pop_front i pop_back poden escriure error a la sortida, i la instrucció get_mid_value pot escriure error o un valor a la sortida. Se sobreentén que la llista que simulem està inicialment buida, i que l’efecte de cada instrucció és el següent:

• push_front x afegeix l’enter x al principi de la llista.
• push_back x afegeix l’enter x al final de la llista.
• pop_front elimina l’element que es troba al principi de la llista. Si la llista és buida ha d’escriure error i salt de linia.
• pop_back elimina l’element que es troba al final de la llista. Si la llista és buida ha d’escriure error i salt de linia.
• get_mid_value escriu l’element que es troba just enmig de la llista si aquesta té mida senar, i escriu error si la llista té mida parell. També escriu un salt de linia. Per tant, la sortida tindrà tantes linies com instruccions get_mid_value hi hagi més totes aquelles altres que hagin produït error.

Observació

Per tal de superar els jocs de proves públics podeu fer una implementació senzilla a on el càlcul de get_mid_value tingui cost lineal. De fet, us recomanem que no us lieu i seguiu aquest enfoc.

Però els jocs de proves privats són grans. Per tal d’aconseguir superar-los tots i obtenir així la màxima nota, convindrà trobar un enfoc més eficient.