結果
問題 | No.61 リベリオン |
ユーザー | gigurururu |
提出日時 | 2014-11-10 13:56:02 |
言語 | Ruby (3.3.0) |
結果 |
AC
|
実行時間 | 656 ms / 5,000 ms |
コード長 | 1,606 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,416 KB |
最終ジャッジ日時 | 2024-04-21 17:18:55 |
合計ジャッジ時間 | 2,396 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 89 ms
12,160 KB |
testcase_01 | AC | 87 ms
12,160 KB |
testcase_02 | AC | 89 ms
12,160 KB |
testcase_03 | AC | 656 ms
12,160 KB |
testcase_04 | AC | 649 ms
12,416 KB |
testcase_05 | AC | 86 ms
12,288 KB |
コンパイルメッセージ
Syntax OK
ソースコード
q=gets.to_i q.times{ w,h,d,mx,my,hx,hy,vx,vy=gets.split.map(&:to_i) # vxが0だと下解法の式が成り立たないのでxy軸入れ替え if vx==0 w,h=h,w mx,my=my,mx hx,hy=hy,hx vx,vy=vy,vx end gcd=vx.abs.gcd(vy.abs) vx/=gcd vy/=gcd d*=gcd pointcnt=[d,(w+1)*(h+1)*4].min # 弾丸が通る整数座標数 wcnt=((hx+vx*d)/w).abs # 弾丸が通るx軸方向の室数 # 2つのうちループ数が少なくなる解法で解く # pointcntはwに比例、wcntはwに反比例なのでどちらかが大きければ逆は小さいはず # トレードオフの真ん中をつかれるテストケースだと時間制約に間に合わなさそう・・・? puts (if pointcnt<wcnt #No.60と同じ解法(弾丸の位置を時間ごとにシミュレーション) (0..pointcnt).any?{|i| (ansx=hx+vx*i)==(wn=ansx/w)*w+(wn%2==0?mx:(w-mx))&& (ansy=hy+vy*i)==(hn=ansy/h)*h+(hn%2==0?my:(h-my)) } else #時間内に弾丸が通る室のMami(虚像含む)のいるx座標ごとに #弾丸が通るy座標とMamiのy座標が一致するか確認 #最初と最後の室はMamiのx軸を弾丸が通らない可能性があるので最後にチェックする xr=vx>0?(hx..hx+vx*d):(hx+vx*d..hx) #弾丸が通るx軸範囲 (vx>0?(0..wcnt):(-wcnt..0)).any?{|i| ansx=i*w+(i%2==0?mx:(w-mx)) # y=(vy/vx)(x-hx)+hy expecty=vy.quo(vx)*(ansx-hx)+hy hn=expecty.to_i/h expecty==(hn*h)+(hn%2==0?my:(h-my))&&(xr===ansx) } end)?"Hit":"Miss" }