海盗与金币

12名海盗在一个小岛上发现了大量的金币，后统计一共有将近5万枚。
登上小岛是在夜里，天气又不好。由于各种原因，有的海盗偷拿了很多，有的拿了很少。
后来为了“均贫富”，头目提出一个很奇怪的方案：
每名海盗都把自己拿到的金币放在桌上。然后开始一个游戏。
金币最多的海盗要拿出自己的金币来补偿其他人。
补偿的额度为正好使被补偿人的金币数目翻番(即变为原来的2倍)。
游戏要一直进行下去，直到无法完成。
（当金币数最多的不只一个人或最多金币的人持有金币数不够补偿他人的）

游戏就这样紧张地进行了，一直进行了12轮，恰好每人都“放血”一次，
更离奇的是，刚好在第12轮后，每个人的金币数居然都相等了！！这难道是天意吗？

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

答案形如：
8 15 29 58 110 ...
当然，这个不是正确答案。

注意：
需要提交的是一行空格分开的整数，不要提交任何多余的内容。
分隔符要用一个西文的空格，不要用其它符号（比如逗号，中文符号等）

我的答案：

此题应该比较水，显然是12个人按顺序为其余11人加倍，什么样的顺序无所谓，显然最后一个补偿其它人的人在之前已经被补偿了11次，通过题意每人都补偿了其他人一次，所以第十二个人补偿完以后12个人的金币数都相等了，设为d，那么第十一次时，含有金币最多的人也就是最后进行补偿其他人的人含有的金币数一定是（1<<11）的倍数，被补偿就是翻倍，它翻倍了11次呢，所以说被补偿11次后他的金币数其实是d + 11*d/2,这个很好理解，他要给其他人补偿，最后所有人都是d，包括他自己，那么推到上一次就是其他人的和的一半是属于它的，所以d + 11 * d / 2 = x * (1 << 11),x是未知数，我们要保证12 * d <= 50000,根据题目应该是这个意思，这样的话其实满足条件的x只有13，然后d就是4096，反过来就可以推出最初他们的金币数。

代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
int have[12],ans[12],flag;
bool vis[12] = {true};
bool could(int k) {
    for(int i = 0;i < 12;i ++) {
        if(i != k) {
            if(have[i] % 2 == 0) {
                have[i] /= 2;
                have[k] += have[i];
            }
            else {
                for(int j = 0;j < i;j ++) {
                    if(j != k) {
                        have[k] -= have[j];
                        have[j] *= 2;
                    }
                }
                return false;
            }
        }
    }
    return true;
}
void recover(int k) {
    for(int i = 0;i < 12;i ++) {
        if(i != k) {
            have[k] -= have[i];
            have[i] *= 2;
        }
    }
}
void dist(int k) {
    for(int i = 0;i < 12;i ++) {
        if(i != k) {
            ans[k] -= ans[i];
            ans[i] *= 2;
        }
    }
}
void print() {
    for(int i = 0;i < 12;i ++) ans[i] = have[i];
    for(int i = 0;i <= 12;i ++) {
        int max_ = 0;
        cout<<"第"<<i<<"次";
        for(int j = 0;j < 12;j ++) {
            cout<<" "<<ans[j];
            if(ans[max_] < ans[j]) max_ = j;
        }
        cout<<endl;
        if(i < 12) dist(max_);
    }
}
void dfs(int k) {
    if(flag) return;
    if(k >= 11) {
        print();
        flag = 1;
        return;
    }
    for(int i = 1;i < 12;i ++) {
        if(flag) return;
        if(!vis[i] && could(i)) {
            vis[i] = true;
            dfs(k + 1);
            vis[i] = false;
            recover(i);
        }
    }
}
int main() {
    for(int i = 13;i * (1 << 12) / 13 * 12 <= 50000;i += 13) {
        int d = i * (1 << 12) / 13;
        have[0] = d / 2 * 13;
        for(int j = 1;j < 12;j ++) {
            have[j] = d / 2;
            vis[j] = false;
        }
        dfs(0);
    }
}