// Copyright (C) 2015 Katayama Hirofumi MZ. All Rights Reserved.
//
// http://p...content-available-to-author-only...h.net/test/read.cgi/tech/1437736018/
//
// 式 1/2^(a1) + 1/2^(a2) + … + 1/2^(an) ＝ 1 
// を満たす非負整数a1～an（ただしa1≦a2≦・・・≦an）を求める 
// プログラムをBASICで作りたい。ｎを適当に指定できるようにして 
// すべての解を出力するプログラムを書け。 
#include <iostream>
#include <set>
#include <map>
using namespace std;
 
int n;
set<map<int, int> > solutions;
 
void print(const map<int, int>& m) {
    for (auto& pair : m) {
        for (int i = 0; i < pair.second; ++i) {
            cout << pair.first << " ";
        }
    }
    cout << endl;
}
 
int total_count(const map<int, int>& m) {
    int c = 0;
    for (auto& pair : m) {
        c += pair.second;
    }
    return c;
}
 
void do_it(const map<int, int>& m) {
    if (total_count(m) == n) {
        solutions.emplace(m);
        return;
    }
    for (auto& pair : m) {
        if (pair.second > 0) {
            auto m2 = m;
            m2[pair.first] -= 1;
            m2[pair.first + 1] += 2;
            do_it(m2);
        }
    }
}
 
int main(void) {
    cout << "n: ";
    cin >> n;
 
    map<int, int> m;
    m.emplace(0, 1);
    do_it(m);
 
 
    cout << "solutions: " << endl;
    for (auto& ans : solutions) {
        print(ans);
    }
 
    return 0;
}
 

Ly8gQ29weXJpZ2h0IChDKSAyMDE1IEthdGF5YW1hIEhpcm9mdW1pIE1aLiBBbGwgUmlnaHRzIFJlc2VydmVkLgovLwovLyBodHRwOi8vcC4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4uaC5uZXQvdGVzdC9yZWFkLmNnaS90ZWNoLzE0Mzc3MzYwMTgvCi8vCi8vIOW8jyAxLzJeKGExKSArIDEvMl4oYTIpICsg4oCmICsgMS8yXihhbikg77ydIDEgCi8vIOOCkua6gOOBn+OBmemdnuiyoOaVtOaVsGEx772eYW7vvIjjgZ/jgaDjgZdhMeKJpmEy4omm44O744O744O74ommYW7vvInjgpLmsYLjgoHjgosgCi8vIOODl+ODreOCsOODqeODoOOCkkJBU0lD44Gn5L2c44KK44Gf44GE44CC772O44KS6YGp5b2T44Gr5oyH5a6a44Gn44GN44KL44KI44GG44Gr44GX44GmIAovLyDjgZnjgbnjgabjga7op6PjgpLlh7rlipvjgZnjgovjg5fjg63jgrDjg6njg6DjgpLmm7jjgZHjgIIgCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBuOwpzZXQ8bWFwPGludCwgaW50PiA+IHNvbHV0aW9uczsKCnZvaWQgcHJpbnQoY29uc3QgbWFwPGludCwgaW50PiYgbSkgewogICAgZm9yIChhdXRvJiBwYWlyIDogbSkgewogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcGFpci5zZWNvbmQ7ICsraSkgewogICAgICAgICAgICBjb3V0IDw8IHBhaXIuZmlyc3QgPDwgIiAiOwogICAgICAgIH0KICAgIH0KICAgIGNvdXQgPDwgZW5kbDsKfQoKaW50IHRvdGFsX2NvdW50KGNvbnN0IG1hcDxpbnQsIGludD4mIG0pIHsKICAgIGludCBjID0gMDsKICAgIGZvciAoYXV0byYgcGFpciA6IG0pIHsKICAgICAgICBjICs9IHBhaXIuc2Vjb25kOwogICAgfQogICAgcmV0dXJuIGM7Cn0KCnZvaWQgZG9faXQoY29uc3QgbWFwPGludCwgaW50PiYgbSkgewogICAgaWYgKHRvdGFsX2NvdW50KG0pID09IG4pIHsKICAgICAgICBzb2x1dGlvbnMuZW1wbGFjZShtKTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICBmb3IgKGF1dG8mIHBhaXIgOiBtKSB7CiAgICAgICAgaWYgKHBhaXIuc2Vjb25kID4gMCkgewogICAgICAgICAgICBhdXRvIG0yID0gbTsKICAgICAgICAgICAgbTJbcGFpci5maXJzdF0gLT0gMTsKICAgICAgICAgICAgbTJbcGFpci5maXJzdCArIDFdICs9IDI7CiAgICAgICAgICAgIGRvX2l0KG0yKTsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIGNvdXQgPDwgIm46ICI7CiAgICBjaW4gPj4gbjsKCiAgICBtYXA8aW50LCBpbnQ+IG07CiAgICBtLmVtcGxhY2UoMCwgMSk7CiAgICBkb19pdChtKTsKCiAgICAKICAgIGNvdXQgPDwgInNvbHV0aW9uczogIiA8PCBlbmRsOwogICAgZm9yIChhdXRvJiBhbnMgOiBzb2x1dGlvbnMpIHsKICAgICAgICBwcmludChhbnMpOwogICAgfQoKICAgIHJldHVybiAwOwp9Cg==

MTA=

10