#P18255. Money Game 2
Money Game 2
Money Game 2
Putata 和 Budada 正在组织一个游戏。 名玩家围成一圈,编号为 。玩家 的两名相邻玩家编号分别为 和 。最初,玩家 有整数金额 。
每轮游戏中,组织者选择一名此前没有被选择过的玩家 。玩家 将自己当前金额的一半,向下取整,赠送给自己的一名相邻玩家。也就是说,每名玩家最多只能赠送一次;赠送前收到的钱也属于其当前金额。
令 表示经过若干轮游戏(也可以进行零轮)后,玩家 可能拥有的最大金额。请对所有 求出 。
不同玩家的答案相互独立计算,不要求在同一组操作中同时达到所有最大值。
输入格式
第一行包含一个整数 ,表示测试用例数。
每个测试用例包含两行:
- 第一行包含一个整数 ,表示玩家数;
- 第二行包含 个整数 ,表示每名玩家的初始金额。
输出格式
对每个测试用例,输出一行 个整数 。
数据范围
- ;
- ;
- ;
- 所有测试用例的 之和不超过 。
编号按模 计算。因此, 时向相邻玩家赠送就是向自己转账,金额不变; 时两个方向指向同一名玩家,一轮仍只能赠送一次。
样例 1
3
5
2 1 4 3 5
5
2 1 3 1 2
1
1000000000
6 5 7 8 8
4 4 5 4 4
1000000000
样例 2
1
10
8 15 18 15 13 4 14 4 17 5
30 37 41 39 34 27 29 26 31 27