Entrenamiento IOI - Etapa #2 - Problem: Cellphone Typing - Judge: UVa - 21/11/2014 - Puntaje: 100% (AC) - Structure Solution: Trie (Tree).

gistfile1.cpp

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int N;
double answer = 0;
struct NODO {
	int prefix = 0;
	NODO* hijos[30];
};
NODO* init(){
	int i;
	NODO* nodo = new NODO;
	nodo->prefix = 1;
	for(i=0; i<30; ++i){
		nodo->hijos[i]=NULL;
	}
	return nodo;
}
void agregar(NODO* nodo, string word, int idx, int tam){
	if(idx>=tam)
		return;
	else {
		int k = (int) word[idx]-'a';
		if(nodo->hijos[k] == NULL){
                NODO* a = init();
                nodo->hijos[k] = a;
		} else {
			nodo->hijos[k]->prefix += 1;
		}
		agregar(nodo->hijos[k], word, ++idx, tam);
	}
}

int busca(NODO* nodo, string word, int i, int tam, int keypress){
	int k = (int) word[i]-'a';
	if(i>=tam){
		return keypress;
	}
	else if(!keypress){
		return busca(nodo->hijos[k], word, i+1, tam, ++keypress);
	}
	else if(nodo->hijos[k] == NULL){
		return 0;
	}
	else{ 
		if(nodo->prefix != nodo->hijos[k]->prefix && (i+1)<=tam){
			keypress++;
		}
		return busca(nodo->hijos[k], word, i+1, tam, keypress);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int i, tam;
    while(cin>>N){
	    NODO* trie = init();
	    answer = 0;
	    string cad[100002];
	    for(i=0; i<N; ++i){
	    	cin>>cad[i];
	    	agregar(trie,cad[i],0,cad[i].size());
	    }
	    int sum = 0;
	    for(i=0; i<N; ++i){
	    	sum += busca(trie,cad[i],0,cad[i].size(),0);
	    }
	    answer = (double) (double(sum)/N);
	    printf("%.2lf\n", answer);
	}
	return 0;
}