No.1405 Zigzag Robot
タグ : / 解いたユーザー数 5
作問者 :
CuriousFairy315
/ テスター :
SSRS
Problem Statement
315-san is competing in the qualifying round of a contest.
In the qualifying round, two robots and coordinates are given, and a contestant passes the round by moving each robot to its designated coordinates.
315-san immediately tried to send commands to the two robots, but Robot 1 cannot be controlled, perhaps because its communication device is broken!
Fortunately Robot 2 still works, so 315-san decided to move Robot 2 and place obstacles on the path of Robot 1, thereby getting Robot 1 to its designated position.
The movement of Robot 1 is determined by a preset command sequence $S$ of length $N$.
In the $i$-th move, the robot moves as follows according to the character written in $S_i$.
- If the current coordinates are $(x, y)$ and $S_i$ is
L, the robot moves to $(x-1, y)$. - If the current coordinates are $(x, y)$ and $S_i$ is
S, the robot moves to $(x, y+1)$. - If the current coordinates are $(x, y)$ and $S_i$ is
R, the robot moves to $(x+1, y)$.
Initially, Robot 1 is placed at coordinates $(0, 0)$.
Find one placement of obstacles such that Robot 1 is at coordinates $(X, Y)$ when all the moves are finished.
Input
$N\ X\ Y$ $S$
- $1 \leq N \leq 2021$
- $0 \leq X, Y \leq N$
- $S$ is a string of length $N$ consisting only of the three characters
L,S,R - $N, X, Y$ are integers
Output
If there exists a placement of obstacles that moves Robot 1 to coordinates $(X, Y)$, print the number of obstacles $M\ (0 \leq M \leq 20000)$ on the first line.
Then print the coordinates of the obstacles $(x_i, y_i)\ (-20000 \leq x_i, y_i \leq 20000)$ in order, one per line.
It can be proved that, under the constraints of this problem, whenever a placement of obstacles satisfying the conditions exists, there always exists one satisfying $M \leq 20000$ and $|x_i|, |y_i| \leq 20000 $.
If there is no placement of obstacles that moves Robot 1 to coordinates $(X, Y)$, print -1.
In either case, print a newline at the end.
Sample
Sample 1
Input
4 1 3 SSRS
Output
0
Sample 2
Input
15 0 4 RRSLLSRRSLLSRRS
Output
2 1 2 0 5
Sample 3
Input
1 1 1 S
Output
-1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。