Fişierul intrare/ieşire:zuzu.in, zuzu.outSursăLot Suceava 2007
AutorDoru Popescu AnastasiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.3 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zuzu

Pe planeta Zuzu toate obiectele sunt caracterizate prin faptul ca au forma paralelipipedica. Mai mult, chiar si norii au forma unor paralelipipede dreptunghice. La un moment dat cerul se intuneca si deasupra unei zone a planetei Zuzu apar N nori, evident toti in forma de paralelipiped dreptunghic. Considerand un sistem de axe tridimensional cu Ox, Oy si Oz perpendiculare, doua cate doua, se observa faptul ca toti norii au toate laturile paralele cu axele. Pentru fiecare nor se cunosc coordonatele (date in metri) a doua colturi: cel din stanga-sus-spate (punctul A), respectiv cel din dreapta-jos-fata (punctul B), ca in figura alaturata.

Norii pot sa treaca unii prin altii si se pot deplasa doar in sase sensuri: in sensul axei Ox (sens notat cu 1), in sens opus axei Ox (sens notat cu 2), in sensul axei Oy (sens notat cu 3), in sens opus axei Oy (sens notat cu 4), in sensul axei Oz (sens notat cu 5), in sens opus axei Oz (sens notat cu 6). La fiecare unitate de timp fiecare nor se deplaseaza cu cate 1 metru pe directia sa de deplasare. Prin intrepatrunderea si lipirea norilor se pot forma formatiuni noroase (o formatiune noroasa poate fi formata si dintr-un singur nor). Un nor face parte dintr-o formatiune noroasa, daca are in comun cel putin un paralelipiped dreptunghic sau un dreptunghi cu alt nor din ea. Norii dispar, ca din senin, dupa T unitati de timp.

Cerinta

Sa se determine volumul maxim al unei formatiuni noroase si dupa cat timp se realizeaza formatiunea respectiva. Daca exista mai multe formatiuni cu acelasi volum maxim, se cere timpul minim la care se obtine o astfel de formatiune.

Date de intrare

Fisierul de intrare zuzu.in contine pe prima linie numerele naturale N si T separate printr-un spatiu, iar pe urmatoarele N linii sapte numere reale xA, yA, zA, xB, yB, zB, S separate intre ele prin cate un spatiu. Primele trei numere sunt coordonatele coltului A, urmatoarele trei numere sunt coordonatele punctului B, iar S poate fi una dintre cifrele 1, 2, 3, 4, 5, 6 si este sensul de deplasare pentru un norul respectiv. 

Date de iesire

In fisierul zuzu.out se va scrie pe prima linie volumul (partea sa intreaga), iar pe a doua linie numarul de unitati de timp din cerinta.

Restrictii

  • 2 ≤ N ≤ 40
  • 1 ≤ T ≤ 15
  • Coordonatele colturilor paralelipipedelor sunt numere reale cu maxim 5 zecimale si nu depasesc in valoare absoluta numarul 1000.

Exemplu

zuzu.inzuzu.out
3 15
0 0 30 10 10 20 6
20.05 0 5 25 5.3 0 1
10 0 10 20 10 0 2
2000
10

Explicatie

Dupa 0 unitati de timp formatiunea noroasa cea mai mare are volumul 1000 si este alcatuita din norul 1. Dupa 10 unitati de timp formatiunea noroasa cea mai mare are volumul 2000 si este alcatuita din norii 1 si 3 (au o fata comuna). Pentru 15 unitati de timp nu se mai determina formatiuni noroase, deoarece acestea dispar.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content