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 two arrays \(a\) and \(b\), each contains \(N\) elements. Additionally, you are given a target value \(x\) and a len \(L\).

For each element \(a_i\) in \(a\), you have to find the index \(j\) of an element \(b_j\), such that the sum \(a_i + b_j\) is as close to \(x\) as possible. Also, the search for \(b_j\) is limited to a contiguous range of elements starting from \(b_i\) and extending up to L elements or until the end of array b, whichever comes first. (i.e. \(i \le j \le min(N, i + L) - 1\))

If there are multiple \(b_j\) result in the same closest sum to \(x\), you need to output the smallest index \(j\).

Input

The first line contains three integers \(N, L, x\).
The second line contains \(N\) integers \(a_0, a_1 \dots a_{N - 1}\)
The third line contains \(N\) integers \(b_0, b_1 \dots b_{N - 1}\)

\(N \quad L \quad x\)
\(a_0 \quad a_1 \dots a_{N - 1}\)
\(b_0 \quad b_1 \dots b_{N - 1}\)

Constraints

• \(1 \le N, L \le 2 * 10^5\)
• \(1 \le a_i, b_i, x \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss