Olimpiadi di Informatica - Selezione Regionale 2008
problema
Codici e pizzini (PIZZINI)
- livello difficoltà 1
soluzione in C++ proposta dal prof.Carlo Salvagno
/* Selezione Regionale 2008 - Codici e pizzini (PIZZINI) - Difficoltà D = 1 Descrizione del problema: 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 | | input.txt | output.txt | +-----------+------------+ +-----------+------------+ | 6 | 411244 | | 4 | 0537 | | 1949 | | | 022 | | | 21 | | | 524 | | | 9419 | | | 322 | | | 12 | | | 742 | | | 4356373 | | +-----------+------------+ | 9149 | | +-----------+------------+ Nota/e: Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio. ------------------------------------------------------------------------------- Olimpiadi di Informatica - Selezione Regionale 2008 Soluzione problema CODICI E PIZZINI proposta da Carlo Salvagno, Referente Regionale VEN1 - ITIS "C.Zuccante", in Dev-C++ IDEA RISOLUTIVA - vengono lette le 'n' stringhe e caricate nel vettore 'seq' - per ogni stringa vengono calcolate le frequenze delle cifre e caricate nella matrice 'freq', matrice di 'n' righe e 10 colonne - per ogni stringa di posizione 'i' si contano gli anagrammi prendendo in considerazione le stringhe da 'i' a 'n'; ogni volta che si trova che la stringa di posizione 'j' è un anagramma della stringa 'i', si memorizza nel vettore 'indAnag' la posizione 'j'; il primo elemento del vettore 'indAnag' contiene il valore 'conta'; si riporta infine nella stringa 'codice' i caratteri degli anagrammi trovati --------------------------------------------------------------------------- */ #include <iostream.h> #include <fstream.h> #include <stdlib.h> #include <string.h> const int NMAX = 100; const char CODICE_NON_DEFINITO = ' '; typedef char* tStringa; typedef int tVettFreq[10]; typedef tVettFreq* tFreqStringhe; void calcolaFrequenze(tStringa riga, int i, tVettFreq* freq); void trovaAnagrammi(tVettFreq* freq, int pos, int numElem, char* codice, int* indAnag); int isAnag(const tVettFreq str1, const tVettFreq str2); /* ------------------------------------------------------------------------- */ int main(int argc, char *argv[]) { ifstream in("input.txt"); ofstream out("output.txt"); int r,i,numAnag; tStringa* seq; char riga[81]; char codice[NMAX+1]; int posAnag[NMAX+1]; int n; tFreqStringhe freq; in >> n; in.getline(riga, 80); // cout << n; codice[n]='\0'; freq= new tVettFreq[n]; seq= new tStringa[n]; /* -- Lettura input -- */ // lettura delle righe for ( r =0; r < n; r++ ) { codice[r] = CODICE_NON_DEFINITO; seq[r] = new char[81]; in.getline(seq[r], 80); calcolaFrequenze(seq[r], r, freq); // cout <<"\n" <<seq[r]; } // trova anagrammi e prepara caratteri codice for (r=0; r<n; r++) { if (codice[r] == CODICE_NON_DEFINITO) { trovaAnagrammi(freq, r, n, codice, posAnag); numAnag= posAnag[0]; // cout <<"\n" <<r <<" " << numAnag; for (i=1; i<= numAnag; i++) { codice[posAnag[i]] = seq[posAnag[i]][numAnag-1]; } } } // cout <<"\n"<<codice <<"\n"; out <<codice; in.close(); out.close(); // system("PAUSE"); return 0; } /* ------------------------------------------------------------------------- */ void calcolaFrequenze(tStringa riga, int i, tVettFreq* freq){ int colCar; for (int colCar=0; colCar<10; colCar++) freq[i][colCar]=0; for (int c=0; riga[c]; c++){ colCar = riga[c] - '0'; freq[i][colCar]++; } } /* ------------------------------------------------------------------------- */ void trovaAnagrammi(tVettFreq* freq, int pos, int numElem, char* codice, int* indAnag){ int numAnag=1; indAnag[1] = pos; int i; for (i=pos+1; i< numElem; i++) if ( (codice[i]== CODICE_NON_DEFINITO) && isAnag(freq[pos], freq[i]) ) { numAnag++; indAnag[numAnag] = i; } indAnag[0] = numAnag; } /* ------------------------------------------------------------------------- */ int isAnag(const tVettFreq str1, const tVettFreq str2) { for (int i=0; i<= 9; i++) { if (str1[i] != str2[i]) return 0; } return 1; }
Testo del problema