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
0 | 6 89 1
|
Tesztadatok
Címkék
A feladat forrása: ACM feladat
Algoritmusok: dinamikus programozás
megoldás