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

Price of fertilizers in the world are raising! Adding Jinkela in fertilizer, one bag can cover two bags!!

People from America, Africa, Japan are lining up in a queue to buy Jinkela. Each person is given a unique id x. The country of each person can be identified by the remainder of his id divided by 3. If x mod 3 = 0, he is from America; if x mod 3 = 1, he is from Africa; if x mod 3=2, he is from Japan. Lining up is tedious, everyone wants to cut in line! These American, African, and Japanese follow some rule when they cut in line:

When a person enters the queue,

1. If the queue is empty, he becomes the first person in the queue.
2. If there isn't anyone who comes from the same country in the queue, he becomes the last person in the queue.
3. Otherwise, of all people coming from the same country in the queue, he finds the last of them and lines up after him ( and possibly cuts in line ).

After a person buys Jinkela, he leaves the queue immediately and will not enter the queue again.

You are curious about the order people get their Jinkela. Given the status of the queue. Whenever someone leaves the queue, output his id.

Refer to the sample IO for example if you don't understand the rule.

For example, assume the queue is empty initially.

• ENQUEUE 0: An American with id 0 enters the queue. Since the queue is empty, he becomes the first person in the queue

queue: 0

• ENQUEUE 1: An African with id 1 enters the queue. Since there isn't any other African in the queue, he becomes the last person in the queue.

queue: 0 1

• ENQUEUE 3: An American with id 3 enters the queue. Since he finds an American (id=0) in the line, he lines up right after him.

queue: 0 3 1

• ENQUEUE 6: An American with id 6 enters the line. He finds two American (id=0, id=3) in the line, where American with id 3 is the last one, he lines up after American with id 3.

queue: 0 3 6 1

• DEQUEUE: The first person leaves the line. Output his id(0).

queue: 3 6 1 output: 0

Input

The status of queue is represented as several commands.

The first line of Input consists of a single integer n (n ≦ 10^6), indicating there are n commands in total.

The following n lines are the commands. There are two kinds of commands:

• ENQUEUE x: person with id x enters the queue. x is an integer, 0 ≦ x ≦ 10^6
• DEQUEUE: the first person in the queue buys his Jinkela and leaves the queue

Output

For each DEQUEUE command, please output the id of person who leaves the queue.

Each output occupies a single line.

Sample Input  Download

Sample Output  Download

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 3 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.

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

You start the game with full HP and level 1. What is the minimun number of rounds you need to kill the monster?

Input

First line contains 4 numbers L, HP, MHP, MDMG.

• L = max level
• HP = your max HP
• MHP = monster's HP in the beginning of game
• MDMG = monster's damage point

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:

• L <= 15
• HP <= 300
• MHP <= 400
• MDMG <= 10000
• DMG <= 10000
• HL <= 50

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.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Since we are now undergoing the covid-19 pandemic, the CECC(疫情指揮中心) announce that two people should keep space between themselves at a social distance at s meters.

Inside a classroom, there are n seats numbered from 1 to n in a row and there are walls on the left of the 1-st seat and on the right of the n-th seat. m students numbered from 1 to m are coming to class. The distance between to neighboring seats or walls is 1 meter. Initially there are no people on the seats.

Each student takes a seat and leaves the seat at some time and they will take the seat that is farthest from the wall and the other people. If there are multiple seats to choose from, he or she will choose the leftmost one (i.e. the seat with smallest number).

More detailed description of how a student pick a seat:

Let D be minimum distance between any two people (note that walls are not people) during the whole class. If D >= s then we say the class is safe, otherwise it is not safe.

Given the time when each student enters and leaves classroom. Your professor wants to know whether he is clockwise whether he follows the CECC's rules , so he wants you to write a program to calculate the value of D and tells him if the class is safe or not.

Explanation for sample IO

Let d be the minimum distance between any two people at a specific time.

0. _ _ _ _ _ _ _ _ _, d = INF

1. _ _ _ _ 1 _ _ _ _, d = INF

2. _ 2 _ _ 1 _ _ _ _, d = 3

3. _ 2 _ _ _ _ _ _ _, d = INF

4. _ 2 _ _ _ 3 _ _ _, d = 4

5. _ _ _ _ _ 3 _ _ _, d = INF

6. _ _ _ _ _ _ _ _ _, d = INF

During the whole class min d = 3, therefore D = 3 < S = 5, it is not safe.

Input

The first line are three integers n m s (mentioned in problem description).

Then there are 2 x m lines, each line represents the event that one student enters or leaves the classroom. For the k-th line:

• i x means that the student with number x comes in the classroom and takes a seat at time k

• o x means that the student with number x leaves the seat and goes out the classroom at time k

It is guaranteed that:

• A student will never comes back to class after he or she leaves

• When a student leaves, he or she must be in the classroom (i.e. for a student x, i x must appear before o x)

Technical Restrictions:

• For first test case:

  • 1 <= m <= n <= 10

  • 1 <= s <= 10

• For second test case:

  • 1 <= m <= n <= 2000

  • 1 <= s <= 2000

• For third test case:

  • 1 <= m <= 2000

  • 1 <= m <= n, s <= 10^9

• For fourth and fifth test case:

  • 1 <= m <= 10^5

  • 1 <= m <= n, s <= 10^9

Output

Please output D (If D is infinity, then print "INF").  Please output "YES" if it is safe and "NO" if it is not safe.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The goal of this problem is to transform the arrangement of tiles from the initial arrangement to a goal arrangement.

The legal moves are the moves in which the tiles adjacent to the empty tile are moved to either left, right, up, or down.

Your goal is to find the minimum move to solve the problem.

ouo.

hint

Using BFS/DFS to find answer may exceed memory limit and time limit of some test cases, so we recommend using A* algorithm,  which is more efficient. In A* algorithm, it determine the direction of searching by “steps until now + heuristic value”.

A* algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm

To improve heuristic function, you can adopt manhattan distance with Linear Conflict.

Manhattan distance: https://en.wikipedia.org/wiki/Taxicab_geometry

Linear Conflict: The tile set(t1, t2) is linear conflict if they have same goal row(column), and they are now in that row(column), but they are blocked by each other. A set of lenear conflict will cause at least two extra steps.

Input

Input contains 4 lines, each line has 4 numbers.

The given puzzle is guaranteed to contain numbers from 0 ~ 15.

The zero denotes the empty tile.

It is guaranteed that the given puzzle is solvable.

Output

Output the minimum move to solve the puzzle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Several men and women are going to attend the singles mixer (聯誼會) tonight. As the organizer, you have collected the personal score of each participant. Several independent events will occur during the party. Each event has a random lucky value e_i. If the sum of the scores of a man and a woman equals e_i, they will form a perfect pair and dance together. However, since this is a singles mixer and the events are independent, a specific man/woman may dance with a different woman/man in a different event.

Your staff has shown you the lucky value of each event. To gain more control over the party, you want to calculate whether there is a perfect pair in each event before the singles mixer.

!!WARNING!!

You may get TLE if you use std::set and the compile language C++ is chosen, instead of C++11.

Input

The first line contains 3 positive integers M, W and E, where there're M men, W women and E events.

The second line contains M integers, denoting the personal score of each man.

The third line contains W integers, denoting the personal score of each woman.

Next, followed by E lines, each line has the lucky score e_i.

Constraints:

• Cases 1~2 : either the score of every man or woman is 0
  E=200000; M+W<200000
• Cases 3~4 : either the score of every man or woman is the same (e.g. all of the men have the score of 87)
  E=200000; M+W<200000
• Cases 5~8: M+W<200000; min(M, W)*log₂(max(M, W))*E < 10⁸;

The absolute values of all scores range in [0, 10⁷).

Output

For each event, if there exist at least a perfect pair, print "Yes"  in a line; otherwise, print "No". Remember to add a '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Your goal is to find the minimum number of steps to eat all the dots inside an enclosed maze without ghosts.

The possible tiles are listed as follows:

'o': The PacMan on a tile

' ': Nothing on a tile

'.': A dot on a tile

'#': Wall

Your program only needs to deal with valid inputs. It is guaranteed that:​

• all tiles other than wall tiles are within an enclosed area formed by wall tiles;
• no more than 5 dots;
• there is at least one solution.

Example 1:

Input:

1
4 9
#########
#   o...#
# . #####
#########

Output:

9

Sequence of steps:

ASAWDDDDD

where:

• W: move the PacMan up
• A: move the PacMan left
• S: move the PacMan down
• D: move the PacMan right

Input

The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.

For each test case:

• the first line gives two integers N and M (1 ≤ N*M ≤ 256);
• each of the next N lines consists of M characters, representing the tiles of each row.

Output

For each test, output the minimum number of steps to eat all the dots inside the enclosed maze without ghosts.

Sample Input  Download

Sample Output  Download

Tags

Discuss