Computer Science

# Abstract Data Types: Level 3-4 Challenges

One fateful day, 9 people numbered 1, 2, 3, 4, 5, 6, 7, 8 and 9 are trying to cross a road that contains several deep holes. To pass through a hole with depth 3, the 3 leading people have to go into the holes in order so that the other people can safely cross the hole. Then, the last people who crossed the hole will pull the highest people from the hole up, and so on. For clarity, look at the diagram below where 4 people is crossing a hole with depth 3 :

If the output sequence is $1,2,3,4,5,6,7,8,9$ and the $30$ holes they must pass through in order has depth of

 1 3 5 9 8 5 1 8 5 4 5 3 8 6 7 2 6 3 9 2 5 2 7 8 6 7 3 6 9 2 5 

respectively, what is the input sequence?

If you think the output sequence is $6,5,4,3,2,1$, input your answer as 654321.

You are advised to solve the Easy and Medium version of this problem first.

A Mathematician was tasked to do a magic show in front of a group of elderly in an elderly home. Using his mathematical knowledge, he made a magic trick on the spot but was stuck at the last step, can you help him? The magic trick is as follows:

1. Get a member of the audience to pick a card from the deck and with only the audience knowing the value of the card, place the card at the bottom of the pile.

2. Take the top half of the deck (26 cards) and place them at the bottom of the card.

3. Take the 26 cards in the middle and place them on top of the pile.

4. Remove the bottom 26 cards from the deck.

5. Once again, take 14 cards from the centre of the deck out and remove the other cards.

6. For the last time, we take 6 cards from the middle and remove everything else.

7. He then places all removed cards on top of the current deck in the order they were removed.

8. Pull out the $n^{th}$ card from the top and show it to the audiences.

The question is, what is $n$?

Definition of terms used

• $n$ cards from the middle - We take the number of cards into the deck to be 5. if $n=3$, if means the we take the 2nd, 3rd and 4th card.

• The order they were removed - Assuming we have 7 cards and we remove the middle 3 cards(3rd, 4th, 5th) and then remove the middle 2 cards(2nd and 6th), we will then put the cards in order meaning that we first place the 3rd card, followed by the 4th, then the 5th, then the 2nd and lastly the 6th.

###### Image credit: Wikipedia Wuprisha

10 students are standing in a row. From left to right, they are labeled as 1 to 10. When the teacher left for the bathroom, they start to switch positions. When the teacher come back on the $k^\text{th}$ minute, the queue becomes the $k^\text{th}$ lexicography order.

• K L N : On the $k^\text{th}$ minute, what is the label of the $n^\text{th}$ person from the left?
• K P N : On the $k^\text{th}$ minute, what is the position of the person labeled $n$?

This file contains 1000 queries. What is the sum of all output?

Sample Input

 1 2 3 4 5 6 7 8 1 L 1 1 L 2 1 L 10 2 L 10 1 P 1 1 P 2 1 P 10 2 P 9 

Sample Output

 1 2 3 4 5 6 7 8 1 2 10 9 1 2 10 10 

For this example, the answer is 45.

×