Target Practice
Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤105) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤105) commands, each one of L, F, or R:
- L: Bessie moves one unit to the left.
- R: Bessie moves one unit to the right.
- F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.
If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?
If you make no changes to the string, Bessie will hit two targets:
Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (can't destroy target more than once) R | 0 | 1 F | 0 | 2 R | 1 | 2 R | 2 | 2
If you change the last command from R to F, Bessie will hit all three targets:
Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (can't destroy target more than once) R | 0 | 1 F | 0 | 2 R | 1 | 2 F | 1 | 3
If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.
SCORING:
- Inputs 4-6: T,C≤1000
- Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar
Source: USA Computing Olympiad.
Input Format
The first line contains T and C.
The next line contains the locations of the T targets, distinct integers in the range [−C,C].
The next line contains the command string of length C, containing only the characters F, L, and R.
Output Format
Print the maximum number of targets that Bessie can hit after changing up to one command in the string.