Un peu d'ordre – Qualification 2024

Level 2 ⋅ Validation weight: 20%

Énoncé

Höder est arrivé à temps pour réaliser la photo familiale. Frigg, la divinité de la famille et du mariage, porte une attention particulière à cette photo et envisage que chaque membre soit ordonné. Frigg se sent débordée vu le nombre de proches faisant partie de la photo, c'est pourquoi Jøsëf Marchand propose son aide pour ordonner rapidement toute la famille.

Cette famille est composée de $N$ personnes.

Le but est de ranger chaque personne en fonction de sa taille. Le premier sur la photo doit être le plus petit et le dernier doit être le plus grand. Pour ordonner tout ce monde, nous pouvons faire cette opération autant de fois que voulu :

  • Choisir $i$.
  • Inverser la $i^{ème}$ et la $(i + K)^{ème}$ personne.

$K$ est le nombre magique, il vous est donné.

Afficher s'il est possible d'ordonner les personnes de la famille.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : K, le nombre magique.
  • Sur la ligne suivante, un entier : N, le nombre de personnes.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : tailles, la liste des tailles de chaque personne.

Sortie

Afficher OUI s'il est possible de trier les personnes par taille ou NON si ce n'est pas possible.

Contraintes

  • $1 \le K \le 1\,000$
  • $1 \le N \le 1\,000$
  • $1 \le tailles_i \le 1\,000$

Contraintes de performance

  • $1 \le N \le 100\,000$

Runtime constraints

Maximum memory usage
100000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
1
5
5 4 3 2 1
Sample output
OUI
Note

Au départ, la famille est ordonnée comme suit : 5 4 3 2 1. Vu que $K = 1$, il nous est possible, autant de fois que nous le souhaitons, d'échanger deux personnes adjacentes.

Voici un exemple de comment nous pouvons ordonner la famille :

  1. 5 4 3 2 1, on effectue ensuite l'opération avec $i = 4$, ce qui inverse 2 et 1,
  2. 5 4 3 1 2, on choisit alors $i = 3$, ce qui inverse 3 et 1,
  3. 5 4 1 3 2, on choisit alors $i = 2$, ce qui inverse 4 et 1,
  4. 5 1 4 3 2, on choisit alors $i = 1$,
  5. 1 5 4 3 2, on choisit alors $i = 4$,
  6. 1 5 4 2 3, on choisit alors $i = 3$,
  7. 1 5 2 4 3, ...
  8. 1 2 5 4 3
  9. 1 2 5 3 4
  10. 1 2 3 5 4
  11. 1 2 3 4 5

Nous pouvons bel et bien ordonner la famille.

Sample input
2
5
5 4 3 2 1
Sample output
OUI
Note

Au départ, la famille est ordonnée comme suit : 5 4 3 2 1. Vu que $K = 2$, il nous est possible, autant de fois que nous le souhaitons, d'échanger deux personnes qui se situent à un écart de 2 l'une de l'autre.

Voici un exemple de comment nous pouvons ordonner la famille :

  1. 5 4 3 2 1, on effectue ensuite l'opération avec $i = 1$, ce qui échange 5 et 3,
  2. 3 4 5 2 1, on choisit alors $i = 2$,
  3. 3 2 5 4 1, on choisit alors $i = 3$,
  4. 3 2 1 4 5, et on choisit enfin $i = 1$,
  5. 1 2 3 4 5.

Nous pouvons bel et bien ordonner la famille.

Sample input
3
5
5 4 3 2 1
Sample output
NON
Note

Il est impossible d'ordonner la famille avec 3 comme nombre magique.

Submit your solution

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