Codeforces Round #630 (Div. 2) – Walk on Matrix

我好懒,下一场CF都要开始了这一场的题解还没写完。

这道题挺有趣的,我从来没有见过这种题耶qwq。所以……自然是不会做了。

D. Walk on Matrix

  • time limit per test: 2 seconds
  • memory limit per test: 512 megabytes

Bob is playing a game named “Walk on Matrix”.

In this game, player is given an $n×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 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×m$ matrix $A=(a_{i,j})$ such that

  • $1≤n,m≤500$ (as Bob hates large matrix);
  • $0≤a_{i,j}≤3⋅10^5$ for all $1≤i≤n,1≤j≤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≤k≤10^5$, there exists a matrix satisfying the above constraints.

Please help him with it!

Input

The only line of the input contains one single integer $k$ $(0≤k≤10^5)$.

Output

Output two integers $n, m$ $(1≤n,m≤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.

Examples

input

0

output

1 1
300000

input

1

output

3 4
7 3 3 1
4 8 3 6
7 7 7 3

Note

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$.

题意

给出了一个DP算法来求在 n × m 矩阵上从 (1,1) 行走至 (n,m) 途径元素的与运算最大值。这个算法有问题,给出一个数值 k ,要求构造一个矩阵,在这个矩阵上跑算法的结果和其真实的最大值相差为 k

思路

构造矩阵,按照给出的DP算法算出来的值为 0 ,而实际最大值为 k

然后就很神奇了,我看网上也没有具体的思路过程,再加上我本身对位运算就非常不敏感,只能看到答案去理解,但是我的大脑是构造不出这个东西的……qwq

$\begin{bmatrix} x+k & x & 0 \\ k & x+k & k\end{bmatrix}$

其中, x 是一个足够大的数且只有第一位为 1 ,而且这个必须满足如果 ka 位, x 至少有 a + 1 位。

也就是说意味着:

  • k & k = k
  • x & k = 0
  • (x + k) & k = k
  • (x + k) & x = x

用原算法跑一遍答案显然是 0, 然而如果按照 x + k -> x -> x + k -> k 的顺序跑,答案是 k

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    // freopen("in.txt", "r", stdin);
    int k; scanf("%d", &k);
    int x = (1 << 17);
    printf("2 3\n%d %d %d\n%d %d %d\n", x+k, x, 0, k, x+k, k);
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇