Loqueteaux – Regional event 2022

Level 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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
2
0 0 0 1 1 0 0 1 1 1
Sample output
OUI
Note

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.

Sample input
10
3
0 0 0 1 1 0 0 1 1 1
Sample output
NON
Note

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

Submit your solution

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