#PU1352. USACO 2023 December Contest, Silver — Problem 3. Target Practice
USACO 2023 December Contest, Silver — Problem 3. Target Practice
USACO 2023 December Contest, Silver — Problem 3. Target Practice
题目描述
Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of targets located at distinct positions. Bessie starts at position and follows a string of 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?
输入格式
The first line contains and . The next line contains the locations of the targets, distinct integers in the range . The next line contains the command string of length , containing only the characters F, L, and R.
输出格式
Print the maximum number of targets that Bessie can hit after changing up to one command in the string.
数据范围
Inputs 4-6: Inputs 7-15: No additional constraints. Problem credits: Suhas Nagar
样例
样例 1
3 7
0 -1 1
LFFRFRR
3
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
样例 2
1 5
0
FFFFF
1
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.
样例 3
5 6
1 2 3 4 5
FFRFRF
3