ACM RTK - 2. skupina

Vnos šifre

Dana je številčna tipkovnica, na kateri so tipke kvadratne oblike in razporejene v pravokotniku podoben lik, kot kaže naslednja slika:

Radi bi si izbrali neko n-mestno zaporedje števk, ki ga bomo uporabljali kot šifro oz. geslo. Da ga bo čim lažje tipkati, si želimo, da bi se vsak par zaporednih števk v šifri tipkal z isto tipko ali pa s tipkama, ki sta si na gornji tipkovnici sosedi. Pri tem sosednost pomeni, da imata tipki skupno eno od stranic; na primer, v šifri se lahko takoj za števko 4 pojavi števka 1, 5 ali 7, ne pa 2 ali 8. Nekaj primerov veljavnih 6-mestnih šifer: 414558, 696969, 089632.

Napiši podprogram NastejSifre(n), ki kot parameter dobi naravno število n in izpiše vse n-mestne šifre, ki ustrezajo opisani omejitvi. Pri tem je vseeno, v kakšnem vrstnem redu jih program izpiše, mora pa izpisati vsako primerno šifro natanko enkrat.

Lažja različica naloge: če ti je dosedanja naloga pretežka, lahko rešiš lažjo različico, pri kateri ima n vedno vrednost 6, torej nas zanimajo le 6-mestne šifre. Za rešitev te različice lahko dobiš pri tej nalogi največ 15 točk (od 20 možnih).