Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Mutation

  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].

 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"