RiseOJ – 사격 연습

설명

베시는 로보바인(robovine), 즉 카우보그(cowborg)이다. 베시는 수직선 위에서 서로 다른 위치에 놓인 $$T$$ $(1 \leq T \leq 10^5)$ 개의 표적을 맞히려고 한다. 베시는 위치 $$0$$ 에서 시작하여, 각각 L, F, R 중 하나인 $$C$$ $(1 \leq C \leq 10^5)$ 개의 명령으로 이루어진 문자열을 따른다.

L: 베시가 왼쪽으로 한 칸 이동한다.
R: 베시가 오른쪽으로 한 칸 이동한다.
F: 베시가 발사한다. 베시의 현재 위치에 표적이 있으면 그 표적은 맞아서 파괴되며, 다시 맞힐 수 없다.

베시가 문자열을 따르기 시작하기 전에 문자열의 명령을 최대 하나까지 다른 명령으로 바꿀 수 있다면, 베시가 맞힐 수 있는 표적의 최대 개수는 얼마인가?

문제 제공: Suhas Nagar

제약

채점 방식

입력 4-6: $T,C \le 1000$
입력 7-15: 추가 제약 조건 없음.

문제 제공: Suhas Nagar

입력 형식

첫째 줄에 $$T$$ 와 $$C$$ 가 주어진다.

다음 줄에 $$T$$ 개 표적의 위치가 주어진다. 각 위치는 $$[-C,C]$$ 범위의 서로 다른 정수이다.

다음 줄에 F, L, R 문자로만 이루어진 길이 $$C$$ 의 명령 문자열이 주어진다.

출력 형식

문자열에서 명령을 최대 하나까지 바꾼 후 베시가 맞힐 수 있는 표적의 최대 개수를 출력한다.

예제 1

입력

3 7
0 -1 1
LFFRFRR

출력

설명

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

출력

설명

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

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > December > Silver

올림피아드 > USACO > 2023-2024 > December > Silver

태그

JudgeUSACO

사격 연습

평가 및 의견

풀이 제출