Codeforces Round 630 (Div. 2) |
---|
Закончено |
Боб играет в игру под названием «Прогулка по матрице»
В этой игре игроку дается $$$n \times m$$$ матрица $$$A=(a_{i,j})$$$, то есть элемент в $$$i$$$-й строке в $$$j$$$-м столбце — $$$a_{i,j}$$$. В начале игры игрок стоит на позиции $$$(1,1)$$$ со счетом $$$a_{1,1}$$$.
Чтобы достичь финиша, позиции $$$(n,m)$$$, игрок может ходить вправо или вниз, то есть из $$$(x,y)$$$ в $$$(x,y+1)$$$ или $$$(x+1,y)$$$, до тех пор, пока не выходит за пределы матрицы.
Каждый шаг, однако, изменяет счет игрока на побитовое И текущего счета и значения клетки, в которую он переходит.
Конечно же, Боб сразу решил вычислить максимальный счет, который он может набрать, с помощью недавно изученной им техники динамического программирования. Вот его алгоритм для данной задачи.
Однако, он тут же понял, что его алгоритм неправильно находит максимальный счет для некоторой матрицы $$$A$$$. Поэтому теперь он хочет для каждого неотрицательного целого числа $$$k$$$ найти такую $$$n \times m$$$ матрицу $$$A=(a_{i,j})$$$, что
Можно показать, что для любого целого $$$k$$$ такого, что $$$0 \le k \le 10^5$$$, существует матрица, удовлетворяющая данным условиям.
Помогите Бобу с этой задачей!
В единственной строке записано одно целое число $$$k$$$ ($$$0 \le k \le 10^5$$$).
В первой строке выведите два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n,m \le 500$$$), обозначающие размеры матрицы.
Затем выведите $$$n$$$ строк по $$$m$$$ целых чисел в каждой строке, $$$a_{i,j}$$$ в $$$(i+1)$$$-й строке, $$$j$$$-м столбце.
0
1 1 300000
1
3 4 7 3 3 1 4 8 3 6 7 7 7 3
В первом примере максимальный счет, который может набрать Боб, равен $$$300000$$$, и вывод его алгоритма тоже $$$300000$$$.
Во втором примере максимальный счет, который Боб может набрать, равен $$$7\&3\&3\&3\&7\&3=3$$$, когда вывод его алгоритма — это $$$2$$$.
Название |
---|