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

As you know, Little Brick is a student is NTHU, major in CS,
he often told his friends that he have a dream - Grow Taller.

He said that every time he lines up in a queue,
he cannot see anything since there are always someone taller than him,
and standing in front of him.

He is furious, he hate to stand after people who is taller than him,
so, he define a formula to calculate the confort level of standing in the i_th position in a line.
The confort level f(i) is defined as the number of consecutive people standing in front of him, and are shorter than him.

That see if there is a line, and their heights are 150, 170, 180, 160, 165, fron front to end,
then f(1)=0 since there are no anyone standing in front of position 0,
f(2)=1, since 150 < 170,
f(3)=2, since 170 < 180 and 150 < 180,
f(4)=0, and f(5)=1

One day, Little Brick told you that he is waiting in a long line,
looking forward to shaking hand with his favorite idol,
which is your favorite one, too.

You called Little Brick and asked: "Where are you, Little Brick",
and Little Brick replied: "I am at the position where the comfort level is X",
you: "Wait, what the f...", but it was too late, he had already hang up the phone.

Now, inorder to find Little Brick so that you can cut in line to shake hand with your favorite idol,
you need to find where Little Brick may be at.

That is, given you 2 integers N and X,
where N is the number of people in the line,
and X is the comfort level Little Brick at.
Then N distinct numbers Ai,
representing the height of the people standing at the i_th position,
from the front to the end,
you need to find all possible position where Little Brick may be at.

ouo.

For example, the sample input:
6 2
3 1 6 2 4 5,
we can calculate the formula of all index,
f(1)=0, f(2)=0, f(3)=2, f(4)=0, f(5)=1, f(6)=2,
and X=2, so Little Brick may be at position 3 or 6.

Input

The first line contains 2 integer N, X,
N is the number of people, and X is the comfort level,
the second line contains N integer Ai, separate by a space,
representing the height of people standint at the i_th position.

It is guarantee that,
1<=N,X<=10^7,
1<=Ai<=10^9

 

Output

Output contains one line,
output all possible positions where Little Brick may be at,
separate by a blank.
If there is no possible position where Little Brick may be at,
output a single line "ouo" (without quote).

The index of position start from 1, and you must output the index in increasing order.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

NTHU is a kingdom, housing students and various creatures, those creatures like Procat (破貓), Crazytingyaobeast (瘋狂挺腰獸), Koprofessor (摳腳獸), EmperorPenguin07 (皇帝企鵝7號), FatFatCat (胖胖貓), Thankshanger (謝衣架), and more. We refer to these creatures as “Pokemon” because they are cute and unique in their own way.
One day, a Pokemon snake, though it does not consider itself a Pokemon ^^, has escaped!
Recently, several computer science students have found the snake near the 新齋.

Our snake-catching team leader (捕蛇大隊長), Thanksone, volunteered to capture the snake. He prepared to go with a wooden stick and a blue laundry basket.

[Thanksone is ready to catch the snake]

However, Koying thought this was too dangerous and decided to lend the road roller to Thanksone, allowing him to use it to crush the snake.

Once Thanksone got hold of the road roller, he became very excited and embarked on numerous modifications to the machine. These modifications were aimed at making it easier for him to capture the snake.

---

[Simulation environment]: In order to test whether the modified road roller could successfully crush the snake, Thanksone designed a simulation environment.

1. There is an N x M grid map, representing the campus of NTHU.
2. Each grid cell in row i and column j on the map contains a unique Pokemon Value P_{i, j}, representing the frequency of appearance of a Pokemon at the cell.
3. All creatures within NTHU, including the snake and Thanksone, will not leave the campus.

[Snake's movement]: Since the snake doesn't consider itself a Pokemon, it will start from the grid with the lowest Pokemon Value.

1. The snake moves one grid in one second, and its movement does not consume any energy.
2. The snake initially faces to the right, and it will try to move in the direction it is currently facing.
   If it can't move in that direction, it will switch its facing direction, that is right to left or left to right. This change of direction happens instantly and doesn't consume any time.
   For example
   

The snake keeps moving until it is crushed by the road roller or the road roller runs out of fuel.

[Road roller's movement]: On the other hand, since Thanksone thinks that the snake is also a Pokemon, he will start the road roller from the grid with the highest Pokemon Value.

1. The road roller moves one grid in one second, and each grid movement consumes one unit of fuel. The road roller can move in eight directions (up, down, left, right, up-left, up-right, down-left, down-right).
2. In particular, the road roller periodically emits searchlights (探照燈) in all eight directions (up, down, left, right, up-left, up-right, down-left, down-right), searching for the snake. These searchlights extend in those directions until they are blocked.
   • If a searchlight illuminates the snake, the road roller will move in the direction of (Snake_x, Snake_y), where (Snake_x, Snake_y) is the current location of the snake. It will move one grid at a time, repeatedly, until it reaches the position (Snake_x, Snake_y) or runs out of fuel.
     For example:
     
   • If no searchlights illuminate the snake, the road roller will teleport (傳送) in one second to the grid which has not been visited and is with the closest Pokemon Value to the current grid's Pokemon Value. (If there are multiple such grids, move to the one with the lowest Pokemon Value.) (Guarantees that there is at least a grid available for teleportation.)
     For example:
     
   • After the teleportation is completed or upon reaching (Snake_x, Snake_y), the road roller will emits searchlights again.

The road roller keeps moving following the policy in Step 2 until it runs out of fuel or the snake is successfully crushed.

---

We define the road roller crushing the snake as the snake and the road roller being on the same grid at the same time.

When the road roller comes to a stop, please output how much fuel is remaining.

• If the road roller successfully crushes the snake, also output "Gotcha!" (without quotes).
• Otherwise, also output "NO Snake QQ~" (without quotes).

Input

The first line consists of three positive integers, N, M, and S, indicating that the map size is N x M, and the initial fuel level of the road roller is S.
Following that, there are N lines, each containing M positive integers, denoted as P_{i, j}, representing the Pokemon Value for the grid cell in row i and column j.

Constraints

• Test Cases 1 ~ 3: N = 1
• Test Cases 4 ~ 6: 1 ≤ N ≤ 10²
• For all test cases: 2 ≤ M ≤ 10², 1 ≤ S ≤ N * M, 1 ≤ P_{i, j} ≤ 10000
• It is guaranteed that no two grid cells have the same Pokemon Value.

Output

In the first line, please output an integer, representing the remaining fuel of the road roller.
In the second line:

• if the road roller successfully crushes the snake, output "Gotcha!" (without quotes).
• if the snake is not crushed by the road roller, output "NO Snake QQ~" (without quotes).

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

Sample IO Description

Sample I/O 1:

1. The road roller emits searchlights (探照燈) in all eight directions.

2. A searchlight illuminates the snake and the snake is at (3, 3), so the road roller decided to go to (3, 3).
Since the snake can't go right, it switches to facing the left.

3. The road roller goes 1 step on the right-down direction and takes 1 unit of fuel, with 6 units of fuel left.
The snake goes 1 step on the left direction.

4. The road roller goes 1 step on the right-down direction and takes 1 unit of fuel, with 5 units of fuel left.
The snake goes 1 step on the left direction.

5. Since the road roller reaches (3, 3), it emits searchlights in all eight directions again.

6. A searchlight illuminates the snake and the snake is at (3, 1), so the road roller decided to go to (3, 1).
Since the snake can't go left, it switches to facing the right.

7. The road roller goes 1 step on the left direction and takes 1 unit of fuel, with 4 units of fuel left.
The snake goes 1 step on the right direction.
The snake met the road roller at (3, 2) and the road roller has 4 units of fuel left, so Thanksone stops road rolling.

Sample I/O 2:

1. The road roller emits searchlights (探照燈) in all eight directions.

2. No searchlights illuminate the snake, so the road roller will teleport to the grid with the closest Pokemon Value to 95 and has not been visited. (If there are multiple such grids, move to the one with the lowest Pokemon Value.)
So the road roller teleports to 91, which costs 1 unit of fuel, with 3 units of fuel left.
The snake goes 1 step on the right direction.

3. The road roller emits searchlights (探照燈) in all eight directions.

4. A searchlight illuminates the snake and the snake is at (3, 3), so the road roller decided to go to (3, 3).
Since the snake can't go right, it switches to facing the left.

5. The road roller goes 1 step on the right direction and takes 1 unit of fuel, with 2 units of fuel left.
The snake goes 1 step on the left direction.
The snake met the road roller at (3, 2) and the road roller has 2 units of fuel left, so Thanksone stops road rolling.

 

 

Sample Input  Download

Sample Output  Download

Tags

Discuss