A13267. Walk on Matrix
编程题
普及/提高-
知识点
题目描述
Bob is playing a game named "Walk on Matrix".
In this game, player is given an $n \times m$ matrix $A=(a_{i,j})$ , i.e. the element in the $i$ -th row in the $j$ -th column is $a_{i,j}$ . Initially, player is located at position $(1,1)$ with score $a_{1,1}$ .
To reach the goal, position $(n,m)$ , player can move right or down, i.e. move from $(x,y)$ to $(x,y+1)$ or $(x+1,y)$ , as long as player is still on the matrix.
However, each move changes player's score to the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of the current score and the value at the position he moves to.
Bob can't wait to find out the maximum score he can get using the tool he recently learnt — dynamic programming. Here is his algorithm for this problem.
However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix $A$ . Thus, for any given non-negative integer $k$ , he wants to find out an $n \times m$ matrix $A=(a_{i,j})$ such that
- $1 \le n,m \le 500$ (as Bob hates large matrix);
- $0 \le a_{i,j} \le 3 \cdot 10^5$ for all $1 \le i\le n,1 \le j\le m$ (as Bob hates large numbers);
- the difference between the maximum score he can get and the output of his algorithm is exactly $k$ .
It can be shown that for any given integer $k$ such that $0 \le k \le 10^5$ , there exists a matrix satisfying the above constraints.
Please help him with it!
In this game, player is given an $n \times m$ matrix $A=(a_{i,j})$ , i.e. the element in the $i$ -th row in the $j$ -th column is $a_{i,j}$ . Initially, player is located at position $(1,1)$ with score $a_{1,1}$ .
To reach the goal, position $(n,m)$ , player can move right or down, i.e. move from $(x,y)$ to $(x,y+1)$ or $(x+1,y)$ , as long as player is still on the matrix.
However, each move changes player's score to the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of the current score and the value at the position he moves to.
Bob can't wait to find out the maximum score he can get using the tool he recently learnt — dynamic programming. Here is his algorithm for this problem.
However, he suddenly realize that the algorithm above fails to output the maximum score for some matrix $A$ . Thus, for any given non-negative integer $k$ , he wants to find out an $n \times m$ matrix $A=(a_{i,j})$ such that
- $1 \le n,m \le 500$ (as Bob hates large matrix);
- $0 \le a_{i,j} \le 3 \cdot 10^5$ for all $1 \le i\le n,1 \le j\le m$ (as Bob hates large numbers);
- the difference between the maximum score he can get and the output of his algorithm is exactly $k$ .
It can be shown that for any given integer $k$ such that $0 \le k \le 10^5$ , there exists a matrix satisfying the above constraints.
Please help him with it!
输入格式
The only line of the input contains one single integer $k$ ( $0 \le k \le 10^5$ ).
输出格式
Output two integers $n$ , $m$ ( $1 \le n,m \le 500$ ) in the first line, representing the size of the matrix.
Then output $n$ lines with $m$ integers in each line, $a_{i,j}$ in the $(i+1)$ -th row, $j$ -th column.
Then output $n$ lines with $m$ integers in each line, $a_{i,j}$ in the $(i+1)$ -th row, $j$ -th column.
输入输出样例
输入 #1
0
输出 #1
1 1 300000
输入 #2
1
输出 #2
3 4 7 3 3 1 4 8 3 6 7 7 7 3
说明/提示
In the first example, the maximum score Bob can achieve is $300000$ , while the output of his algorithm is $300000$ .
In the second example, the maximum score Bob can achieve is $7\&3\&3\&3\&7\&3=3$ , while the output of his algorithm is $2$ .
In the second example, the maximum score Bob can achieve is $7\&3\&3\&3\&7\&3=3$ , while the output of his algorithm is $2$ .