Selezioni regionali 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
| File input.txt | File output.txt |
6
1949
21
9419
12
4356373
9149
|
411244
|
| File input.txt | File output.txt |
4
022
524
322
742
|
0537
|
Nota/e
- Un programma che restituisce sempre lo stesso valore,
indipendentemente dai dati in input.txt, non totalizza
alcun punteggio.