Advertisement
Guest User

eso.cpp

a guest
Aug 22nd, 2014
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.99 KB | None | 0 0
  1. #include <algorithm>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <deque>
  5. #include <string>
  6. #include <math.h>
  7.  
  8. using namespace std;
  9.  
  10. class Nodo{
  11.     public:
  12.         bool tonda;
  13.         deque<int> num;
  14.         deque<class Nodo*> succ;
  15. };
  16.  
  17. // costrusco ricorsivamente l'albero della sequenza passata per parametro e ritorno un puntatore alla radice al main
  18. Nodo* insert(int vet[], int s, int e){
  19.    
  20.     Nodo* node;
  21.     node = new Nodo();
  22.    
  23.     if(vet[s] == -1)
  24.         node->tonda = true;
  25.     else
  26.         node->tonda = false;
  27.  
  28.     node->num.resize(0);
  29.     s++;
  30.     e--;
  31.    
  32.     int i;
  33.     int neg = -5;
  34.     for(i=s; i<=e; i++)
  35.         if(vet[i] > 0)
  36.             node->num.push_back(vet[i]);
  37.         else{
  38.             int par = 1;
  39.             int _s = i;
  40.             int _e;
  41.             while(par != 0){
  42.                
  43.                 i++;
  44.                 if(vet[i] == -1 || vet[i] == -3)
  45.                     par++;
  46.                 else
  47.                     if(vet[i] == -2 || vet[i] == -4)
  48.                         par--;
  49.             }
  50.             _e = i;
  51.             node->succ.push_back(insert(vet, _s, _e));
  52.             node->num.push_back(neg);
  53.             neg--;
  54.         }
  55.    
  56.     return node;
  57. }
  58. /*
  59. void visit(Nodo* node, int num){
  60.     printf("\n<%d> %d:\t",node->tonda, num);
  61.     for(int i=0; i<node->num.size(); i++)
  62.         printf("%4d", node->num[i]);
  63.        
  64.     for(int i=0; i<node->succ.size(); i++)
  65.         visit(node->succ[i], 0-i-5);
  66. }
  67. */
  68.  
  69. // costruisco la sequenza senza parentesi e la ritorno al main
  70. deque<int> getSeq(Nodo* node){
  71.    
  72.     deque<int> out;
  73.    
  74.     for(int i=0; i<node->num.size(); i++)
  75.         if(node->num[i] >= 0)
  76.             out.push_back(node->num[i]);
  77.         else{
  78.             deque<int> t = getSeq(node->succ[0-node->num[i]-5]);
  79.             for(int j=0; j<t.size(); j++)
  80.                 out.push_back(t[j]);
  81.         }
  82.            
  83.    
  84.     return out;
  85. }
  86.  
  87. // ordino tutte le sequenze di numeri dei nodi
  88. void order(Nodo* node){
  89.    
  90.     // se la parentesi è tonda ordino tutto in modo crescente
  91.     if(node->tonda)
  92.         sort(node->num.begin(), node->num.end());
  93.     else
  94.         // altrimenti la parentesi è quadra, e se il primo numero è maggiore dell'ultimo ribalto la sequenza
  95.         if(node->num.size() > 1)
  96.             if(node->num[0] > node->num[node->num.size()-1]){
  97.                 for(int i=0; node->num.size()-i-1 > i; i++)
  98.                     swap(node->num[i], node->num[node->num.size()-i-1]);
  99.             }
  100.    
  101.     // ordino tutti i sottonodi
  102.     for(int i=0; i<node->succ.size(); i++)
  103.         order(node->succ[i]);
  104.    
  105. }
  106.  
  107. main(){
  108.     FILE *pF = fopen("input.txt","r");
  109.     int n,m;
  110.     fscanf(pF,"%d %d",&n,&m);
  111.  
  112.     int i,j,c;
  113.     int vet[m];
  114.    
  115.     deque<class Nodo*> eso;
  116.    
  117.     for(c=0;c<n;c++){
  118.         fscanf(pF,"\n%d",&vet[0]);
  119.         for(j=1;j<m;j++)
  120.             fscanf(pF," %d",&vet[j]);
  121.            
  122.         // costruisco l'albero
  123.         eso.push_back(insert(vet, 0, m-1));
  124.        
  125.     }
  126.     fclose(pF);
  127.    
  128.    
  129.     deque<deque<int> > ris;
  130.     for(i=0; i<eso.size(); i++){       
  131.         // ordino l'albero
  132.         order(eso[i]);
  133.         // costruisco le sequenze ordinate
  134.         ris.push_back(getSeq(eso[i]));
  135.     }
  136.        
  137.    
  138.     // count[i] contiente il numero delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
  139.     int count[n];
  140.     for(i=0; i<n; i++)
  141.         count[i] = 0;
  142.        
  143.     // lista delle posizioni delle sequenze uguali alla (i+1)^ sequenza compresa se stessa
  144.     deque<deque<int> > position(n);
  145.     position[0].push_back(1);
  146.     count[0] = 1;
  147.     int flag;
  148.    
  149.     // per tutte le sequenze tranne la prima
  150.     for(i=1; i<ris.size(); i++){
  151.         // controllo se è uguale a una delle sequenze precedenti
  152.         for(j=0; j<i; j++){
  153.            
  154.             flag = 1;
  155.            
  156.             for(c=0; c<ris[i].size(); c++)
  157.                 if(ris[i][c] != ris[j][c]){
  158.                     flag = 0;
  159.                     break;
  160.                 }
  161.            
  162.             // se si incremento count e aggiungo la posizione alla lista
  163.             if(flag){
  164.                 count[j]++;
  165.                 position[j].push_back(i+1);
  166.                 break;
  167.             }
  168.            
  169.         }
  170.        
  171.         // altrimenti creo un nuovo gruppo
  172.         if(!flag){
  173.             count[i]++;
  174.             position[i].push_back(i+1);
  175.         }
  176.        
  177.     }
  178.    
  179.     pF = fopen("output.txt", "w");
  180.     c = 0;
  181.     for(i=0; i<n; i++)
  182.         if(count[i] > 0)
  183.             c++;
  184.     fprintf(pF, "%d", c);
  185.     for(i=0; i<n; i++)
  186.         if(count[i] > 0){
  187.             fprintf(pF, "\n%d", count[i]);
  188.             for(j=0; j<position[i].size(); j++)
  189.                 fprintf(pF, " %d", position[i][j]);
  190.         }
  191.     fclose(pF);
  192. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement