Hack It

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 668    Accepted Submission(s): 216
Special Judge

Problem Description

Tonyfang is a clever student. The teacher is teaching he and other students "bao'sou".
The teacher drew an n*n matrix with zero or one filled in every grid, he wanted to judge if there is a rectangle with 1 filled in each of 4 corners.
He wrote the following pseudocode and claim it runs in O(n2):

let count be a 2d array filled with 0s
iterate through all 1s in the matrix:
  suppose this 1 lies in grid(x,y)
  iterate every row r:
    if grid(r,y)=1:
      ++count[min(r,x)][max(r,x)]
      if count[min(r,x)][max(r,x)]>1:
        claim there is a rectangle satisfying the condition
claim there isn't any rectangle satisfying the condition

As a clever student, Tonyfang found the complexity is obviously wrong. But he is too lazy to generate datas, so now it's your turn.
Please hack the above code with an n*n matrix filled with zero or one without any rectangle with 1 filled in all 4 corners.
Your constructed matrix should satisfy 1≤n≤2000 and number of 1s not less than 85000.

Input

Nothing.

Output

The first line should be one positive integer n where 1≤n≤2000.

n lines following, each line contains only a string of length n consisted of zero and one.

 题意：

这道题很有意思，是一道构造题，在我做不出其他题的时候全程都在推这道题的规律。

看了杜老师的构造真的觉得很牛逼！！QAQ

打印数字n和一个n*n的矩阵，里面只有1和0，里面的1不可以四角构成一个矩形。

而且1的个数要不少于85000个，n的范围为1到2000。

思路：

用分块的思想，分成m*m个正方形，子正方形的边长也为m，且m必须为质数。

例如以m为5作为例子

为了打出2000*2000的矩阵

因此推出最小且适合的质数为47。

AC代码：

#include<bits/stdc++.h>
using namespace std;
int mapp[47*47+2][47*47+2];
int main() {
	memset(mapp, 0, sizeof(mapp));
	int n = 47;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int k = 0; k < n; k++){
				mapp[i*n+j][k*n+((k*j)+i)%n] = 1;
			}
		}
	}
	printf("2000\n");
	for(int i = 0; i < 2000; i++){
		for(int j = 0; j < 2000; j++){
			printf("%d",mapp[i][j]);
		}
		printf("\n");
	}
	return 0;
}