Bright, Nice, Brilliant

题意翻译

给定一个金字塔（第 $i$ 层有 $i$ 个房间），设第 $i$ 层的第 $j$ 个房间为 $a_{i,j}$，那么可以从 $a_{i,j}$ 到达 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。每个房间可以选择放 $1$ 个灯泡或者不放，每个房间的亮度是所有能到达这个房间并且放了灯泡的房间的数量，要求第 $i$ 行的 $i$ 个房间亮度两两相同，请求出一种放灯泡的方案使放置的灯泡数量最多。

题目描述

There is a pyramid which consists of $ n $ floors. The floors are numbered from top to bottom in increasing order. In the pyramid, the $ i $ -th floor consists of $ i $ rooms. Denote the $ j $ -th room on the $ i $ -th floor as $ (i,j) $ . For all positive integers $ i $ and $ j $ such that $ 1 \le j \le i < n $ , there are $ 2 $ one-way staircases which lead from $ (i,j) $ to $ (i+1,j) $ and from $ (i,j) $ to $ (i+1,j+1) $ respectively. In each room you can either put a torch or leave it empty. Define the brightness of a room $ (i, j) $ to be the number of rooms with a torch from which you can reach the room $ (i, j) $ through a non-negative number of staircases. For example, when $ n=5 $ and torches are placed in the rooms $ (1,1) $ , $ (2,1) $ , $ (3,2) $ , $ (4,1) $ , $ (4,3) $ , and $ (5,3) $ , the pyramid can be illustrated as follows: In the above picture, rooms with torches are colored in yellow, and empty rooms are white. The blue numbers in the bottom-right corner indicate the brightness of the rooms. The room $ (4,2) $ (the room with a star) has brightness $ 3 $ . In the picture below, the rooms from where you can reach $ (4,2) $ have red border. The brightness is $ 3 $ since there are three torches among these rooms. The pyramid is called nice if and only if for all floors, all rooms in the floor have the same brightness. Define the brilliance of a nice pyramid to be the sum of brightness over the rooms $ (1,1) $ , $ (2,1) $ , $ (3,1) $ , ..., $ (n,1) $ . Find an arrangement of torches in the pyramid, such that the resulting pyramid is nice and its brilliance is maximized. We can show that an answer always exists. If there are multiple answers, output any one of them.

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of the test cases follows. The only line of each test case contains a single positive integer $ n $ ( $ 1 \le n \le 500 $ ) — the number of floors in the pyramid. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

输出格式

For each test case, output $ n $ lines, the arrangement of torches in the pyramid. The $ i $ -th line should contain $ i $ integers, each separated with a space. The $ j $ -th integer on the $ i $ -th line should be $ 1 $ if room $ (i,j) $ has a torch, and $ 0 $ otherwise. We can show that an answer always exists. If there are multiple answers, output any one of them.

输入输出样例

输入样例 #1

3
1
2
3

输出样例 #1

1 
1 
1 1 
1 
1 1 
1 0 1

说明

In the third test case, torches are placed in $ (1,1) $ , $ (2,1) $ , $ (2,2) $ , $ (3,1) $ , and $ (3,3) $ . The pyramid is nice as rooms on each floor have the same brightness. For example, all rooms on the third floor have brightness $ 3 $ . The brilliance of the pyramid is $ 1+2+3 = 6 $ . It can be shown that no arrangements with $ n=3 $ will have a greater brilliance.

题意翻译

给定一个金字塔（第 $i$ 层有 $i$ 个房间），设第 $i$ 层的第 $j$ 个房间为 $a_{i,j}$，那么可以从 $a_{i,j}$ 到达 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。每个房间可以选择放 $1$ 个灯泡或者不放，每个房间的亮度是所有能到达这个房间并且放了灯泡的房间的数量，要求第 $i$ 行的 $i$ 个房间亮度两两相同，请求出一种放灯泡的方案使放置的灯泡数量最多。