P15565 [COCI 2025/2026 #5] Scissors / Škare

The full score for this problem is $50$.

To master the skill of using scissors, Fran came up with a new training method. He has a paper strip of length $n$ centimeters and a pair of scissors, and he asks Lana to give him cutting instructions. Lana will give Fran a total of $k$ instructions, each of the form: “Cut the $x$-th strip at a point $l$ centimeters from the left end.” At the beginning, Fran has only one strip. After the first cut, it becomes two pieces with lengths $l$ and $n-l$. After that, each time he cuts one piece, the two newly created pieces **replace** the original piece and stay in the same position in the sequence. More formally: suppose there are currently $m$ strips with lengths $a_1,a_2,\dots,a_m$ in order. If Lana tells him to cut the $x$-th strip at $l$ centimeters, then the new sequence becomes: $a_1,a_2,\dots,a_{x-1},\,l,\,a_x-l,\,a_{x+1},\dots,a_m$. After all cuts are done, they want to verify whether the process was correct. One way is to count how many **different strip lengths** appear in the final sequence. Please compute this number.

The first line contains two natural numbers $n,k$ ($2 \le n \le 500$，$1 \le k < n$), representing the original strip length and the number of instructions. The next $k$ lines each contain two natural numbers $x_i,l_i$ ($1 \le x_i \le i$, and $1 \le l_i \le L-1$, where $L$ is the length of the $x_i$-th strip at that time), meaning to cut the $x_i$-th strip from left to right at $l_i$ centimeters from its left end.

Output one line with an integer, representing how many different lengths of strips remain after all cuts are completed.

#### Sample Explanation Explanation for Sample #1: $[5] \to [2,3]$. Explanation for Sample #2: $[6] \to [4,2] \to [2,2,2]$. Explanation for Sample #3: $[10] \to [2,8] \to [2,3,5] \to [2,3,2,3]$. #### Subtasks | Subtask | Score | Constraint | | :----: | :--: | :--: | | $1$ | $9$ | $k \le 3$ | | $2$ | $6$ | For all $i$, $l_i = 1$ | | $3$ | $13$ | For all $i$, $x_i = i$ | | $4$ | $22$ | No additional constraints | Translated by ChatGPT 5