結果

問題 No.62 リベリオン(Extra)
ユーザー kohei2019kohei2019
提出日時 2021-07-19 00:28:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 388 ms / 5,000 ms
コード長 2,247 bytes
コンパイル時間 556 ms
コンパイル使用メモリ 82,288 KB
実行使用メモリ 80,280 KB
最終ジャッジ日時 2024-07-16 03:59:22
合計ジャッジ時間 2,016 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def extgcd(a, b):
    if b == 0:
        return (a, 1, 0)
    (g, y, x) = extgcd(b, a % b)
    return (g, x, y - (a // b) * x)


def easy(M, H, V, HW, OM, OH, D): # 真横or縦の時
    if OM != OH:
        return "Miss"
    if H >= M:
        if(H - M <= D * V):
            return "Hit"
        else:
            return "Miss"
    else:
        if(HW * 2 - H - M <= D * V):
            return "Hit"
        else:
            return "Miss"

def solve(TY, H, W, D, MY):
    TY -= MY
    if TY < 0:
        TY += (TY // (2 * H)) * (2 * H)
    while TY < 0:
        TY += 2 * H
    A = 2 * H
    B = 2 * W

    gcd, mb, ma = extgcd(B, A)
    if TY % gcd != 0:
        return False
    
    loop = A * B // gcd

    ma *= TY // gcd
    mb *= TY // gcd
    
    step = (2 * W) * mb
    
    step %= loop


    while step < 0:
        step += loop

    return step <= D


def check(P, W):
    P %= W * 2
    if P <= W:
        return P
    else:
        return (2*W) - P

def calc(W, H, D, HX, HY, MX, MY, VX, VY):

    if VY == 0:
        return easy(MX, HX, VX, W, MY, HY, D)
    if VX == 0:
        return easy(MY, HY, VY, H, MX, HX, D)

    mulX = VX
    mulY = VY

    # 速さ分だけ領域、時間を拡張

    H *= mulX
    MY *= mulX
    HY *= mulX

    W *= mulY
    MX *= mulY
    HX *= mulY

    D *= mulY
    D *= mulX

    # X座標を合わせる
    move = 0
    flag = False
    if MX <= HX:
        move = HX - MX
        flag = True
    else:
        move = W + W - HX - MX #鏡位置の点
    MX += move
    MY += move
    D-= move


    if solve(HY, H, W, D, MY) or solve(H + H - HY, H, W, D, MY): #順と逆位置
        return "Hit"
    else:
        if flag:
            move = 2 * (W - HX)
        else:
            move = 2 * HX

        
        MX += move
        MY += move
        D-= move

        if solve(HY, H, W, D, MY) or solve(H + H - HY, H, W, D, MY):
            return "Hit"
        else:
            return "Miss"

    

Q = int(input())
ans = []
for i in range(Q):
    W,H,D,Mx,My,Hx,Hy,Vx,Vy = map(int,input().split())
    if Vy < 0:
        My = H - My
        Hy = H - Hy
        Vy = -Vy
    if Vx < 0:
        Mx = W - Mx
        Hx = W - Hx
        Vx = -Vx
    print(calc(W,H,D,Mx,My,Hx,Hy,Vx,Vy))
0