| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13732 | Easy Domo Problem! |
|
| 13741 | Find A Way Out For Domo! |
|
| 13763 | Portal maze mid2 version |
|
Description
Domo is facing his midterm 2 and wants to get a good grade. Otherwise, he will be punished and his dinner will be reduced.
He wants to have a perfect dinner after this midterm. Can you help him?
There're N problems in this midterm, and each problem has different point. Since Domo does not have enough time to finish all of them, he can only finish K problems among them.
What is the maximum point Domo can get?
Input
The first line contains two integers N and K (1 ≤ N ≤ 10000, 1 ≤ K ≤ N)
The second line contains N integers (a1 ... an), describing the point you'll get when you solve each problem. (1 ≤ ai ≤ 106)
Output
Output the maximum score you can get, and print a newline character at the end of the line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Domo is a brilliant dog. He needs to find the shape of the key to get out of the room, otherwise, he will not catch up with the FIFA final.
Domo has a key in his hand and wants to modify the shape of this key to match the correct key for this room.
Given the original key and the target key, please find out how many ways Domo can get the target key with exactly K operations.
The key will be a grid that consists of N rows and M columns, which contains exactly one 'x' and others are '1' and '0'.
In each operation, you can swap 'x' with the adjacent element. The element (i, j) is adjacent to the element (i-1, j-1), (i-1, j+1), (i+1, j-1), (i+1, j+1) if it's in the bound.
There're 2 methods for the sample input 1.
Input
The first line consists of three integers N, M, and K. (1 ≤ N, M ≤ 102, 1 ≤ K ≤ 5)
For the next N line, each line consists of M elements, describing the shape of the key in Domo's hand.
For the next N line, each line consists of M elements, describing the correct shape of the key of this room.
Output
Print the number of ways Domo can get the target key with exactly K operations.
Print a newline character at the end of the line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are T tasks you have to solve. In each task, you are given a maze which is a n x m grid. Each cell is marked exactly one character. In the begining, you are at starting point. You need to answer whether it's possible to go to destination. Here are the rules:
- The cell marked '$' is starting point and the cell marked '&' is destination. There must be exactly one starting point and exactly one destination.
- The cell marked '#' is wall, you cannot be at that cell.
- Suppose you are at the cell (i, j), you can go to adjacent cell(i.e (i-1, j), (i, j-1), (i, j+1) and (i+1, j)) if the cell you want to go is not out of bounds and is not marked as '#'.
- If you are at the cell marked lower case letter, you will be send to the cell marked in corresponding upper case letter. But not vice versa. That is if you are at the cell marked upper case letter, nothing will happen. So you can imagine that they are one-way portal. For every existing lower case letter, there must be exactly one corresponding upper case letter. And vice versa.
The folloing show how to go to destination for the first and the third task in Sample.
$b.#. $a.#.
...#B ...#A
...## #..#.
##..& ...#&
.#.#.
-the first task -the third task
Note: be carefule of the efficiency of your strategy.
Input
The first line contains an integer T (1 ≤ T ≤ 10) – the number of tasks you have to solve.
For each task, first there are two integers N, M (2 ≤ N, M ≤ 300) – the gridsize of the maze. Then following N lines contain M characters each, the j-th element in the i-th line Sij is the character marked for the (i, j) cell(Sij must be '$' or '&' or '#' or '.' or letter).
Output
For each task output "Yes" if it's possible to go to destination. Otherwise output "No". Then print a newline('\n').