Bài toán N con xe

[ngtrhieu0011]

Trên 1 bàn cờ NxN, mỗi ô bàn cờ có 1 con số thuộc đoạn [-1000,1000]. Hãy tìm các đặt N con xe trên bàn cờ sao cho không có con xe nào khống chế con xe nào (không có 2 con xe nằm trên cùng hàng hoặc cột), và tổng N ô mà N con xe đứng lớn nhất có thể có.

Dữ liệu vào trong file Conxe.Inp:
Dòng đầu ghi số N
i trog N dòng tiếp theo, mỗi dòng ghi lần lượt N số nguyên là giá trị của N ô trong dòng đó.
Dữ liệu kết quả trong file Conxe.Out:
Dòng đầu ghi số M là tổng lớn nhất tìm được
Dòng thứ 2 ghi N số, số thứ i ghi vị trí của ô được chọn trong dòng i.
Giới hạn: 0< N < 201
Thời gian chạy: 10s.

Ví dụ:
Conxe.Inp
4
2 8 1 3
8 9 6 4
2 8 3 5
5 9 2 6

Conxe.Out
25
2 1 3 4

Giải thích:
Tổng tìm được là 25
Các ô được chọn là
(1,2)
(2,1)
(3,3)
(4,4)

Mình đã có sẵn 10tests đây, các bạn post code lên thử mình test xem ai chạy "trâu bò" hơn nhé ^^

[quangtq]

Xong. Bài này mình làm theo cách mà mình thích nhất (giỏi nhất phần này): quay lui.


Uses Crt;
Const Max = 200;
Var
A,Result:Array[1..Max] of 1..Max;
V:Array[1..Max,1..Max] of -1000..1000;
n:1..Max;
k:LongInt;
Free:Array[1..Max] of Boolean;
FI,FO:Text;

Procedure Enter;
Var i,j:Integer;
Begin
Assign(FI,'CONXE.INP'); Reset(FI);
Assign(FO,'CONXE.OUT'); Rewrite(FO);
Readln(FI,n);
For i:=1 to n do
For j:=1 to n do Read(FI,V[i,j]);
FillChar(Free,n+1,True);
FillChar(A,n+1,0);
k:=-1000*n-1;
End;

Procedure PrintResult;
Var i:Integer;
Begin
Writeln(FO,k);
For i:=1 to n do Write(FO,Result[i]:5);
End;

Function Sum:LongInt;
Var S:LongInt;
i:Integer;
Begin
S:=0;
For i:=1 to n do s:=s+V[i,a[i]];
Sum:=S;
End;

Procedure Try(i:Integer);
Var j:Integer;
Begin
For j:=1 to n do If Free[j] then
Begin
A[i]:=j;
If i=n then
Begin
If k<Sum then Begin k:=Sum; Result:=A; End;
End
Else
Begin
Free[j]:=False;
Try(i+1);
Free[j]:=True;
End;
End;
End;

BEGIN
ClrScr;
Enter;
Try(1);
PrintResult;
Writeln(' Everything is done !! ');
Close(FI); Close(FO);
Readln;
END.

Pro QHĐ bld vào thử QHĐ bài này xem

[ngtrhieu0011]

Bài bạn Quangtp nếu mà chấm bằng chương trình chấm tự động là cho Zeros rồi: lý do là không bao giờ dùng hàm Read hay Readln để dừng chương trình.

Sau khi xóa lệnh Readln thì bài này chạy được 4/10 tests.

[=========> Bổ sung bài viết <=========]

Bài bạn Quangtp nếu mà chấm bằng chương trình chấm tự động là cho Zeros rồi: lý do là không bao giờ dùng hàm Read hay Readln để dừng chương trình.

Sau khi xóa lệnh Readln thì bài này chạy được 4/10 tests.

[quangtq]

Nhục quá. Tại quay lui nên dữ liệu lớn thì chậm.
Các test còn lại là sai hay chậm hả anh?

[ngtrhieu0011]

chậm
==========================================

[quangtq]

Biết ngay mà. Thử cách khác xem sao.

[bld]

Writeln(' Everything is done !! ');
Readln;
END.

Pro QHĐ bld vào thử QHĐ bài này xem

everything is done ? vui nhỉ ... đúng là máy chấm thì ko dc điểm rồi (đọc đoạn này thấy quang hơi giống mr.Bo :p )
bài này QHD được à ,.. để nghĩ xem , nhưng ko phải lúc nào QHD cũng dc
P/S : sẵn đây nói luôn , mình ko phải pro , nhiều người hơn lắm , chỉ là làm nhiều thì quen , thế thôi ^^

[quangtq]

Mình hay viết câu đấy khi dùng file. :D
Uhm. Tưởng bài này bld nghĩ ra cách nào QHĐ. Uhm. Vậy phải cắt nhánh thế nào đó. Chậm quá

[ngtrhieu0011]

dùng Greedy đi, bài nào tham lam càng khéo càng tốt, test ra cần xác xuất chính xác thôy

[=========> Bổ sung bài viết <=========]

ý là cách tìm ra có sai khác với đáp án 1 khoảng nào đó chấp nhận được thì có thể coi là đúng ^^

[quangtq]

Chưa nghĩ ra tham lam thế nào. Anh Hiếu thử nói đi.
P/S: Thi Tin học trẻ thì máy chấm hay người chấm?

[ngtrhieu0011]

thi nào thì máy cũng chấm cả, đừng lo, cả trăm thí sinh đâu ai rảnh đọc code???

[quangtq]

Vậy 2 thằng cùng đúng thì chơi thằng nào?
Giả thiết thời gian như nhau, thuật toán khác nhau.
Lúc đó chắc phải ngồi đọc chứ

[m2mpro]

Bạn quangtq đừng suy nghĩ việc so sánh chương trình làm gì, bài Tin đc làm phải dựa trên 2 cơ sở : thuật toán đúng đắn và thời gian chạy của thuật toán, nếu thuật toán là đúng đắn và chạy trong 1 thời gian chưa vượt quá time limit của đề thì vẫn đc cho là chính xác, 2 thằng cũng đc 100 pts mà 1 thằng chạy 0.01s một thằng chạy 0.99s (time limit 1s) thì cả 2 thằng vẫn đc trọn điểm bài đó.

Còn nếu đi thi các cuộc thi có nói các bạn in code ra rồi nộp chỉ là thủ tục để khi bạn có phúc khảo hoặc kiện tụng gì đó sẽ so sánh code trên file và code trên giấy để chắc chắn chạy đúng file của thí sinh thôi :).