Target Practice
실버 II의견: 0
Bessie is a robovine, also known as a cowborg. She is on a number line trying to
shoot a series of \(T\) \((1 \leq T \leq 10^5)\) targets located at distinct
positions. Bessie starts at position \(0\) and follows a string of \(C\)
\((1 \leq C \leq 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?
Problem credits: Suhas Nagar
SCORING
- Inputs 4-6: \(T,C \le 1000\)
- Inputs 7-15: No additional constraints.
Problem credits: Suhas Nagar
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.
3 7
0 -1 1
LFFRFRR3If 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
1 5
0
FFFFF1If 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.
5 6
1 2 3 4 5
FFRFRF3riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > December > Silver
평가 및 의견
Target Practice
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Target Practice