| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11291 | Mouse Maze |
|
| 12458 | Writing APP |
|
| 12979 | Diet |
|
Description
Write a program that simulates a mouse in a maze. The program must count the steps taken by the mouse from the starting point to the final point.
The maze type is shown in following figure:
S$###
$$#$$
$$$##
##$$F
it consists of S (starting point), #(walls), $(road) and F (final point).
In above case, it needs 7 steps from S to F as following figure,
S$###
$$#$$
$$$##
##$$F
and the mouse can move in the four directions: up, down, left, right. There may be more than one way to reach final point, the program only need to print the least steps.
If there is no way from S to F, then print -1.
Input
The first line has an integer N(1<=N<=10^6), which means the number of test cases.
For each case, the first line has two integers. The first and second integers R and C (3<=R, C<=500) represent the numbers of rows and columns of the maze, respectively. The total number of elements in the maze is thus R x C.
The following R lines, each containing C characters, specify the elements of the maze.
Output
Print out the least steps for each case, and there is a new line character at the end of each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
APP stands for "Another Palindrome Problem".
Given a string str with length n and an integer k, is it possible to transform str to a palindrome(回文) by removing at most k characters?
Explanation of sample io
You are given str = "fadicaf" and you can remove 3 characters at most. In this case you can remove 'd', 'i', and get "facaf", which is a palindrome. Therefore please output "Yes". Note that there may be multiple ways to transform str to a palindrome.
Maybe useless hints
Maybe useful hints
Draw the recursion tree, and then observe how many recursive function calls with same arguments are re-calculated. Is it possible to store the result of each recursive function call once it is calculated? If so, is it possible to use the results you have stored instead of re-calculate?
Input
The first line is two integers n, k, which are string length and max number of characters you can remove.
The second line is a string str.
-
1 <= n <= 1000
-
1 <= k <= 20, for the 1-5 th test case
-
1 <= k <= 1000, for the 6 th test case. Some tricks must be applied to pass this test case.
-
str is of length n, consisting of lower case characters (a-z) only
Output
Output "Yes" (without quotation mark) in a line if str can be transformed to a palindrome by removing at most k characters, otherwise output "No" (without quotation mark) in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are n cookies on the table, the i-th one has ci calories. Sandy wants to eat them but she is on a diet and can only consume exactly k calories a day. She wants to know whether it is possible for her to consume exactly k calories by eating some of the cookies.
Notes for sample IO
There are 4 cookies, and Sandy can consume exactly 13 calories.
Each cookie has calories 1, 2, 4, 7, respectively.
Sandy can choose the second, third, and fourth cookie so that the sum of their calories is 2+4+7=13.
Input
The first line of the input are two integers n and k.
The second line are n numbers c1, c2, ..., cn.
-
1 <= n <= 20
-
0 <= ai, k < 109, for i=1~n
Output
Output "YES" (without quotation mark) in one line if it is possible to consume exactly k calories, outplut "NO" (without quotation mark) in one line otherwise.