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

Electric Mingw is a handsome and electric rich man. Nevertheless, he has a weird hobby to collect resources in his own recyclables depot which is located at the upstream of Golden River, containing items ranging from golden tiolet to recyclable plastic.

Since the recycled resources he collected are too many, Enmingw decides to hold an auction of recycled resources, offering various combanations.

Your task is to compute the number of pairs of recycled resources whose sum of values is equal to \(V\).

Note

TL; DR

What's the difference between set/map and unordered_set/map? Overall, their behaviors are alike. We could deem them as the same Abstract Data Types (ADT) implemented in different approaches. set/map are based on Red-Black Tree (a self-balanced Binary Search Tree), while unordered_set/map are hash tables. In fact, they're declared by polymorphism in Java, a more Object-Oriented language.

A balanced BST could perform insertion and deletion in \(O(\log N)\) even despite of the worst case, whereas a hash table has a average \(O(1)\) time complexity in amortized analysis yet decline to \(O(N)\) when collision, i.e., different keys have the same hash value, occurred.

Though hash tables are faster than BSTs in the most cases, it's easy to construct test cases which lead to many collisions, if we know the hash function the hash table used. So everytime you use unordered_set/map, be care of this pitfall.

So how to avoid this? We could use other hash tables and custom hash function (random and/or time-dependent argument), or simply use set/map alternatively.

Input

There is an integer \(N\) in the first line, indicating the number of recycled resources to be auctioned.

The next line contains \(N\) integers \(a_i\), representing the values of each recycled resource.

The test case is ended by an integer \(V\) mentioned above.

\[1\leq N\leq10^6,0\leq a_i\leq10^6,-2^{31}\leq V<2^{31}\]

Output

For \(V\), please print out an integer which is the number of \((i, j)\) such that \(i<j\land a_i+a_j=V\).

Remember to put a new line character at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss