NézetNyomtat

Alice és Bob kódja (Megoldás)
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ó!"
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.beabcode.ki
25114 1111111111 3333333333 06 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.

Tesztadatok