
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
possible
Author: XU, Chuan Source: ZOJ Monthly, January 2003 