Đề thi chọn HSG

SỞ GIÁO DỤC ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH
HÀ TĨNH LỚP 12 THPT NĂM HỌC 2013-2014
Môn thi: Tin học
Thời gian: 180 phút
ĐỀ CHÍNH THỨC
----------------------------------------------------------------------------------------------


Bài 1: Độ lệch cực đại
Với một số N có 4 chữ số và không phải tất cả các số đều giống nhau, phép tính độ lệch cực đại của nó được thực hiện như sau:
- Tạo số thứ nhất N1 bằng cách sắp xếp các chữ số theo trình tự giảm dần
- Tạo số thứ hai N2 bằng cách sắp xếp các chữ số theo trình tự tăng dần (Nếu có chữ số 0 thì N2 không phải là số 4 chữ số.)
- Tính hiệu N3=N1-N2.
Các bước trên lại được thực hiện với số N3 cho đến khi nhận được kết quả là 6174 hoặc 0.
Hãy xác định số lần biến đổi thực hiện được.
Dữ liệu vào là tệp văn bản DLCD.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên có 4 chữ số và không phải tất cả các chữ số đều giống nhau.
Dữ liệu ra là tệp văn bản DLCD.OUT chứa số lần biến đổi thực hiện được với mỗi số trong tệp dữ liệu vào, mỗi số ghi trên một dòng tương ứng.
Ví dụ:

DLCD.INP
DLCD.OUT

5364
2221
3
5


Bài 2: Bố trí nhân công.
Trong một đơn vị sản xuất có N nhân công có số hiệu là 1..N. Do đặc thù của việc sản xuất mà các nhân công được bố trí theo từng nhóm K người. Trong từng nhóm K người, mỗi người có một số thứ tự khác nhau và làm một công việc khác nhau tùy theo số thứ tự của người đó trong nhóm.
Hãy đưa ra tất cả các cách bố trí nhân công theo từng nhóm K người để thực hiện các công việc phục vụ sản xuất.
Dữ liệu vào là tệp văn bản BTNC.INP chỉ có một dòng ghi hai số nguyên dương N, K cách nhau ít nhất một ký tự trống (1<=K<=5; 1<=K Dữ liệu ra là tệp văn bản BTNC.OUT có cấu trúc:
- Dòng đầu tiên ghi một số nguyên dương M là số lượng các cách bố trí nhân công
- M dòng tiếp theo, mỗi dòng ghi K số nguyên dương cách nhau ít nhất một ký tự trống là số hiệu của các nhân công trong một cách bố trí.
Ví dụ:






BTNC.INP
BTNC.OUT

3 2
6
1 2
1 3
2 1
2 3
3 1
3 2

 Bài 3: Tần số phát sóng
Người ta phân hoạch một vùng đất hình chữ nhật thành MxN ô vuông bởi các đường kẻ song song với các đường biên của vùng đất đó. Vị trí của mỗi mảnh đất ô vuông được xác định bởi cặp (x,y) trong đó x là số thứ tự dòng tính từ trên xuống dưới, y là số thứ tự cột tính từ trái sang phải của mảnh đất ô vuông đó khi ta ở một tư thế nhìn từ một mặt phẳng song song phía trên mặt phẳng chứa vùng đất. Tại mỗi vị trí ô vuông của vùng đất được đặt một máy phát sóng vô tuyến điện tử. Mỗi máy có thể phát ra các loại sóng có dải tần số A hoặc B; tại mỗi thời điểm phát sóng chỉ phát ra một loại sóng có một dải tần số nào đó mà thôi. Ta có thể di chuyển từ vị trí máy phát sóng này đến vị trí máy phát sóng khác nếu hai máy phát sóng đó nằm trên hai mảnh đất ô vuông có chung cạnh. Một vùng máy phát sóng là một tập hợp các mảnh đất ô vuông kề cạnh với nhau và trên đó đặt các máy phát sóng phát ra loại sóng có cùng dải tần số. Việc xác định hai máy phát sóng nào đó nằm trên hai mảnh đất ô vuông có cùng một vùng phát sóng tại một thời điểm phát sóng nào đó hay không có ý nghĩa cho việc lên kế hoạch phát sóng trong lần phát sóng kế tiếp.
Cho trước vị trí của hai mảnh đất ô vuông, hãy xác định hai mảnh đất ô vuông đó có vùng một vùng phát sóng tại một thời điểm phát sóng nào đó hay không?
Dữ liệu vào là tệp văn bản TSPS.INP có cấu trúc:
- Dòng đầu tiên ghi hai số M, N (1<=M<=100, 1<=N<=100).
- M dòng tiếp theo, mỗi dòng ghi N ký tự ‘A’ hoặc ‘B’ nếu máy phát sóng đặt trên mảnh đất ô vuông tương ứng phát loại sóng có dải tần số A hoặc B trong một lần