The following is a simple challenge that I came up with for a student programming contest held nation-wide in Luxembourg. It is based on a classic problem (if you know the problem, you have the solution in no time):
As each year, my family decided to go on holidays together, in the exact same hotel as every year. As we do not have enough money to book single-bed rooms for everyone, we have to organize ourselves to sleep in a limited number of rooms together. As in every family, some members just can't stand each other and refuse to sleep in the same room together.
Given the amount of people that go on holiday together, the number of rooms and the relations between each of the members, determine if it is possible to organize them in such a way that they can all share rooms without any problems.
The input is a text file with the following:
- the first line is the number of people N
- the second line is the number of rooms R
- the next N lines all contain N-1 (we do not need to specify if a person hates himself or not) numbers that determine if two people hate each other (the first number in the first line determines whether person 1 likes person 2)
Example input:
5
3
1 1 0 0
1 0 1 1
1 0 0 0
0 1 0 1
0 1 0 1
The problem should output whether it is possible to find a distribution or not. We can assume that the number of people that can sleep in the same room is infinite.
If you know the solution, don't spoil the fun for everyone and use "invisible colors" or send me your idea by PM.
