Table 10
Time limit1sMemory limit512 MB
Build an N by N digit table (2 <= N <= 10) where every row, column, and main diagonal reads as a distinct multiple of M with no leading zero.
- Level
Hard8 of 10
- Topics
- Backtracking, Brute force, Number theory, Implementation
- Solved
- No attempts yet
Problem
For a given integer M, build a square table with N rows and N columns (2 ≤ N ≤ 10) filled with decimal digits, subject to the following restriction: the N-digit numbers formed by the digits of each row (left to right), each column (top to bottom), and each main diagonal (top to bottom) must all be multiples of M, must not start with the digit 0, and must be distinct within the table.
For example, a valid table for M = 2 is
2 3 4
5 6 6
8 2 0
The following tables are not valid for M = 2:
4
because N < 2;
2 0
4 8
because the numbers in the last column and on one of the main diagonals start with the digit 0;
2 3 4
5 8 8
2 0 2
because the number 482 appears twice in the table.
The task is not always solvable. For example, it has no solution for M = 10.
Input
The first line contains a single value of M.
Output
The first line must contain N, the number of rows and columns of the table. The i+1-st line (1 ≤ i ≤ N) must contain the elements of the i-th row as N digits separated by spaces.
Constraints
M = 259
Hint
It is known that every given test input has at least one solution.