P7928 [COCI 2021/2022 #1] Kamenčići

Alice and Bob are playing a game again. In front of them, there are $n$ stones in a row. Each stone is either red or blue. Alice moves first. On each turn, a player chooses one end and takes one stone from that end. Whoever takes $k$ red stones first loses. Assuming both Alice and Bob play optimally, determine who will win in the end.

The first line contains two integers $n, k$. The next line contains a string of length $n$, consisting only of `C` and `P`. `C` represents a red stone, and `P` represents a blue stone.

If Alice is guaranteed to win, output `DA`; otherwise, output `NE`.

#### Constraints For all testdata, $1 \le k < n \le 350$, and red stones appear at least $2k-1$ times. | Subtask | Special Constraint | Score | | :----------: | :--------: | :-------: | | $1$ | $n \le 20$ | $10$ | | $2$ | $n \le 50$ | $20$ | | $3$ | No special constraints. | $40$ | #### Notes **The total score of this problem is $70$ points.** This problem is translated from [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T2 Kamenčići. Translated by ChatGPT 5