ĐỀ VÀ ĐÁP ÁN _ HSG ĐBSCL _XVI - 2009¬_Cần Thơ _ Môn: Tin

SỞ GIÁO DỤC VÀ ĐÀO TẠO TP.CẦN THƠ
TRƯỜNG THPT CHUYÊN LÝ TỰ TRỌNG
KỲ THI HSG ĐỒNG BẰNG SÔNG CỬU LONG
LẦN THỨ 16 – NĂM HỌC 2008 – 2009



ĐỀ THI ĐỀ NGHỊ MÔN TIN HỌC
Thời gian làm bài : 180 phút

Thí sinh chỉ nộp file bài làm *.PAS.
Đề có 3 câu:

Bài
File bài làm
File dữ liệu
File kết quả

Bài 1: Dãy con lồi
DAYLOI.PAS
DAYLOI.INP
DAYLOI.OUT

Bài 2: Dây chuyền thông báo
THONGBAO.PAS
THONGBAO.INP
THONGBAO.OUT

Bài 3: Bày tranh
PICTURE.PAS
PICTURE.INP
PICTURE.OUT


Bài 1 - Dãy con lồi
Dãy giá trị nguyên A=(A1, A2, …, AN) được gọi là lồi, nếu nó giảm dần từ A1 đến một Ai nào đó, rồi tăng dần tới AN.
Ví dụ dãy lồi: 10 5 4 2 −1 4 6 8 12
Yêu cầu: Lập trình nhập vào một dãy số nguyên, bằng cách xóa bớt một số phần tử của dãy và giữ nguyên trình tự các phần tử còn lại, ta nhận được dãy con lồi dài nhất.
Dữ liệu: Dayloi.inp có dạng
- Dòng đầu là N (N≤2000)
- Dòng tiếp theo là N số nguyên của dãy số (các số kiểu integer)
Kết quả: Dayloi.out gồm:
- Dòng đầu tiên ghi số phần tử lớn nhất của dãy con tìm được
- Dòng tiếp theo ghi các số thuộc dãy con (không thay đổi trật tự các phần tử trong dãy ban đầu)
Ví dụ



Bài 2 - Dây chuyền thông báo
Các học sinh trong một lớp học quyết định lập một dây chuyền thông báo như sau. Mỗi học sinh chọn một học sinh duy nhất khác làm người kế tiếp để truyền trực tiếp thông báo. Khi mỗi học sinh nhận được thông báo, anh ta sẽ truyền ngay cho người kế tiếp của mình.
Dây chuyền thông báo được gọi là tốt nếu nó thoả mãn điều kiện: Khi một học sinh A1 bất kỳ gửi thông báo cho người kế tiếp A2, A2 lại gửi cho người kế tiếp A3,..., cứ như vậy thì cuối cùng thông báo sẽ đến mọi người trong lớp kể cả người ban đầu (A1) đã phát ra thông báo. Không nhất thiết mọi dây chuyền thông báo là tốt.
Bài toán đặt ra là: Cho trước một dây chuyền thông báo, hãy tìm số ít nhất việc thay đổi người kế tiếp để có thể nhận được một dây chuyền thông báo tốt.
Dữ liệu: file văn bản THONGBAO.INP trong đó dòng thứ nhất ghi số N < 10000 là số hcjc sinh trong lớp, các họcc sinh này có tên từ 1 đến N. Trong dòng tiếp theo ghi N số, số thứ i là tên người kế tiếp của học sinh i.
Kết quả: file THONGBAO.OUT như sau: dòng thứ nhất ghi số K là số thay đổi cần tiến hành (nếu dây chuyền thông báo đã cho là tốt thì K=0). Nếu K>0, trong K dòng tiếp theo, mỗi dòng ghi hai tên học sinh, người sau là người kế tiếp mới được thay đổi của người trước.
Ví dụ:
THONGBAO.INP
THONGBAO.OUT

10 6 9 2 7 3 1 10 3 6 9
3 1 4 10 8 8 5



Bài 3 - Bày tranh
Cho n bức tranh mã số từ 1..n (n≤50). Người ta cần chọn ra một bức để đặt ở cửa phòng tranh, số còn lại được treo thẳng hàng trong phòng trên m vị trí định sẵn có mã số 1..m từ trái qua phải. Các bức tranh phải được treo theo trật tự nghiêm ngặt sau đây: tranh có số hiệu nhỏ phải treo ở trên tranh có số hiệu lớn.
Biết các thông tin sau về mỗi bức tranh:
- Tranh thứ i treo tại cửa sẽ đạt trị thẩm mỹ c[i];
- Tranh thứ i treo tại vị trí j sẽ đạt trị thẩm mỹ v[i,j].
- m+1≥n.
- Các giá trị thẩm mỹ là những số tự nhiên không vượt quá 50.
Yêu cầu: Hãy xác định một phương án treo tranh để có tổng trị thẩm mỹ là lớn nhất.
Dữ liệu: Picture.INP
- Dòng thứ nhất ghi n, m (cách nhau 1 dấu cách)
- Dòng tiếp theo là n giá trị c.
- Tiếp đến là n dòng, dòng i gồm m vị trí v[i,1], v[i,2],..v[i,m].
Kết quả: Picture.OUT
- Dòng thứ nhất ghi giá trị thẩm mỹ lớn nhất tìm được
- Dòng thứ hai: ghi mã số hiệu bức tranh treo ở cửa phòng tranh.
-