| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14228 | 2024_IDS_Spring_Lab2_Josephus Problem |
|
| 14229 | 2024_IDS_Spring_Lab2_Basic Linked List Problem |
|
Description
Consider a game where there are n children (numbered 1,2,⋯ ,n) in a circle. During the game, every second child is removed from the circle, until there are no children left. Counting begins at child 1 in the circle and proceeds around the circle in clockwise direction (where the number of the children is increasing except child n and child 1). In which order will the children be removed?
Input
The only input line has an integer nn.
Constraints
- 1≤n≤2⋅105
Output
Print n integers: the removal order.
Do not include any spaces at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a linked list, which supports the following operations:
-
IH i : Insert head. Insert a new node with integer i to the head of the linked list.
-
IT i : Insert tail. Insert a new node with integer i to the tail of the linked list.
-
RH : Remove head. Remove the node at the head of the linked list. (If the linked list is empty, don't do anything.)
-
RT : Remove tail. Remove the node at the tail of the linked list. (If the linked list is empty, don't do anything.)
-
S i : Search. Traverse the linked list and find if there exists a node with integer i. If yes, print a line "Y". Otherwise, print a line "N". (If the linked list is empty, print a line "E".)
-
O : Output. Traverse the linked list from head to tail. Print the integers saved in the nodes sequentially. (If the linked list is empty, print a line "E".)
Input
The first line is an integer n, being the number of operations. Following n lines, each line contains one operation described above.
Restrictions
- For testcase 1, 1≤n≤104
- For testcase 2, 1≤n≤105
- For testcase 3, testcase 4 and testcase 5, 1≤n≤106
- In each testcase, 1≤i≤99 for every i in "Insert head", "Insert tail" and "Search" operations
- In each testcase, it is guaranteed that the total number of "Search" operations and "Output" operations will not exceed 50
Note that:
- In single testcase, the integers i of "Insert head" and "Insert tail" operations may duplicate.
- You may receive operations "Remove head", "Remove tail", "Search" or "Output" when the linked list is empty.
HINT:
You may reference following structure to construct your linked list.
struct Node
{
int data;
Node *prev;
Node *next;
};
Output
For each "Search" operation and "Output" operation, output one line.
Remember to print a ‘\n’ at the end of the output.
Do not include any spaces at the end of line.