Fişierul intrare/ieşire:	menger.in, menger.out	Sursă	ACM 2014
Autor	Vlad Manea	Adăugată de	FMI No Stress •fmins123
Timp execuţie pe test	0.25 sec	Limită de memorie	4608 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Menger

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³ 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.

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.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• T = 20
• 0 ≤ G ≤ 5
• 0 ≤ X1 ≤ X2 ≤ 10³
• 0 ≤ Y1 ≤ Y2 ≤ 10³
• 0 ≤ Z1 ≤ Z2 ≤ 10³

Exemplu

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.

Cum se trimit solutii?