Programozás‎ > ‎Feladatok‎ > ‎

Telefonszámok

A telefonszámok egyre hosszabbak, ezért egyre nehezebb megjegyezni őket. A memorizálás egyik "trükkje", hogy a számokhoz szavakat rendelünk, az SMS begépelésénél használt leütések szerint. Például, ha a telefonunk így néz ki:
akkor az AKAD szó a 2523 szám kódja. Mivel a megfeleltetés nem egyértelmű, van egy kis játéklehetőségünk, és megpróbálhatunk a számokhoz olyan szót rendelni, ami értelmes, és esetleg még köthető is ahhoz a személyhez, akinek telefonszámát kódolja.

Feladat

Írjunk programot, ami egy adott telefonszámhoz és a használható szavak listájához megadja szavaknak egy olyan legrövidebb sorozatát, ami a számot kódolja, és minden szó a megadott listából lett kiválasztva!

Bemenet

A bemenet első sorában a megjegyzendő szám olvasható, ez legfeljebb 100 jegyű. A következő sor a megengedett szavak számát tartalmazza, amelyek száma legfeljebb 50000. Ezután a szavak következnek, soronként egy, mindegyik legfeljebb 50 karakterből áll, és csak az angol ábécé kisbetűit tartalmazza.

Kimenet

Írjuk ki a legkevesebb szóból álló megfelelő sorozatot, vagy a "Nincs megoldás" szöveget, ha nem feleltethető meg szósorozat a telefonszámnak.

Példa

Bemenet  Kimenet
7325189087
5
it
your
reality
real
our
reality our

Tesztadatok

Címkék

A feladat forrása: CEOI 1999, 1. nap, 2, feladat ( link )
Algoritmusok: összes eset generálása, mintaillesztés, visszalépéses keresés