Challenge: The Bouncing Flying Ball
Subdomeniu: Number Theory (number-theory)
Scor cont: 100.0 / 100
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775517
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/the-bouncing-flying-ball/problem
Cerinta
Sergey and Chen are locked in a rectangular box of Dimension L\*W\*H. Evil Larry has put a machine which is located at a point inside the box (p,q,r) which starts shooting balls in every direction (dx,dy,dz) where
-N ≤ dx, dy, dz ≤ N except (0, 0, 0)
such that the ball goes through (p, q, r) -> (p + dx, q + dy, r + dz) -> (p + 2dx, q + 2dy, r + 2dz) and so on.
so, a total of (2N + 1)<sup>3</sup> - 1 balls are fired. Sergey is standing at (a,b,c) and Chen is standing at (d,e,f). Provided all the balls follow reflection property and have constant velocity and gravity is not taken into account, can you tell how many balls are caught by Sergey and Chen? Sergey and Chen can catch the ball if it passes through the point at which they are standing.
**Input Format**
The first line contains the number of test cases, T lines follow, each containing a testcase.
Each testcase contains 13 integers in the following order
L W H a b c d e f p q r N
**Output Format**
For each test case please output two integers indicating the number of balls that are caught by Sergey and C, respectively.
**Constraints**
T = 1
1 ≤ L, W, H, a, b, c, d, e, f, p, q, r, N ≤ 50
**Sample Input**
1
3 3 3 1 1 1 1 1 2 2 2 2 1
**Sample Output**
8 4
**Explanation**
Here, L, W, H = (3, 3, 3), Sergey is at (1, 1, 1) and Chen is at (1, 1, 2) and the machine Larry put is at (2, 2, 2).
Balls are thrown at -1 ≤ x, y, z ≤ 1 from (2, 2, 2).
+ (-1, -1, -1): (2, 2, 2)->(1, 1, 1) Sergey
+ (-1, -1, 0): (2, 2, 2)->(1, 1, 2) Chen
+ (-1, -1, 1): (2, 2, 2)->(1, 1, 3)->(0, 0, 2)->(1, 1, 1) Sergey
+ (-1, 0, -1): (2, 2, 2)->(1, 2, 1)->(0, 2, 0)->(1, 2, 1)->(2, 2, 2)->(3, 2, 3)->...
+ (-1, 0, 0): (2, 2, 2)->(1, 2, 2)->(0, 2, 2)->(1, 2, 2)->(2, 2, 2)->(3, 2, 2)->...
+ (-1, 0, 1): (2, 2, 2)->(1, 2, 3)->(0, 2, 2)->(1, 2, 1)->(2, 2, 0)->(3, 2, 1)->...
+ (-1, 1, -1): (2, 2, 2)->(1, 3, 1)->(0, 2, 0)->(1, 1, 1) Sergey
+ (-1, 1, 0): (2, 2, 2)->(1, 3, 2)->(0, 2, 2)->(1, 1, 2) Chen
+ (-1, 1, 1): (2, 2, 2)->(1, 3, 3)->(0, 2, 2)->(1, 1, 1) Sergey
+ (0, *, *): x-coordinate never changed
+ (1, -1, -1): (2, 2, 2)->(3, 1, 1)->(2, 0, 0)->(1, 1, 1) Sergey
+ (1, -1, 0): (2, 2, 2)->(3, 1, 2)->(2, 0, 2)->(1, 1, 2) Chen
+ (1, -1, 1): (2, 2, 2)->(3, 1, 3)->(2, 0, 2)->(1, 1, 1) Sergey
+ (1, 0, -1): (2, 2, 2)->(3, 2, 1)->(2, 2, 0)->(1, 2, 1)->(0, 2, 2)->...
+ (1, 0, 0): (2, 2, 2)->(3, 2, 2)->(2, 2, 2)->(1, 2, 2)->(0, 2, 2)->...
+ (1, 0, 1): (2, 2, 2)->(3, 2, 3)->(2, 2, 2)->(1, 2, 1)->(0, 2, 0)->...
+ (1, 1, -1): (2, 2, 2)->(3, 3, 1)->(2, 2, 0)->(1, 1, 1) Sergey
+ (1, 1, 0): (2, 2, 2)->(3, 3, 2)->(2, 2, 2)->(1, 1, 2) Chen
+ (1, 1, 1): (2, 2, 2)->(3, 3, 3)->(2, 2, 2)->(1, 1, 1) SergeyCod sursa
# Enter your code here. Read input from STDIN. Print output to STDOUT
from math import gcd
def solutionExists(L, x, dx):
"""
Exists k such that x = dx * k (mod L)
"""
if dx == 0:
return x == 0
return x % gcd(L, dx) == 0
diafant_cache = {}
def diafantSolution(a, b, c):
"""
Find a solution of ax + by = c in a form
(x,y) = (x0,y0)+t(x1,y1)
Existence of the solution must be verified in advance.
a != 0 and b != 0
"""
key = f"{a},{b},{c}"
if key in diafant_cache:
return diafant_cache[key]
a1, b1 = 1, 0
a2, b2 = 0, 1
while b:
d = (a - a % b) // b
a, b = b, a - d * b
a1, b1 = b1, a1 - d * b1
a2, b2 = b2, a2 - d * b2
x0, y0 = a1 * c // a, a2 * c // a
x1, y1 = b1, b2
if x1 < 0:
x1, y1 = -x1, -y1
while x0 < 0:
x0 += x1
y0 += y1
while x0 - x1 > 0:
x0 -= x1
y0 -= y1
diafant_cache[key] = (x0, y0, x1, y1)
return x0, y0, x1, y1
def step(L, x, dx):
start = 0
while start <= L and start * dx % L != x:
start += 1
if start == L + 1:
return None
step = 1
while (start + step) * dx % L != x:
step += 1
return start, step
def dxAndSteps(L, xs, xm, N):
result = {}
for dx in range(-N, N + 1):
if dx % L in result:
continue
r = []
if solutionExists(L, xs, dx):
r.append(step(L, xs, dx))
if xs != xm:
if solutionExists(L, xm, dx):
r.append(step(L, xm, dx))
if r:
result[dx % L] = r
return result
def hit(nxs, nys, nzs):
for nx in nxs:
startX, stepX = nx
for ny in nys:
startY, stepY = ny
if stepX == stepY and startX != startY:
continue
for nz in nzs:
startZ, stepZ = nz
if stepX == stepZ and startX != startZ:
continue
if stepZ == stepY and startZ != startY:
continue
m14 = stepX * (startZ - startY)
m24 = stepY * (startZ - startX)
m34 = stepZ * (startY - startX)
gcd123 = gcd(stepX * gcd(stepY, stepZ), stepY * stepZ)
if m14 % gcd123 == m24 % gcd123 == m34 % gcd123 == 0:
return True
return False
def shortestPath(nxs, nys, nzs, limit):
result = limit
for nx in nxs:
startX, stepX = nx
for ny in nys:
startY, stepY = ny
if stepX == stepY and startX != startY:
continue
for nz in nzs:
startZ, stepZ = nz
if stepX == stepZ and startX != startZ:
continue
if stepZ == stepY and startZ != startY:
continue
x0, _, x1, _ = diafantSolution(stepX, -stepY, startY - startX)
m14 = stepX * (startZ - startY)
m24 = stepY * (startZ - startX)
m34 = stepZ * (startY - startX)
gcd123 = gcd(stepX * gcd(stepY, stepZ), stepY * stepZ)
if m14 % gcd123 == m24 % gcd123 == m34 % gcd123 == 0:
z0, _, _, _ = diafantSolution(-stepZ, stepX * x1, startZ - startX - stepX * x0)
newRes = startZ + stepZ * z0
result = min(result, newRes)
return result
def solve(L, W, H, x1, y1, z1, x2, y2, z2, x0, y0, z0, N):
L += L
W += W
H += H
x1s, x1m = (x1 - x0) % L, (L - x1 - x0) % L
x2s, x2m = (x2 - x0) % L, (L - x2 - x0) % L
y1s, y1m = (y1 - y0) % W, (W - y1 - y0) % W
y2s, y2m = (y2 - y0) % W, (W - y2 - y0) % W
z1s, z1m = (z1 - z0) % H, (H - z1 - z0) % H
z2s, z2m = (z2 - z0) % H, (H - z2 - z0) % H
DX1 = dxAndSteps(L, x1s, x1m, N)
DY1 = dxAndSteps(W, y1s, y1m, N)
DZ1 = dxAndSteps(H, z1s, z1m, N)
DX2 = dxAndSteps(L, x2s, x2m, N)
DY2 = dxAndSteps(W, y2s, y2m, N)
DZ2 = dxAndSteps(H, z2s, z2m, N)
result1 = 0
result2 = 0
limit = L * W * H
cache = {}
for dxx in range(-N, N + 1):
for dyy in range(-N, N + 1):
gxy = gcd(dxx, dyy)
for dzz in range(-N, N + 1):
if dxx == dyy == dzz == 0:
continue
g = gcd(gxy, dzz)
dx, dy, dz = (dxx // g) % L, (dyy // g) % W, (dzz // g) % H
key = (dx * limit + dy) * limit + dz
if key in cache:
r1, r2 = cache[key]
result1 += r1
result2 += r2
continue
firstHit, secondHit = False, False
if dx in DX1 and dy in DY1 and dz in DZ1:
firstHit = hit(DX1[dx], DY1[dy], DZ1[dz])
if dx in DX2 and dy in DY2 and dz in DZ2:
secondHit = hit(DX2[dx], DY2[dy], DZ2[dz])
if firstHit and secondHit:
N1 = shortestPath(DX1[dx], DY1[dy], DZ1[dz], limit = limit)
N2 = shortestPath(DX2[dx], DY2[dy], DZ2[dz], limit = N1 + 1)
if N1 < N2:
result1 += 1
cache[key] = (1, 0)
else:
result2 += 1
cache[key] = (0, 1)
elif firstHit:
result1 += 1
cache[key] = (1, 0)
elif secondHit:
result2 += 1
cache[key] = (0, 1)
return result1, result2
if __name__ == "__main__":
input()
L, W, H, x1, y1, z1, x2, y2, z2, x0, y0, z0, N = list(map(int, input().split()))
r1, r2 = solve(L = L, W = W, H = H, x1 = x1, y1 = y1, z1 = z1, x2 = x2, y2 = y2, z2 = z2, x0 = x0, y0 = y0, z0 = z0, N = N)
print(f"{r1} {r2}")
HackerRank Number Theory – The Bouncing Flying Ball