I suggest that it's always possible to paint all the doors in such a way that the problem requirements will be satisfied. So I just DFS starting from every room and paint the door to some room in yellow if the amount of green rooms is more than amount of yellow ones for that door, and paint it in green in the other case.
And I get WA10 :D

Edited by author 06.10.2006 22:59