SCRIVIOI - Scrivener - IOI 2012

Crayfish scrivener

For a better understanding: http://www.ioi2012.org/wp-content/uploads/2011/12/Scrivener.pdf

Some people say that Leonardo was a great admirer of Johannes Gutenberg, the German blacksmith who invented movable-type printing, and that he paid homage by designing a machine called the crayfish scrivener — il gambero scrivano — a very simple typing device. It is somehow similar to a simple modern typewriter and accepts only two commands: one to type the next character and one to undo the most recent commands. The notable feature of the crayfish scrivener is that the undo command is extremely powerful: an undo is also considered to be a command itself,

and can be undone.

 

Statement

 

Your task is to realize a software version of the crayfish scrivener: it starts with an integer representing the number of queries and accepts a sequence of commands entered by the user, and queries for specific positions of the current version of the text, as follows.

 

T L — append to the end of the text a single lowercase letter L chosen from

a, …, z.

 

U C — undo the the last C commands, for a positive integer C.

 

P X — return the letter at position X in the current text, for a non-negative index X. The first letter in the text has index 0. (This query is not a command and thus is ignored by the undo command.)

 

 

It is guaranteed that C in query 'U' will not exceed the number of previously received commands, and that X in query 'P' will be less than the current text length ( the number of letter in the current text ).

 

As for query 'U', it undoes the previous C commands in reverse order: if the command to be undone is T L, then it removes L from the end of the current text; if the command to be undone is U X for some value X, it re-does the previous X commands in their original order.

 

Example

 

Input                                 Output

10                                       a

T c                                      c

T z

T u

T a

T i

T h

T f

T z

P 3

P 0

 

 


Added by:Mateus Dantas [ UFCG ]
Date:2013-05-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:International Olympiad in Informatics 2012

hide comments
2014-03-06 01:26:20 Fabián Gómez González
If Freddy explained you how to solve this problem, leave a comment :D !
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.