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.c

Partial Judge Header

11335.h

Tags

Discuss

Description

Niflheimr discovers an interesting fact: trees grow upward in real world, but trees grow downward in CS world.
He decides to study the trees in CS world, so he choose the simplest one for his study: binary tree. Before study begins, he needs to construct a binary tree first.

Given a in-order traversal sequence and a pre-order traversal sequence of a binary tree, construct the binary tree and print the post-order traversal sequence of that binary tree.

 

Hint:

      1. If you have no idea how to implement, please take it as your reference.

function.h

#include <stdlib.h>
#include <stdio.h>
typedef struct _node {
    int value;
    struct _node *left;
    struct _node *right;
} Node;

Node *create_node(int value);
void postorder(Node *root);
void destroy(Node* root);

/*
    Parameter description:
    int *inorder : the inorder traversal sequence of the binary tree.
    int *preorder : the preorder traversal sequence of the binary tree.
    int inorder_start : the starting index of the inorder traversal of the subtree.
    int inroder_end : the ending index of the inorder traversal of the subtree.

    As for the preorder traversal index, try declaring a static variable inside this function.
*/
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);

      2. If you get a TLE in the last testcase, try to think over the property underlined in "Input" section.

​

Input

 The first line of input contains a integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the in-order traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the pre-order traversal sequence of the binary tree.

 

It is guaranteed that:

• 1 ≤ N ≤ 2*10⁵
• For all x being the number on the binary tree, 0 ≤ x ≤ N-1.

Output

Print out the post-order traversal sequence of the binary tree.
There is a white space after each number (including the last one). For example, [0 1 2 3 ].
Remember to print a '\n' at the end of the output.

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.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’, print its truth table.

 

For example, if input is "|&AC|AB", then result will be

A B C D output

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss