Alice e Bob sono dei turisti stranieri che hanno organizzato un'escursione sulla cima dell'Etna, dove non c'è copertura per usare i cellulari. Dovendo comunicare da un punto all'altro dell'Etna, decidono di scambiarsi i messaggi attraverso dei segnali di fumo, vista la facile reperibilità di sbuffi fumosi sull'Etna.
Viene concordato un codice comune che utilizza due soli tipi di nuvole di fumo, piccole e grandi, facilmente distinguibili. Viene assegnato il simbolo 0 a ciascuna nuvola piccola e il simbolo 1 a ciascuna nuvola grande. In tal modo, i segnali di fumo sono facilmente identificabili con le sequenze binarie, composte da 0 e 1, di lunghezza arbitraria.
La lingua madre di Alice e Bob usa un alfabeto di sette lettere: A, B, C, D, E, F, G. Viene quindi deciso di assegnare un codice binario a ciascuna delle lettere suddette:
Sfortunatamente, dopo le prime trasmissioni, Alice e Bob realizzano che messaggi diversi sono codificati dalla stessa sequenza binaria. Per esempio, quando arriva la sequenza 00100, questa è ambigua in quanto può essere stata prodotta da ADA, AF, CAA, CB oppure EA. Con sequenze binarie più lunghe, il grado di ambiguità aumenta ulteriormente. Inoltre, non tutte le sequenze binarie corrispondono a messaggi: per esempio, 00101 non codifica alcun messaggio, mentre 001010 corrisponde a CD.
Data una sequenza binaria S, aiuta Alice e Bob a individuare l'ultima cifra x del numero (rappresentato in decimale) di messaggi diversi che hanno codifica S. Per esempio, la sequenza S = 000000 corrisponde a 13 messaggi distinti, per cui x = 3.
Il file input.txt contiene due righe. La prima riga contiene un intero N che rappresenta la lunghezza della sequenza binaria.
La seconda riga contiene una sequenza binaria di N valori (0 oppure 1) separati da uno spazio. L'i-esimo valore in tale riga rappresenta l'i-esimo elemento della sequenza binaria.
Il file output.txt deve contenere una sola riga con l'ultima cifra x del numero (rappresentato in decimale) di messaggi diversi la cui codifica è la sequenza binaria in input.txt.
| File input.txt | File output.txt |
5 0 0 1 0 0 | 5 |
| File input.txt | File output.txt |
6 0 0 1 0 1 0 | 1 |
| File input.txt | File output.txt |
5 0 0 1 0 1 | 0 |
| File input.txt | File output.txt |
6 0 0 0 0 0 0 | 3 |