Description

Given a string S, output all different possible set of K characters in the string. And sort them in the dictionary order.

For example, if K=2 and the given string S is ‘CDBABBD’, output

AB
AC
AD
BB
BC
BD
CD
DD

Input

The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases. For each case, there is a string S and a positive integer K in a line. The length of the S is less than or equal to 100 and  S contains only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.

For test 1: T <= 10, K <= 3,   |S| <=10
For test 2: T <= 15, K <= 5,   |S| <=25
For test 3: T <= 20, K <= 8,   |S| <=50
For test 4: T <= 30, K <= 10, |S| <=100

T, K, |S| are all positive integers, and K <= |S| for all test cases.

Output

For each test case, output all different possible set of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given several fractions, compute their sum and express the answer in the simplest fraction form.

Input

There are many test cases in one subtask.

The first line of each test case contains an integer t, which indicates the number of fractions in the input. Each of the following t lines contains two integers a and b, which represent the numerator and the denominator of a fraction.

subtask 1 : t=2. 1<=a,b<=10.
subtask 2 : t<=5. 1<=a,b<=10.
subtask 3 : t<=5. 1<=a,b<=50.
subtask 4 : t<=10. 1<=a,b<=100.

Output

Each test case outputs one line.

Namely, you need to add '\n' at the end of each line.

The output is the sum reduced to the simplest fraction form. You need to print a '/' between the numerator and the denominator.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Please compute the sum of two given n-bit binary numbers.

Input

The first line of the input file contains a positive integer t indicating the number of test cases. The first line of each test case is a positive integer n denoting the length of bits. The second and third lines are the two n-bit binary numbers. The first bit of each binary number is always 0, which guarantees that the sum of the two binary numbers can still be expressed as an n-bit binary number.

Case1 : t<=100, n<=100
Case2 : t<=200, n<=1000
Case3 : t<=300, n<=5000
Case4 : t<=400, n<=10000

Output

For each test case, your program should print the sum in the same format as the binary numbers given in input.

Notice that each answer is ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an integer sequence, say {6, 1, 3, 4, 5, 2}, can we sort the sequence by keeping swapping the first number with its two neighbors: the second number and the last number ? 

For example, Swap the first number 6 and with the last number 2 to get {2, 1, 3, 4, 5, 6}, and then swap the first number 2 and the second number 1 to get {1, 2, 3, 4, 5, 6}, and we get the sequence sorted.

In function.h we define a class called SwapSort. A constructor and a member function show_solutions are implemented. Your task is to complete the implementation of the following two functions:

1. set<State> extend(State s);
A State is defined as using State = vector<int>;
For some State s, we may extend it by swapping the first number with the second one, or swapping the first number with the last one. Therefore, from State s we may generate two new states, and insert them into a set.

2. void solve(int steps);
This function tries to solve the problem in a number of swaps specified by steps. The found solutions are stored in the class member set<list<State>> _solutions;

Notice that, no duplicate states are allowed in a solution.

You need to implement the two functions in function.cpp

main.cpp

#include "function.h" int main() { State s;// = {2, 1, 3}; int e; while (cin >> e) { // press Ctrl + Z to end the input s.push_back(e); } SwapSort prob1(s); prob1.solve(4); prob1.show_solutions(); cout << "\n"; }

function.h

#ifndef _SWAPSORT_ #define _SWAPSORT_ #include <iostream> #include <vector> #include <set> #include <list> #include <algorithm> using namespace std; using State = vector<int>; class SwapSort { private: set<list<State>> _paths; set<list<State>> _solutions; set<State> _explored; public: SwapSort(State init) { list<State> ls; ls.push_back(init); _paths.insert(ls); } void show_solutions() { if (_solutions.size()==0) { cout << "No solution.\n"; } else { for (auto p : _solutions) { for (auto s : p) { for (auto i : s) { cout << i << " "; } cout << "-> "; } cout << ".\n"; } } } set<State> extend(State s); void solve(int steps); }; #endif

function.cpp

#include "function.h" set<State> SwapSort::extend(State s) { set<State> SS; // your code here return SS; } void SwapSort::solve(int steps) { while (steps>0) { set<list<State>> oldPaths; set<list<State>> newPaths; for (auto p : _paths) { // your code here } for (auto p : oldPaths) { _paths.erase(p); } for (auto p : newPaths) { _paths.insert(p); } --steps; } }

Input

An integer sequence, separated by spaces. End by EOF.

Output

The output will be generated by function.h

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given an integer sequence, say {6, 1, 4, 3, 5, 2}, we can choose any pair of two neighboring numbers (in a circular sense) and swap them to generate a new sequence. For example,

If we choose 6 and 2, we get {2, 1, 4, 3, 5, 6} after swapping.
If we choose 1 and 4, we get {6, 4, 1, 3, 5, 2} after swapping.

Try to generate all possible results for the original sequence, and print the results in lexicographical order. For the example above, the output would be

1 6 4 3 5 2
2 1 4 3 5 6
6 1 3 4 5 2
6 1 4 3 2 5
6 1 4 5 3 2
6 4 1 3 5 2

Hint:
1. Use the set and vector containers.
2. The items in a set will be automatically sorted in lexicographical order.

main

#include <iostream> #include <vector> #include <set> using namespace std; // Define "extend" here. int main() { vector<int> v; // = {6, 1, 4, 3, 5, 2}; int e; while (cin >> e) { // press Ctrl + Z to end the input v.push_back(e); } auto S = extend(v); // the type of S will depend on the return type of extend for (auto s : S) { cout << s[0]; for (unsigned i=1; i<s.size(); ++i) { cout << " " << s[i]; } cout << "\n"; } }

Input

An integer sequence, separated by spaces. End by EOF.

Output

List all possible results for the original sequence in lexicographical order.

Each line contains one sequence, where there is a space between each number.

 Note that there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two vectors of numbers, output their intersection set.

Note: the numbers of vectors need not to be unique.

Input

There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set. All the numbers are 32 bit signed integers. The input is terminated if N = 0.

For case 1, 1 <= N, M <= 10³
For case 2, 1 <= N, M <= 10⁴
For case 3, 1 <= N, M <= 10⁵
For case 4, 1 <= N, M <= 10⁶

Output

For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print “empty” (without quotes).

Note: There's a newline character at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N numbers in a queue.  The origin sequence is from 1 to N. (1 is the head). The operation “Move a ” means to move the first two numbers to the back of a without changing order. Note that if "a" is the first two numbers then you don't need to do anything. Given several such operations and output the final status of the sequence.

For example:N = 5,then the sequence will be 1 2 3 4 5.  If Move 3, the sequence will be 3 1 2 4 5. Since that the first two numbers is 1 2,you have to move 1 2 in the back of 3.

Input

There will be only one test case. The test case begins with an integer N indicating the number of people.  There are several operations followed.  The format is “Move a” (without quote).  The test case is terminated by “Exit” (without quote).

subtask 1 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 2 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 3 : 1<=N<=100000, you need use O(1) algo for each operation.

subtask 4 : 1<=N<=1000000, you need use O(1) algo for each operation.

Output

Output the numbers from the first one to the last one, and separate two consecutive numbers by a space. You DON'T need to print "\n" or space at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Partial Judge Header

Tags

Discuss