kry loves 2048
题目背景
kls是一个人赢。
题目描述
kls最近在玩一款类似2048的游戏,规则是这样的:
一开始,有$n$个方块,每个方块上有一个$1$到$m$的整数。
kls可以进行两种操作:
1. 选择两个数字相同的方块(不一定要相邻),将它们合并成一个数字为原来的两倍的方块;
2. 减小一个方块上的数字。
操作的次数没有限制,最终的得分为所有方块上的最大的数字。
因为kls要去陪妹子了,没有时间继续玩,他想让你帮忙计算一下,最多能得到多少分。
输入输出格式
输入格式
因为数据可能很大,读入容易超时,所以kls给你们提供了一个c++的随机数生成器。
```cpp
void generate_array(int a[], int n, int m, int seed) {
unsigned x = seed;
for (int i = 0; i < n; ++i) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
a[i] = x % m + 1;
}
}
```
把这个函数复制到你的程序里。用一个足够大的数组,以及输入数据给出的$n$,$m$和$seed$作为参数,调用这个函数。然后这个数组里就是一开始的方块上的数字(下标从0开始)。
输入一行三个数$n,m,seed$,含义如上。
输出格式
一行一个数,表示最大得分。
输入输出样例
输入样例 #1
5 10 233
输出样例 #1
24
输入样例 #2
5 50 3
输出样例 #2
48
输入样例 #3
1000 1000 666
输出样例 #3
374784
说明
### 样例解释
样例1生成出来的数是 6 10 7 5 4。
样例2生成出来的数是 8 12 48 4 4。
### 数据范围
对于30%的数据,$n, m \le 10$;
对于60%的数据,$n, m \le 10^5$;
对于100%的数据,$n, m \le 10^7$,$1 \le seed \le 10^9$。