Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int resp;
- struct node{
- bool end;
- bool ponte;
- int pass;
- struct node* word[26];
- } *head;
- void init(){
- head = new node();
- head->ponte = false;
- head->end = false;
- head->pass = 0;
- }
- void add(string palavra){
- node* current = head;
- bool create = false;
- for(int i = 0; i < palavra.size(); i++){
- //cout << palavra[i] << " ";
- int letra = palavra[i]-(int)'a';
- current->pass++;
- if(current->ponte){
- resp++;
- //cout << "ponte ";
- }
- if(current->word[letra] == NULL){
- current->word[letra] = new node();
- if(!create && i){
- //cout << "criado ";
- if(!current->ponte){
- //cout << "dividido ";
- resp += current->pass;
- current->ponte = true;
- }
- }
- create = true;
- }
- current = current->word[letra];
- cout << endl;
- }
- if(!create && !current->ponte){
- //cout << "final em meio\n";
- resp++;
- current->ponte = true;
- }
- current->end = true;
- }
- int main(){
- int num;
- while(cin>> num){
- init();
- resp = 0;
- for(int i = 0; i < num; i++){
- string palavra; cin >> palavra;
- add(palavra);
- }
- //cout << resp << endl;
- printf("%.2f\n",(resp+num)/(double)num);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement