How many squares and rectangles are hidden in the 4 x 4 grid below? Maybe you can count it by hand for such a small grid, but what about for a 100 x 100 grid or even larger?
What about higher dimensions? Can you count how many cubes or boxes of different size there are in a 10 x 10 x 10 cube, or how many hypercubes and hyperboxes there are in a four-dimensional 5 x 5 x 5 x 5 hypercube?.
Your program needs to be efficient, so be clever. You should assume that squares are not rectangles, cubes are not boxes, and hypercubes are not hyperboxes.
A 4 x 4 Grid A 4 x 4 x 4 Cube
The input contains one integer N ( 0<=N<=100) in each line, which is the length of one side of the grid, cube, or hypercube. In the example above N = 4. There may be as many as 100 lines of input.
For each line of input, output six integers S2, R2, S3, R3, S4, R4 on a single line, where S2 denotes the number of squares and R2 the number of rectangles occurring in a two-dimensional ( N x N) grid. The integers S3, R3, S4, R4 denote similar quantities in higher dimensions.
1 2 3
1 0 1 0 1 0 5 4 9 18 17 64 14 22 36 180 98 1198