Demi-finale 2008, épreuve machine - 42 revisité

DIFFICULTE

LIMITE DE MEMOIRE

600 ko

LIMITE DE TEMPS

500 ms

Joseph Marchand, en bon geek, est obsédé par le nombre 42.

A chaque fois qu'il lit un nombre dans la rue, il essaye de trouver si 42 s'y cache. Par exemple, 42 se cache dans les nombres 452, 87648120, 9876543214, mais pas dans les nombres 24, 1234, 123456789. (Vous l'aurez compris, on dira que 42 se cache dans un nombre x si on peut obtenir 42 à partir de x en retirant certains de ses chiffres).

Etant donné un nombre, Paul se demande combien de 42 différents il peut y lire (deux 42 lus dans un nombre seront dits différents lorsque les positions des chiffres des deux 42 ne sont pas rigoureusement les mêmes).

Un nombre entier x, 0<=x<=10^9

Un nombre entier, le nombre de 42 différents que Joseph peut lire dans x.

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

14422

4

Exemple 2
en entrée ...

42424242

10