結果
問題 |
No.61 リベリオン
|
ユーザー |
![]() |
提出日時 | 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())