Задача 212
Общий объем прямоугольных параллелепипедов

Выравненный по осям прямоугольный параллелепипед, определяемый параметрами { (x_(0),y_(0),z_(0)), (dx,dy,dz) }, состоит из таких точек (X,Y,Z), для которых x_(0) ≤ X < x_(0)+dx, y_(0) < Y ≤ y_(0)+dy и z_(0) ≤ Z ≤ z_(0)+dz. Объем прямоугольного параллелепипеда есть произведение dx × dy × dz. Общий объем набора прямоугольных параллелепипедов равен объему объединенных прямоугольных параллелепипедов, и, в случае их перекрытия, он будет меньше суммы отдельных объемов.

Пусть C_(1),...,C_(50000) - набор 50000 выравненных по осям прямоугольных параллелепипедов, параметры каждого прямоугольного параллелепипеда C_(n) представлены ниже:

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)

где S_(1),...,S_(300000) получают с помощью "генератора Фибоначчи с задержкой":

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

Таким образом, параметры C_(1): {(7,53,183),(94,369,56)}, параметры C_(2): {(2383,3563,5079),(42,212,344)}, и т.д.

Общий объем первых 100 прямоугольных параллелепипедов C_(1),...,C_(100) равен 723581599.

Чему равен общий объем всех 50000 прямоугольных параллелепипедов C_(1),...,C_(50000)?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net