Un peu d'ordre – Qualification 2024

Niveau 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$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
1
5
5 4 3 2 1
Exemple de sortie
OUI
Commentaire

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.

Exemple d'entrée
2
5
5 4 3 2 1
Exemple de sortie
OUI
Commentaire

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.

Exemple d'entrée
3
5
5 4 3 2 1
Exemple de sortie
NON
Commentaire

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