← 返回题目列表

Codeforces · 1734/B

B. 明亮,漂亮,辉煌

中文机器翻译题面 查看原题

有一个金字塔,由 $$$n$$$ 层组成。楼层从上到下按递增顺序编号。在金字塔中,$$$i$$$层由$$$i$$$个房间组成。

将 $$$i$$$ 层的第 $$$j$$$ 个房间表示为 $$$(i,j)$$$。对于所有正整数 $$$i$$$ 和 $$$j$$$ 使得 $$$1 \le j \le i < n$$$,存在 $$$2$$$ 单向楼梯,分别从 $$$(i,j)$$$ 到 $$$(i+1,j)$$$ 和从 $$$(i,j)$$$ 到 $$$(i+1,j+1)$$$。

在每个房间中,您可以放置​​火把或将其留空。将房间 $$$(i, j)$$$ 的亮度定义为拥有手电筒的房间数量,从这些房间可以通过非负数的楼梯到达房间 $$$(i, j)$$$。

例如,当 $$$n=5$$$ 且火把放置在房间 $$$(1,1)$$$、$$$(2,1)$$$、$$$(3,2)$$$、$$$(4,1)$$$、$$$(4,3)$$$ 和 $$$(5,3)$$$ 时,金字塔可以表示如下:

在上图中,有火把的房间是黄色的,空房间是白色的。右下角的蓝色数字表示房间的亮度。

房间$$$(4,2)$$$(有星星的房间)的亮度为$$$3$$$。在下图中,您可以到达 $$$(4,2)$$$ 的房间有红色边框。由于这些房间中有三个火把,亮度为 $$$3$$$。

当且仅当对于所有楼层,该楼层中的所有房间都具有相同的亮度时,金字塔才被称为“好的”。

将漂亮金字塔的亮度定义为房间 $$$(1,1)$$$、$$$(2,1)$$$、$$$(3,1)$$$、...、$$$(n,1)$$$ 的亮度总和。

在金字塔中找到火把的排列方式,这样最终的金字塔就很漂亮并且它的光彩最大化。

我们可以证明答案总是存在的。如果有多个答案,则输出其中任意一个。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个正整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 金字塔的楼层数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。

输出

对于每个测试用例,输出 $$$n$$$ 行,即金字塔中火把的排列。

第 $$$i$$$ 行应包含 $$$i$$$ 个整数,每个整数之间用空格分隔。如果房间 $$$(i,j)$$$ 有火炬,则第 $$$i$$$ 行上的第 $$$j$$$ 整数应为 $$$1$$$,否则为 $$$0$$$。

我们可以证明答案总是存在的。如果有多个答案,则输出其中任意一个。

示例

输入 #1

3
1
2
3

输出 #1

1 
1 
1 1 
1 
1 1 
1 0 1

注意

在第三个测试用例中,火把放置在 $$$(1,1)$$$、$$$(2,1)$$$、$$$(2,2)$$$、$$$(3,1)$$$ 和 $$$(3,3)$$$ 中。

金字塔很漂亮,因为每层的房间都有相同的亮度。例如,三楼的所有房间的亮度为$$$3$$$。

金字塔的光辉是$$$1+2+3 = 6$$$。可以证明$$$n=3$$$的安排不会有更大的辉煌。