## Combined Volume of Cuboids

### Problem 212

Published on Saturday, 11th October 2008, 06:00 am; Solved by 917; Difficulty rating: 70%An axis-aligned cuboid, specified by parameters { (x_{0},y_{0},z_{0}), (dx,dy,dz) }, consists of all points (X,Y,Z) such that x_{0} ≤ X ≤ x_{0}+dx, y_{0} ≤ Y ≤ y_{0}+dy and z_{0} ≤ Z ≤ z_{0}+dz. The volume of the cuboid is the product, dx × dy × dz. The combined volume of a collection of cuboids is the volume of their union and will be less than the sum of the individual volumes if any cuboids overlap.

Let C_{1},...,C_{50000} be a collection of 50000 axis-aligned cuboids such that C_{n} has parameters

x_{0} = S_{6n-5} modulo 10000

y_{0} = S_{6n-4} modulo 10000

z_{0} = S_{6n-3} modulo 10000

dx = 1 + (S_{6n-2} modulo 399)

dy = 1 + (S_{6n-1} modulo 399)

dz = 1 + (S_{6n} modulo 399)

where S_{1},...,S_{300000} come from the "Lagged Fibonacci Generator":

For 1 ≤ `k` ≤ 55, S_{k} = [100003 - 200003`k` + 300007`k`^{3}] (modulo 1000000)

For 56 ≤ `k`, S_{k} = [S_{k-24} + S_{k-55}] (modulo 1000000)

Thus, C_{1} has parameters {(7,53,183),(94,369,56)}, C_{2} has parameters {(2383,3563,5079),(42,212,344)}, and so on.

The combined volume of the first 100 cuboids, C_{1},...,C_{100}, is 723581599.

What is the combined volume of all 50000 cuboids, C_{1},...,C_{50000} ?