Задача №113861. Козлы и овцы
Начинается финальная схватка козлов и овец за право владеть полем. Для этого N животных выстроились по кругу так, что второе животное стоит за первым, третье животное стоит за вторым, ..., N -е стоит за N - 1 -м, а первое — за N -м. И дальше животные стали по очереди называть числа, после первого число называет второе, после второго — третье, ..., после N - 1 -го — N -е, а после N -го — 1 -е.
С самого начала известны 2 числа M и K . Ходы животных устроены так: вначале первое животное называет какое-то целое число x 1 от 1 до K , но так, чтобы x 1 было меньше M . Следующее животное по кругу называет какое-то целое число x 2 от x 1 + 1 до x 1 + K , но так, чтобы x 2 было меньше M и так далее. То есть каждое следующее число должно быть больше предыдущего и не больше чем предыдущее, увеличенное на K , а также оно должно быть меньше M . Первый игрок, который не сможет сделать ход проигрывает. В зависимости от того, какое животное начинает укажите, представитель какого вида животных победит при правильной игре.
В первой строке даны числа N , M и K ( 1 ≤ N , M , K ≤ 5 000 ).
Во второй строке вводятся N чисел, i -е равно 0 если на i -м месте стоит козёл, и 1 , если на i -м месте стоит овца.
В одной строке выведите N чисел, на i -е число должно быть равно 0 если, начиная с i -го животного, победят козлы и 1 , если, начиная с i -го животного, победят овцы.
Решения, правильно работающие при 1 ≤ N , M , K ≤ 500 , будут оцениваться в 60 балов.
В первом тесте козёл может победить так: В начале он говорит число 2 , после чего овца говорит 3 или 4 . Независимо от этого козёл говорит 5 . Дальше, независимо от числа овцы, козёл скажет 8 , и овца не сможет сделать ход.
2 9 2 0 1
0 1
6 499 5 1 0 0 1 1 0
0 1 1 1 1 0
10 100 10 0 0 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1