Elastic Stack P65123

Suposem una nova estructura de dades anomenada “elastic stack”. Una elastic stack funciona de forma similar a una pila, amb l’afegit de que les seves operacions són personalitzables. Així, a una elastic stack hi poden haver operacions per treure o afegir més d’un element, o que retornin el producte dels dos primers elements, etc. Evidentment, el cost de les operacions d’una elastic stack no són equivalents.

Per a aquest problema l’únic que es demana és calcular, donada una elastic stack buida i la descripció de les seves operacions amb els seus costos, el nombre de maneres possibles d’arribar a que l’elastic stack tingui b elements en a unitats de temps, i el nombre mínim d’operacions que calen per arribar-hi.

Per a simplificar el problema, supossarem que les operacions de consulta només actuen sobre un element (l’exemple del producte dels 2 primers elements només es podría fer quan l’elastic stack tingués més d’un element) i que es poden fer en qualsevol moment, inclòs quan l’elastic stack és buida.

Entrada

La entrada comença amb un nombre d’operacions k, i un natural z, seguits de k linies describint les operacions. Cada linia consisteix en un string: “afegir”, “treure” o “consulta”, el cost de l’operació (>0) i, si aquesta no és de consulta, el nombre d’elements que afegeix o treu (>0). A continuació, l’entrada continua amb parelles d’enters a,b.

Suposeu a,b≤500, 0<z<2³² i 0≤ k≤50.

Sortida

Per a cada parella a,b, treieu en una linea el nombre de maneres en mòdul z d’arribar a una elastic stack amb b elements en a unitats de temps i el mínim nombre de passos per arribar-hi, o −1 si no es pot arribar.