Description

Given a link list structure named Node.

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

Given a list, rotate the list to the left by k places, where k is non-negative and k is smaller than the count of nodes in linked list.

For example: 
Given 1->2->3->4->5->NULL and k = 3, 
return 4->5->1->2->3->NULL.

Input

The input contains 2 sequence of positive integers.The first sequence is to create a linked list of integers, except the last one, which is -1, indicating the end of the sequence. The second line is an integer k. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)

Pre-order:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

In-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Post-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Input

The input contains two lines. The first line is a integer n (n<=8000) , and the second line is a sequence S, where S contain n non-negative integer number. (The first number in the sequence S is the root.) 

Output

Please print out the tree with preorder, inorder and postorder.(total three line)

Each line has '\n' in the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

In this problem, you are given a prefix Boolean expression, which has at most N=10^5 variables and 2 kinds of operators ‘&’ and ‘|’. Each variable has an ID number. The values of these variables can be either 0 or 1, and are all initialized as 0.

You will be given M ID numbers. For each ID number, you should flip (0 will become 1, 1 will become 0) the value of the corresponding variable and then compute/output the result of the prefix Boolean expression.

Example:

Assume the prefix Boolean expression is &[1][2] and the given ID numbers are “2 1”. First the value of variable 2 will change from 0 to 1. The output of &[1][2] is 0&1=0. Next, the value of variable 1 will change from 0 to 1. The output of &[1][2] is 1&1=1.

Hint: (You can go to the Input/Output description directly, and come back for hints if necessary.)

Hint 1: To solve this problem, you can parse the input and derive the output recursively each time a variable is flipped. Unfortunately, this brute-force approach is not efficient and can lead to TLE, in particular the 3^rd and 4^th testcases in this problem. We encourage you to use the syntax tree of the prefix Boolean expression for better efficiency.

Hint 2: The key idea behind the syntax-tree approach is to avoid re-evaluation of the whole expression every time a bit is flipped. Some more hints are provided for you as follows:

• [Data structure] Use a tree node pointer array to record the address of each variable (leaf) node of the syntax tree: you can locate each variable to be flipped directly;
• [Data structure] For each tree node i, record the value of its subtree (rooted at node i);
• [Algorithm] Starting from the variable node to be flipped, move upward following the syntax tree and update the node values until the output of the syntax tree (or the Boolean expression) can be determined. 

Example:

Consider the following syntax tree for "|&|[1][2][3][4]". Assume [1] is flipped. You will find that the value of node A should be changed to 1|0=1. Moreover, you note that the value of B remains unchanged, i.e., 1&0=0, and the checking process can stop.

Later, when [3] is flipped, both the values of node B and the root node should be changed. In this case, the output is also changed.

Sample structure:

typedef struct node{

    int value; // This is the value of the subtree, not the ID number

    int tokentype;

    struct node *leftchild;

    struct node *rightchild;

    struct node *parent; //pointing to the parent node

}Node;

Node* variable[100001]; // This array stores the pointers pointing to the tree nodes. For example, variable[0] points to the node with ID number 0.

Input

The first line has one number T, 0<T<= 7, indicating the number of testcases.

The following lines are the inputs of the testcases.

Each testcase contains three lines:

1. N, M (0<N<=100000, indicating the number of variables in a given prefix Boolean expression. 0<M<=100000, indicating how many times the values are flipped).

2. A string S, describing the prefix Boolean expression (& means and gate, | means or gate, [i] means a variable ID)

3. M numbers, where each number i means the value of variable i is flipped. The order matters.

Note that all the variables are initially 0.

Each ID number only appears once in the prefix Boolean expression.

The depth of the tree is no more than 30.

Output

For each testcase, you should output M lines, each showing the output of the prefix Boolean expression after a variable is flipped.

0 for false, 1 for true.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem brought to you by NTHU Order a Rabbit club.

On her birthday, Chiya received a fabric of N cm from her friends, and she wants to make a kimono out of it.

The fabric has up to 26 different colors of flowers on it, and every centimeter of it has exactly one flower. She will cut exactly one continuous segment from it, and for aesthetic reasons, she will only cut at some integer number cm.

Yet again for aesthetic reasons, she wants the fabric for kimono to be K-partite for her favorite number K. A piece of fabric of M cm can be represented as a string S of lower-case latin letter, and it is K-partite if it satisfies the following conditions:

(1) the length is at least K

(2) the fabric can be partitioned into exactly K non-empty contiguous segments of the same color, with each pair of neighboring segments having different colors.

For example, the strings “aaabbbccc” and “ggoogg” are both 3-partite. The partitioning are as follows:

aaa | bbb | ccc
gg | oo | gg

While the string “wwwwwaaa” is not 3-partite.

So given the fabric "abcdccgggk" and K=2, Chiya has the following choices of cutting out a K-partite segment:

1. [ab]cdccgggk

2. ab[cd]ccgggk

3. abc[dcc]gggk

4. abcd[ccgg]gk

...

Chiya wonders what is the lengths of the longest and shortest K-partite subsegment she can cut out from this fabric. (Since you are from CS town, she knows you can solve this within a minute.)

A picture of Chiya to cheer you up:

Input

The input file contains two lines. The first line has 2 integers N and K, while the second line has a string of length N, consisting of only lowercase latin letters.

The whole string is guaranteed to be X-partite for some X>=K, so that the answer always exists.

1 <= N <= 5*10⁵

Output

Output two integers L1 and L2: the longest and shortest lengths of a K-partite subsegments.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Loliforce is currently the most popular online FPS game, and it is rumored that free lolis (a species of cat) will be given to the players who have reached the top 1% on the rank (namely, the “red” players).

Joy and Shepherd have both become red players recently, and they are now at Loliforce HQ to receive their prize. There is an array of N lolis available, and the i-th loli has height h_i. The lolis are bio-engineered to have distinct heights.

Since they both like big lolis, they will take turn choosing the tallest loli not chosen, and K lolis on the left closest to it, and K lolis on the right closest to it (if on one side, there are less than K lolis, all of them will be chosen). If a loli is chosen on a turn, it is taken away from the array. The process continues until the array is empty.

Since Shepherd is the senpai, he will take the first turn; but the array is really big, he wants you to write a program to find out which lolis belongs to him in the end, to save him from the tedious process. Can you help Joy and Shepherd?

Input

Each input file contains only one testcase, which has two lines: two integers N K on the first line, and N integers h₁,h₂...h_N on the second line.

1 <= K <= N <= 2*10^5

1 <= hi <= 10^9 for i = 1...N

for each pair of indexes (i, j), if i ≠ j, hi ≠ hj.

Output

For each testcase, output a single string S of length N, the i-th character of which should be ‘S’ if ith loli ends up going to Shepherd and ‘J’ if otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem brought to you by NTHU Amusement Programming Club.

Aoba works as a character designer at a game comapny Eaglesquat, and their new game Black Souls is almost finished.

As usual, things do not go too smoothly at the debugging stage. One report points out that, no matter how hard one might try, it is impossible to go to the final boss room. Aoba steals a peek at the map and suspects that the entrance to the final maze may not even be connected to the entrance to the final boss room.

The maze can be modelled as a 2D grid with size N∗M, with rows numbered from 1...N and column numbered from 1...M. The cell is numbered (i,j) if it is positioned at the ith row and jth column; and it is marked ‘1’ if player can walk on it or ‘0’ if not. The player can walk only in the up/down/left/right direction, and of course they can’t walk out of the maze.

The entrance to the maze (x1,y1) and the exit to the final boss room (x2,y2) are given, and their positions can not be modified. Two are connected if and only if the player can walk from the former to the latter.

If the entrance and exit are not connected, the crew would have to change the map structure to make them so. Since the release date is near, they have to do it quick and simple; only one horizontal or vertical corridor may be added, and they want the length to be minimized. A corridor is a series of consecutive cells on which the player can walk on.

Formally, an extra corridor that starts at (xi,yi) and ends at (xj,yj) may be added, if xi=xj or yi=yj, and the cost would be |xj−xi+1| if it is vertical or |yj−yi+1| if horizontal. The '0’s and '1’s between the endpoints do not affect the cost.

Since you are a CS student, Aoba knows you can write a program to find out the minimum length of the corridor that needs to be added. Ganbatte kudasai!

The sample testcase illustrated, orange cells denote the entrance and exit, while blue cells denote the corridor added.

Input

Each input file contains only one testcase. For each test case, there will be three lines and the maze map represented as a binary matrix:

The first line contains a pair of integers N M, denoting the size of the maze.

The second line contains a pair of integers x1 y1, which is the position of the entrance.

The third line contains a pair of integers x2 y2, which is the position of the exit.

The entrance and the exit are guaranteed to be at two different positions.

Following come N lines, each with a string of length M consisting of only 0 or 1, which is the maze as described in the problem. The row number is numbered from up to down, and the column number left to right. The numbers are 1-indexed.

2 <= N, M <= 500

Output

Output a single integer that is the minimum length of a corridor that needs to be built. If it is impossible to satisfy the requirements, output -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given N integers , output them in an increasing sequence.

Input

There will be multiple testcases in each input file, but no more than 10

A single integer N in first line, means the numbers of elements in the sequence. 

And N elements Xi in the second line , 1 <= i <= N

1 <= N <= 10³

1 <= Xi <= 10⁷

Output

Output an increasing sequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem brought to you by NTHU Amusement Programming Club.

After being kicked out of NTHU due to lack of talents in programming, GY Lin had no choice but to start living in a tree (a connected, acyclic graph). If you fail this course, you will meet the same fate.

Knowing this, his friend and tutor Shepherd comes to visit GY. Unfortunately for him, GY is not at home, but he doesn’t realized this until he has already traversed every node. During that, he discovered something interesting: when he steps onto a node, the view may change dramatically.

The tree has N nodes, and nodes are numbered distinctly from 1 to N. The view from a node u can be quantified as a single integer val(u), which can be obtained using the following algorithm:

The dfs algorithm is defined as follows:

Shepherd is now standing on node S, so he wants you to help him calculate val(S), for he doesn't have the computer right now.

Input

There is only one testcase per input file, each describing the structure of a tree.

On the first line, there two integers N S, the number of nodes and the node that Sheep is standing on; N−1 lines follow, each containing two integers u v, meaning there is an edge between node u and v.

1 <= N <= 2*10⁵

Output

Output a single integer that is val(S).

Sample Input  Download

Sample Output  Download

Tags

Discuss