Bài 4: Xổ số điện toán

 Bài 4: Xổ số điện toán
Có N người (đánh số từ 1 đến N) tham gia một đợt xổ số điện toán. Mỗi người nhận được một thẻ gồm M ô (đánh số từ 1 đến M). Người chơi được chọn K ô trong số các ô đã cho bằng cách đánh dấu các ô được chọn. Sau đó các thẻ này được đưa vào máy tính để xử lý.
Máy tính chọn ra K ô ngẫu nhiên (gọi là các ô kết quả) và chấm điểm từng thẻ dựa vào kết quả đã sinh. Cứ mỗi ô chọn đúng với ô kết quả thì thẻ chơi được tính 1 điểm. Giả thiết biết các ô chọn cũng như các điểm tương ứng của từng thẻ chơi, hãy xác định tất cả các kết quả có thể có mà máy sinh ra.
Dữ liệu vào đọc từ file vănbản XOSO.INP gồm:
- Dòng đầu ghi các số N, M, K
- Dòng thứ i trong N dòng tiếp ghi thẻ chơi của người i gồm K+1 số: K số đầu là các số hiệu của các ô chọn, cuối cùng là điểm tương ứng.
Ghi kết quả ra file văn bản XOSO.OUT, mỗi dòng là một kết quả gồm K số ghi số hiệu các ô mà máy đã sinh.
Ghi chú:
- Các số trên cùng một dòng trong các file vào/ ra, được ghi cách nhau ít nhất một dấu trắng.
- Giới hạn kích thước:N ≤ 100, M ≤50, K ≤10.
- Dữ liệu vào trong cáctest là hợp lệ và đảm bảo có ít nhất một đáp án.
Ví dụ:

Hướng dẫn giải
Ta nhận thấy rằng mỗi nghiệm của bài toán chính là một cấu hình của tổ hợp chập K của M phần tử. Ta áp dụng thuật toán quay lui để duyệt mọi cấu hình tổ hợp để tìm ra cấu hình thoả mãn. Tuy nhiên để giảm bớt số lần duyệt ta cần phải loại những thẻ mà chúng có tổng điểm bằng 0 và cần đánh dấu những thẻ đã được chọn.
Dùng mảng ok[0..51] of boolean để phân biệt giữa ô có điểm và những ô không có điểm. Nếu ok[i]= false thì cho biết thẻ thứ i không có điểm. Còn logic[i,j] = true cho ta biết người thứ i đánh dấu vào thứ j của thẻ.
Văn bản chương trình
Program Xoso_dien_toan;
Type MangA = array[0..100,0..11] of byte;
MangBool = array[0..51] of boolean;
MangLogic = array[0..101,0..51] of boolean;
Cauhinh = array[0..11] of byte;

Const Fi = ’XOSO.INP’;
Fo = ’XOSO.OUT’;
var M,N,K : byte;
A : MangA;
B : Cauhinh;
Ok : MangBool;
Diem : integer;
Logic : MangLogic;
F : Text;

Procedure Init;
Begin
Fillchar(A,sizeof(A),0);
Fillchar(B,sizeof(B),0);
Fillchar(ok,sizeof(ok),1);
Fillchar(logic,sizeof(logic),0);
End;

Procedure Read_inp;
Var i,j : byte;
Begin
Assign(F,Fi); Reset(F);
Readln(F,N,M,K);
For i:= 1 to N do
begin
For j:= 1 to k do
begin
Read(f,A[i,j]); Logic[i,A[i,j]]:= true;
end;
Read(F,A[i,k+1]); Inc(diem,A[i,k+1]);
If A[i,k+1] = 0 then
For j:= 1 to k do ok[A[i,j]]:= false;
end;
Close(F);
End;

Function Chapnhan(j: byte): boolean;
Var v : byte;
Begin
Chapnhan:= false;
For v:= 1 to n do
If (A[v,K+1] = 0) and logic[v,j] then exit;
Chapnhan:=true;
End;

Procedure Rutgon(j: byte);
Var i : byte;
Begin
For i:= 1 to N do
If logic[i,j] then
begin
Dec(A[i,k+1]);Dec(diem);
end;
End;
Procedure Morong(j: byte);
Var i : byte;
Begin
For i:= 1 to N do
If logic[i,j] then
begin
Inc(A[i,k+1]); Inc(diem);
end;
End;

Procedure Write_out;
Var d: byte;
Begin
For d:= 1 to K do write(f,B[d],’ ’); Writeln(F);
End;

Procedure Try(i:byte);
Var j: byte;
Begin
For j:= B[i-1] + 1 to M - K + i do
If ok[j] and chapnhan(j) then
begin
B[i]:= j;
Ok[j]:= false;
Rutgon(j);
If (diem = 0) and (i = k) then write_out
else if i < k then try(i+1);
ok[j]:= true;
Morong(j);
end;
End;

Procedure Run;
Begin
Assign(F,Fo); Rewrite(F);
Try(1);
Close(f);
End;

BEGIN
Init;
Read_inp;
Run;
End.