Vode

As we all very well know, goats and sheep have been fighting for years about the fields
they’re grazing. After many fierce fights, the goat leader and the sheep leader decided to
meet to try to find a peaceful solution to their problem. After many hours of discussion, they
agreed that they will play a game for each field and that the winner will get to graze that field.
The game is played such that a total of \(N\) animals (that can be goats or sheep) form a circle
(the exact order of goats and sheep is an agreement between their leaders). After animal \(i\) (1
≤\(i \le N-1\)), the game is continued by animal \(i+1\), and after animal \(N\), the game is continued by
animal 1. The animal starting the game can say any positive integer from the interval [1, \(K\)],
but only if that number is not greater than \(M\). If the animal that started the game said the
number \(j\), then the next animal can say a number in interval [\(j+1\), \(j+K\)], but only if that number
is not greater than \(M\). In other words, each animal can say a number that is greater by
minimally 1, and maximally by \(K\) than the number said by the animal before, but only if the
new number is not greater than \(M\). If an animal must say number \(M\), its team (goats or
sheep) loses.
If both the goats and the sheep are playing optimally, for each \(i\) (\(1 \le i \le N\)), determine who
will win the field if the game is started by the \(i^{th}\) animal.

In test cases worth a total of 60% of points, it will hold \(1 \le N\), M, \(K \le 500\).

The first line of input contains N, M and \(K\) (\(1 \le N\), M, \(K \le 5000\)), the numbers from the task.
The following line contains \(N\) numbers, 0 if the \(i^{th}\) animal is a sheep, and 1 if it’s a goat.

Output \(N\) space-separated numbers. For each animal \(i\) (\(1 \le i \le N\)) output 0 if the sheep will
win the field, and 1 if the goats will win, if the \(i^{th}\) animal is starting the game.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 4