Đề và đáp án đề thi HSG môn Tin học tỉnh Ninh Bình(vòng 2)

Sở giáo dục và đào tạo Đề thi chọn học sinh giỏi lớp 12 THPT
Tỉnh ninh bình năm học 2007 - 2008
Môn: Tin học (Vòng 2)
Thời gian làm bài: 180 phút (không kể thời gian giao đề)

Đề thi gồm 03 bài trong tổng số 02 trang


Tên bài
Tên file chương trình
File dữ liệu vào
File kết quả

Bài 1
Lịch thi đấu bóng đá
CALENDAR.PAS
CALENDAR.INP
CALENDAR.OUT

Bài 2
Cắt hình chữ nhật
RECT.PAS
RECT.INP
RECT.OUT

Bài 3
Rút gọn
AUT.PAS
AUT.INP
AUT.OUT


Bài 1 - Lịch thi đấu bóng đá (8 điểm):
Một giải bóng đá X-League có M đội bóng (M = 2N - 1, N nguyên dương) được đánh số thứ tự từ 1 đến M. X-League được tổ chức thi đấu vòng tròn một lượt. Như vậy mỗi đội sẽ phải thi đấu M-1 trận với các đội còn lại. Trong một trận đấu, một đội được đá trên sân nhà, đội còn lại là đá trên sân khách.
Ban tổ chức cần xếp lịch thi đấu thành M vòng, các trận đấu trong cùng một vòng đá cùng một giờ. Mỗi vòng sẽ có N-1 cặp đấu và một đội được nghỉ. Hãy đề xuất với ban tổ chức X-League một phương án xếp lịch sao cho mỗi đội đều có số trận thi đấu trên sân nhà và số trận thi đấu trên sân khách bằng nhau (cùng bằng N-1 trận).

Dữ liệu vào: File văn bản CALENDAR.INP chứa duy nhất số nguyên dương M, (3 ( M ( 100).
Dữ liệu ra: File văn bản CALENDAR.OUT gồm N dòng:
Dòng thứ i là lịch thi đấu ở vòng thứ i.
Mỗi dòng gồm N cặp số x1 y1 x2 y2 … xN yN. Trong đó cặp xj yj là trận đấu giữa đội bóng thứ xj và đội bóng thứ yj trên sân nhà của xj. Giữa các số ngăn cách nhau bằng một ký tự cách.
Ví dụ:
CALENDAR.INP
CALENDAR.OUT

5
2 3 4 5
3 4 5 1
4 1 5 2
1 2 3 5
1 3 2 4


Bài 2 - Cắt hình chữ nhật (6 điểm):
Người ta dùng máy cắt để cắt một hình chữ nhật có kích thước M x N, (M, N nguyên dương) thành các hình vuông có kích thước nguyên dương và có các cạnh tương ứng song song với các cạnh của hình chữ nhật ban đầu (luôn thực hiện được bằng cách cắt hình chữ nhật thành MxN hình vuông kích thước 1x1). Nhát cắt của máy cắt có phương song song với một trong hai cạnh của hình chữ nhật đó. Hãy tìm một phương án cắt sao cho số hình vuông được tạo ra là ít nhất.

Dữ liệu vào: File văn bản RECT.INP gồm một dòng chứa 2 số nguyên M và N (1( M, N ( 100)
Dữ liệu ra: File văn bản RECT.OUT:
Dòng đầu ghi số nguyên K là số lượng các hình vuông được tạo ra.
Dòng tiếp theo ghi K số nguyên dương là độ dài cạnh của K hình vuông đó.
Ví dụ:
RECT.INP
RECT.OUT

5 6
5
3 3 2 2 2


Bài 3 – Rút gọn (6 điểm):
Cho một hình vuông H kích thước