"LAZY COURSE SELECTION" (USA)
When students enroll in a university, they are usually confused by the complexity of the rules for earning a degree. A degree in Computer Science, for instance, has many requirements, and each requirement can be satisfied by many courses. To complicate things further, any single course may satisfy several of the requirements at once. These rules are presented to students when they enter, and the students are left to pick the courses which will earn them a degree.
Since most good programmers are lazy, an entering Computer Science student will want to take as few courses as possible. You should write a program to help a lazy Computer Science freshman select courses to earn a degree.
Courses are numbered by consecutive integers from 1 to C (total number of available courses). Given a description of which courses satisfy which requirements, your program should recommend a set of courses so that every requirement for the degree is fulfilled by at least one recommended course. If there is any requirement left unfulfilled, then the poor student does not get a degree, and the solution is considered invalid and scores zero points. If a solution is determined to be valid, then points are awarded based on the quality of the solution: the fewer courses the student must take, the more points the solution earns.
Note that you will almost certainly not be able to find the optimum answer for some of the test cases within the given run time limit. You should try to get as good a solution as you can in time, making sure your program outputs it and exits before time runs out.
It is guaranteed that there will always be a valid solution.
The first line of the file LAZY.IN contains two space separated integers, C and R. C is the number of courses available to the student (1 £ C £ 200), and R is the number of requirements for a degree (1 £ R £ 100).
The rest of the file contains C lines, one for each course (the first is for course number 1, up through the last for course number C). Each line has R space separated integers (the first is for requirement 1, the last for requirement R).
The r'th integer on the files c+1'st line is 1 if course c fulfills requirement r, and 0 otherwise.
Output file LAZY.OUT should contain two lines. The first line should contain a single integer N - the recommended number of courses for the student to take. The second line should contain N integers separated by single space character indicating the N recommended course numbers. Course numbers may be in any order.
Input data(file LAZY.IN)
Output data(file LAZY.OUT)
4 3 2
0 1 0 2 3
1 1 0
0 1 1
0 0 1
There are 4 available courses and 3 requirements: course 1 fulfills only requirement 2, course 2 fulfills requirements 1 and 2, course 3 fulfills requirements 2 and 3 and course 4 fulfills only requirement 3.
Only two courses (#2 and #3) are recommended.