結果

問題 No.61 リベリオン
コンテスト
ユーザー chocorusk
提出日時 2020-09-10 08:12:16
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 105 ms / 5,000 ms
コード長 1,119 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-12-21 14:03:20
合計ジャッジ時間 1,160 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
readlines=sys.stdin.buffer.readlines
import math
import itertools
def inv(a, mod):
    b, x, y=mod, 1, 0
    while b:
        t=a//b
        a-=t*b
        x-=t*y
        a, b=b, a
        x, y=y, x
    return x%mod
q=int(readline())
for _ in range(q):
    w, h, d, mx, my, hx, hy, vx, vy=map(int, readline().split())
    if vx<0:
        vx=-vx
        hx, mx=w-hx, w-mx
    if vy<0:
        vy=-vy
        hy, my=h-hy, h-my
    ok=False
    a=2*h*vx
    b=2*w*vy
    g=math.gcd(a, b)
    a//=g
    b//=g
    for cx, cy in itertools.product((mx, 2*w-mx), (my, 2*h-my)):
        c=(cx-hx)*vy-(cy-hy)*vx
        if c%g!=0:
            continue
        c//=g
        if b:
            r=inv(a, b)*c%b
            x1=-2*h*r-cy+hy
            if (x1+2*h*b-1)//(2*h*b)<=(x1+d*vy)//(2*h*b):
                print("Hit")
                break
        else:
            s=inv(b, a)*c%a
            x1=-2*w*s-cx+hx
            if (x1+2*w*a-1)//(2*w*a)<=(x1+d*vx)//(2*w*a):
                print("Hit")
                break
    else:
        print("Miss")
0