XXVIII Всеукраїнська олімпіада з інформатики
Перший тур
1. Мутація
Вчені планети Олімпія кожен рік досліджують різноманітні мутації геномів примітивних організмів. Геном таких організмів може бути представлений як послідовність N невід’ємних цілих чисел, які занумеровані зліва направо від одиниці до N та не перевищують число N. Геноми підлягають постійним мутаціям. На кожному етапі мутації геном змінюється таким чином:
· на перше місце записується кількість одиниць увхідному геномі;
· на друге місце записується кількість двійок увхідному геномі;
· ...,
· на місце номер N записується кількість чисел, якідорівнюють N, у вхідному геномі.
Наприклад, геном [1, 2, 3] з трьох чисел після мутаціїперетвориться на [1, 1, 1] — по одній одиниці, двійці татрійці. Інші приклади:
· [1, 2, 2, 3, 3, 3] --> [1, 2, 3, 0, 0, 0]
· [7, 7, 7, 4, 7, 4, 4] --> [0, 0, 0, 3, 0, 0, 4]
Далі геном продовжує змінюватися за тим самимпринципом.
Завдання
Напишіть програму mutation, яка за інформацією пропочатковий вигляд геному визначить його станпісля K мутацій.
Вхідні дані
Програма Mutation читає з пристроюстандартного введення два цілих числа N і K (1<-N<=10^5 ,1<=K<=10^9),що задають початковий розміргеному та кількість мутацій, які геном переживе. Другий рядок містить N невід’ємних цілих чисел, що не перевищують N, — початковий вигляд геному.
Вихідні дані
Програма виводить на пристрій стандартноговиведення геном після K мутацій у тому ж форматі,що й у вхідному файлі: N чисел, розділені пропуском.
Приклад
|
Введення |
Виведення |
|
4 2 1 3 1 4 |
2 1 0 0 |
Пояснення. Спочатку [1, 3, 1, 4] мутує в геном [2, 0, 1, 1], який у свою чергу мутує в [2, 1, 0, 0].