結果

問題 No.62 リベリオン(Extra)
ユーザー titiatitia
提出日時 2023-04-12 01:22:16
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 432 ms / 5,000 ms
コード長 1,759 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-10-07 21:12:00
合計ジャッジ時間 1,552 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import sys
input = sys.stdin.readline
from math import gcd
# .ax+by=gcd(a,b)(x,y)(x,y)gcd(x,y).
def Ext_Euc(a,b,axy=(1,0),bxy=(0,1)): # axy=a*1+b*0,bxy=a*0+b*1,a,b(1,0),(0,1)
q,r=divmod(a,b)
if r==0:
return bxy,b # a*bxy[0]+b*bxy[1]=b
rxy=(axy[0]-bxy[0]*q,axy[1]-bxy[1]*q) # r.
return Ext_Euc(b,r,bxy,rxy)
# 使
def Chirem(a,ma,b,mb): # N=a mod ma,N=b mod mbN=k mod(lcm(ma,mb))k,lcm(ma,mb).
(p,q),d=Ext_Euc(ma,mb)
if (a-b)%d!=0:
return -1 # -1
return (b*ma*p+a*mb*q)//d%(ma*mb//d),ma*mb//d
def calc(W,H,D,Mx,My,Hx,Hy,Vx,Vy):
GCD=gcd(Vx,Vy)
D*=GCD
Vx//=GCD
Vy//=GCD
Gx=gcd(Vx,2*W)
if (Mx-Hx)%Gx!=0:
return False
Vx=Vx//Gx
mx=(Mx-Hx)//Gx
Dx=2*W//Gx
Gy=gcd(Vy,2*H)
if (My-Hy)%Gy!=0:
return False
Vy=Vy//Gy
my=(My-Hy)//Gy
Dy=2*H//Gy
#print((mx*pow(Vx,-1,Dx),Dx,my*pow(Vy,-1,Dy),Dy))
kx=Chirem(mx*pow(Vx,-1,Dx),Dx,my*pow(Vy,-1,Dy),Dy)
if kx==-1:
return False
k,GCD=kx
if k<=D:
return True
Q=int(input())
for tests in range(Q):
W,H,D,Mx,My,Hx,Hy,Vx,Vy=map(int,input().split())
flag=0
if calc(W,H,D,Mx,My,Hx,Hy,Vx,Vy)==True:
flag=1
if calc(W,H,D,-Mx,My,Hx,Hy,Vx,Vy)==True:
flag=1
if calc(W,H,D,Mx,-My,Hx,Hy,Vx,Vy)==True:
flag=1
if calc(W,H,D,-Mx,-My,Hx,Hy,Vx,Vy)==True:
flag=1
if flag==0:
print("Miss")
else:
print("Hit")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0