COCI '21 Contest 1 #2 Kamenčići

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

This summer, Antun and Branka stumbled upon a very interesting beach, which was completely covered with plastic 'pebbles' brought by the sea from the containers that fell from the cargo ships. They decided to take back with them n of these pebbles, some red and some blue. Now that autumn has arrived, they are playing with the pebbles and reminiscing about the warm summer days.

Their game proceeds as follows: in the beginning, they place the n pebbles in a row. Then, Antun and Branka make moves in turn, each time removing one of the pebbles from one of the ends of the row, until someone obtains k red pebbles, losing the game. Antun moves first and is wondering whether he could win regardless of the moves Branka makes. Please help him and write a program which will answer his question.


1101 \le n \le 20
2201 \le n \le 50
3401 \le n \le 350

Input Specification

The first line contains two integers, n and k (1 \le k < n \le 350).

The second line contains a sequence of n characters C or P, where C denotes a red pebble, and P denotes a blue pebble. The character C appears at least 2k-1 times.

Output Specification

If Antun can win regardless of Branka's moves, you should print DA; otherwise, print NE.

Sample Input 1

4 1

Sample Output 1


Sample Input 2

8 2

Sample Output 2


Explanation for Sample Output 2

Antun can take a blue pebble from the left (CPPCCCC). Then, Branka has to take a red pebble.

If she takes a pebble from the left (PPCCCC), Antun will take the first, and Branka the second blue pebble on the left, after which only red pebbles remain and Branka will lose.

If she takes a pebble from the right (CPPCCC), Antun can take another pebble from the right and then Branka will again have to take another red pebble and lose.

Sample Input 3

9 1

Sample Output 3



There are no comments at the moment.