huff

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct V{
    double val;
    int l;
    int r;
};
vector<V> g;
vector<string> ans;
void dfs(int v, string cur){
    if(g[v].l == -1){
        ans[v] = cur;
        return;
    }
    dfs(g[v].l, cur + "1");
    dfs(g[v].r, cur + "0");
}

signed main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    multiset<pair<double,int>> s;
    ans.resize(1<<10);
    for(int i = 0; i < (1<<10); i++){
        double ver = 1;
        for(int j = 0; j < 10; j++){
            if(i & (1<<j)){
                ver *= 0.1;
            }
            else ver *= 0.9;
        }
        g.push_back((V){ver, -1, -1});
        s.insert({ver, i});
    }
    while(s.size() > 1){
        pair<double, int> F = *s.begin();
        s.erase(*s.begin());
        pair<double,int> S = *s.begin();
        s.erase(*s.begin());
        g.push_back((V){F.first + S.first, F.second, S.second});
        s.insert({F.first + S.first, g.size() - 1});
    }
    dfs((*s.begin()).second, "");
    double mat = 0;
    for(int i = 0; i < (1<<10); i++){
        for(int j = 9; j >= 0; j--){
            cout << ((int)1 &(i>>j));
        }
        cout << '\t';
        cout << ans[i]<<'\n';
        mat += g[i].val * ans[i].size();
    }
    cout << mat;
    return 0;
}