Advertisement
Manioc

telefone

Feb 4th, 2018
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int resp;
  6.  
  7. struct node{
  8.     bool end;
  9.     bool ponte;
  10.     int pass;
  11.     struct node* word[26];
  12. } *head;
  13.  
  14. void init(){
  15.     head = new node();
  16.     head->ponte = false;
  17.     head->end = false;
  18.     head->pass = 0;
  19. }
  20.  
  21. void add(string palavra){
  22.     node* current = head;
  23.     bool create = false;
  24.     for(int i = 0; i < palavra.size(); i++){
  25.         //cout << palavra[i] << " ";
  26.         int letra = palavra[i]-(int)'a';
  27.        
  28.         current->pass++;
  29.         if(current->ponte){
  30.             resp++;
  31.             //cout << "ponte ";
  32.         }
  33.        
  34.         if(current->word[letra] == NULL){
  35.             current->word[letra] = new node();
  36.            
  37.             if(!create && i){
  38.                 //cout << "criado ";
  39.                 if(!current->ponte){
  40.                     //cout << "dividido ";
  41.                     resp += current->pass;
  42.                     current->ponte = true;
  43.                 }
  44.             }
  45.             create = true;
  46.         }
  47.        
  48.         current = current->word[letra];
  49.         cout << endl;
  50.     }
  51.     if(!create && !current->ponte){
  52.             //cout << "final em meio\n";
  53.             resp++;
  54.             current->ponte = true;
  55.     }
  56.     current->end = true;
  57. }
  58.  
  59.  
  60. int main(){
  61.     int num;
  62.     while(cin>> num){
  63.         init();
  64.         resp = 0;
  65.         for(int i = 0; i < num; i++){
  66.             string palavra; cin >> palavra;
  67.             add(palavra);
  68.         }
  69.         //cout << resp << endl;
  70.         printf("%.2f\n",(resp+num)/(double)num);
  71.     }
  72.     return 0;
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement