Alice és Bob kódja
(Megoldás)
Versenyek > ACM
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Versenyek > ACM
Elmélet > Algoritmusok > Dinamikus programozás
Címkék > Feladat
Alice és Bob kódja
az Alphacode című ACM feladat nyomán
A feladat szövege
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ó!"
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ó!"
Alicet 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.
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 kiementi 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
| abcode.be | abcode.ki |
| 25114 1111111111 3333333333 0 | 6 89 1 |
További feladatok
- Írjunk programot, ami beolvas egy kizárólag az angol ábécé nagybetűit tartalmazó karakterláncot a billentyűzetről, és kódolja azt.
- Írjunk programot, ami megadja egy kódolt számsor összes lehetséges dekódolását.