Đề thi chọn đội tuyển dự thi HSG quốc gia môn Tin học (Đề 1) - Năm học 2006-2007 - Sở GD&ĐT Nghệ An

 §Ò chÝnh thøc
Së Gd&§t NghÖ an
Kú thi chän ®éi tuyÓn dù thi hsg quèc gia líp 12 
N¨m häc 2006 - 2007
B¶n chÝnh
M«n thi: tin häc
Thêi gian 180 phót( Kh«ng kÓ thêi gian giao ®Ò)
Ngµy thi: 06/11/2006
(§Ò thi nµy cã 2 trang) 
BÀI 1: ĐẤU BÓNG
 Giải bóng đá Quốc gia năm 2006 có N đội tham gia ( 2£ N£20). Ban tổ chức giải đưa ra luật thi đấu như sau: Các đội thi đấu vòng tròn một lượt, nghĩa là mỗi đội đều phải thi đấu với tất cả các đội khác đúng một trận. Sau mỗi trận, đội thắng sẽ được 3 điểm và đội thua được 1 điểm, còn trận đấu hoà thì mỗi đội được 0 điểm. Kết quả thi đấu của giải được cho bởi mảng 2 chiều A[1..N,1..N+1] trong đó A[i,j] bằng số điểm đội i đạt được trong trận thi đấu với đội j. A[i,N+1] bằng tổng số điểm của đội i trong toàn giải. Quy ước A[i,i]=0. Do sơ suất của ban tổ chức, bảng kết quả thi đấu của tất cả các đội đã bị nhoè, một số chỗ không đọc được. Bạn hãy giúp ban tổ chức khôi phục lại những thông tin đã mất. 
	Dữ liệu: Vào từ file văn bản DAUBONG.inp có cấu trúc:
	* Dòng đầu ghi số nguyên dương N là số đội bóng 
	* N dòng tiếp theo là bảng kết quả thi đấu của các đội nhưng bị nhoè , những ô bị nhoè được cho bởi giá trị −1. 
	Kết quả: Ghi ra file văn bản DAUBONG.out, liệt kê mọi khả năng có thể. Mỗi khả năng cách nhau một dòng trắng. 
	Ví dụ: 
DAUBONG.INP
DAUBONG.OUT
3
0 1 1 -1
-1 0 -1 -1
3 -1 0 -1
0 1 1 2
3 0 0 3
3 0 0 3
0 1 1 2
3 0 1 4
3 3 0 6
0 1 1 2
3 0 3 6
3 1 0 4
BÀI 2: BIẾN ĐỔI BẢNG 
Cho một lưới ô vuông kích thước NxM. Mỗi ô của lưới ghi số 0 hoặc 1. Người ta có thể biến đổi bảng này bởi 2 phép biến đối sau: 
* Hoán vị 2 hàng bÊt kú của lưới cho nhau. 
* Thay toàn bộ số 0 bới số 1 vµ thay toàn bộ số 1 bởi số 0 trên một cột nào đó. 
Bài toán đặt ra là: Cho trạng thái ban đầu và trạng thái đích của lưới. Hỏi có thể chuyển lưới từ trạng thái ban đầu về trạng thái đích hay không?
Dữ liệu vào cho File văn bản LUOI.inp có cấu trúc như sau:
Dòng đầu tiên ghi 2 số nguyên dương N, M (1<N, M£100) là kích thước của lưới.
* N dòng tiếp theo, mỗi dòng ghi M số 0 hoặc 1 là trạng thái ban đầu của lưới. 
* N dòng tiếp theo, mỗi dòng ghi M số 0 hoặc 1 là tình trạng đích của lưới 
Kết quả ghi ra File văn bản LUOI.out
Nếu chuyển được ghi số 1, còn trong trường hợp không chuyển được ghi số 0
Ví dụ2
LUOI.inp
LUOI.out
2 2
1 1
1 0
0 0
0 0
0
Ví dụ1
LUOI.inp
LUOI.out
4 3 
1 0 1
0 1 1
1 1 1
0 0 1
1 0 1
0 0 1
1 1 1
0 1 1
1
BÀI 3. BA DÃY SỐ
 Cho 3 dãy số thực, mỗi dãy gồm n số: 
 a1, a2, , an.
 	 b1, b2, , bn.
 	 c1, c2, , cn.
Yêu cầu: Tìm dãy dài nhất các chỉ số i1, i2, , ik mà i1 < i2 << ik đồng thời : 
	ai1 ai2  aik.
	bi1 bi2  bik.
	ci1 ci2  cik.
Dữ liệu: Vào từ file văn bản BADAY.INP có cấu trúc:
Dòng đầu là số nguyên dương n (n 10000).
N dòng tiếp theo: dòng thứ i trong n dòng này ghi 3 số ai, bi, ci. 
Kết quả: Ghi ra file văn bản BADAY.OUT như sau:
Dòng đầu ghi số k là số lượng các chỉ số tìm được.
Dòng thứ hai ghi các chỉ số: i1, i2, , ik. 
Ví dụ
BADAY.INP
BADAY.OUT
10
3 3 2
4 2 1
5 6 2
4 2 3
5 3 6
6 8 7
7 8 7
2 5 0
9 9 8
2 10 6 
6
2 4 5 6 7 9
------------HÕt------------
Hạn chế kỹ thuật: 
- Tất các File dữ liệu vào ra của các bài, các số ghi trên một dòng cách nhau một ký tự trắng
- Chương trình giải các bài 1, bài 2, bài 3 lần lượt ghi lên đĩa với tên BAI1.pas; BAI2.pas; BAI3.pas.
- Giám thị không phải giải thích gì thêm.