시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB43019311040.000%

문제

활자 인쇄기를 발명한 독일 대장장이인 요하네스 구텐베르크는 레오나르도가 열렬히 존경하는 사람이었다. 레오나르도는 크래이피쉬 글쓰는 기계 — il gambero scrivano —로 불리는 매우 단순한 타자 기계를 설계하여 구텐베르크에게 존경을 표시하였다. 이것은 단순한 현대의 타자기와 매우 비슷하며, 단지 두 개의 명령어만 받아들인다: 하나는 그 다음 문자를 타자하는 것이고, 다른 하나는 가장 최근의 명령어들을 취소(undo)하는 것이다. 이 타자 기계의 주목할만한 특징은 취소 기능이며, 이는 매우 강력한 기능이다: 취소 명령은 자기자신, 즉 취소 명령어에 대해서도 적용될 수 있다.

여러분이 할 일은 크래이피쉬 글쓰기 기계와 같이 동작하는 소프트웨어를 구현하는 것이다: 빈 텍스트에서 시작하고, 사용자가 입력한 명령어의 순서들을 받아들이고, 다음과 같이 텍스트의 현재 상황의 특정 위치에 대한 질의를 수행한다.

  • Init() — 실행 초기에 인자가 없이 한번만 호출된다. 이 함수는 자료 구조를 초기화 하는데 사용될 수 있다. 이것은 결코 취소될 필요가 없을 것이다.
  • TypeLetter(L) — a, …, z으로부터 선택된 하나의 소문자 L을 텍스트의 끝에 추가한다.
  • UndoCommands(U) — 양의 정수 U에 대해, 가장 최근의 U 개의 명령어를 취소한다.
  • GetLetter(P) — 음이 아닌 인덱스 P에 대해, 현재 텍스트에서 위치 P의 문자를 되돌려준다. 텍스트에서 첫 번째 문자의 인덱스는 0 이다. (이 질의는 명령어가 아니어서 취소 명령어에서는 무시된다.)

Init()를 호출한 후에, 그 외의 루틴들은 임의의 순서로 0번 이상 호출 될 수 있다. U는 이전에 들어온 명령어들의 수를 초과하지 않음이 보장되며, P는 현재의 텍스트의 길이보다 작을 것이다 (현재 텍스트에서의 문자의 수).

UndoCommands(U)에서는 이전의 U개의 명령어를 역순으로 취소한다: 만약 취소될 명령어가 TypeLetter(L)라면, 이것은 현재 텍스트의 끝에서부터 L을 삭제한다: 만약 취소될 명령어가 어떤 값 X에 대해 UndoCommands(X) 라면 이것은 이전의 X개의 명령어를 원래의 순서대로 다시 실행한다.

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

Call Returns Current text
Init()    
TypeLetter(a)   a
TypeLetter(b)   ab
GetLetter(1) b ab
TypeLetter(d)   abd
UndoCommands(2)   a
UndoCommands(1)   abd
GetLetter(2) d abd
TypeLetter(e)   abde
UndoCommands(1)   abd
UndoCommands(5)   ab
TypeLetter(c)   abc
GetLetter(2) c abc
UndoCommands(2)   abd
GetLetter(2) d abd

입력

첫째 줄에 명령어와 질의의 수 L이 주어진다. 다음 줄부터 L개 줄에는 명령어와 질의가 주어진다.

첫 번째 문자가 T인 경우에는 TypeLetter 명령이다. T a와 같이 주어진 경우에는 TypeLetter(a)를 호출하면 된다. U인 경우에는 UndoCommands, P는 GetLetter를 의미하며, 공백으로 구분되어 주어지는 숫자를 인자로 호출하면 된다.

출력

GetLetter에 의해 리턴된 문자를 한 줄에 하나씩 출력한다.

서브태스크

번호배점제한
15

명령어와 질의의 전체 수가 1이상 100이하이고, UndoCommands의 호출은 없다.

27

명령어와 질의의 전체 수가 1이상 100이하이고, UndoCommands가 취소되는 경우는 없다.

322

명령어와 질의의 전체 수가 1이상 5,000이하이다.

426

명령어와 질의의 전체 수가 1이상 1,000,000이하이고, GetLetter에 대한 모든 호출은 TypeLetter 와 UndoCommands의 모든 호출뒤에 발생한다.

540

명령어와 질의의 전체 수가 1이상 1,000,000이하이다.

예제 입력 1

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

예제 출력 1

b
d
c
d

출처

Olympiad > International Olympiad in Informatics > IOI 2012 > Day 1 3번

  • 문제를 만든 사람: Bruce Merry

채점 및 기타 정보

  • 예제는 채점하지 않는다.