Description

Out of the N NTHU 2015 Computer Science (CS) majors, X of them take the course CS13550* Introduction to Programming (I), Y of them take the course CL10100* College Chinese, and Z of them take none of the two courses (i.e., CS13550* and CL10100*). How many NTHU 2015 CS majors take both of the two courses? And how many take CS13550* but not CL10100*?

Input

Four integers N, X, Y, Z which are separated by blanks. Note that 0<N<1000, 0<X<1000, 0<Y<1000 and 0<Z<1000.

Output

Two integers separated by a blank. The first integer is the number of NTHU 2015 CS majors who take both CS13550* and CL10100*, and the second one is the number of NTHU 2015 CS majors who take CS13550* but not CL10100*. Note that you do not need to print '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There were n rows of seats in the classroom. Each row of seats littered with a_i unit of trash. 

For example: first row contained a₁ unit of trash

The janitor wanted to know how many units of trash were littered among row l to row r?

For example: If janitor ask you about row l = 3 to row r = 6. You should answer a₃ + a₄ + a₅ + a₆ unit of trash.

There will be q queries, help janitor  find out the answer so janitor  can clean up the class room.

Note that because janitor  is furious about picking up trash, each number will be follow by a symbol " (/`A`)/ ~I__I " without quotation mark and then there is a blank to separate from the next number.

Note that if you use a loop to get the sum of a_l ~ a_r at each query you will get an Time limit exceed. 

You can use prefix sum to solve this problem

Input

input contains several lines.

First line contains two integer n(1 <= n <= 10⁶), q(1 <= q <= 10⁵) -- the number of rows and the number of queries.

Second line contains n integer a₁ ~ a_n (0 <= a_i <= 10⁹), and each interger followed by a symbol " (/`A`)/ ~I__I " and then there is a blank to separate from the next number.

The following q lines each lines contains two integers l, r ( 1 <= l <= r <= n )

Output

output contain q lines, to each query output the sum of a_l ~ a_r. remember to print \n at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Long long long long long long long long long long time ago, there's a lovely kingdom named "Chess". There's King, Queen, Knight, Castle, Bishop, ...etc. Just like the modern game "chess". 

A king definitely have not only one castle or knight. But no one says that a king shouldn't have two or more queens (same as queen, a queen is able to have two or more kings). Now in this kingdom, the king has N queens. 

However, all the queens want to get the title "King's favorite", if one is uglier than the other one (which is judged by the king), then just win by manner. If one is more rude than the other one, then just win by skills. But if a queen loses on everything...... then just let them disappear or die "accidentally"...HEHEHE..... The king soon realized that, for the safety of all of his lovely queens, he must make them cannot see each other. 

Now, the king ask you, the mighty programming knight, for a mission. They want to find out how many possibilities that the queens won't launch a war in the palace.

---

• There are N queens in the palace.
• The palace is just like a chessboard with size N*N. 
• Queen can see all people in 8 directions(←, ↑, →, ↓, ↖, ↗, ↘, and ↙. Just like what queen in the chess does). If any queen see other queens, the mission will fail. 
• Find out the total amount of states that all queens are placed in the palace and mission isn't fail.

Warning! Do not just look up the answer table! You are supposed to solve this problem by recursive. Otherwise you will regret it!

Input

The input contains exactly one number N. 

1 <= N <= 14.

Output

Output only one number ── the total amount of states that queens are placed in the palace and mission isn't failed.

Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

And now my watch begins.

~by a binge watching man

Your a lord commander of the night's watch. You wants to choose some men to be your soldiers while other lords also needs to choose some men. There're n lords and n soldiers and there're k lords who are your friends therefore they will follow your order. And each soldier's ability is represented by a number ai. Since the lords stand in a line and wait for their turn to choose, you are standing in the m-th position.

Given a sequence of numbers a1 ~ an. n people standing in a line to choose one number from the sequence.

Each person can only choose a number from the head or the tail of the sequence.

Once a number is chosen, it will be remove from the sequence.

You are at m-th position of the line.

You want to get the number as big as possible.

You can command at most k people to choose what you want them to choose(head or tail).

But you can not change your command during the choosing process.

And those who you don't give a command will choose arbitrarily.

Your task is to find out what is the greatest integer x such that, no matter what are the choices of the others you didn't choose to control, the element you will take from the array will be at least x?

 

Example:

If there are n=6 numbers 2, 9, 2, 3, 8, 5.

You are at m=4 position.

And you can control k=2 people.

If the first person ordered by you choose tail 5.

The second person ordered by you choose head 2.

Then the third person can choose either 9 or 8.

No matter what the third person choose, you can get at least 8.

Therefore the answer is 8.

Input

The first line of input will be t(1 <= t <= 10) means number of testcases.

Each testcases contains two lines.

First line contains three integers n( 1 <= n <= 5000), m(1 <= m <= n), k(0 <= k <= n-1).

Second line contains n integers ai(1 <= ai <= 10^9).

Output

For each testcases, print a single integer x.

Each output is ended by \n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I'm a salary thief who don't answer students' question

~by anonymous TA

"I sucked!" TA think he's the worst, therefore he only asks you to do some cut and paste.

You got a string and your cursor is at the leftmost position of the string.

Let's call the leftmost position of the string position 0.

The string only contains character '1'~'3'.

You need to move the cursor to the right x times.

Each time only cross one character.

After the move, you divide the string into two part.

You cut the right part, and paste it for n times.

For n = the last character of left part of the string.

You need to answer how long the string is after x moves.

Because the string may be very long, you only need to answer the length of the final string mod 10^9+7(output positive number)

We guarantee that each move will not on empty character​. 

Example:

Given x = 5, string = "231"

Move 1(position 0->1):

cut the string "231" -> "2" and "31"

the last character of left part of the string = "2"

past "31" for 2 times, we got "23131"

Move 2(position 1->2):

cut the string "23131" -> "23" and "131"

the last character of left part of the string = "3"

past "131" for 3 times, we got "23131131131"

Move 3(position 2->3):

cut the string "23131131131" -> "231" and "31131131"

the last character of left part of the string = "1"

past "31131131" for 1 times, we got "23131131131"

Move 4(position 3->4):

cut the string "23131131131" -> "2313" and "1131131"

the last character of left part of the string = "3"

past "1131131" for 3 times, we got "2313113113111311311131131"

Move 5(position 4->5):

cut the string "2313113113111311311131131" -> "23131" and "13113111311311131131"

the last character of left part of the string = "1"

past "13113111311311131131" for 1 times, we got "2313113113111311311131131"

 

The final string "2313113113111311311131131" has length 25.

The answer will be 25%(10^9+7) = 25

Input

First line contains one integer t(1 <= t <= 10) which means the number of testcases.

Each testcase contains two lines.

First line contains one integer x(1 <= x <= 10^6)

Second line contains a string. ( 1 <= length of the string <= 500)

Output

For each testcase, print only one positive number which means the length of the final string mod 10^9+7

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. Only C only allowed. Solving problems with other languages (e.g. python, java) are forbidden, otherwise you'll get zero point.

2. Paper references, electronic devices, or other items that may contain any information relative to this exam are not allowed.

3. Before leaving, please tell TAs, we'll check if your accepted / partially accepted submissions are all written in C . After you pass the check, you may sign your name as a record and leave.

4. The score of each problem is shown below:

   • 12733: 7 points

   • 12179: 5 points

   • 12661: 5 points

   • 10728: 9 points

   • 12125: 9 points

If you get partially correct in a problem, your score of the problem will be

• score of the problem * number of testcases you passed / number of testcases

For example, if score of a problem is 10 points and the problem contains 6 testcases. If you pass the 3 testcases, you'll get 10*3/6=5 points on this problem.

學號	總分	11617(7分)	12134(9分)	12137(5分)	12138(5分)	12139(9分)
105000037	33.25	5.25	9	5	5	9
105000040	23	0	9	0	5	9
105000043	23	0	9	0	5	9
105041042	34.16667	7	9	5	4.166667	9
106010019	35	7	9	5	5	9
106011172	9	0	9	0	0	0
106011207	0
106031131	35	7	9	5	5	9
106031245	28.33333	7	9	0	3.333333	9
106032024	0
106081035	33.25	5.25	9	5	5	9
107000125	0
107000237	23	0	9	0	5	9
107011129	35	7	9	5	5	9
107011217	35	7	9	5	5	9
107012063	0
107020086	35	7	9	5	5	9
107021121	35	7	9	5	5	9
107021216	35	7	9	5	5	9
107031208	35	7	9	5	5	9
107034004	35	7	9	5	5	9
107034025	14	0	9	5	0	0
107072150	35	7	9	5	5	9
107080004	12.16667	0	9	1.666667	0	1.5
107195020	33.25	5.25	9	5	5	9
107195024	35	7	9	5	5	9
107590012	21.33333	0	9	0	3.333333	9
108000121	35	7	9	5	5	9
108006262	28.25	5.25	9	0	5	9
108020013	29.75	1.75	9	5	5	9
108020024	29.75	1.75	9	5	5	9
108020026	30	7	9	0	5	9
108020037	33.33333	7	9	5	3.333333	9
108020038	35	7	9	5	5	9
108021106	33.33333	7	9	5	3.333333	9
108021114	29.75	1.75	9	5	5	9
108021207	35	7	9	5	5	9
108022130	35	7	9	5	5	9
108022205	33.25	5.25	9	5	5	9
108022211	33.25	5.25	9	5	5	9
108034015	0
108034016	0
108034025	35	7	9	5	5	9
108034030	35	7	9	5	5	9
108034047	33.25	5.25	9	5	5	9
108034049	0
108034053	0
108042018	17.58333	5.25	9	0.833333	2.5	0
108042037	23	0	9	0	5	9
108048229	35	7	9	5	5	9
108060002	31.58333	5.25	9	5	3.333333	9
108060071	17.5	7	9	0	0	1.5
108062181	0
108062224	33.25	5.25	9	5	5	9
108070003	22.25	1.75	9	5	5	1.5
108070004	35	7	9	5	5	9
108070061	29.75	1.75	9	5	5	9
108081013	35	7	9	5	5	9
108081032	35	7	9	5	5	9
108090014	12	0	3	0	0	9
108095029	9	0	9	0	0	0
108096019	30	7	9	5	0	9
108193011	0
108193045	0
108193072	0
109000162	25	7	9	0	0	9
109006207	0
109010017	30	7	9	5	0	9
109010018	35	7	9	5	5	9
109010023	31.66667	7	9	1.666667	5	9
109010071	35	7	9	5	5	9
109020002	35	7	9	5	5	9
109020005	35	7	9	5	5	9
109020015	35	7	9	5	5	9
109020021	35	7	9	5	5	9
109020038	29.75	1.75	9	5	5	9
109020039	35	7	9	5	5	9
109021124	35	7	9	5	5	9
109023023	35	7	9	5	5	9
109023026	0
109030007	33.25	5.25	9	5	5	9
109030026	16.83333	0	9	0	3.333333	4.5
109031128	35	7	9	5	5	9
109031538	0
109034030	35	7	9	5	5	9
109034055	21.33333	0	9	0	3.333333	9
109060002	28.08333	1.75	9	5	3.333333	9
109060005	35	7	9	5	5	9
109060008	23.83333	0	9	5	0.833333	9
109060009	34.16667	7	9	5	4.166667	9
109060023	24.66667	0	9	5	1.666667	9
109060035	35	7	9	5	5	9
109060041	29.75	1.75	9	5	5	9
109062234	23.08333	1.75	9	0	3.333333	9
109062316	35	7	9	5	5	9
109070003	33.25	5.25	9	5	5	9
109070014	0
109070015	35	7	9	5	5	9
109070016	28.08333	1.75	9	5	3.333333	9
109070018	0
109070020	11.33333	0	9	0	0.833333	1.5
109070022	18.83333	0	9	0	0.833333	9
109070024	23.41667	1.75	6	1.666667	5	9
109070025	35	7	9	5	5	9
109070026	33.33333	7	9	5	3.333333	9
109070028	35	7	9	5	5	9
109070030	35	7	9	5	5	9
109070034	29.75	1.75	9	5	5	9
109071018	35	7	9	5	5	9
109072133	0
109072142	35	7	9	5	5	9
109072146	0
109072242	31.58333	5.25	9	5	3.333333	9
109080001	35	7	9	5	5	9
109080002	0
109080005	30.5	7	9	5	5	4.5
109080009	0
109080018	0
109080020	9	0	9	0	0	0
109080024	0
109080025	31.5	3.5	9	5	5	9
109090012	35	7	9	5	5	9
109090019	28	0	9	5	5	9
109090031	14	0	9	5	0	0
109099010	10.66667	0	9	1.666667	0	0
1092001s	35	7	9	5	5	9
1092169s	9	0	9	0	0	0
x1091058	35	7	9	5	5	9

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss