問題一覧 > 通常問題

No.1405 Zigzag Robot

レベル : / AI推定難易度 : 2800 / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : CuriousFairy315 / テスター : SSRS
お気に入りにしたユーザー ProblemId : 5002 / 自分の提出
問題文最終更新日: 2023-12-28 03:35:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 283 (順位表) の他の問題:

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)$.
However, if the destination is an obstacle, the robot does not move.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。