Android Unlock – Regional event 2010

Level 4

ÉNONCÉ

Avez-vous déjà observé comment débloquer un téléphone portable sous le système d'exploitation Android ? L'écran d'accueil affiche une surface de 3x3 cases, sur laquelle l'utilisateur doit dessiner un motif avec son doigt pour pouvoir débloquer son téléphone. Seul le motif correct débloque le téléphone.

Dans ce problème, il s'agit de calculer le nombre de motifs différents possibles pour évaluer la sécurité de ce système. Voici comment peuvent être formés les motifs. Le téléphone comporte un tableau de 3x3 cases. Pour former un motif, l'utilisateur pose son doigt sur l'une de ces cases, et déplace ensuite son doigt de cases en cases, jusqu'à ce qu'il décide de le relever de l'écran. Au fur et à mesure que l'utilisateur déplace son doigt, les cases visitées s'allument. Le motif final est constitué de l'ensemble des cases allumées ainsi que l'ordre dans lequel elles ont été allumées. Passer au-dessus d'une case déjà allumée ne change pas l'état de la case. Enfin, il est possible de faire un déplacement du type (+2, +1) (c'est-à-dire avec une différence d'une ligne et de deux colonnes entre deux cases successives), ainsi que toutes les déplacements symétriques, en n'allumant que la case de départ et d'arrivée.

Prenez l'exemple du motif suivant :

Android

Le motif est composé de 5 cases allumées. Remarquez que l'on passe deux fois sur la case centrale (sans changer son état la deuxième fois), et que le déplacement entre la troisième et la quatrième case visitée est un exemple d'un déplacement du type (+2, +1) (c'est-à-dire avec une différence de deux lignes et d'une colonne ici), sans allumer les cases adjacentes.

Ecrivez un programme qui renvoie le nombre de motifs possibles commençant par une case de départ donnée en entrée (le coin en haut à gauche ayant les coordonnées (0,0)), et ayant un nombre de cases fixé.

ENTRÉE

  • Sur la première ligne : l'entier x (entre 0 et 2, bornes incluses), la colonne de départ.
  • Sur la deuxième ligne : l'entier y (entre 0 et 2, bornes incluses), la ligne de départ.
  • Sur la trosième ligne : l'entier k (entre 1 et 9, bornes incluses), le nombre de cases des motifs à énumérer.

SORTIE

Un entier, le nombre de motifs possibles remplissant les conditions demandées.

Runtime constraints

Maximum memory usage
5000 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
0
0
2
Sample output
5
Sample input
1
2
3
Sample output
37

Submit your solution

You have to register or log in to be able to submit your solution.