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?
INPUT FORMAT (pipe stdin):
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 (pipe stdout):
Print the maximum number of targets that Bessie can hit after changing up to one command in the string.
SAMPLE INPUT:
3 7
0 -1 1
LFFRFRR
SAMPLE OUTPUT:
3
If you make no changes to the string, Bessie will hit two targets:
If you change the last command from R to F, Bessie will hit all three targets:
SAMPLE INPUT:
1 5
0
FFFFF
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
5 6
1 2 3 4 5
FFRFRF
SAMPLE OUTPUT:
3
SCORING:
Inputs 4-6: T,C≤1000
Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
