Background

In-contest Q&A

This parkour thing still depends on luck (for example, zm and mt)...

Problem Description

In Minecraft, parkour can be considered a skill. Steve now wants to do parkour on a (2D) track. But Steve does not know whether he can reach the finish, so he checked the MC Wiki to learn more. The details are as follows.

Health Points

1. We define that each player starts with $20$ health points.
2. Fall damage calculation:
   • If the player’s height is $3$ blocks or less, this damage is ignored.
   • If the player’s height is $4$ blocks or more, it causes $x-3$ damage, where $x$ is the falling height.
   • The height here is relative height, i.e., the height difference between the current block and the next block.
3. Cases where fall damage is reduced: see Special Blocks.
4. When health becomes $0$, it is considered that the finish cannot be reached.

Parkour

1. For a player standing on a block, the player can jump forward at most $3$ blocks, and can also jump up by $1$ block.
2. For a player standing on a block, the player can also jump forward at most $4$ blocks, but cannot jump up by $1$ block.
3. For convenience, we assume the player does not move while falling. That is, if the next block is lower than the current block, we can only fall exactly to the position of the next block.
4. By default, the finish is the last block.

Special Blocks

1. Slime Block: It will bounce you up to a height equal to $60\%$ of the falling distance. If there is a decimal part, round down. When you reach the highest point, you can only move forward by one more block. Of course, if you land on a block in front, you will still take fall damage. You can also hold the Shift key to cancel the bounce. We assume that doing parkour on slime blocks is not affected by the slowdown limit.
2. Cobweb: It makes you ignore damage while falling. We also assume that doing parkour on cobwebs is not affected by the slowdown limit.

Steve found you and asked you to solve this problem. Determine whether Steve can reach the finish.

• If he can reach the finish, output the minimum number of jumps.
• If he cannot reach the finish, output: qwq.

Input Format

The first line contains an integer $n$, meaning there are $n$ blocks.

Starting from the second line, the next $n$ lines describe the $n$ blocks. Each block has its attributes: $x$-coordinate, height, and whether it is a special block. (A normal block is given as $\verb!P!$, a slime block as $\verb!N!$, and a cobweb as $\verb!Z!$.)

Output Format

If he can reach the finish, output one integer, the minimum number of jumps. If he cannot reach the finish, output qwq.

2
1 4 P
4 5 P

1

3
1 6 P
2 4 N
3 4 P

0

2
5 8 P
7 11 P

qwq

Hint

Constraints and Notes

The testdata guarantees that the input $x$-coordinates are strictly increasing. Each $x$-coordinate has exactly one block.

The testdata guarantees that there will not be two special blocks between two adjacent $x$-coordinates.

For blocks, by default there are no floating blocks; that is, every block has a supporting pillar beneath it.

For convenience, you cannot jump first and then fall. That is, you can only fall onto the block that is one block ahead.

For $30\%$ of the testdata, $n\le 10$. For another $20\%$ of the testdata, it is guaranteed that there are no special blocks. For the first $50\%$ of the testdata, it is guaranteed that Steve’s forward jump can only be either $4$ blocks far, or $3$ blocks far with $1$ block upward. For $100\%$ of the testdata, $1\le n\le 1000$, $1\le x_{\rm max}\le 10000$, $1\le height\le 1000$.

The testdata is guaranteed to have a reasonable difficulty gradient.

Translated by ChatGPT 5