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

Notice: This work is licensed under a BY-NC-SA. Permalink: Codici e pizzini

Comments are closed.