/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
N \times N のグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と呼びます。
各マスに 0,1 のいずれかを書き込む方法に対して、以下のように f(X) を定めます。
- X が書かれているマスから、1 回以上「右に隣接するマスに移動するか、下に隣接するマスに移動する」という操作を繰り返して X が書かれている別のマスへ移動する方法の個数
f(0) = f(1) を満たす書き込み方を 1 個構築してください。この問題の制約下において解が存在することが保証されます。
制約
- 1 \le N \le 500
入力
入力は以下の形式で標準入力から与えられる。
N
出力
N 行出力せよ。i(1 \le i \le N) 行目には (i,1),(i,2),\dots,(i,N) に書き込む数字をこの順で空白を入れずに出力せよ。
入力例 1
2
出力例 1
01 01
f(0) の条件を満たす操作方法は以下の 1 通りなので、f(0) = 1 です。
- (1,1) から始め、(2,1) に移動する。
f(1) の条件を満たす操作方法は以下の 1 通りなので、f(1) = 1 です。
- (1,2) から始め、(2,2) に移動する。
f(0) = f(1) であるため、条件を満たします。
入力例 2
6
出力例 2
100111 101000 100010 011101 010000 110001
Score : 600 points
Problem Statement
There is an N \times N grid. The cell at the i-th row from the top and j-th column from the left is called (i,j).
For each way of writing 0 or 1 in each cell, define f(X) as follows:
- The number of ways to move from a cell with X written on it to another cell with X written on it by repeating the operation "move to the right adjacent cell or move to the down adjacent cell" one or more times.
Construct one way of writing that satisfies f(0) = f(1). It is guaranteed that a solution exists under the constraints of this problem.
Constraints
- 1 \le N \le 500
Input
The input is given from Standard Input in the following format:
N
Output
Output N lines. The i-th line (1 \le i \le N) should contain the digits to be written in (i,1),(i,2),\dots,(i,N) in this order without spaces.
Sample Input 1
2
Sample Output 1
01 01
There is one way, shown below, to perform operations satisfying the condition for f(0), so f(0) = 1.
- Start from (1,1) and move to (2,1).
There is one way, shown below, to perform operations satisfying the condition for f(1), so f(1) = 1.
- Start from (1,2) and move to (2,2).
Since f(0) = f(1), the condition is satisfied.
Sample Input 2
6
Sample Output 2
100111 101000 100010 011101 010000 110001