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 ≤ 10⁴
• Number on cards are non-negative integer and do not exceed 10⁷
• # of cards in the card stack will never exceeds 2*10⁴
• 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

There are n people in a circle, numbered from 1 to n in clockwise direction. They are playing a game, and there will be m lucky people that can get the prizes.

Rules of the game:
1. Each prize has a lucky number.
2. Who is counted as the lucky number can get a prize.
3. If the lucky number is odd, count clockwise.
4. If the lucky number is even, count counterclockwise.
5. The student who gets a prize shall leave the circle.
6. After someone left the circle, if the new lucky number is odd, count from the next person, otherwise count from the previous person (in clockwise order).

For example: 
n = 8
m = 3
lucky number = 3 4 5

The sequence of getting prize is:
first number is 3, so count clockwise starting from 1: 1 2 3
second is 4, so we count from 2, and counterclockwise: 2 1 8 7
last number is 5, so we count from 8, and clockwise: 8 1 2 4 5

Then people 3, 7, 5 can get the prize.

Please use doubly circular linked list to solve this problem.

Input

The first line has two integer n and m, where n is the number of total people, and m is the number of prizes.

The second line has m positive number a_{1 ~} a_m.

testcases:

1. 1 <= m <= n <= 10000, 1 <= a_i <= n
2. 1 <= m <= n <= 10000, 1 <= a_i <= n
3. 1 <= m <= n <= 10000, 1 <= a_i <= n
4. 1 <= m <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
5. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
6. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000

Output

The output has m lines, each line contains a number: who can get the prize.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13129.c

Partial Judge Header

13129.h

Tags

Discuss

Description

Do you notice that the ID of this problem is a palindrome number? This problem, though, requires you to determine whether a linked list is a palindrome - it reads the same backwards as forwards.

Please implement a function to detect whether the linked list given is a palindrome or not.

Input

Since this problem is judged partially, you needn't be concerned about the format of input.

The length of the linked list is at least 1 and won't exceed 100000.

In case your're interested in sample I/O, there are several test cases in a file, which starts with a interger n indicating the length of the list and the next line contains n intergers.

Output

Since this problem is judged partially, you needn't be concerned about the format of output.

In case your're interested in sample I/O, for each test case, if the list is a palindrome, it should print a single T, otherwise print a F. There should be a new line at the end of file (EOF).

Sample Input  Download

Sample Output  Download

Partial Judge Code

13431.c

Partial Judge Header

13431.h

Tags

Discuss

Description

To implement the prominent sorting algorithm, Quicksort, the most vital step is partitioning the sequence by a value pivot. Specifically, given a sequence (linked list in this case) and a value pivot, you should partition the sequence such that all elements less than pivot come before the ones greater than or equal to pivot, and the orders within each part should be preserved.

For instance, if we have the sequence {1, 3, 8, 2, 8} and pivot=3, then the partitioned sequence would be {1, 2, 3, 8, 8}, where {1, 2} is the part less than pivot and {3, 8, 8} is the one greater than or equal to pivot.

Please note that this is a partial-judged problem. That is, you are required to define the function:

node *partition_linked_list(node *, int);

Where node is declared as:

typedef struct _node
{
    int val;
    struct _node *next;
} node;

 

Input

The function would be called with the head of the linked list and the pivot.

It's guaranteed that the sum of the length of the linked lists would not exceed 100000.

Output

It should return the head of the partitioned linked list.

Follow-up

Could you do it in-place, i.e., without using additional space?

Sample Input  Download

Sample Output  Download

Partial Judge Code

13828.c

Partial Judge Header

13828.h

Tags

Discuss