Description

A string is said to be valid if it matches one of the following rules:

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

Given a string consisting of parentheses, determine if it is a valid string.

Input

The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

For case 1,2 : 1<N<100. 0<=length<100

For case 3,4 : 1<N<1000. 0<=length<1000

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There’s a numberline. Initially, no point is lying on it.
Given N queries, each is one of the following two types:
1 x: Add a point x on the numberline. If x is already lying on the numberline, remove it instead.

2 x: There are a lot of segments, separated by the points on the numberline. You have to answer the length of the segments that x is lying on. If x is the endpoints of two segments, x is considered lying on the right one. Furthermore, if the length of the segment is infinite, output −1.

Constraints

• 1 ≤ N ≤ 100000
• 1 ≤ x ≤ 1000000000

Input

 

The first line contains a integer N represents the number of queries.
In the following N lines, each contains two integers, represents the query.

Output

 

For each query of type 2, outputs its answer line by line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

下載後將副檔名改成zip（.cpp和.h為相同檔案，下載一個即可）

更改副檔名教學 : 

打開任意資料夾 >> 點擊上方 "檢視" >> 勾選 "副檔名" >> 將.cpp或.h更改成.zip

解壓縮 >> 點進 reference 目錄 >> 點進 en 目錄 >> Main_Page.html  就可以看到完整的cpprefernce.com離線版

===================================================================================================

Download the partial judge code and change the extension to .zip. (.cpp and .h is the same file. Donwload one of them is enough.)

Open the folder with the file in it >> click "view" >> check "File name extensions" >> change .cpp or .h to .zip
Unzip the file >> click "reference" > click "en" >> open "Main_Page.html". Then you can use the offline version of cppreference.com.

Input

Output

Sample Input  Download

Sample Output  Download

Partial Judge Code

13930.cpp

Partial Judge Header

13930.h

Tags

Discuss

Description

You are playing a game. The goal of this game is to kill the monster when you are still alive (HP > 0, HP = health point). The monster is dead if and only if its HP <= 0.

This game consists of rounds, and you go first in each round.

You have 5 options in each round:

1. ATTACK. This will deduct the monster's HP. If your damage point is p, then you can deduct p monster's HP.
2. HEAL. You can recover some of your HP, but it can't exceed your max HP.
3. Level-up. Level-up might enhance the effect of attacking or healing, but if you are not lucky enough, sometimes it will deduct the effect of attacking and healing. Thus, choosing to level-up is not always a good choice. If you have reached max level, taking this action makes no effect.

Besides, you are also given some potions (魔法藥水), which can be used to further increase your own capability or decrease the monster's capability. Specifically,

4. Drink-potion. By drinking one bottle of potions, the effect of your next ATTACK or HEAL will be multiplied by 5. Note that: 1) this effect will only be applied once, and 2) consecutive drinking of several bottles of potions cannot stack the effect. If there are no remaining potions, this action cannot be performed.
5. Throw-potion. Throwing one bottle of potions can add one layer of poisons (毒藥) on the monster to cause X points of damage to the monster, which will take effect starting from the next round and last for each of the following rounds (that is, the monster's HP will be deducted by X in each of these rounds) until the monster dies. Note that poisons can be accumulated, meaning that accumulated P layers of poisons in a given round will totally damage P * X points in that round. If there are no remaining potions, this action cannot be performed.

In each round, the monster will attack you once with a fixed amount of damage points.

You start the game with full HP, level 1 and K bottles of potions.

What is the minimun number of rounds you need to kill the monster? What is the sequence of actions to achieve the minimum number of rounds?

Additional Requirement: Since there could be multiple possible sequences of actions, output the lexicographically smallest string representation among all the possible sequences of actions. The conversion method is as follows: start with an empty string T, and then append the corresponding letters to the string T based on the action sequence. The letters are mapped as follows:

• ATTACK → 'A'
• HEAL → 'B'
• LEVEL-UP → 'C'
• DRINK POTION → 'D'
• THROW POTION → 'E'

Input

The first line of the input contains an integer T, representing the number of test cases (1 ≤ T ≤ 5).

For each of the T test cases, first line contains 7 numbers L, HP, MHP, MDMG, K, X, FLAG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point
• K = amount of potions you have in the beginning
• X = damage point of each layer of poisons
• FLAG = 0 or 1. If FLAG = 1, you need to output the lexicographically smallest sequence of actions. If FLAG = 0, you don't.

Each of the next L lines describes each level, i-th line of them describing level i. Each of them consists of two numbers, DMG and HL.

• DMG = your damage point when you use ATTACK at level i
• HL = amount of HP you can recover when you use HEAL at level i

---

Limits:

• 1 ≤ L ≤ 10
• 1 ≤ HP ≤ 100
• 1 ≤ MHP ≤ 100
• 0 ≤ MDMG ≤ 10000
• 0 ≤ DMG ≤ 10000
• 0 ≤ HL ≤ 50
• 0 ≤ X ≤ 50
• 0 ≤ K ≤ 10
• FLAG = 0 or 1

Output

Print a single integer, denoting the mininum number of steps you need to kill the monster. If you are unable to beat the monster, print -1.

If FLAG = 1, output the sequence of actions to achieve it, each action in one line.

 

Test Case Constraints

• Testcases 1, 2: it is guaranteed that K = 0 and FLAG = 0.
• Testcase 3: it is guaranteed that X = 0 and FLAG = 0.
• Testcase 4: it is guaranteed that FLAG = 0.
• Testcase 5: it is guaranteed that X = 0 and FLAG = 1.
• Testcase 6: it is guaranteed that FLAG = 1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this world, everyone needs to work to earn money to survive.

Jobs are provided by armored men (盔甲人), and little cutes (小可愛) will try to get the jobs they want.

After working, the armored men will calculate the day's salary for each little cute.

To efficiently pay salaries to little cutes, the armored men need to track which job is chosen by which little cute. Therefore, they decided to write a program to assist them.

There are N jobs, numbered from 1 to N, and each job has a type t_i (1 ≤ i ≤ N).

Next, there will be Q events happening. Each event will have an Action and an ID. The Action can only be one of two types: {"Apply", "Quit"}. The ID represents the identification number of the little cute in the event. "Apply" means that the little cute with the specified ID wants to apply for the jobs, while "Quit" means that the little cute with the specified ID wants to quit from his jobs.

For an event where the Action is "Apply", there will be two lines of input:

• The first line contains K and Order, indicating that the little cute wants to apply for K jobs, and Order specifies the order in which the little cute prefers jobs of the same job type. The job_id (1 ≤ job_id ≤ N) should conform to the specified Order.
• The second line contains K positive integers, representing the K jobs that the little cute wants to apply for.

Note: The Order can only be one of three types: {"MIN", "MAX", "MID"}. When Order is "MIN", the little cute prefers the job with the smallest job_id. When Order is "MAX", the little cute prefers the job with the largest job_id. When Order is "MID", the little cute prefers the job with the "median" job_id.

Assuming there are J sorted job_id's, the median is defined as:

• If J is odd, the median is the job_id at the (J - 1) / 2 position.
• If J is even, the median is the job_id at the (J / 2) - 1 position.

For example:

• If job_id = {1, 3, 5, 7, 9}, the median is job_id[2] = 5.
• If job_id = {4, 5, 6, 7, 9, 10, 11, 12}, the median is job_id[3] = 7.

And once a little cute gets all his jobs, he will leave the queue; otherwise, he will stay in the queue and cry, and at last the little cute and those behind him all can't get the jobs.

For an event where the Action is "Quit", the little cute with the numbered ID wants to quit from his current jobs. Notice that the jobs he resigns from will not be returned to the armored men (盔甲人), not allowing other little cutes to apply for these jobs.

It is guaranteed that for each little cute, there will be at most one "Apply" and one "Quit" events, and the "Quit" event will always occur after the "Apply" event, meaning that a little cute can only resign after he has applied for jobs.

For each job, you should output the little_cute_id of the little cute who has taken it, or 0 if nobody does (including those returned).

Despite the crying little cute in the queue hindering (阻礙) others from applying for new jobs, little cutes with existing jobs can still take the "Quit" actions. (Please refer to Sample IO 4)

 

Sometimes, when you feel like you can't do it, just give up directly?

  

Constraints

• 1 ≤ N, Q ≤ 2 * 10⁵
• 1 ≤ t_i, ID ≤ 10⁹
• ∑K ≤ 2 * 10⁵

Subtasks

• testcases 1 ~ 3: Action only contains "Apply", Order only contains "MIN", 1 ≤ ID ≤ 10⁶.
• testcases 4 ~ 5: Action contains "Apply" and "Quit", Order contains "MIN" and "MAX".
• testcases 6 ~ 7: No additional constraints.

Input

The first line of input contains two positive integers N, Q, as described in the statement.

Next, there would be N integers, t₁∼ t_N, as the statement describes.

Finally, there would be Q events, each represented by an Action and an ID. The Action can only be one of two types: {"Apply", "Quit"}. The ID represents the identification number of the little cute in the event.

If the Action is "Apply", then you will be given a job set, represented by two lines:

1. the first line contains a positive integer K_ID, denoting the size of the ID_th little cute's job set, and a string Order, specifying the order in which the little cute prefers jobs of the same job type.
2. the second line contains K_ID integers, each denoting one of the job types in this job set.

Output

Output N integers, each integer indicating which little cute has taken the corresponding job.

Please append a space after each number, and add a newline at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given \(N\) integers \(a_1 \dots a_N\) and \(M\) queries.
In each query, you will be given one integer \(x\), please output an integer in \(a\) which is closest to \(x\).
If there are more than one such integer, please output the smaller one.

ps. We suggest you use std::set to do this problem :)

Input

The first line contains two integers \(N, M\).
The second line contains \(N\) integers \(a_1, a_2 \dots a_N\)
Each of the next \(M\) lines contains an integer \(x\).

\(N \quad M\)
\(a_1 \quad a_2 \dots a_N\)
\(x_1\)
\(\vdots\)
\(x_M\)

Constraints

• \(1 \le N, M \le 10^5\)
  
• \(0 \le a_i, x_i \le 10^9\)

Output

Please output the answer of each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss