AjM: /* Exemplu */

2024-06-03T14:35:21Z

Exemplu

← Older revision		Revision as of 14:35, 3 June 2024
Line 24:		Line 24:

	6 2 3 10 3 1 9 5 7 8		6 2 3 10 3 1 9 5 7 8

	cuburi.out		cuburi.out

AjM: Pagină nouă: == 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ă acoperi...

2024-06-03T14:34:48Z

Pagină nouă: == 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ă acoperi...

New page

== 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>

0613 - Cuburi - Revision history

AjM: /* Exemplu */