Loqueteaux – Épreuve régionale 2022

Niveau 3

É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

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
10
2
0 0 0 1 1 0 0 1 1 1
Exemple de sortie
OUI
Commentaire

Il est possible d'échanger les loqueteaux en position 4 et 6, ainsi que les loqueteaux en position 5 et 7 (On considère une position comme étant un nombre allant de 1 à $N$). Ainsi les 5 loqueteaux en position 0 se retrouveront dans la moitié gauche de la liste.

Exemple d'entrée
10
3
0 0 0 1 1 0 0 1 1 1
Exemple de sortie
NON
Commentaire

Il n'est pas possible d'ouvrir la porte en n'échangeant que des loqueteaux situés à une distance de 3.