| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11335 | Josephus Problem using doubly circular linked list |
|
| 11840 | Moving books |
|
| 12680 | Card Magic |
|
Description
Based on the original Josephus Problem introduced in class, an additional rule of this problem is to change
direction of counting after killing a person. For example, there are 8 people, numbered 1 to 8, in a circle
and arranged in clockwise. The step to kill is 3.
The sequence of killing people is
1, 2, 3 (kill 3, change the direction to counter-clockwise)
2, 1, 8 (kill 8, change the direction to clockwise)
1, 2, 4 (kill 4, change the direction to counter-clockwise)
2, 1, 7 (kill 7, change the direction to clockwise)
1, 2, 5 (kill 5, change the direction to counter-clockwise)
2, 1, 6 (kill 6, change the direction to clockwise)
1, 2, 1 (kill 1)
So the person numbered 2 is the survivor.
You're asked to solve this problem using circular linked list.
You will be provided with main.c and function.h, and you need to implement function.c.
Note there is a time limit to solve this problem: 3 seconds.
Input
The input has two integers, n and m, where n is the number of total people, and m is the step to kill.
Output
The output is an integer: the survivor's number. There is a newline after that.
Sample Input Download
Sample Output Download
Partial Judge Code
11335.cPartial Judge Header
11335.hTags
Discuss
Description
The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on their own table (numbered from 0 to n-1, means book 0 lies on table 0) with book bi adjacent to book bi+1 for all 0 <= i < n-1
as shown in the diagram below:
|
Book 0 |
Book 1 |
Book 2 |
Book 3 |
Book 4 |
Book 5 |
…… |
Book N-1 |
|
Table 0 |
Table 1 |
Table 2 |
Table 3 |
Table 4 |
Table 5 |
Table N-1 |
The valid commands and limited for moving books are:
Any command in which A = B or in which A and B are in the same stack of books is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of books.
- move A onto B
Return any books that are stacked on the top of book A and book B to their own table. Then puts book A onto book B.
- move A over B
Return any books that are stacked on the top of book A to their own table.
Then puts book A onto the top of book B.
- pile A onto B
Return any books that are stacked on the top of book B to their own table.
Then puts book A and all books on the top of book A onto the top of book B.
- pile A over B
Put book A and all books on the top of book A onto the top of book B.
- exit
Finish moving the books
Input
The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n < 25.
The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
Output
The output should consist of the final state of the books. Each table numbered i (0 <= i < n, where n is the number equal to books initial position) should appear followed immediately by a colon.
If there is at least a book on it, the colon must be followed by one space, followed by a list of books that appear stacked in that position with each book number separated from other book numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each book position (i.e., n lines of output where n is the integer on the first line of input).
You are asked to add a new line character at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Mr. Lu is a famous magician. There’s a poker magic tutorial on his youtube channel.
There’re N stacks of cards on the table at begining.
And then, Mr. Lu make M actions on these card stacks.
There’s only two kinds of actions Merge and Cut:
- Merge x y: put the x-th card stack on the top of y-th card stack.
- Cut x i: cut the x-th card stack into two stacks. One is the card stack contains ( 1~i )-th cards of original stack. The other one is the remaining. The former’s index will be x, the latter’s will be (x+1)
- The indexes of stacks and cards will be changed after Merge and Cut.
For example:
As a lazy CS student, you only focus on the result.
Therefore, you decide to write a program to compute the final state of card stacks.
It’s partial judge for this problem.
Please download the code at the bottom to see the interface and main function.
You have to implement a data structure like below:
Input
Two integer N,M on the first line.
For each of the next N lines, there’re several integers Ni and Ci,1,Ci,2...Ci,Ni.
Ni means the number of cards in the i-th stack.
Ci,j denotes the j-th card of i-th stack.
The folloing M lines contains one action per line.
Every Action is one of “Merge x y” or “Cut x i”.
It’s guaranteed that:
- 1 ≤ N, M ≤ 9000
- ∑ Ni ≤ 4∗104
- Ci,j is non-negative integer.
- In “Merge x y” action:
- the x, y-th stacks always exist.
- x is not equal to y.
- In “Cut x i” action:
- the x-th stack always exists.
- i is always between 1 and Nx - 1.
- There’s at least 1 card in each card stack.
Output
Print the card stacks by the order of index.
One line for one card stack.
Please refer to the sample input/output for the precise format.
There is a ‘\n’ at the end of each line.