問題一覧 > 通常問題

No.1405 ジグザグロボット

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 4
作問者 : CuriousFairy315CuriousFairy315 / テスター : SSRSSSRS
3 ProblemId : 5002 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-28 03:35:02

問題文

315さんは大会の予選に出場しています。
予選では2台のロボットと座標が与えられ、それぞれのロボットを所定の座標まで動かせば予選通過となります。
早速2台のロボットに命令を送ろうとした315さんですが、なんとロボット1の通信機が壊れたのか制御することができません!
幸いロボット2は動くので、315さんはロボット2を動かして障害物をロボット1の進路上に配置することで、ロボット1を所定の位置に動かそうと思いました。
ロボット1の移動は予めセットしてあった長さ $N$ の命令列 $S$ によって決定されます。
$i$ 番目の移動では、 $S_i$ に書かれた文字によって次のように移動します。

  • 現在座標が $(x, y)$ で $S_i$ がLのとき、ロボットは $(x-1, y)$ に移動します。
  • 現在座標が $(x, y)$ で $S_i$ がSのとき、ロボットは $(x, y+1)$ に移動します。
  • 現在座標が $(x, y)$ で $S_i$ がRのとき、ロボットは $(x+1, y)$ に移動します。
ただし、移動先が障害物の場合、ロボットは移動を行いません。
最初はロボット1は座標 $(0, 0)$ に置かれています。
全ての移動が終わったときロボット1が座標 $(X, Y)$ にいるために必要な障害物の置き方を一つ求めてください。

入力

$N\ X\ Y$
$S$

  • $1 \leq N \leq 2021$
  • $0 \leq X, Y \leq N$
  • $S$ は長さ $N$ の文字列であり、L, S, Rの3文字のみで構成されている
  • $N, X, Y$ は整数である

出力

ロボット1を座標 $(X, Y)$ に移動させる障害物の置き方が存在するとき、1行目には障害物の個数 $M\ (0 \leq M \leq 20000)$ を出力してください。
続いて障害物の座標 $(x_i, y_i)\ (-20000 \leq x_i, y_i \leq 20000)$ を各行に順に出力してください。
今回の制約の下では、条件を満たす障害物の置き方が存在するときは必ず $M \leq 20000$ かつ $|x_i|, |y_i| \leq 20000 $を満たすようなものが存在することが証明できます。
ロボット1を座標 $(X, Y)$ に移動させる障害物の置き方が存在しないとき、-1を出力してください。
いずれの場合も、最後に改行してください。

サンプル

サンプル1
入力
4 1 3
SSRS
出力
0

サンプル2
入力
15 0 4
RRSLLSRRSLLSRRS
出力
2
1 2
0 5

サンプル3
入力
1 1 1
S
出力
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。