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.