De thi HSG mon tin 12 vong 2

SỞ GIÁO DỤC – ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 CẤP TỈNH
THỪA THIÊN HUẾ NĂM HỌC 2005 – 2006
Đề chính thức Môn thi: TIN HỌC, vòng 2
Số báo danh: Thời gian: 150 phút (không kể thời gian giao đề)

HỌC SINH LẬP TRÌNH GIẢI HAI BÀI TOÁN SAU:
(đề thi có 4 trang)
Tổng quan về các file:
Tên bài
Tên file nguồn
Tên file văn bản chứa dữ liệu vào, ra



Vào
Ra

Xếp gạch
XEPGACH.PAS
XEPGACH.INP
XEPGACH.OUT

Chinh phục thế giới
THEGIOI.PAS
THEGIOI.INP
THEGIOI.OUT


BÀI 1: XẾP GẠCH.
Minh rất thích trò chơi xếp các chiếc hộp có hình viên gạch. Minh đặt các viên gạch chồng lên nhau và xây thành nhiều chồng có độ cao khác nhau. Minh khoe với chị rằng “Chị trông, em đã xây được một bức tường”. Chị của Minh trả lời “Em phải xếp các viên gạch có độ cao giống nhau mới được gọi là một bức tường”. Sau khi nghe chị nói như vậy nó cân nhắc một tí và cho rằng ý kiến ấy là đúng. Vì vậy em bắt đầu tiến hành sắp xếp lại các chồng gạch lần lượt từng chiếc một cho đến khi hoàn thành công việc. Khi công việc đã hoàn tất, Minh mệt lả và muốn có bạn nào giúp Minh di chuyển các viên gạch với số lần ít nhất.










Các chiếc hộp trước và sau khi xếp
Yêu cầu: Hãy lập trình đưa ra số lần di chuyển ít nhất của các viên gạch sao cho từ các chồng gạch có độ cao khác nhau trở thành các chồng gạch có độ cao bằng nhau; lần lượt từng chiếc một cho đến khi hoàn thành công việc.
Dữ liệu vào: có cấu trúc sau:
dòng đầu tiên là số n, n là số các chồng gạch,
dòng tiếp theo lần lượt là các hi, độ cao của chồng gạch thứ i. (1≤ n ≤ 50; 1≤ hi ≤ 100; i = 1..n). Lưu ý rằng số viên gạch bao giờ cũng chia hết cho số chồng gạch.
Dữ liệu ra: chỉ có một dòng chứa một số nguyên dương là kết quả tính toán số lần ít nhất sau khi xếp lại các chồng gạch. Nếu không có kết quả cũng phải ghi rõ “KHONG CAN DI CHUYEN LAN NAO”
Ví dụ: với hình trên ta có dữ liệu vào, ra:
DỮ LIỆU VÀO
DỮ LIỆU RA

6
5 2 4 1 7 5
Số lần di chuyển tối thiểu là 5 lần

BÀI 2: CHINH PHỤC THẾ GIỚI .
Chinh phục thế giới là trò chơi của các chiến binh La Mã chơi trong những lúc nghỉ ngơi. Trò chơi có nhiều người chơi đối kháng với nhau, tất cả đều cố gắng chinh phục thế giới. Bảng trò chơi là một bản đồ thế giới theo giả thuyết các nước được nối với nhau có hình gấp khúc. Trong lượt đi của người chơi, quân đội của một nước chỉ được cho phép tấn công các nước mà có cùng biên giới chung. Từ đó, quân đội có thể di chuyển vào trong nước mới chiến thắng để tiếp tục đi đến nước khác.
Trong tiến trình của trò chơi, người chơi nhắm vào mục đích chinh phục là phải chiến thắng và sử dụng nước vừa chiếm được để chuyển một khối lượng lớn quân đội từ nước bắt đầu nào đó đến một nước khác cho đến khi kết thúc trò chơi. Người chơi cần coi trọng việc đánh chiếm các nước sao cho tối giản số nước sẽ được chinh phục. Các quốc gia được đánh số từ 1 đến M (1 ≤ M ≤ 100). Hình vẽ sau mô tả một bảng trò chơi với 20 nước giữa 1 và 19 kết nối tới các nước khác.


Sơ đồ kết nối minh họa mẫu nhập vào.
Yêu cầu: Nhiệm vụ của bạn phải viết một chương trình từ nước bắt đầu và một nước nơi đến sau đó tính toán số tối thiểu của các nước phải được chinh phục để đạt đến được đích. Không cần ghi cụ thể ở đầu ra các bước đi, chỉ ghi số nước sẽ được chinh phục kể cả đích đến. Ví dụ, nếu nước bắt đầu và nơi đến láng giềng, thì chương trình của bạn cần phải trả lại một số thôi.
Dữ liệu đầu vào: là tập cấu hình của bảng trò chơi. Dữ liệu vào mô tả bảng nằm trên các dòng 1 đến M-1. Trình bày ranh giới mỗi quốc gia tránh liệt kê hai lần, chỉ liệt kê các biên giới quốc gia I quốc gia J, khi I < J. Như vậy, hàng thứ I, I < M, chứa một