trungchanh

Bài này là bài thi Tin học trẻ không chuyên của Vĩnh Long hơi khó nên cần người trợ giúp
****Xếp lịch thi*****
Có n sinh viên tham dự một kỳ thi gồm m môn ghti, mỗi sinh viên tham dự nhiều môn thi. Việc xếp lịch thi là phân
chia kỳ thi ra thành nhiều đợt thi, mội đợt thi gồm nhì6u môn thi được thi đồng thời, nhưng phải bảo đảm là mọi sinh viên đều có thể dự thi tất cả các môn thi của mình.
Viết chương trình tìm ra các cách xếp lịch thi với số đợt thi <=4.
Dữ liệu vể kỳ thi được ghi trong tập tin inp.b4, gồm n+2 dòng:
- Dòng 1: m
- Dòng 2: n
- n dòng tiếp theo chứa: số đầu tiên là số môn mà sinh viên tham dự, các số tiếp theo là các số chỉ môn thi mà sinh viên tham dự.
Ví dụ:
3
4
2 1 2
3 1 3 4
2 1 4
2 3 4
có nghĩa: có 3 môn thi, 4 sinh viên, sinh viên 1 thi 2 môn là môn 1 và môn 2, sinh viên 2 thi 3 môn là môn 1, môn 3 và môn 4, sinh viên 3 thi 2 môn là môn 1 và môn 4, sinh viên 4 thi 2 môn là môn 3 và môn 4.
Ghi dữ liệu xuất ra tập tin out.b4, mỗi dòng là một phương án xếp lịch, gồm m số, mỗi số là đợt thi của môn tương ứng.

__________________
Vịnh Hạ Long niềm tự hào của người Việt đang đứng trước cơ hội trở thành một trong bảy kì quan thiên nhiên thế giới. Vì vậy, hãy bình chọn cho Vịnh Hạ Long.
Click www.vtv.vn để xem hướng dẫn bình chọn
Click www.new7wonders.com để bình chọn
Nhanh tay lên nào !

thienthan

Đề hơi có vấn đề một tí nhớ thắc mắc với người ra đề nhé. Trong trường hợp sau thì không thể làm được: nếu một người thi nhiều hơn 4 môn.
Phần yêu cầu in dữ liệu như vậy đọc sao ổn: yêu cầu như vậy làm sao biết mỗi phiên gồm những môn thi nào?

Nhìn thấy câu này thì bạn tự code lấy ai code hộ bao giờ.

Bạn đã hỏi nên mình gợi ý giải thuật. Đọc dữ liệu chắc không vấn đề gì (dùng hàm kiểm tra xem đã tới cuối dòng chưa).

Nếu chỉ tìm phương pháp tối ưu nhất thì có phương pháp khác.
Sắp xếp danh sách thí sinh theo dạng sau: số môn thí sinh đó tham gia (gợi ý dùng phép đếm phân phối).

Chọn theo quy ước sau:
Đầu tiên sắp xếp dãy dữ liệu vào theo môn của người chọn nhiều môn thi nhất mà có nhiều người thi môn đó nhất.
Cứ chọn môn đó làm môn đầu tiên. và cứ tuần tự chọn các môn còn lại cùng là môn của người thi nhiều môn nhất. Cứ như vậy bạn chọn được phương án tối ưu nhất sau đó bỏ qua môn đó chọn môn kém tối ưu hơn cứ làm như vậy nếu không dạt yêu cầu nữa thì các phương án chọn sau cũng không thể đạt được nữa.

Chúc may mắn!