No.2968 Final MIGISITA Strike
ねしん
遭難者ストーリー
とある配信ににて、伝説の名言が爆誕する…???「皆さん、やってまいりました。ファイナル右下のお時間です。」
問題文
横の長さ $H$、縦の長さ $W$ のスマホ画面において、配信者のキャラクターと味方のキャラクター $N$ 体、敵のキャラクターが $M$ 体存在しています。以降、スマホの画面を$xy$平面とみなしていきます。
スマホ画面の四隅は $(0,0),(H,0),(H,W),(0,W)$ となっており、スマホ画面の側面は壁になっています。それぞれ、配信者のキャラクターは $(X,Y)$、味方のキャラクターは $(x_i,y_i)(1 \leq i \leq N)$、敵のキャラクターは $(a_i,b_i)(1 \leq i \leq M)$ に配置されています。
配信者のキャラクターのスピードは始め $S$ であり、右下 $45$ 度、つまり、$X$座標の値が $1$ 増えると、$Y$座標の値が $1$ 減るような方向に打ち出します。以下の事象が起こった時のみ、スピード、進行方向が変動します。
配信者のキャラクターのスピードが $0$ 以下になった時、その場で止まります。このとき、配信者のキャラクターの停止位置、味方に当たった数、敵に当たった数をそれぞれ求めてください。ただし、止まらない場合はそのことを報告してください。また、味方に当たった数、敵に当たった数はそれぞれ $998244353$ で割った余りを求めてください。
ただし、配信者のキャラクター以外は動かないものとし、すべてのキャラクターは小さいので座標が一致しない限りキャラクター同士は当たらないものとします。
入力
$H$ $W$ $N$ $M$ $S$ $C$ $X$ $Y$ $x_1$ $y_1$ $A_1$ $x_2$ $y_2$ $A_2$ $\vdots$ $x_N$ $y_N$ $A_N$ $a_1$ $b_1$ $B_1$ $a_2$ $b_2$ $B_2$ $\vdots$ $a_M$ $b_M$ $B_M$
出力
停止位置の座標を $(x_{STOP},y_{STOP})$、味方に当たった数を $s$、敵に当たった数を $t$ としたとき、以下の様に出力してください。
味方に当たった数、敵に当たった数に関してはそれぞれ $998244353$ で割った余りを出力してください。
ただし、止まらない場合は $-1$ を出力してください。
$x_{STOP}$ $y_{STOP}$ $s$ $t$
サンプル
サンプル1
入力
4 3 1 1 6 1 1 2 2 1 3 3 2 2
出力
3 2 2 3
まず始めに味方に当たり、スピードが $9$ になります。
そのあと、$2$回壁に当たり、スピードが $7$ になります。
そのあと、敵に当たり、スピードが $5$ になります。
そのあと、$3$回壁に当たり、スピードが $2$ になります。
そのあと、味方に当たり、スピードが $5$ になります。
そのあと、敵に当たり、スピードが $3$ になります。
そのあと、角に当たり、スピードが $1$ になります。
そのあと、敵に当たり、スピードが $-1$ になり停止します。
味方に $2$ 回、敵に $3$ 回当たっているので、上記の様に出力してください。
サンプル2
入力
3 3 1 1 5 1 1 2 2 1 100 2 2 100
出力
-1
この場合はスピードが上がり続けて停止しません。$-1$ を出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。