ZOJ Problem Set - 1483
Xylophone produces N working robots. But these robots are just lazy as Xylophone. Each time their work assginment is not well arranged so that some robots do more work than others, they complains a lot and even goes on strike sometimes.
The other day, Xylophone asks the robots to do his homework. He has M problems to do, each of which has a difficulty level. for convenience, Xylophone assigns these problems in their original order, so that each robot gets some neighboring problems. Xylophone needs a scheme to assign the problems, so that the difference between the total difficulty points of a robot and the average value does not exceed K. Notice that a robot gets difficulty point 0 if he is not assigned any problems.
Your job is to tell whether such a scheme exists.
There are multiple cases.
The first line contains three integers N, M and K. (0 < N, M<= 500, 0 < K <= 2,000,000)
The following M lines contains one integer Di (0 < Di <= 2,000,000), which is the difficulty level of the ith problem.
One line for each case, eith "possible" or "impossible".
2 3 1
Author: XU, Chuan
Source: ZOJ Monthly, January 2003