Codici e pizzini

Fase Territoriale 2008

Il Commissario Basettoni è riuscito a localizzare il nascondiglio del pericoloso Gambadilegno.
Facendo irruzione nel covo, Basettoni trova una serie di foglietti (detti pizzini) che riportano, cifrati, i codici di accesso ai conti correnti del gruppo di malavitosi capeggiato da Gambadilegno.

Il Commissario Basettoni chiede aiuto a Topolino per interpretare questi pizzini.
Dopo approfondite analisi, Topolino scopre le seguenti cose:

• ogni pizzino contiene N righe e ciascuna riga è una sequenza di cifre decimali (‘0’, ‘1’, …, ‘9’) concatenate senza spazi intermedi (quindi la sequenza 0991, come tale, non va interpretata come il numero 991);
• ogni pizzino riporta, cifrato, un codice di accesso a N cifre;
• tale codice si ottiene concatenando una dopo l’altra, senza spazi intermedi, le cifre estratte dalle N sequenze scritte nel pizzino, più precisamente, una cifra per ogni sequenza;
• la cifra da estrarre per ciascuna sequenza è quella in posizione p, dove p è il numero di anagrammi che, per tale sequenza, appaiono nel pizzino.

Un anagramma di una sequenza S è ottenuto permutando le sue cifre (per esempio, 1949 e 9419 sono anagrammi); inoltre, S è anagramma di se stessa.
Quindi Topolino deduce che, per calcolare il numero p di anagrammi di S, deve includere S tra i suoi anagrammi contenuti nel pizzino.
In questo modo, p=1 indica che una sequenza non ha altri anagrammi, a parte se stessa, per cui va estratta la sua prima cifra.

Per illustrare quanto descritto sopra a Basettoni, Topolino prende un pizzino che contiene i tre anagrammi 1949, 9419 e 9149 (e non ce ne sono altri) e ne estrae la loro terza cifra, ossia 4, 1 e 4, poiché p=3; poi, prende un altro pizzino con due soli anagrammi 1949 e 9419, estraendone la seconda cifra, ossia 9 e 4, poiché p=2.
Utilizzando questo meccanismo di estrazione delle cifre, aiutate Topolino a decifrare i pizzini di Gambadilegno trovati da Basettoni.

Dati di input

Il file input.txt è composto da N+1 righe.

• La prima riga contiene un intero positivo che rappresenta il numero N di sequenze contenute nel pizzino.
• Ciascuna delle successive N righe contiene una sequenza di cifre decimali (‘0’, ‘1’, …, ‘9’) senza spazi intermedi.

Dati di output

Il file output.txt è composto da una sola riga contenente una sequenza di N cifre decimali, senza spazi intermedi, ossia il codice di accesso cifrato nel pizzino.

Assunzioni

• 1 ≤ N ≤ 100
• Ogni sequenza contiene al massimo 80 cifre decimali.
• Le sequenze contenute in uno stesso pizzino sono tutte diverse tra di loro.
• Una sequenza di K cifre decimali presenta al massimo K anagrammi in uno stesso pizzino.
  Inoltre, tali anagrammi non necessariamente appaiono in righe consecutive del pizzino.

Esempi di input/output

input.txt	output.txt
6 1949 21 9419 12 4356373 9149	411244
4 022 524 322 742	0537

/*
    www.valcon.it
    OII 2008 - Fase territorale - CODICI E PIZZINI
*/

#include 
#include 
#include  

#define LMAX 80
#define NMAX 100

struct parola1 { char testo[LMAX+1];   // INPUT
                 int  risp;            // posizione carattere output 
               };
struct parola2 { char testo[LMAX+1];   // ELABORAZIONE   
                 int  pos;             // posizione originale della parola
               };

struct parola1 le_parole1[NMAX];
struct parola2 le_parole2[NMAX];  
int            N;                      // numero di sequenze
char           risposta[LMAX+1];       // messaggio


int cmp_char(const void *a, const void *b)
{
   char c1=*((char*)a);
   char c2=*((char*)b);
     
   return c1-c2;
}

int cmp_word(const void *a, const void *b)  // se le due parole sono uguali 
{                                           // allora per posizione originale...
   struct parola2 p1=*((struct parola2*)a);
   struct parola2 p2=*((struct parola2*)b);
   
   int ris=strcmp(p1.testo, p2.testo);
   if(ris != 0)
       return ris;
   else
       return p1.pos - p2.pos;
}

int main()
{
    FILE* fin =fopen( "input.txt", "r");
    FILE* fout=fopen("output.txt", "w");
  
    fscanf(fin, "%d", &N);
    for(int i=0; i < N; i++)
    {
       fscanf(fin, "%s", le_parole1[i].testo);
       strcpy(le_parole2[i].testo, le_parole1[i].testo);
       le_parole2[i].pos=i;
    }
    //+++++++++++++++++++++++++ ordina le parole e l'array di parole ++++++++++++++++++
    for(int i=0; i < N; i++)  
        qsort(le_parole2[i].testo, strlen(le_parole2[i].testo), sizeof(char), cmp_char);
    qsort(le_parole2, N, sizeof(struct parola2), cmp_word);
    //+++++++++++++++++++++++++ quante volte ogni parola ++++++++++++++++++++++++++++++
    int prima=0;
    int quante=1;
    for(int i=1; i < N; i++)
    {
      if(strcmp(le_parole2[prima].testo, le_parole2[i].testo) == 0)
          quante++;
      else
      {   
          for(int j=0; j < quante; j++)
          {
             int p=le_parole2[prima+j].pos;
             le_parole1[p].risp=quante;
          }
          quante=1; // ricomincia a contare
          prima=i;
      }
    }
    for(int j=0; j < quante; j++) // c'è ancora qualcosa da sistemare...
    {
        int p=le_parole2[prima+j].pos;
        le_parole1[p].risp=quante;
    }
    //+++++++++++++++++++++++++ costruisce la risposta, per carattere ++++++++++++++++
    for(int i=0; i < N; i++)  
    {
       int p=le_parole1[i].risp-1;
       risposta[i]=le_parole1[i].testo[p];
    }
    risposta[N]='\0';
    fprintf(fout, "%s", risposta);
    return 0;
}