Informatica Online Judge

  경곽이의 책상 [1708 / 06AC]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 33   Total Tried : 33


The Champion of this Problem (C++) : ajou709 - 6ms / 763byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]

Background

경곽이는 학습실의 자기 책상에 책을 순서대로 올리고 필요할 때 마다 한 권씩 가져가서 공부를 한다. 그러나 경곽이의 어머니는 자주 학교에 오시고 책상에 올려진 책들의 순서가 늘 마음에 들지 않아서 새롭게 정리하기를 원하신다. 경곽이가 책을 정리하고 필요한 책을 가져가고 경곽이의 어머님이 책을 정리하는 규칙을 나타내는 연산은 다음과 같다.
규칙:
add x : x의 값을 가지는 책을 책상에 왼쪽부터 한 권씩 일렬로 올린다.
take : 책상에 놓여진 책들 중 가장 오른쪽 책을 가져가고 책상에서는 사라진다.
mum! : 책상위에 놓여진 책의 왼쪽 절반을 하나씩 오른쪽으로 옮긴다. 홀수 개의 책이 있다면 총 책의 절반을 넘지 않는 가장 작은 수 만큼의 책을 오른쪽으로 하나씩 옮긴다.
* 초기 책상은 비어 있다.

Input

첫 줄에 연산의 수를 나타내는 정수 N이 입력 된다.
두 번째 줄부터 N가지의 연산이 입력 된다.
[입력값의 정의역]
1<= N <= 1,000,000
1 <= x <= N

Output

첫 줄에 남아 있는 책의 수를 출력한다.
두 번째 줄에 남아 있는 책의 번호를 출력한다.

IO Example

8
add 1
add 2
add 4
add 3
add 5
add 8
take
mum!

출력
5
4 3 5 1 2
설명1:
take를 만나기 전까지 책상에는 1 2 4 3 5 8 이라는 책이 있으며 take를 만나 8이라는 책이 사라지고 1 2 4 3 5 라는 책이 남는다. mum!을 만나면 5개의 절반인 5/2 = 2 권을 앞에서 부터 하나씩 뒤로 옮겨서 놓는다. 그 결과 4 3 5 1 2 라는 순서로 책이 놓여 있게 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]