問題
베시는 로보바인이자 카우보그입니다. 그녀는 서로 다른 위치에 있는 일련의 T (1≤T≤10^5) 타겟을 쏘려고 숫자 라인 위에 있습니다. 베시는 위치 0에서 시작하고 각각 L, F 또는 R 중 하나의 C (1≤C≤10^5)명령을 따릅니다.
- L: 베시는 왼쪽으로 한 칸 이동합니다.
- R: 베시는 오른쪽으로 한 칸 이동합니다.
- F: 베시가 발사합니다. 베시의 현재 위치에 타겟이 있으면 명중되어 파괴되며 더 이상 명중될 수 없습니다.
명령 문자열을 따르기 전에 명령 문자열에서 하나를 다른 명령으로 변경할 수 있다면, 베시가 몇 개의 타겟을 최대로 명중할 수 있을까요?
[original]
Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of T (1≤T≤10^5) targets located at distinct positions. Bessie starts at position 0 and follows a string of C (1≤C≤10^5) 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?
輸入
첫 번째 줄에는 T와 C가 있습니다.
다음 줄에는 T개의 타겟의 위치가 있으며, [−C, C] 범위의 서로 다른 정수입니다.
다음 줄에는 길이가 C인 명령 문자열이 있으며 F, L 및 R 문자만 포함합니다.
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.
輸出
명령 문자열에서 하나를 변경한 후 베시가 명중할 수 있는 최대 타겟 수를 출력합니다.
Print the maximum number of targets that Bessie can hit after changing up to one command in the string.
範例 #1
3 7
0 -1 1
LFFRFRR
3
명령 문자열을 변경하지 않으면 베시는 두 개의 타겟을 명중할 것입니다:
명령 | 위치 | 총 명중된 타겟
-----+-------+-------------------
시작 | 0 | 0
L | -1 | 0
F | -1 | 1
F | -1 | 1 (타겟은 한 번 이상 명중될 수 없음)
R | 0 | 1
F | 0 | 2
R | 1 | 2
R | 2 | 2
마지막 명령을 R에서 F로 변경하면 베시는 세 개의 타겟을 모두 명중할 것입니다:
명령 | 위치 | 총 명중된 타겟
-----+-------+-------------------
시작 | 0 | 0
L | -1 | 0
F | -1 | 1
F | -1 | 1 (타겟은 한 번 이상 명중될 수 없음)
R | 0 | 1
F | 0 | 2
R | 1 | 2
F | 1 | 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
명령이 변경되지 않으면 위치 0의 유일한 타겟이 파괴됩니다. 타겟은 여러 번 파괴될 수 없으므로 답은 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
需要登入才能撰寫程式碼。