結果

問題 No.62 リベリオン(Extra)
コンテスト
ユーザー 古寺いろは
提出日時 2015-04-10 22:39:36
言語 Python2
(2.7.18)
結果
AC  
実行時間 442 ms / 5,000 ms
コード長 2,196 bytes
コンパイル時間 100 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-07-04 13:36:21
合計ジャッジ時間 1,365 ms
ジャッジサーバーID
（参考情報） 		judge1 / 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):
    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;

    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(raw_input())
W = H = D = MX = MY = HX = HY = VX = VY = 0

while Q > 0:
    Q -= 1
    W, H, D, MX, MY, HX, HY, VX, VY = map(int,raw_input().strip().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