結果

問題 No.61 リベリオン
コンテスト
ユーザー gigurururu
提出日時 2014-11-10 13:56:02
言語 Ruby
(3.4.1)
結果
AC  
実行時間 662 ms / 5,000 ms
コード長 1,606 bytes
コンパイル時間 68 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-10-13 16:14:01
合計ジャッジ時間 2,196 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

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軸方向の室数

  # ２つのうちループ数が少なくなる解法で解く
  # 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"
}
0