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

 

X missionaries (傳教士) and Y cannibals (食人族) must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals. If they were, the cannibals would eat the missionaries. The boat cannot cross the river by itself with no people on board. Initially, they are all on the left bank.

List all possible solutions to the given X and Y.

This is a Partial Judge problem.

We define a "State" as follows:

// A state contains five components:
// The first two components denote the current numbers of
// missionaries and cannibals at the left bank of the river.
// The third and fourth components denote the current numbers
// of missionaries and cannibals at the right bank.
// The fifth component denotes the location of the boat:
// 1 means "left bank" and -1 means "right bank".
using State = vector<int>;

Basically, you need to implement five functions:

// the starting porint of your implementation
void solve();
// extend to other possible states from a certain state
set<State> extend(State s);
// may use s[4] to indicate the direction of move
State Go(State s, int missionary, int cannibal);
// check the validity of a state
bool valid(State s);
// check if all people are at the right bank
bool found(State s);

Notice that, if you don't want to follow the scheme we provide, you can just implement the sovle() function and make the others blank, e.g. bool found(State s) { }.

Input

A single line containing two integers seperated by a space.

The first number is X denoting the number of missionaries. The second number is Y denoting the number of cannibals.

Actually, you don't need to worried about the input, we handle it for you.

Output

List all possible solutions one by one. "done" denotes the end of a solution.

A solution contains several moves. A move is represented by a line with the format of:

(#M on the left bank, #C on the left bank)(#M on the right bank, #C on the right bank) [left/right]

M: missionary, C: cannibal, left/right: of the boat.

There is 

Just like below,

 

Also, we've already handled the output functionality for you, so you don't have to worried about this, either.
You just need to add your solutions to the variable set<list<State>> _solutions and the order of addition doesn't matter.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11495.cpp

Partial Judge Header

11495.h

Tags

Discuss

Description

Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find out all the possible methods to fill this N-liter empty container using the provided smaller containers. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.

For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, all the possible methods are listed below:

1. 1 container of 10 liters, 1 container of 5 liters, and 2 containers of 1 liter.
2. 1 container of 10 liters, 0 containers of 5 liters, and 7 containers of 1 liter.
3. 0 containers of 10 liters, 3 containers of 5 liters, and 2 containers of 1 liter.
4. 0 containers of 10 liters, 2 containers of 5 liters, and 7 containers of 1 liter.
5. 0 containers of 10 liters, 1 container of 5 liters, and 12 containers of 1 liter.
6. 0 containers of 10 liters, 0 containers of 5 liters, and 17 containers of 1 liter.

Note that

1.      This problem involves three files.

• function.h: Function definition of filliing and showResult.
• function.c: Function describe of filling and showResult.
• main.c: A driver program to test your implementation.

You will be provided with main.c and function.h, and asked to implement function.cpp.

2.     For OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

function.h

main.c

 Hint 

You can use the following incomplete code of function.c to solve this problem.

function.c

Input

The input contains three lines.

The first line contains an integer M (0<M<=5) which represents the number of different size containers.

The second line contains M numbers, S1 ,S2 , …, SM. Si represents the size of the i-th container. Note that these M numbers are in decreasing order.

The third line contains an integer N (0<M<100) which represents the size of the empty container.

Output

Display all the possible methods to fill the empty container. Each line represents a method in the format “(C1,C2,…,CM)”, where Ci represents the number of the size Si container.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10832.c

Partial Judge Header

10832.h

Tags

Discuss