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\leq500$, $0<z<2^{32}$ i $0\leq k\leq50$.

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.