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.

Case 1 : t <= 100, n <= 100
Case 2 : t <= 200, n <= 1000
Case 3 : t <= 300, n <= 5000
Case 4 & 5 : 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 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 & 5, 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

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 a string S, output all different possible set of K characters in the string with P paddings. And sort them in the dictionary order. A padding is expressed as an underline '_'.

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

_AB
_AC
_AD
_BB
_BC
_BD
_CD
_DD
A_B
A_C
A_D
AB_
AC_
AD_
B_B
B_C
B_D
BB_
BC_
BD_
C_D
CD_
D_D
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, a positive integer K, and a nonnegative integer P 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 & 2: T <= 15, K <= 5, P <= 2,  |S| <= 25

T, K, |S| are all positive integers, P is a nonnegative integer, and K <= |S| for all test cases.

Output

For each test case, print all different possible sets 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

Implement a queue of numbers that supports the following operations:

1. print: print the content of the queue, from beginning to end
(use # to specify the end of queue)
2. enqueue: add a number at the end of the queue
3. dequeue: remove a number from the front of the queue
4. delete-mid: remove the item in the middle of the queue, if the queue has odd number of items. Otherwise, remove the two items in the middle of the queue if the queue has even number of items.  
(Do nothing when the queue is empty)

Assuming we start with an empty queue, our target is to perform a sequence 
of operations specified by the input.
 

Input

Each line contains one operation. The input is terminated by end of file. (EOF)

Operations in all cases will be less than 1000.

Output

For each print operation, print the content of the queue, from beginning to end. Use # to specify the end of queue. Each number and # should be separated by a blank. Note that there is no blank after #. See the Sample Output below.

Sample Input  Download

Sample Output  Download

Tags

Discuss