16 năm Olympic Quốc tế (1989-2006)

 
 Đây là cuộc thi Olympiad Quốc tế môn Tin học đầu tiên được tổ chức tại thành phố Pravetz, Bulgaria từ ngày 16 đến ngày 19 tháng 5 năm 1989
 
Bài toán 1
Cho trước 2*N hộp nằm cạnh nhau trên cùng một hàng với N <= 5. Trong đó có hai hộp liền nhau trống rỗng, các hộp còn lại chứa N-1 vật "A" và N-1 vật "B".
Ví dụ, với N = 5 ta có như sau:


 
Quy tắc trao đổi: Chuyển các vật trong hai hộp liền nhau chứa đồ vật sang hai hộp rỗng, giữ nguyên vị trí các hộp.
Yêu cầu
Tìm cách hoán chuyển sao cho tất cả các hộp chứa vật A nằm bên trái các hộp chứa vật B, không cần biết các hộp rỗng nằm ở đâu.
Bài toán đặt ra
Hãy viết chương trình:
1. Xây dựng mô hình hoán chuyển các hộp với số hộp và trạng thái ban đầu của các hộp được nhập từ bàn phím. Mỗi hoán chuyển được nhập bằng số (thuộc từ 1 đến N-1) của hai hộp liền nhau đầu tiên sẽ được đổi chỗ cho các hộp rỗng. Chương trình phải tìm và báo cáo trạng thái các hộp sau khi hoán chuyển.
2. Cho trước hiện trạng các hộp, tìm ít nhất một cách hoán chuyển đạt mục tiêu cuối cùng của bài toán. Chương trình phải báo cáo cả trạng thái ban đầu và trạng thái hiện tại sau mỗi bước hoán chuyển.
3. Tìm những cách hoán chuyển để số hộp bị di chuyển ít nhất và vẫn đạt được mục đích.

Bài toán 2
 Các tầng trong một tòa nhà được đánh số tuần tự từ 0, 1, 2, ..., N (N<=15). Trong tòa nhà có tất cả K (1<=K<=4) thang máy. Thang máy được điều khiển từ một trung tâm và chỉ chấp nhận hai lệnh được nhập vào bằng cách bấm nút. Các nút ngoài thang máy (một nút ra lệnh lên và một nút ra lệnh xuống) có ở tất cả các tầng. Các nút trong (ra lệnh đến một tầng cụ thể) có trong mỗi thang máy.
 Hãy viết chương trình mô phỏng quá trình điều khiển thang máy với các lệnh sau:
1. Trong tòa nhà có một thang máy (K=1) và mỗi lần nó chỉ chấp nhận một lệnh.
Các lệnh khác chỉ được chấp nhận khi lệnh trước đó được hoàn thành.
2. Trong tòa nhà có nhiều thang máy (K>=1). Mỗi thang máy chỉ chấp nhận lệnh từ nút trong nếu không có lệnh nào đang được xử lý. Thiết bị điều khiển có thể nhận nhiều lệnh cùng lúc. Các lệnh trong luôn được thang máy thực hiện mỗi khi ra lệnh. Thiết bị điều khiển sẽ chọn chiếc thang máy đang rỗi phù hợp nhất để thực hiện lệnh ngoài.
3. Xét trường hợp tương tự trong yêu cầu 2 với điều kiện các thang máy số chẵn chỉ có thể dừng ở các tầng số chẵn và các thang máy số lẻ chỉ dừng ở các tầng số lẻ. Tất cả các thang máy đều có thể dừng ở tầng 0.
4. Xét trường hợp trong yêu cầu 3 và giả sử tại mỗi thang máy có nhiều lệnh đang đợi thực hiện. Tất cả các lệnh trong đều được chấp nhận dù cho thang máy có rỗi hay không.

Gợi ý:
Tất cả các thang máy đều đồng bộ và tại một điểm thời gian, các thang máy đều ở các tầng cho trước nào đó.
Trong một khoảng thời gian tiếp theo, một thang máy có thể đi lên đi xuống hay ở nguyên tầng cũ.
Các lệnh có thể nhập vào bất cứ lúc nào, các lệnh có định dạng sau:
a, Lệnh ngoài - ;
b, Lệnh trong -
Tại mỗi thời điểm có thể nhập nhiều lệnh hoặc không nhập lệnh nào.
Tại mỗi thời điểm chương trình báo vị trí của mỗi chiếc thang máy.
Thang máy đủ lớn và không bị quá tải.
Chương trình phải điều khiển thang máy sao cho tối ưu nhất.


Bài toán 3
Cho trước một nhóm N người. Mỗi người là bạn của hơn [N/2] người còn lại và là kẻ thù
của không quá K người. Một người có một cuốn sách mà tất cả mọi người đều muốn đọc và thảo luận với một số người khác.
Hãy viết chương trình:
1. Tìm cách truyền tay nhau cuốn sách sao cho tất cả mọi người đều được đọc nó một lần và chuyển nó cho bạn mình và cuối cùng cuốn sách về tay người chủ.
2. Chia nhóm người thành S tổ để thảo luận về cuốn sách. Mỗi người phải có không quá P kẻ thù trong