Crêpes parfaites – Qualification 2018

Level 5

Énoncé

Joseph Marchand se lance un défi, il doit produire une crêpe tout en se promenant sur la plage, promenade qui doit satisfaire certaines contraintes qu'il a définies à l'avance.

Il a commencé par dessiner des disques à certains endroits sur le sol qu'il numérote de 0 à $N$ - 1, le disque 0 correspondant à l'emplacement de son stand à crêpes. Sur chacun d'entre eux, il plante une pancarte indiquant 2 directions pointant chacune vers respectivement 2 autres emplacements.

Sa promenade doit commencer à l'instant 0 au niveau de son stand et à chaque disque rencontré il doit prendre une des deux directions indiquées selon le critère suivant :

  • la première si le nombre de 1 dans l'écriture binaire du nombre de disques déjà rencontrés est pair

  • la seconde sinon

Joseph tient à ce que sa crêpe soit parfaite, pour cela il faut impérativement qu'elle soit retournée pile au milieu du temps de cuisson. Pour pouvoir réaliser une telle crêpe il faut donc qu'il se trouve au niveau de son stand aux instants $T$, $T+t$ puis $T+2t$ où $T$ est l'instant de début de cuisson, et $t$ la durée de mi-cuisson, cela sachant qu'il met exactement une seconde (il est très rapide) pour se déplacer d'un disque à l'autre.

À l'instant 0 il met en marche sa poêle, et il ne peut pas lancer directement la cuisson d'une crêpe, il lui faudra attendre au moins son prochain retour sur son stand. Par ailleurs, comme il n'est pas infatigable, Joseph arrêtera sa promenade après la seconde $L$ (il peut encore arrêter la cuisson d'une crêpe à cet instant).

Combien Joseph a-t-il de manières différentes de réaliser une crêpe parfaite ?

Entrée

La première ligne contiendra 2 entiers $L$ et $N$, la durée de sa promenade et le nombre de disques qu'il a tracés sur le sol. $N$ lignes suivront, la $i$-ème d'entre elles contiendra 2 entiers qui correspondront dans l'ordre aux 2 directions sur le $i$-ème disque.

Sortie

Vous afficherez un seul entier : le nombre de manières différentes pour Joseph de réaliser une crêpe parfaite pendant sa promenade.

Contraintes

  • $1 \le N \le 2\ 500$
  • $1 \le L \le 2\ 000\ 000$

Attention ! Il n'y a pas de tests de performance pour ce problème, c'est à dire que pour valider les tests de correction il faut déjà avoir la bonne complexité (ie une solution correcte mais trop lente sera jugée non valide).

Runtime constraints

Maximum memory usage
64000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
9 3
1 2
1 2
0 0
Sample output
1
Note

Joseph commence à compter :

  • 0 a un nombre pair (0) de bits à 1, il va donc au disque 1
  • 1 a un nombre impair (1) de bits à 1, il va donc au disque 2
  • 2 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
  • 3 a un nombre pair (2) de bits à 1, il va donc au disque 1
  • 4 a un nombre impair (1) de bits à 1, il va donc au disque 2
  • 5 a un nombre pair (2) de bits à 1, il va donc au disque 0 (son stand à crêpe)
  • 6 a un nombre pair (2) de bits à 1, il va donc au disque 1
  • 7 a un nombre impair (3) de bits à 1, il va donc au disque 2
  • 8 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)

Joseph peut donc commencer à faire cuire une crêpe après 3 secondes, il retombera sur son stand à crêpe 3 secondes plus tard pour la retourner et enfin, 3 secondes après pour la manger.

Sample input
11 3
0 1
2 0
0 1
Sample output
5
Note

Les 5 manières de cuire une crêpe parfaite sont :

  • 3s par côté en commençant à T=1
  • 1s par côté en commençant à T=9
  • 3s par côté en commençant à T=4
  • 4s par côté en commençant à T=3
  • 2s par côté en commençant à T=7

Submit your solution

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