Two spies in a grid will have their covers blown if:
- They are both in the same row.
- They are both in the same column.
- They can see each other diagonally (i.e., lie in a line inclined ° or ° to the base of the grid).
The level of danger is now increased! In addition to the conditions above, no spies may lie in any straight line. This line need not be aligned ° or ° to the base of grid.
Write a program in the language of your choice to place spies (one spy per row) on an grid without blowing anyone's cover. Your program must then print the following lines describing a valid configuration:
- The value of .
- A space-separated list of -indexed column numbers, where each value is the column number of the spy in row (where ).
Solve this problem for as large as possible, up to (and including) .
Note: Run and Custom Input are not available for this challenge; you must click Submit Code for your submission to be scored. Your score for this challenge will always be the maximum value scored by any of your submissions.
Examples
In the examples below, denotes a spy and * denotes an empty cell.
Sample Configuration 0
A valid configuration for :
* S * * * * * * * * *
* * * S * * * * * * *
* * * * * * S * * * *
S * * * * * * * * * *
* * * * * * * S * * *
* * * * * * * * * * S
* * * * S * * * * * *
* * S * * * * * * * *
* * * * * * * * S * *
* * * * * S * * * * *
* * * * * * * * * S *
Sample Output 0
This C++ code:
#include <stdio>
using namespace std;
int main(){
cout << "11\n" ;
cout << "2 4 7 1 8 11 5 3 9 6 10" ;
return 0 ;
}
Produces this output:
11
2 4 7 1 8 11 5 3 9 6 10
This configuration will earn a score of .
Sample Configuration 1
A valid configuration for :
S * * * * * * * * * * * *
* * S * * * * * * * * * *
* * * * * * * * * * * S *
* * * * * * * * * S * * *
* * * * * * S * * * * * *
* S * * * * * * * * * * *
* * * * * * * * * * S * *
* * * * S * * * * * * * *
* * * * * * * S * * * * *
* * * * * * * * * * * * S
* * * * * * * * S * * * *
* * * S * * * * * * * * *
* * * * * S * * * * * * *
Sample Output 1
This Python code:
print "13"
print "1 3 12 10 7 2 11 5 8 13 9 4 6"
Produces this output:
13
1 3 12 10 7 2 11 5 8 13 9 4 6
This configuration will earn a score of .
Sample Configuration 2
An invalid configuration for :
S * * * * * *
* * S * * * *
* * * * S * *
* * * * * * S
* S * * * * *
* * * S * * *
* * * * * S *
Sample Output 2
The following output:
7
1 3 5 7 2 4 6
will earn a score of because the spies in the first rows are in a straight line as are the spies in the next rows.
Input Format
There is no input for this challenge.
Constraints
- is odd.
- (Do not submit for any value of larger than )
Scoring
A correct configuration will get a score of .
Output Format
Print the following lines of output:
- The first line should be a single integer denoting the value of .
- The second line should contain a space-separated list of integers. Each integer (where ) should be the -indexed column number where the spy in row is located.