## COCI '14 Contest 3 #5 Stogovi

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

Mirko is playing with stacks. In the beginning of the game, he has an empty stack denoted with number . In the step of the game he will choose an existing stack denoted with , copy it and do one of the following actions:

• a. place number on top of the new stack
• b. remove the number from the top of the new stack
• c. choose another stack denoted with and count how many different numbers exist that are in the new stack and in the stack denoted with

The newly created stack is denoted with .

Mirko doesn't like to work with stacks so he wants you to write a programme that will do it for him. For each operation of type output the number removed from stack and for each operation of type count the required numbers and output how many of them there are.

#### Input

The first line of input contains the integer , the number of steps in Mirko's game.

The steps of the game are chronologically denoted with the first integers.

The of the following lines contains the description of the step of the game in one of the following three forms:

• a v for operation of type .
• b v for operation of type .
• c v w for operation of type .

The first character in the line denotes the type of operation and the following one or two denote the accompanying stack labels that will always be integers from the interval .

For each operation of type , the stack we're removing the element from will not be empty.

#### Output

For each operation type or output the required number, each in their own line, in the order the operations were given in the input.

#### Sample Input 1

5
a 0
a 1
b 2
c 2 3
b 4

#### Sample Output 1

2
1
2

#### Explanation for Sample Output 1

In the beginning, we have the stack . In the first step, we copy and place number on top, so . In the second step, we copy and place on top of it, . In the third step we copy and remove number from it, . In the fourth step we copy and denote the copy with , then count the numbers appearing in the newly created stack and stack , the only such number is number so the solution is . In the fifth step we copy and remove number from it, .

#### Sample Input 2

11
a 0
a 1
a 2
a 3
a 2
c 4 5
a 5
a 6
c 8 7
b 8
b 8

#### Sample Output 2

2
2
8
8

• commented on July 8, 2017, 12:38 p.m. edit 2

For future reference, the c query is poorly worded, it is asking for the number of distinct numbers that appear in stacks and

E.g. is and , the answer is , because appear in both stacks.

• commented on Dec. 20, 2016, 9:54 a.m. edit 2

nvm

• commented on March 25, 2016, 4:41 a.m. edited

Could someone explain the c operation. I'm having a tough time tying together the test data and explanation.

And for the explanation, shouldnt the first set be S0 = {1} instead of S1?