| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11335 | Josephus Problem using doubly circular linked list |
|
| 11832 | Play cards |
|
| 11840 | Moving books |
|
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
Niflheimr is playing cards with his friends. As a CS student, he wants to play in a programmer way. He decides to write a program for shuffling the cards. By the way, more friends may come while he is shuffling cards, so sometimes he needs to insert new cards into the card stack, too.
Hint: You can use linked list to implement.
Input
- ADD idx num: Add a new card with number num before card idx.
- CUT a b: Move cards whose index between a and a+b-1 ( [a, a+b) ) to the top of the card stack. Order of the cards inside the moved part won't be changed.
- 1 ≤ n, m ≤ 104
- Number on cards are non-negative integer and do not exceed 107
- # of cards in the card stack will never exceeds 2*104
- in CUT operation, card with index = a+b-1 always exists.
Output
Print out the card stack from top (index 0) to buttom (largest index), each number occupies one line.
Sample Input Download
Sample Output Download
Tags
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.