问题 A: Merge Sort[Easy]

Description

题目描述

 

Merge sort is a widely known sorting algorithm. In each step of merge sort, it sorts two arrays and combine them to one sorted array. Now, Joy has already implemented sorting algorithm successfully, but he does not know how to combine the two sorted arrays to one. Can you help Joy?

 

输入

 

First line will be a positive integer T (T<=15), which is the number of test cases.

 

In each test case, the first line will be two integer n and m, which are the lengths of the two arrays. The second line will be the terms of the first array. The third line will be the terms of the second array.

 

(1 <= n, m <= 100000, the combat values will in the range of [0, 109])

 

 

 

输出

 

For each test case, print the combined array.

 

样例输入

 

 

2

 

4 5

 

1 2 3 4

 

1 2 3 4 5

 

• 3

 

2

 

• 3 4

 

样例输出

 

 

1 1 2 2 3 3 4 4 5

 

1 2 3 4

 

问题 B: Combine polynomials[Easy]

 

题目描述

 

Linked List is one of the most simple and basic data structure, thus has a very wide application. For example, linked list can be used to calculated the sum of two polynomials. Now, giving you two polynomials by the coefficient and exponent of each term, please output the sum of the two polynomials.

 

输入

 

First line will be a positive integer T (T<=100), which is the number of test cases.

 

The first line will be an integer n, which is the number of terms of the first polynomial. Then n lines will be the coefficients and exponents of the terms.

 

After n + 1 lines, there will be an integer m for the number of terms of the second polynomial. And m lines of (coefficient, exponent) pairs.

 

(0 <= n, m <= 1000, all exponents are in the range [0, 109], all coefficients are in the range [-10000, 10000])

 

输出

 

For each test case, print the polynomial in ascending order of each exponents. Be attention to the format of the polynomial.

 

样例输入

 

 

2

 

2

 

• 2

 

2 3

 

2

 

2 2

 

• 4

 

2

 

2 0 -2 1 2

 

3 1

 

• 2

 

样例输出

 

 

3x^2+2x^3+x^4

 

2+x+x^2

 

 

 

 

 

 

问题 C: HuaXin BookStore[Easy]

 

题目描述

 

HuaXin bookstore is a not so famous bookstore. However, it still attracts many people to go there every day. Now, there are serveral kinds of books in HuaXin bookstore. Each kind of book has an amount of ai (1 <= ai <= 20). People come to HuaXin bookstore to find the book he(she) wants to read. But after statistics, the boss found that some customers may leave without having a look of the book if there is no book available. And the customers who enters with no book to read will only hang in the bookstore without looking any book before he leave. Your task is to write a program that tells the boss how many customers left without having a look of the book.

 

输入

 

The input consists of data for one or more kinds of books, followed by a line containing the number 0 that signals the end of the input. Data for each kind of book is a single line containing a positive integer, representing the amount of this kind of book, followed by a space, followed by a sequence of uppercase letters. Letters in the sequence occur in pairs. The first occurrence indicates the arrival of a customer, the second indicates the departure of that same customer. No letter will occur in more than one pair.

 

输出

 

For each kind of book, output the number of customers walked away.

 

样例输入

 

 

• CBBCJJKZKZ

 

3 GAKKBDDBAGNN

 

3 NACCQNDDQAEE

 

0

 

样例输出

 

 

0

 

1

 

0

 

 

问题 D: Differentiate the polynomials! [Medium]

 

题目描述

 

Joy is now working on a project including bunches of mathematical problems. However, as you know, Joy is not good at math.(You can assume he is not good at everything) He wants to get a program to calculate the differentiate of polynomials.

 

输入

 

 

 

 

First line will be a positive integer T (T<=100), which is the number of test cases.

 

The first line will be an integer n, which is the number of terms of the polynomial. Then n lines will be the coefficients and exponents of the terms.

 

(0 < n<= 1000, all exponents are in the range [-1000, 1000], all coefficients are in the range [-1000, 1000])

 

 

 

输出

 

For each test case, print the polynomial in ascending order of each exponents. If there exists several terms with the same exponent, you should add them up. Be attention to the format of the polynomial.

 

样例输入

 

 

2

 

2

 

• 2

 

2 3

 

2

 

• -2 -2 3

 

样例输出

 

 

2x+6x^2

 

-2x^-3-6x^2

 

 

 

问题 E: Three Body[Medium]

 

题目描述

 

Three body is a very popular book among teenagers. It tells us there are some planets that are far away from us but can destroy earth as easy as killing an ant. Suppose one day, the most powerful planet begins to kill other planets. We suppose other planets are arranged in a circle. It destroys other planets in the following way:

 

From among n planets, numbered 0,1, 2, . . ., n-1, standing in circle. The first round starts from the planet numbered 0. Every round the (m + 1)th (we call m the destroy number) planet is going to be destroyed, after that, the planet right after it becomes the first planet in the next time. The most powerful planet consecutively attack other planets until all other planets are destroyed.

 

Now, give you the index of earth, please determine whether the earth is the last planet to be destroyed.

 

输入

 

First line will be a positive integer T (T<=100), which is the number of test cases.

 

For each test case, the line will be n and m and e, indicating the number of planets, the destroy number, and the index of earth.

 

(1 <= n, m <= 100, 0 <= e < n)

 

输出

 

For each test case, if earth is the last to be destroyed, output a line containing “Yes”, otherwise output a line containing “No”.

 

样例输入

 

 

3

 

3 4 0

 

3 4 1

 

3 3 1

 

样例输出

 

 

Yes

 

No

 

Yes

 

 

 

 

 

 

问题 F: Joy’s New Job[Hard]

 

题目描述

 

Macau casino has a popular game: horse racing. However, the rule is different from the normal ones. It is guessing the kth fastest horse. Joy wants to apply a job in the casino. But his boss give him a test, he can get the job only if he pass the test. It is as follows:

 

Given the strength of n horses, (to simplify, the strength of the n horses is a permutation of 1 to n, and horse with larger strength run faster), the boss wants to know the sum of all the kth fastest horse in every consecutive interval of the n horses, and remember only the intervals equal or longer than k should be considered.

 

Joy is not good at math, so he turns to you for help.

 

输入

 

There is only one integer T (1 <= T <= 10) in the first line, denoting the number of test cases.

 

For each test case, the first line consists of two integers n and k.

 

k <= min(n, 80), the sum of n in all test cases does not exceed 5 * 105

 

The second line is the strength of the n horses.

 

输出

 

For each test case, output a line containing the answer.

 

样例输入

 

 

1

 

5 2

 

1 2 3 4 5

 

样例输出

 

 

30

 

 

问题 G: Casino Finance Work[Hard]

 

题目描述

 

Under your help, Joy finally get the job in casino. The boss of the casino is very busy, he can only go to the casino one time every two days. When the boss goes to the casino, he asks Joy to give him the median of the past days’ turnovers. The median is the number in the middle of an array after sorting it. As you know, Joy is not good at math, he turns to you again!

 

Now given the turnovers for n days, the boss will come to casino on the first day, and the third day, the fifth day… Please help Joy write a program to output the median of the turnovers when boss comes.

 

输入

 

The first line will be an integer T(1 <= T <= 10), which is the number of test cases.

 

For each test case, the first will be an integer n. Then there will be n integers, a[i].

 

( 1 <= n <= 300000, 0 <= a[i] <= 300000)

 

输出

 

For each test case, output the median every time the boss comes.

 

样例输入

 

 

1

 

5

 

1 2 3 4 5

 

样例输出

 

 

1 2 3