Números d-espaiats P78422

Donada una base b ≥ 2 i una xifra 0 ≤ d ≤ b, diem que un enter no negatiu n és d-espaiat si n expressat en base b no té cap parell de xifres consecutives tals que totes dues són diferents de d. Per exemple:

• En base 10, l’enter 145447 és 4-espaiat, mentre que el 145 és 4-espaiat però no és 1-espaiat (el parell de dígits 45 no compleix la condició).
• En base 2, l’enter 9 (1001 en binari) és 0-espaiat però no 1-espaiat (el parell de xifres 00 no compleix la condició).
• En base 16, l’enter 298 (12A en hexadecimal) només és 2-espaiat.

Donada una seqüència de casos, a on cada cas està format per un enter b ≥ 2, un enter 0 ≤ d ≤ b, un enter n ≥ 0, i una seqüència d’n enters no negatius volem saber, per cada cas, quants elements de la seqüència són d-espaiats en base b.

Entrada

L’entrada és una seqüència de casos. Cada cas comença amb una base b ≥ 2, una xifra 0 ≤ d ≤ b i un enter no negatiu n, i li segueix una seqüència d’n enters no negatius.

Sortida

Per cada cas, s’ha de dir quants dels elements de la seqüència d’enters és d-espaiat en base b.