ACM RTK - 2. skupina

Popravljanje testov

Profesor Golob pazi razred n učencev, ki pišejo test iz matematike. Na robu katedra ima označeno mesto, kamor morajo učenci odložiti test, ko zaključijo z delom. Test vedno odložijo na vrh kupa, če ta obstaja. Po tem, ko je na kupu vsaj en test, začne prof. Golob popravljati teste. Nov test vedno vzame z vrha in po popravljanju ga odloži drugam. Primer zaporedja oddajanja in popravljanja bi lahko predstavili z nizom ABCXDXXRXXHXQX, kjer X pomeni, da je profesor vrhnji test vzel s kupa, druge črke pa, da je neka oseba test odložila na kup. V zgornjem primeru bi prof. Golob po vrsti popravljal teste CDBRAHQ.

Učencem je obljubil, da jim bo teste vrnil v enakem vrstnem redu, kot so jih oddajali. Zgolj iz zaporedja CDBRAHQ vrstnega reda oddajanja ne more rekonstruirati, verjame pa, da bi lahko pravilno rekonstruiral vrstni red, če bi vedel še, koliko testov je bilo na kupu vsakič, ko je vzel test s kupa. Če bi torej imel zapis oblike ???C?DB?RA?H?Q, ki za vsak X v zgornjem zapisu pove, kateri test je vzel s kupa, znak ? pa predstavlja, da je nek učenec oddal test, bi lahko rekonstruiral niz ABCXDXXRXXHXQX.

Napiši program ali podprogram (funkcijo), ki sprejme niz oblike ???C?DB?RA?H?Q in vrne ali izpiše niz oblike ABCXDXXRXXHXQX. Če vhodni niz ni mogel nastati iz nobenega zaporedja veljavnih oddaj testov, potem to tudi sporoči (vhodni niz štejemo za neveljavnega tudi, če zaporedja oddaj iz njega ni mogoče rekonstruirati). Zaželeno je, da je tvoja rešitev čim bolj učinkovita, torej da bi delovala hitro tudi za velike n (npr. n = 10⁸).

Nekaj primerov:

Vhod: ?A
Izhod: AX

Vhod: ???
Izhod: neveljaven vhod

Vhod: ???C?DB?RA?H?Q
Izhod: ABCXDXXRXXHXQX

Vhod: ??QWE?
Izhod: neveljaven vhod

Vhod: ??????DC??GBAA??WQBA
Izhod: ABAACDXXBGXXXXQWXXXX