Description

Notice: You need to enable the flag -std=c++11 to compile the code!

• In codeblocks, go to Settings->Compiler->check the option "Have g++ follow the C++11 ISO C++ language standard [-std=c++11]"->OK
• In dev-c++, go to Tools->Compiler options->check "Add the following commands ..."->type in "-std=c++11"(without qoute) ->OK

Once upon a time a farmer went to a market and purchased X wolfs, Y goats, and Z cabbages.

On his way home, the farmer came to the left river bank and rented a boat. To cross the river by a boat, the farmer could carry only himself and at most one of his purchases: a wolf, a goat, or a cabbage.

At both left and right banks, if the farmer is not there and the wolves are more than the goats (#W>#G), the wolves will eat the goats. Also, if the farmer is not there and the goats are more than the cabbages (#G>#C), the goats will eat the cabbages.

In this problem, you have to find all solutions that the farmer can carry himself and all his purchases from the left to the right bank.

For each solution, you cannot produce duplicate states.

For example: 

This solution isn't allowed because there are duplicate states.

Hint: You can use set<State> _explored to store each state.

Input

The input has only single line containing three integer X Y Z, representing the number of purchased wolves, goats and cabbages.

Output

List all solutions one by one.
"Done" denotes the end of a solution.
A solution contains several moves. Each move is represented by a line with the format of:

(#W at the left, #G at the left, #C at the left)(#W at the right, #G at the right, #C at the right) [left/right]

W: wolf, G: goat, C: cabbage, left/right: position of the boat.

For example: 

We've created the function to print outputs from the variable set, so you just need to add your solutions to the variable set<list<State>> _solutions. You don't have to worry about the order of your solutions.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given a sequence A = a₁, a₂, ..., a_N and a number K.

A continuous subsequence A[L ... R] = a_L, ..., a_R of  A is called beautiful if the sum of A[L ... R] is K.

For example, if A = 3, 1, 2, 2, 4 and K = 6.

Then

• A[1, 3] = 3, 1, 2 is beautiful.
• A[1, 4] = 3, 1, 2, 2 is not beautiful because 3 + 1 + 2 + 2 is not 6.
• A[4, 5] = 2, 4 is beautiful.

Please find the number of beautiful continuous subsequence of A.

Input

The first line of the input contains a number T — the number of test cases.

The first line of each test case contains two numbers N K — the length of A and the number K described in the statement.

The second line of each test case contains N numbers — a₁, a₂, ..., a_N.

For each test,

1. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
2. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
3. T ≤ 10, N ≤ 10³, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
4. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
5. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.
6. T ≤ 10, N ≤ 10⁵, |a_i| ≤ 10⁹, |K| ≤ 10⁹.

Output

For each test case, print the number of beautiful continuous subsequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

On your way to the Delta Building for class as usual, you accidentally tripped. Just when you were angry and wanted to kick the stone that tripped you away, you found that it was not an ordinary stone, but a magical black box.

The box is amazing, you can add or remove some numbers to it, and you can even ask it some questions. 'The box is so cool, if I can make a same one, I can definitely sell it for a lot of money', you think.

You can do five operations to the black box:

1. 1 k x: add number x into the box k times 
2. 2 k x: remove number x in the box k times, if number x in box is fewer than k, just remove all x
3. 3 x: ask how many x are in the box
4. 4: ask the maximum number in the box, if there are no number in the box, the box will answer you "The box is empty."
5. 5: ask the minimum number in the box, if there are no number in the box, the box will answer you "The box is empty."

If you want to become rich, please make a same magical black box. 

Input

The first line contains an integer N -- the number of operations you will do to the black box.

The next N lines will be the operations as above.

1 <= N <= 2e5.

1 <= k <= 1e9.

-1e9 <= x <= 1e9.

Output

For the third operation, please output how many x are in the box.

For the fourth operation, please output the maximum number in the box, if there are no numbers in the box, output "The box is empty."

For the fifth operation, please output the minimum number in the box, if there are no numbers in the box, output "The box is empty."

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In Object-Oriented Programming (OOP), the inheritance among classes represent ``is-a'' relationships for abstractions. Graphs and trees are both fundamental for computer science. In fact, a tree is a special case of a graph that is connected as well as acyclic.

In fact, we often implement trees and graphs by similar means in practice. For instance, we tend to store trees and graphs by adjacent matrice or lists. Moreover, we traverse trees and graphs in alike ways.

For simplicity, we only consider basic operations on trees and graphs. You need implement BFS traversal for a graph starting from a given source and returning the distance to all other vertices so that trees could inherit that method. Furthermore, you should find the diameter (the longest distance in a tree that we've encountered several times but solved by DFS then) by BFS traversal.

Input

Please see the instructions in the header. BFS traversal would be called with the source. As for diameter, there's no parameter.

It's guaranteed that the graph is connected and simple, and that the number of vertices of a tree is less than 100000.

Output

For BFS traversal, you should return a vector of n integers indicating the minimum distance from source.

As for the diameter, you should return an integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss