0613 - Cuburi

Enunt

Se dau N puncte în spațiul 3D prin coordonatele lor. Dorim să amplasăm două cuburi cu laturile paralele cu axele de coordonate, astfel încât fiecare punct să se afle pe una dintre feţele sau în interiorul a cel puțin unuia dintre cuburi. În plus, latura cubului de latură maximă dintre cele două trebuie să fie minimă.

Cerinţa

Scrieţi un program care să determine latura cubului de latură maximă pentru două cuburi care realizează acoperirea mulțimii de puncte în condiţiile de mai sus.

Date de intrare

Pe prima linie a fişierului cuburi.in se află 10 numere naturale N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz. Coordonatele celor N puncte se generează după următoarele reguli:

X1 = 1, Xi = (Xi-1 * Ax + Bx * i) mod Cx, pentru i = 2...n Y1 = 1, Yi = (Yi-1 * Ay + By * i) mod Cy, pentru i = 2...n Z1 = 1, Zi = (Zi-1 * Az + Bz * i) mod Cz, pentru i = 2...n Al i-lea punct are coordonatele (Xi, Yi, Zi).

Date de ieșire

Fişierul de ieşire cuburi.out va conţine un singur număr natural reprezentând latura cubului de latură maximă.

Restricţii şi precizări

1 ≤ N ≤ 2*1.000.000 1 ≤ Ax, Ay, Az ≤ 1000 1 ≤ Bx, By, Bz ≤ 1010 2 ≤ Cx, Cy, Cz ≤ 1015 Un punct aflat pe o față a cubului (inclusiv pe o muchie sau într-un colț al cubului) se consideră în interiorul cubului Pentru teste în valoare de 30 de puncte N ≤ 100 și Cx, Cy, Cz ≤ 20 Pentru teste în valoare de 60 de puncte N ≤ 10.000

Exemplu

cuburi.in

6 2 3 10 3 1 9 5 7 8

cuburi.out

5

Explicație

Cele 6 puncte au următoarele coordonate: (1,1,1), (8,5,3), (5,0,4), (2,4,0), (9,8,3), (6,3,1). O soluție posibilă este să amplasăm primul cub astfel încât două dintre colțurile opuse să aibă coordonatele (0, 0, 0) respectiv (5,5,5) iar al doilea cub să aibă două colțuri opuse la coordonatele (6,3,1), respectiv (11,8,6).

Rezolvare

<syntaxhighlight lang="python" line> def generate_points(N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz):

   points = []
   X, Y, Z = 1, 1, 1
   points.append((X, Y, Z))
   
   for i in range(2, N+1):
       X = (X * Ax + Bx * i) % Cx
       Y = (Y * Ay + By * i) % Cy
       Z = (Z * Az + Bz * i) % Cz
       points.append((X, Y, Z))
   
   return points

def can_cover_with_max_side(points, max_side):

   min_x = min_y = min_z = float('inf')
   max_x = max_y = max_z = float('-inf')
   
   for x, y, z in points:
       min_x = min(min_x, x)
       max_x = max(max_x, x)
       min_y = min(min_y, y)
       max_y = max(max_y, y)
       min_z = min(min_z, z)
       max_z = max(max_z, z)
   
   # Check all points can fit in 2 cubes of side length max_side
   x_ranges = [(min_x, min_x + max_side), (max_x - max_side, max_x)]
   y_ranges = [(min_y, min_y + max_side), (max_y - max_side, max_y)]
   z_ranges = [(min_z, min_z + max_side), (max_z - max_side, max_z)]
   
   for x1, x2 in x_ranges:
       for y1, y2 in y_ranges:
           for z1, z2 in z_ranges:
               if all(x1 <= x <= x2 and y1 <= y <= y2 and z1 <= z <= z2 for x, y, z in points):
                   return True
   
   return False

def find_minimum_max_side(N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz):

   points = generate_points(N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz)
   
   low, high = 0, max(max(X, Y, Z) for X, Y, Z in points)
   
   while low < high:
       mid = (low + high) // 2
       if can_cover_with_max_side(points, mid):
           high = mid
       else:
           low = mid + 1
   
   return low

def main():

   with open('cuburi.in', 'r') as infile:
       data = list(map(int, infile.read().strip().split()))
       N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz = data
   
   result = find_minimum_max_side(N, Ax, Bx, Cx, Ay, By, Cy, Az, Bz, Cz)
   
   with open('cuburi.out', 'w') as outfile:
       outfile.write(f'{result}\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>