Cellphone Typing - UVa 12526

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define PB push_back

#define REP(i,n) for(int i=0;i<(n);i++)
#define SIZE(a) ((int)((a).size()))

struct Node {
    int words;
    int prefixes;
    Node* edges[26];
    int suffixes;
};

void initialize(Node* vertex) {
    vertex->words = vertex->prefixes = vertex->suffixes = 0;
    REP(i,26) vertex->edges[i] = NULL;
}

void addWord(Node* vertex, const string& word) {
    Node* current = vertex;
    for(int i = 0; i < SIZE(word); ++i) {
        int k = word[i]-'a';
        if(current->edges[k] == NULL) {
            current->edges[k] = new Node();
            initialize(current->edges[k]);
            ++current->suffixes;
        }
        current = current->edges[k];
        if(i == SIZE(word)-1){
            ++current->words;
        }
        ++current->prefixes;
    }
}

Node* root;

int keystrokes(Node* vertex, const string& word) {
    Node* current = vertex;
    int ret = 0;
    bool k = 0,k2 = 0;
    ++ret;
    for(int i = 0; i < SIZE(word); ++i) {
        int x = word[i]-'a';
        current = current->edges[x];
        k2 =0;
        if(current->suffixes > 1 && (i != SIZE(word)-1)) {
            ++ret; k2 = 1;
        }
        if(i != (SIZE(word)-1) && (current->words > 0) && !k2) {
            k = 1;
        }
        if(k && !k2) {
            k = 0; ++ret;
        }
    }
    return ret;
}

char str[100];

int main () {
    int n;
    while(scanf("%d",&n) == 1) {
        root = new Node();
        vector<string> vs;
        initialize(root);
        REP(i,n) {
            scanf("%s",str);
            addWord(root,str);
            vs.PB(str);
        }
        int sum = 0;
        REP(i,n) {
            int x = keystrokes(root,vs[i]);
            sum+=x;
        }
        printf("%.2f\n", (double)sum/n);
    }
    return 0;
}