Loqueteaux – Épreuve régionale 2022

Énoncé¶

$N$ loqueteaux empêchent d'ouvrir une porte. Un loqueteau peut se retrouver dans deux positions: gauche (représenté par un 0), et droite (représenté par un 1). Un loqueteau en position droite fixé sur la porte gauche ou un loqueteau en position gauche fixé sur la porte droite bloquent l'ouverture de la porte. La première moitié des loqueteaux sont fixés sur la porte gauche, et l'autre moitié sont fixés sur la porte droite.

Pour pouvoir ouvrir la porte, il est nécessaire qu'aucun loqueteau ne bloque l'ouverture de la porte. C'est-à-dire que tous les loqueteaux situés sur la porte gauche doivent être en position gauche (0), et tous les loqueteaux situés sur la porte droite doivent être en position droite (1).

Grâce à un système ingénieux, vous pouvez échanger la position de deux loqueteaux situés à une distance de $D$ l'un de l'autre. ($D - 1$ loqueteaux les séparent). Par exemple, si $D = 3$, vous pouvez échanger la position de tous deux loqueteaux à une distance de 3 dans la liste des loqueteaux (Le 1er et le 4ème, par exemple).

Est-il possible d'ouvrir la porte en n'utilisant que ce système ?

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, le nombre de loqueteaux.
• Sur la ligne suivante, un entier : D, la distance entre deux loqueteaux échangeables.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : loqueteaux, la liste des positions des loqueteaux.

Sortie¶

Indiquer s'il est possible d'ouvrir la porte.

Contraintes¶

• $2 \le N \le 1\,000$
• $N$ est garanti pair