Kamenčići
레이팅 미적용의견: 0
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.
Subtask 1 (10 points): \(1 \le n \le 20\)
Subtask 2 (20 points): \(1 \le n \le 50\)
Subtask 3 (40 points): \(1 \le n \le 350\)
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 2\(k - 1\) times.
If Antun can win regardless of Branka’s moves, you should print DA, otherwise print NE.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le n \le 20\) |
2 | 20점 | \(1 \le n \le 50\) |
3 | 40점 | \(1 \le n \le 350\) |
4 1
CCCPDA8 2
PCPPCCCCDA9 1
PPCPPCPPCNEClarification of the second example:
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.
평가 및 의견
Kamenčići
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Kamenčići