結果
問題 | No.62 リベリオン(Extra) |
ユーザー |
|
提出日時 | 2024-03-03 22:03:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 232 ms / 5,000 ms |
コード長 | 3,634 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 79,296 KB |
最終ジャッジ日時 | 2024-09-29 17:08:30 |
合計ジャッジ時間 | 1,907 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 |
ソースコード
import sysimport mathimport bisectfrom heapq import heapify, heappop, heappushfrom collections import deque, defaultdict, Counterfrom functools import lru_cachefrom itertools import accumulate, combinations, permutations, productsys.setrecursionlimit(1000000)MOD = 10 ** 9 + 7MOD99 = 998244353input = lambda: sys.stdin.readline().strip()NI = lambda: int(input())NMI = lambda: map(int, input().split())NLI = lambda: list(NMI())SI = lambda: input()SMI = lambda: input().split()SLI = lambda: list(SMI())EI = lambda m: [NLI() for _ in range(m)]def extgcd(a, b):if b:d, y, x = extgcd(b, a % b)y -= (a // b)*xreturn d, x, yreturn a, 1, 0def main():Q = NI()for qi in range(Q):W, H, D, Mx, My, Hx, Hy, Vx, Vy = NMI()if Vx < 0:Vx *= -1Hx = W - HxMx = W - Mxif Vy < 0:Vy *= -1Hy = H - HyMy = H - Myif Vx == 0:if Hx != Mx:print("Miss")else:if My < Hy:My = 2*H - Myif Vy * D < My - Hy:print("Miss")else:print("Hit")continueif Vy == 0:if Hy != My:print("Miss")else:if Mx < Hx:Mx = 2*W - Mxif Vx * D < Mx - Hx:print("Miss")else:print("Hit")continuevg = math.gcd(Vx, Vy)Vx //= vgVy //= vgD *= vg# Vx > 0, Vy > 0, 互いに素# (Mx + 2W*i, My + 2H*j)# (2W-Mx + 2W*i, My + 2H*j)# (Mx + 2W*i, 2H-My + 2H*j)# (2W-Mx + 2W*i, 2H-My + 2H*j)# が Vy(x-Hx) - Vx(y-Hy) = 0上にあるか# Vy(Mx-Hx + 2W*i) - Vx(My-Hy + 2H*j) = 0# 2Vy*W*i - 2Vx*H*j = -Vy(Mx-Hx) + Vx(My-Hy)# を満たす整数i, jが存在するか?# g=gcd(2Vy*W, -2Vx*H)でわっておく、右辺が割れないなら無理# ai+bj = Rとすると、extgcdでi,jがひとつ求まる(p, qとする)# a(i-p) + b(j-q) = 0# iはpからbずつ動かせるので、HxからVx方向に一番近いものを求めたい# iをb動かすとxは2W*b動く, jはa動くのでyは-2H*a動く# mx + (2W*b) * k > Hx かつ my + (2H*a) * k > Hyをみたす最小のk# k > (Hx - mx) / (2W*b), k > (Hy - my) / (2H*a)MXS = [Mx, Mx, 2*W-Mx, 2*W-Mx]MYS = [My, 2*H-My, My, 2*H-My]ok = Falsefor MX, MY in zip(MXS, MYS):# if ok:# breakR = -Vy*(MX-Hx) + Vx*(MY-Hy)g = math.gcd(2*Vy*W, -2*Vx*H)if R % g:continuea = 2*Vy*W // gb = -2*Vx*H // gd, p, q = extgcd(a, b)p *= R // g // dq *= R // g // d# print(a, p, b, q, R//g)assert a * p + b * q == R//g, (a * p + b * q, R//g, d)mx = MX + 2*W * pmy = MY + 2*H * qkx = (Hx-mx) // (2*W*b)mx += kx * 2*W*bmy += -kx * 2*H*aif mx - Hx <= Vx * D:# print(f"H: {(Hx, Hy)}, M: {(mx, my)}, V: {(Vx, Vy)}, a*p+b*q=R//g: ({a})*({p})+({b})*({q})={R//g}")ok = Trueif ok:# print("#")print("Hit")else:# print("#")print("Miss")if __name__ == "__main__":main()