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

There is a template function unique() in STL (Standard Template Library), which takes two iterators \(begin, end\) as parameters, removes all except the first element from every consecutive group of equal elements in the left-closed-right-open range hold by the two iterators \([begin, end)\) and return the iterator to the new end, i.e., the next of the last element not removed.

For instance, in the first of the sample input, since \(k=1\), it's equivlent to the ordinary unique(). So for the string "qqq", you should return the itrerator next to the first 'q'.

And in this problem, your task is to extend this feature more generally, i.e., remove all excpet the first \(k\) elements from every consecutive group.

Note

You should do it in place, returning valid iterator between origin range. Try to use constant extra space only.

If you want to run the code locally, you have to name your implementation Main.cpp. For more detail, please read instructions in the header.

Input

Since this problem is judged partially, you needn't be concerned about the format of input.

In case your're interested, there are several test cases, each of which contain four lines: the first line is two integers \(n, k\) and the following lines are a sring, \(n\) intergers and \(n\) floating point numbers.

\[0<n<10^6\]

\[0<k\leq n\]

Output

Since this problem is judged partially, you needn't be concerned about the format of output.

In case your're interested, for each test case, the judge code would print out the result after calling k_unique() for the sting, integers and floating point numbers.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

As a CS student, you must be familiar with command-line shell, especially the basic concept of working directory and th cd command. In fact, modern shells (even Windows' Command Propmt included!) maintain a stack (a container that holds FILO (First-In, Last-Out) principle) of directories so that we could traverse among directories easily. For the purpose of understanding the mechanism well, let's simulate the fundamental behaviors.

The paths in Unix-like OS could be divided into 2 types:

• Absolute path. Start with the root directory / and the other directories within the path (if any) are splited by /.
• Relative path. Start with one of the following terms and the other directories within the path (if any) are splited by /.
  • ~ means ones's home directory. Here suppose we're running as super user root thus it equals /root.
  • . denotes the current working directory.
  • .. represents the parent directory of current working directory. Note that if current working directory is root directory, then it's still the root directory.

For instance, ~/.ssh could be expanded to /root/.ssh.

The commands involved are listed below. Though some details vary among shells (e.g., bash or zsh) and this problem is mainly based on bash, slight difference might exist. These commands below support many other useful parameters yet too complex to implement.

• cd. Change directory.
  • If a path is given as argument than change working directory to it.
  • Else if the argument is -, change back to previous ("old") working directory.
  • Otherwise if there's no argument, change to the home directory, namely /root here.
• pwd. Print working directory.
  • No argument.
• pushd. Push directory into stack.
  • You may think of that we push current working directory into the stack, then change working directory just like cd.
  • If no argument is given, swap working directory with the top of the stack.
    • If the stack is empty, print "pushd: no other directory" (without quotation).
• popd. Pop diectory from stack.
  • Change working directory to the top of the stack.
    • If the stack is empty, print "popd: directory stack empty​" (without quotation).
• dirs.
  • Show current working directory and the directories in the stack from top.

Initally, the working directory is the home directory, /root, and we set the old working directory same.

Input

There would be at most 5000 commands. The name of each directory consists of only English letters and numbers, and the length doesn't exceed 10.

About 20% of the testcases contain only absolute paths. Another approximate 30% of the testcases don't containe paths related to .. parent of current working directory.

Assume that all paths are valid.

Output

Already mentioned in above description. Please note that for dirs command, redudant space at the end of line is not allowed.

Sample Input  Download

Sample Output  Download

Tags

Discuss