結果
| 問題 |
No.61 リベリオン
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:20:08 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 344 ms / 5,000 ms |
| コード長 | 6,825 bytes |
| コンパイル時間 | 293 ms |
| コンパイル使用メモリ | 82,400 KB |
| 実行使用メモリ | 79,832 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:56 |
| 合計ジャッジ時間 | 1,616 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 4 |
ソースコード
import math
# Extended Euclidean Algorithm: ax + by = gcd(a,b)
# Returns (gcd, x, y)
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
d, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return d, x, y
def solve_one_case():
W, H, D, Mx, My, Hx, Hy, Vx, Vy = map(int, input().split())
for sx in [-1, 1]:
for sy in [-1, 1]:
# Effective Mami coordinates for this reflection state:
eff_Mx = sx * Mx
eff_My = sy * My
# Vx*t = eff_Mx - Hx + 2*k*W
# Vy*t = eff_My - Hy + 2*l*H
Cx = eff_Mx - Hx
Cy = eff_My - Hy
# Case 1: Vx == 0
if Vx == 0:
# Vy cannot be 0 due to problem constraints (Vx,Vy) != (0,0)
if Cx % (2 * W) != 0: # Bullet path must align with Mami's x-image
continue
# Vy*t = Cy + 2*l*H. We need 0 < t <= D
# Term = Cy + 2*l*H
# If Vy > 0: 0 < Term <= D*Vy
# If Vy < 0: D*Vy <= Term < 0
min_l_val = -float('inf')
max_l_val = float('inf')
if Vy > 0:
# 0 < Cy + 2*l*H <= D*Vy
# -Cy / (2*H) < l <= (D*Vy - Cy) / (2*H)
# Note: H >= 2, so 2*H > 0
min_l_val = math.floor(-Cy / (2 * H)) + 1
max_l_val = math.floor((D * Vy - Cy) / (2 * H))
else: # Vy < 0
# D*Vy <= Cy + 2*l*H < 0
# (D*Vy - Cy) / (2*H) <= l < -Cy / (2*H)
min_l_val = math.ceil((D * Vy - Cy) / (2 * H))
max_l_val = math.ceil(-Cy / (2 * H)) - 1
if min_l_val <= max_l_val:
return "Hit"
continue
# Case 2: Vy == 0 (Vx != 0 here)
if Vy == 0:
if Cy % (2 * H) != 0: # Bullet path must align with Mami's y-image
continue
# Vx*t = Cx + 2*k*W. We need 0 < t <= D
min_k_val = -float('inf')
max_k_val = float('inf')
if Vx > 0:
# -Cx / (2*W) < k <= (D*Vx - Cx) / (2*W)
min_k_val = math.floor(-Cx / (2 * W)) + 1
max_k_val = math.floor((D * Vx - Cx) / (2 * W))
else: # Vx < 0
# (D*Vx - Cx) / (2*W) <= k < -Cx / (2*W)
min_k_val = math.ceil((D * Vx - Cx) / (2 * W))
max_k_val = math.ceil(-Cx / (2 * W)) - 1
if min_k_val <= max_k_val:
return "Hit"
continue
# Case 3: Vx != 0 and Vy != 0
# k*(2W*Vy) + l*(-2H*Vx) = Vx*Cy - Vy*Cx
A_dioph = 2 * W * Vy
B_dioph = -2 * H * Vx
C_dioph = Vx * Cy - Vy * Cx
gcd_val, k0_dioph, l0_dioph = extended_gcd(A_dioph, B_dioph)
if C_dioph % gcd_val != 0:
continue
# Particular solution for k
k_p = k0_dioph * (C_dioph // gcd_val)
# General solution for k: k = k_p + n * (B_dioph // gcd_val)
# Let k_n_coeff = B_dioph // gcd_val
k_n_coeff = B_dioph // gcd_val
# Vx*t = Cx + 2*W*k
# Vx*t = Cx + 2*W*(k_p + n * k_n_coeff)
# Vx*t = (Cx + 2*W*k_p) + n * (2*W*k_n_coeff)
term_base_for_Vxt = Cx + 2 * W * k_p
term_n_coeff_for_Vxt = 2 * W * k_n_coeff
min_n = -float('inf')
max_n = float('inf')
# Condition on t: 0 < t <= D
# This means:
# If Vx > 0: 0 < Vx*t <= D*Vx
# If Vx < 0: D*Vx <= Vx*t < 0 (inequalities flip for multiplication by Vx < 0)
# Sub-condition 1: For t > 0
# If Vx > 0: Vx*t > 0 => term_base_for_Vxt + n * term_n_coeff_for_Vxt > 0
# If Vx < 0: Vx*t < 0 => term_base_for_Vxt + n * term_n_coeff_for_Vxt < 0
if Vx > 0: # target_expr > 0
# term_base_for_Vxt + n * term_n_coeff_for_Vxt > 0
# n * term_n_coeff_for_Vxt > -term_base_for_Vxt
rhs = -term_base_for_Vxt
if term_n_coeff_for_Vxt == 0:
if not (0 > rhs): min_n = float('inf') # Contradiction, makes interval empty
elif term_n_coeff_for_Vxt > 0:
min_n = max(min_n, math.floor(rhs / term_n_coeff_for_Vxt) + 1)
else: # term_n_coeff_for_Vxt < 0
max_n = min(max_n, math.ceil(rhs / term_n_coeff_for_Vxt) - 1)
else: # Vx < 0, so target_expr < 0
# term_base_for_Vxt + n * term_n_coeff_for_Vxt < 0
# n * term_n_coeff_for_Vxt < -term_base_for_Vxt
rhs = -term_base_for_Vxt
if term_n_coeff_for_Vxt == 0:
if not (0 < rhs): min_n = float('inf')
elif term_n_coeff_for_Vxt > 0:
max_n = min(max_n, math.ceil(rhs / term_n_coeff_for_Vxt) - 1)
else: # term_n_coeff_for_Vxt < 0
min_n = max(min_n, math.floor(rhs / term_n_coeff_for_Vxt) + 1)
# Sub-condition 2: For t <= D
# If Vx > 0: Vx*t <= D*Vx => term_base_for_Vxt + n * term_n_coeff_for_Vxt <= D*Vx
# If Vx < 0: Vx*t >= D*Vx => term_base_for_Vxt + n * term_n_coeff_for_Vxt >= D*Vx
if Vx > 0: # target_expr <= D*Vx
# n * term_n_coeff_for_Vxt <= D*Vx - term_base_for_Vxt
rhs = D * Vx - term_base_for_Vxt
if term_n_coeff_for_Vxt == 0:
if not (0 <= rhs): min_n = float('inf')
elif term_n_coeff_for_Vxt > 0:
max_n = min(max_n, math.floor(rhs / term_n_coeff_for_Vxt))
else: # term_n_coeff_for_Vxt < 0
min_n = max(min_n, math.ceil(rhs / term_n_coeff_for_Vxt))
else: # Vx < 0, so target_expr >= D*Vx
# n * term_n_coeff_for_Vxt >= D*Vx - term_base_for_Vxt
rhs = D * Vx - term_base_for_Vxt
if term_n_coeff_for_Vxt == 0:
if not (0 >= rhs): min_n = float('inf')
elif term_n_coeff_for_Vxt > 0:
min_n = max(min_n, math.ceil(rhs / term_n_coeff_for_Vxt))
else: # term_n_coeff_for_Vxt < 0
max_n = min(max_n, math.floor(rhs / term_n_coeff_for_Vxt))
if min_n <= max_n:
return "Hit"
return "Miss"
Q = int(input())
for _ in range(Q):
print(solve_one_case())