IOI 2012 day1 3- 크래이피쉬 글쓰는 기계(Crayfish scrivener) > 문제은행 : 정보올림피아드&알고리즘




1717 : 크래이피쉬 글쓰는 기계(Crayfish scrivener)

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
19 회   
시도횟수
72 회   

문제

활자 인쇄기를 발명한 독일 대장장이인 요하네스 구텐베르크는 레오나르도가 열렬히 존경하는 사람이었다. 

레오나르도는 크래이피쉬 글쓰는 기계 — il gambero scrivano —로 불리는 매우 단순한 타자 기계를 설계하여 구텐베르크에게 존경을 표시하였다.

이것은 단순한 현대의 타자기와 매우 비슷하며, 단지 두 개의 명령어만 받아들인다. 

하나는 그 다음 문자를 타자하는 것이고, 다른 하나는 가장 최근의 명령어들을 취소(undo)하는 것이다. 

이 타자 기계의 주목할 만한 특징은 취소 기능이며, 이는 매우 강력한 기능이다: 

취소 명령은 자기 자신, 즉 취소 명령어에 대해서도 적용될 수 있다.

 

 

해야 할 일
여러분이 할 일은 크래이피쉬 글쓰기 기계와 같이 동작하는 소프트웨어를 구현하는 것이다: 

 

빈 텍스트에서 시작하고, 사용자가 입력한 명령어의 순서들을 받아들이고, 

다음과 같이 텍스트의 현재 상황의 특정 위치에 대한 질의를 수행한다.

 

TypeLetter(L) : a, …, z으로부터 선택된 하나의 소문자 L을 텍스트의 끝에 추가한다.
UndoCommands(U) : 양의 정수 U에 대해, 가장 최근의 U 개의 명령어를 취소한다.
GetLetter(P) : 음이 아닌 인덱스 P에 대해, 현재 텍스트에서 위치 P의 문자를 되돌려준다. 

 

텍스트에서 첫 번째 문자의 인덱스는 0 이다. (이 질의는 명령어가 아니어서 취소 명령어에서는 무시된다.)

UndoCommands(U)에서는 이전의 U개의 명령어를 역순으로 취소한다. 

만약 취소될 명령어가 TypeLetter(L)라면, 이것은 현재 텍스트의 끝에서부터 L을 삭제한다. 

만약 취소될 명령어가 어떤 값 X에 대해 UndoCommands(X) 라면 이것은 이전의 X개의 명령어를 원래의 순서대로 다시 실행한다.

 

 

예제
하나의 가능한 호출순서에 대해서 각 호출후의 텍스트의 상태를 보인다.

 

 

 


 

 


입력형식

첫줄에 n(1 ≤ n ≤ 1,000,000)이 입력되는데 이것은 입력 줄 수이다. 그 다음부터 n줄에 걸쳐 질의가 입력되고 공백 후 값이 입력된다.

T : TypeLetter
U : UndoCommands
P : GetLetter


출력형식

P : GetLetter의 해당 문자를 한 줄에 하나씩 출력한다.


입력 예

14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2

출력 예

b
d
c
d


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP