Problem H
Guard Evaders
More formally: Given a row of $g$ guards labeled $1$ through $g$ from left to right, each player chooses to run through the gap between guards $i$ and $i+1$ (for some $1 \leq i \leq g-1$). A player cannot run to the left of the first guard or to the right of the last. If either guard $i$ is facing right or guard $i+1$ is facing left (or both), the player is caught. Otherwise, guard $i$ turns to face right and guard $i+1$ turns to face left. No other guards change orientation.
Given how the guards are initially facing and the number of players $p$ on your team, can all $p$ players run through the guards without getting caught?
Input
The first line of input contains two positive integers: the number of guards $g$ $(2 \leq g \leq 10)$ and the number of players on your team $p$ $(1\leq p \leq 50)$. The second line contains a string of uppercase letters representing the directions each of the guards is initially facing. Each character in the string is either L (left), F (forward), or R (right). The first illustration shows four guards configured according to input string RFRL.
Output
If with optimal play all players can make it past the guards without getting caught, print 1. Otherwise print 0.
Sample Input 1 | Sample Output 1 |
---|---|
4 1 RFRL |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
4 2 RFRL |
0 |
Sample Input 3 | Sample Output 3 |
---|---|
4 4 FFFF |
1 |