Programozás‎ > ‎Feladatok‎ > ‎

Alice és Bob kódja

Alice és Bob angol nyelven szeretne titkos levelezést folytatni, és a lehetséges kódolási módszerekről beszélgetnek:

Alice: "Használjunk egy egyszerű kódolást: vegyük az angol ábécé nagybetűit, a szóközöket pedig dobjuk el. Legyen 'A' kódja 1, a 'B' kódja 2, és így tovább, végül a 'Z' kódja 26."

Bob: "Ez egy hülye kód, Alice. Tegyük fel, hogy a 'BEAN' szót szeretném neked elküldeni, aminek a kódja 25114. Ezt például többféleképpen is lehet dekódolni."

Alice: "Ez egészen biztos, de a 'BEAN'-en kívűl csupa értelmetlen szót kapnál: 'BEAAD', 'YAAD', 'YAN', 'YKD', és 'BEKD'. Szerintem ezek közül ki tudnád választani a helyes megfejtést. És különben is, miért akarnád nekem a 'BEAN' szót elküldeni?"

Bob: "Ok, akkor ez egy rossz példa volt, de garantálom neked, hogy egy 500 karakter hosszú üzenetnél annyira sok megfejtés lesz, hogy közülük már több is értelmes."

Alice: "Miért, mennyi lesz?"

Bob: "Több trillió!" 

Feladat

Alice-t nem győzték meg Bob érvei; szeretne egy programot, ami megszámolja, hogy egy kódolt karakterláncnak hányféle megfejtése lehetséges. Írjunk programot, ami elvégzi a számolást!

Bemenet

A bemeneti fájl minden sora egy számsort tartalmaz, ami egy karaktersorból készült Alice kódolásával. (Tehát pl. nem kezdődhetnek 0-val.) A fájl utolsó sora egy 0 lesz. 

Kimenet

A kiemeneti fájl eggyel kevesebb sorból áll, mint a bemeneti. Minden sorába a bemeneti fájl adott sorának a lehetséges dekódolásainak a számát kell írni. 

Példa

Bemenet  Kimenet
25114 1111111111 3333333333 06
89
1

Tesztadatok

Címkék

A feladat forrása: ACM feladat
Algoritmusok: dinamikus programozás

megoldás