cub
A group of Romanian geologists found a large gold deposit in the Apuseni mountains. Using state-of-the-art equipment they succeeded in precisely mapping the deposit. The deposit can be represented as a cubic area divided into NxNxN cubes having a width of 1. Those cubes containing improper quality gold ore were also determined. In order to be able to mine effectively from an economic standpoint, the geologists have to identify those cubical areas that have a large enough width.
Task
Write a program that determines the width of the largest cube comprised of unit cubes, that contains only pure gold ore, and the number of distinct cubes that have this property.
Input Data
Input file cub.in contains two positive integers on line one, N and K, representing the size of the deposit and respectively the number of cube units of improper quality.
The following K lines contain three numbers, Xi, Yi, Zi, i belonging to group {1, 2, …, K}, representing the coordinates of the cube units containing impure ore. The triplets are not necessarily distinctive two by two.
Output Data
Output file cub.out will contain, on separate lines, two positive integers representing the maximum width of the requested cube, and respectively the number of cubes having this width.
Restrictions
3 <= N <= 120
0 <= K <= min(N3, 10000)
Examples
| cub.in | cub.out | Explanations |
|
3 6 |
2 |
The cube found contains cube units having coordinates: (1,2,1); (1,3,1); (2,2,1); (2,3,1); (1,2,2); (1,3,2); (2,2,2); (2,3,3) |
Time limit: 0.1 seconds/test
Total available memory: 3 MB, of which 1 Mb for the stack.prof. Alin Burta
"B.P. Haşdeu" Buzău National High School
Contact: allbu2003@yahoo.com