题目

结果填空（满分29分）

标题：海盗与金币

12名海盗在一个小岛上发现了大量的金币，后统计一共有将近5万枚。

登上小岛是在夜里，天气又不好。由于各种原因，有的海盗偷拿了很多，有的拿了很少。

后来为了“均贫富”，头目提出一个很奇怪的方案：

每名海盗都把自己拿到的金币放在桌上。然后开始一个游戏。

金币最多的海盗要拿出自己的金币来补偿其他人。

补偿的额度为正好使被补偿人的金币数目翻番(即变为原来的2倍)。

游戏要一直进行下去，直到无法完成。

（当金币数最多的不只一个人或最多金币的人持有金币数不够补偿他人的）

游戏就这样紧张地进行了，一直进行了12轮，恰好每人都“放血”一次，

更离奇的是，刚好在第12轮后，每个人的金币数居然都相等了！！这难道是天意吗？

请你计算，游戏开始前，所有海盗的初始金币数目，从小到大排列，中间有一个空格分开。

答案形如：

8 15 29 58 110 ...

当然，这个不是正确答案。

注意：需要提交的是一行空格分开的整数，不要提交任何多余的内容。

分隔符要用一个西文的空格，不要用其它符号（比如逗号，中文符号等）

题解

答案为：13 25 49 97 193 385 769 1537 3073 6145 12289 24577

先算出所有人平均的金币数是多少。得知所有人平均金币数后，再暴力求出最开始时的金币数。

求出平均金币数

首先"刚好在第12轮后，每个人的金币数居然都相等了"可以知道所有人的总金币数一定是12的倍数。设第十二轮后每个人都相等的金币数为d。(12*d < 总金币数50000，d > 0，且是一个整数)

在第十一轮时，最后补偿金币的人(下文简称L)已经被其他所有人(下文简称O)补偿了11次（L的原金额已经翻了11倍），他只要最后补偿O（补偿的额度为正好使被补偿人的金币数目翻番），那么所有人金币数都相等了。

由此可知L在第十一轮补偿结束时，他金币数为：d + 11 * d / 2。并且L总共被补偿了11次，也就是说L原来的金币数翻倍了11次。

设L原本持有金币数为x（x最小为1），则在第十一轮后他金币数翻了11倍为：x*(1<<11)，也就是x*(2^11)，2048*x。

由此可以得出公式，第十一轮时L的持有金币数为：d+11 * d / 2 = 2048 * x。化简：13*d/4096=x。

由于我们不知道L在十一轮时持有的金币数x时多少，但是我们要保证d范围为：12 * d < 50000（也就是d < 4167，并且d 要接近 4167）。

在 d < 4167这个范围里，我们可以求出x的最大值为：x = 13。

通过L原本持有的金币数x，带入13 * d / 4096=13中，我们可以知道d的值为：4096。

得知第十二轮所有人都相等的金币数d后，可以暴力求取出最开始时的金币数。

import java.util.Arrays;

/**
 * 1.求出平均金币数
 *
 * 首先"刚好在第12轮后，每个人的金币数居然都相等了"可以知道所有人的总金币数一定是12的倍数。设第十二轮后每个人都相等的金币数为d。(12*d < 总金币数50000，d > 0，且是一个整数)
 * 在第十一轮时，最后补偿金币的人(下文简称L)已经被其他所有人(下文简称O)补偿了11次（L的原金额已经翻了11倍），他只要最后补偿O（补偿的额度为正好使被补偿人的金币数目翻番），那么所有人金币数都相等了。
 * 由此可知L在第十一轮补偿结束时，他金币数为：d+11*d/2。并且L总共被补偿了11次，也就是说L原来的金币数翻倍了11次。
 * 设L原本持有金币数为x（x最小为1），则在第十一轮后他金币数翻了11倍为：x*(1<<11)，也就是x*(2^11)，2048*x。
 * 由此可以得出公式，第十一轮时L的持有金币数为：d+11*d/2 = 2048*x。化简：13*d/4096=x。
 * 由于我们不知道L在十一轮时持有的金币数x时多少，但是我们要保证d范围为：12*d < 50000（也就是d < 4167，并且d 要接近 4167）。
 * 在 d < 4167这个范围里，我们可以求出x的最大值为：x = 13。
 * 通过L原本持有的金币数x，带入13*d/4096=13中，我们可以知道d的值为：4096。
 * 得知第十二轮所有人都相等的金币数d后，可以暴力求取出最开始时的金币数。
 *
 * 参考：https://blog.csdn.net/janhezz/article/details/95047424
 *
 * @author ChangSheng
 * @date 2020-04-05
 */
public class P1_海盗与金币 {
    public static void main(String[] args) {
        int[] gold = new int[12];
        // 第12轮所有人都相等的金币数d
        Arrays.fill(gold, 4096);
        // 12个海盗
        for (int i = 0; i < 12; i++) {
            int sum = 0;
            // 其他海盗补偿给当前海盗
            for (int j = 0; j < 12; j++) {
                if (i == j) continue;
                gold[j] /= 2;
                sum += gold[j];
            }
            gold[i] += sum;
        }
        String ans = Arrays.toString(gold).replaceAll(",", " ");
        System.out.println(ans.substring(1, ans.length()-1));
    }
}