Vizualizare sursă pentru „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>