1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6  7 #define MAXN 255 8 char s[MAXN]; 9 int cnt[27], lens[27];10 11 typedef struct node_t {12     int v;13     int n;14     node_t() { }15     node_t(int vv, int nn) {16         v = vv; n = nn;17     }18     friend bool operator <(node_t a, node_t b) {19         return a.n > b.n;20     }21 } node_t;22 23 void addBits(int x) {24     for (int i=0; i<27; ++i) {25         if(x & (1<<i))26             ++lens[i];27     }28 }29 30 void bfs() {31     priority_queue<node_t> Q;32     int i;33 34     memset(cnt, 0, sizeof(cnt));35     memset(lens, 0, sizeof(lens));36     for (i=0; s[i]; ++i)37         if (s[i] == ‘_‘)38             ++cnt[26];39         else40             ++cnt[s[i]-‘A‘];41 42     for (i=0; i<27; ++i)43         if (cnt[i])44             Q.push(node_t(1<<i, cnt[i]));45 46     if (Q.size() == 1) {47         node_t a = Q.top();48         addBits(a.v);49         return ;50     }51 52     while (Q.size() > 1) {53         node_t a = Q.top();54         addBits(a.v);55         Q.pop();56         node_t b = Q.top();57         Q.pop();58         addBits(b.v);59         Q.push(node_t(a.v|b.v, a.n+b.n));60     }61 }62 63 int main() {64     int len, sum, ans;65 66 #ifndef ONLINE_JUDGE67     freopen("data.in", "r", stdin);68 #endif69 70     while (scanf("%s", s) != EOF) {71         if (strcmp(s, "END") == 0)72             break;73         bfs();74         len = strlen(s);75         sum = len<<3;76         ans = 0;77         for (int i=0; i<27; ++i)78             if (cnt[i])79                 ans += cnt[i]*lens[i];80 81         printf("%d %d %.1lf\n", sum, ans, sum*1.0/ans);82     }83 84     return 0;85 }