cub
Un grup de geologi romani a descoperit in Muntii Apuseni un mare zacamant de aur. Folosind cele mai performante aparate, acestia au reusit sa cartografieze cu mare exactitate zacamantul. Acesta poate fi asimilat unei zone cubice impartite in NxNxN cuburi de latura 1 unitate. Au fost determinate de asemenea acele cuburi care contin un minereu aurifer de puritate necorespunzatoare. Pentru a putea realiza o exploatare eficienta din punct de vedere economic, geologii trebuie sa identifice zone cubice cu latura suficient de mare.
Cerinta
Scrieti un program care sa determine latura celui mai mare cub, format din cuburi unitate, care contine numai zacamant aurifer pur si numarul de cuburi distincte cu aceasta proprietate.
Date de intrare
Fisierul de
intrare cub.in contine pe prima
linie doua numere naturale N
si K, reprezentand dimensiunea
zacamantului, respectiv numarul cuburilor unitate de puritate necorespunzatoare.
Pe urmatoarele K linii se afla
cate trei numere Xi,
Yi, Zi,
i apartinand multimii {1,
2, …, K},
reprezentand coordonatele cuburilor unitate cu minereu impur. Tripletele nu
sunt neaparat distincte doua cate doua.
Date de iesire
Fisierul de iesire cub.out va contine, pe linii separate, doua numere naturale reprezentand latura maxima a cubului cerut, respectiv numarul cuburilor cu aceasta latura.
Restrictii
3
<= N <= 120
0 <= K <= min(N3, 10000)
Exemple
| cub.in | cub.out | Explicatii |
|
3 6 |
2 |
Cubul gasit contine cuburile unitate de coordonate: (1,2,1); (1,3,1); (2,2,1); (2,3,1); (1,2,2); (1,3,2); (2,2,2); (2,3,3) |
Timp maxim de executie/test: 0.1 secunde
Memoria totala disponibila 3 MB, din care 1 Mb pentru stiva.prof. Alin
Burta
Colegiul National
"B.P. Hasdeu" Buzau
Contact:
allbu2003@yahoo.com