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.

题目大意：
有一个金字塔，共有n层，每层的房间数与层数相同。金字塔中的第i层的第j个房间记作(i,j)，从(i,j)可以走到(i+1,j)和(i+1,j+1)。每个房间可以选择放一个灯泡或者不放，每个房间的亮度是由所有能走到这个房间并且放置了灯泡的房间的数量决定的。要求第i行的i个房间亮度两两相同，求出一种放灯泡的方案，使得放置的灯泡数量最多。

输入输出格式：
输入格式：
第一行包含一个整数t(1≤t≤100)，表示测试用例的数量。接下来每个测试用例包含一个正整数n(1≤n≤500)，表示金字塔的层数。所有测试用例的n之和不超过500。

输出格式：
对于每个测试用例，输出n行，表示金字塔中灯泡的放置方案。第i行应包含i个整数，每个整数之间用空格分隔。如果房间(i,j)中有灯泡，则第j个整数为1，否则为0。

输入输出样例：
输入样例 #1
3
1
2
3

输出样例 #1
1
1 1
1 0 1
1
1 1
1 0 1 0 1题目大意： 有一个金字塔，共有n层，每层的房间数与层数相同。金字塔中的第i层的第j个房间记作(i,j)，从(i,j)可以走到(i+1,j)和(i+1,j+1)。每个房间可以选择放一个灯泡或者不放，每个房间的亮度是由所有能走到这个房间并且放置了灯泡的房间的数量决定的。要求第i行的i个房间亮度两两相同，求出一种放灯泡的方案，使得放置的灯泡数量最多。 输入输出格式： 输入格式： 第一行包含一个整数t(1≤t≤100)，表示测试用例的数量。接下来每个测试用例包含一个正整数n(1≤n≤500)，表示金字塔的层数。所有测试用例的n之和不超过500。 输出格式： 对于每个测试用例，输出n行，表示金字塔中灯泡的放置方案。第i行应包含i个整数，每个整数之间用空格分隔。如果房间(i,j)中有灯泡，则第j个整数为1，否则为0。 输入输出样例： 输入样例 #1 3 1 2 3 输出样例 #1 1 1 1 1 0 1 1 1 1 1 0 1 0 1