結果

問題 No.62 リベリオン(Extra)
ユーザー gigurururugigurururu
提出日時 2014-11-10 13:58:54
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,606 bytes
コンパイル時間 54 ms
コンパイル使用メモリ 7,680 KB
実行使用メモリ 19,484 KB
最終ジャッジ日時 2024-06-10 02:20:47
合計ジャッジ時間 7,893 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
12,288 KB
testcase_01 AC 75 ms
12,288 KB
testcase_02 AC 569 ms
12,544 KB
testcase_03 AC 565 ms
12,416 KB
testcase_04 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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