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

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 toilet to recyclable plastic.

Since the recycled resources he collected were too many, Enmingw held an auction of recycled resources, offering various combinations, which was mentioned in Problem 13526. Now there still remains a few recycled resources (less than \(5000\) left). As a consequence, He'd like to have another clearance sale. This time, a combination would contain \(3\) items.

Your task is to compute the number of tuples of \(3\) 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.

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\leq5\times10^3,0\leq a_i\leq10^9,0\leq V\leq3\times10^9\]

Output

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

Remember to put a new line character at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss