프로그램 명: ioi_scrivener
제한시간: 1 초
어떤 사람들은 레오나르드는 movable-type 프린팅을 발명한 구텐베르그의 열렬한 추종자였다고 한다.
그것은 간단한 최근의 타이핑기계와 흡사하고 단지 두 가지의 명령만을 가졌다:
하나는 다음 문자를 치는 것이고 다른 하나는 가장 최근의 명령을 최소(undo) 하는 것이다.
crayfish scrivener 의 주목할 점은 undo 명령이 아주 강력하다는 것이다. undo 명령이 명령 일수도 있고 undone 일수도 있다.
Statement
해야 할 일은 crayfish 타자기의 소프트웨어 버젼을 인식 한다.
빈 텍스트로 시작을 해서 사용자에 의해서 입력되어진 문자열을 받아들이고 아래와 같이 현재 타자된 문자의 위치를 알아낸다.
- Init() -
시작 시 인자 없이 한 번 호출 한다. 이 명령은 undo 가 되지 않는다.
- TypeLetter(L) -
'a' 에서 'z' 까지 소문자중 한 문자가 L 이 될수 있고 마지막에 인쇄된다.
- UndoCommands(U) - 마지막 U 명령을 취소한다. 이 숫자는 양의 정수이다.
- GetLetter(P) -
P 번째 문자를 받아온다. 이 숫자는 음이 아닌 수이고 첫 숫자의 위치는 0 이다. 이는 명령이 아니어서 undo 되지 않는다.
입력
첫 줄에는 줄 수 n 이 주어진다. 1000000 이하이다.
-
T .. type
-
U .. undo
-
P .. get letter
출력
P 명령시 해당 문자를 출력한다.
입출력 예
입력
10
T g
T s
T y
T c
T t
T o
U 4
T w
P 2
P 1
출력
w
s
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 empty text and
accepts a sequence of commands entered by the user, and queries for specific positions of the
current version of the text, as follows.
- Init() - called once at the beginning of the execution, without arguments. It can be used
for initializing data structures. It will never need to be undone.
- TypeLetter(L) - append to the end of the text a single lowercase letter L chosen from a, …, z.
- UndoCommands(U) - undo the the last U commands, for a positive integer U.
- GetLetter(P) - return the letter at position P in the current text, for a non-negative index
P. The first letter in the text has index 0. (This query is not a command and thus is ignored by
the undo command.)
After the initial call to Init(), the other routines can be called zero or more times in any order. It is
guaranteed that U will not exceed the number of previously received commands, and that P will be
less than the current text length (the number of letters in the current text).
As for UndoCommands(U), it undoes the previous U commands in reverse order: if the
command to be undone is TypeLetter(L), then it removes L from the end of the current text; if
the command to be undone is UndoCommands(X) for some value X, it re-does the previous X
commands in their original order.
Example
We show a possible sequence of calls, together with the state of the text after each call
출처:ioi/2012/day1/3 번문제
[질/답]
[제출 현황]
[푼 후(0)]