== include(page="template/taskheader" task_id="menger") ==
Poveste şi cerinţă...
Avem un cub fractal aşezat cu un colţ în originea sistemului de coordonate, şi cu toate celelalte colţuri la coordonate pozitive sau zero.
Cubul se construieşte astfel:
* Cubul de grad $0$ este cubul unitate
* Cubul de grad $n+1$ este mulţimea $(x, y, z)$ din $R^3^$ cu proprietatea că există $i, j, k$ din ${0, 1, 2}$ astfel încât $(3x-i, 3y-j, 3z-k)$ face parte din cubul de grad $n$, şi cel puţin unul dintre $i$, $j$, $k$ este $1$.
Cuburile de grade $0$, $1$, $2$, $3$ sunt ilustrate la scară în imaginea de mai jos.
!problema/menger?sponges.png!
Vrem să calculăm volumul intersecţiei unui astfel de cub cu un paralelipiped dreptunghic, având muchiile paralele cu axele sistemului de coordonate, ale cărui colţuri sunt cunoscute.
h2. Date de intrare
Fişierul de intrare $menger.in$ ...
Fişierul de intrare $menger.in$ conţine pe prima linie numărul de teste $T$. Fiecare test conţine două linii. Pe prima linie se găseşte gradul $G$ al cubului. Pe următoarea linie se găsesc $6$ numere, care reprezintă coordonatele punctelor ce definesc o diagonală a paralelipipedului dreptunghic: $(X1, Y1, Z1)$ şi $(X2, Y2, Z2)$, în această ordine.
h2. Date de ieşire
În fişierul de ieşire $menger.out$ ...
În fişierul de ieşire $menger.out$ se găsesc $T$ linii. Pe fiecare linie se găseşte în ordine volumul intersecţiei celor două corpuri geometrice.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $T = 20$
* $0 ≤ G ≤ 5$
* $0 ≤ X1 ≤ X2 ≤ 10^3^$
* $0 ≤ Y1 ≤ Y2 ≤ 10^3^$
* $0 ≤ Z1 ≤ Z2 ≤ 10^3^$
h2. Exemplu
table(example). |_. menger.in |_. menger.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
0
0 0 0 2 3 4
| 1
|
h3. Explicaţie
...
Fişierul de intrare conţine $1$ test.
Cubul de grad $0$ are volumul $1$ şi ocupă spaţiul dintre $(0, 0, 0)$ şi $(1, 1, 1)$.
O parte din paralelipiped ocupă acelaşi spaţiu dintre $(0, 0, 0)$ şi $(1, 1, 1)$, de volum $1$.
Fişierul de ieşire conţine $1$ linie cu acest volum.
== include(page="template/taskfooter" task_id="menger") ==
== include(page="template/taskfooter" task_id="menger") ==
