Đề thi chọn HSG cho đội tuyển quốc gia môn Pascal12

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


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 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













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ỹ