Codeforces Round 822 (Div. 2) |
---|
Закончено |
У вас есть пирамида, состоящая из $$$n$$$ этажей. Этажи пронумерованы сверху вниз. Так как это пирамида, то на $$$i$$$-м этаже $$$i$$$ комнат.
Будем обозначать $$$j$$$-ю комнату на $$$i$$$-м этаже как $$$(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$$$ чисел, разделенных пробелами. $$$j$$$-е число в $$$i$$$-й строке должно быть равно $$$1$$$, если в комнате $$$(i,j)$$$ есть факел, и $$$0$$$ иначе.
Можно показать, что ответ всегда существует. Если существуют несколько решений, выведите любое из них.
3123
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$$$ с большей блистетельностью.
Название |
---|