Bâtiments – Qualification 2024

Niveau 4 ⋅ Validation weight: 10%

Énoncé

Jörmungandr, le serpent se mordant la queue, n'est pas très adroit. Etant géant et passant dans plusieurs villes, il peut casser des bâtiments en faisant un faux mouvement. Verdandi est une norne mais ne peut voir que dans le présent, elle aimerait alors connaître à l'avance l'état des bâtiments.

Le royaume de Midgard est composé de $N$ villes. Jörmungandr se déplace de ville en ville. Comme il se mord la queue, le chemin des villes qu'il emprunte forme une boucle.

Quand Jörmungandr se déplace dans une ville, le nombre de bâtiments cassés dans cette ville devient alors le plus grand nombre de bâtiments cassés entre cette ville et les $K - 1$ suivantes.

Le premier mouvement impacte la première ville ($i = 1$), puis le second mouvement impacte la seconde ville ($i = 2$) et ainsi de suite.

Afin d'aider Verdandi, votre objectif est le suivant : à partir du nombre initial de bâtiments cassés dans chaque ville, déterminer le nombre de bâtiments cassés dans chaque ville après $R$ mouvements du serpent.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de villes.
  • Sur la ligne suivante, un entier : R, le nombre de mouvements du serpent.
  • Sur la ligne suivante, un entier : K, le nombre de villes impliquées dans chaque mouvement.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : villes, le nombre de bâtiments cassés dans chaque ville.

Sortie

Afficher le nombre de bâtiments cassés à chaque ville après les $R$ mouvements sous la forme d'une suite d'entiers séparés par des espaces.

Contraintes

  • $1 \le N \le 1\,000$
  • $1 \le R \le 1\,000$
  • $1 \le K \le 1\,000$
  • $1 \le villes_i \le 1\,000$

Contraintes de performance

  • $1 \le N \le 100\,000$
  • $1 \le R \le 10\,000\,000$
  • $1 \le K \le 100\,000$
  • $1 \le villes_i \le 100\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
5
2
3
2 4 3 6 8
Exemple de sortie
4 6 3 6 8
Commentaire

Voici le nombre de bâtiments initialement cassés dans les 5 villes : 2 4 3 6 8

Nous faisons $R = 2$ opérations consécutives et pour chaque opération, $K = 3$ villes sont impliquées.

  1. 2 4 3 6 8
  2. 4 4 3 6 8, le 1er élément correspond à $\max(2, 4, 3) = 4$
  3. 4 6 3 6 8, le 2e élément correspond à $\max(4, 3, 6) = 6$
Exemple d'entrée
5
2
4
2 4 3 6 8
Exemple de sortie
6 8 3 6 8
Commentaire

Voici le nombre de bâtiments initialement cassés dans les 5 villes : 2 4 3 6 8

Nous faisons $R = 2$ opérations consécutives et pour chaque opération, $K = 4$ villes sont impliquées.

  1. 2 4 3 6 8
  2. 6 4 3 6 8, le 1er élément correspond à $\max(2, 4, 3, 6) = 6$
  3. 6 8 3 6 8, le 2e élément correspond à $\max(4, 3, 6, 8) = 8$
Exemple d'entrée
5
6
3
5 4 3 2 1
Exemple de sortie
5 4 3 5 5
Commentaire

Voici le nombre de bâtiments initialement cassés dans les 5 villes : 5 4 3 2 1

Nous faisons $R = 6$ opérations consécutives et pour chaque opération, $K = 3$ villes sont impliquées.

  1. 5 4 3 2 1
  2. 5 4 3 2 1, le 1er élément correspond à $\max(5, 4, 3) = 5$
  3. 5 4 3 2 1, le 2e élément correspond à $\max(4, 3, 2) = 4$
  4. 5 4 3 2 1, le 3e élément correspond à $\max(3, 2, 1) = 3$
  5. 5 4 3 5 1, le 4e élément correspond à $\max(2, 1, 5) = 5$
  6. 5 4 3 5 5, le 5e élément correspond à $\max(1, 5, 4) = 5$
  7. 5 4 3 5 5, le 1er élément correspond à $\max(5, 4, 3) = 5$
Exemple d'entrée
10
6
3
1 2 3 4 5 6 7 8 9 10
Exemple de sortie
3 4 5 6 7 8 7 8 9 10
Exemple d'entrée
20
42
3
1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1
Exemple de sortie
7 8 7 8 9 10 10 10 10 10 10 9 8 7 6 5 4 4 5 6