CELLPHONE TYPING (UVA 12526)

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;

// mot node cua cay trie
struct node
{
    node *child[26];
    int keystrokes, numberOfString;
    node()
    {
        for (int i = 0; i < 26; ++i)
            child[i] = NULL;
        keystrokes = numberOfString = 0;
    }
};

// Cay trie
struct Trie
{
    node root;

    void Add(const string &s)
    {
        node *a = &root;
        int id = 0;

        while (id <= (int)s.size())
        {
            ++a->numberOfString;

            if (id == (int)s.size())
                break;

            if (!(a->child[s[id] - 'a']))
                a->child[s[id] - 'a'] = new node;

            a = a->child[s[id] - 'a'];
            ++id;
        }
    }

    int dfs(node *a, int dep = 0)
    {
        int ans(0), cnt(0);

        for (int i = 0; i < 26; ++i)
            if (a->child[i])
            {
                if ((a != &root) && (a->child[i]->numberOfString) == (a->numberOfString))
                    a->child[i]->keystrokes = a->keystrokes;
                else
                    a->child[i]->keystrokes = a->keystrokes + 1;

                cnt += a->child[i]->numberOfString;
                ans += dfs(a->child[i], dep + 1);
            }

        // cout << dep << ": " << (a->keystrokes) << " " << a->numberOfString << " " << cnt << "\n";

        ans += (a->numberOfString - cnt) * (a->keystrokes);

        return ans;
    }

    int GetKeyStroke()
    {
        return dfs(&root);
    }

    void Delete(node *a)
    {
        for (int i = 0; i < 26; ++i)
            if (a->child[i])
            {
                Delete(a->child[i]);
                delete a->child[i];
            }
    }

    void Destroy()
    {
        Delete(&root);
    }
};

int n;
string s[N];

void Solve();

void Read()
{
    while (cin >> n)
    {

        for (int i = 1; i <= n; ++i)
            cin >> s[i];

        Solve();
    }
}

void Solve()
{
    Trie f;
    for (int i = 1; i <= n; ++i)
        f.Add(s[i]);

    cout << fixed << setprecision(2) << (ld)1.0 * f.GetKeyStroke() / n << "\n";

    f.Destroy();
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << endl;
        Read();
        // Solve();
    }
    // cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
1
3
1 0
1 1 2
0 3 4
*/