NHA TRANG – KHÁNH HOÀ HỘI TIN HỌC VIỆT NAM
OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XI
ĐỀ CHÍNH THỨC
KHỐI THI: CHUYÊN
Thời gian làm bài: 180 phút
Ngày thi: 26 – 04 – 2002
Nơi thi: Trường Đại học Thuỷ sản Nha Trang
Anh/chị hãy lập trình giải các bài toán sau:
BÀI 1: ĐIỀU KHIỂN ROBOT Tên chương trình: ROBOT.???
Trong cuộc thi lập trình điều khiển Robot giữa các đội sinh viên các trường đại học Ban Giám
khảo cung cấp cho các đội một loại Robot có khả năng tự thay đổi hình dạng bề ngoài của nó.
Hình dạng bề ngoài của Robot được xác định bởi vào véctơ trạng thái G = (G
1
, G
2
, …, G
N
),
các giá trị G
1
thuộc khoảng [1, N] và khác nhau từng đội với mọi i.
Nói hai trạng thái GA và GB là khác nhau nếu tồn tại ít nhất một chỉ số mà GA
i
≠ GB
i
.
Sau mỗi đơn vị thời gian, véctơ G thay đổi theo một bảng quy tắc định sẵn Q, trong đó, nếu
Q
1
= K, thì vào thời điểm kế tiếp giá trị của G
i

và số nhỏ nhất C
min
thoả mãn các điều kiện trên.
Dữ liệu: Vào từ file văn bản NUM.INP, gồm 2 dòng:
 Dòng đầu chứa số nguyên A.
 Dòng thứ 2 chứa số nguyên B.
Kết quả: đưa ra file văn bản NUM.OUT 2 dòng:
 Dòng đầu: chứa số nhỏ nhất C
min
tìm được
 Dòng thứ 2: chứa số lớn nhất C
max
tìm được
Ví dụ:
NUM.INP NUM.OUT
20
4181
204181
421810
Bài 3: CHIP Tên chương trình: CHIP.???
Ứng dụng công nghệ Nano, người ta đã sản xuất các con chíp với hàng triệu chân trên 1mm
2
.
Các linh kiện được cấy trên một đường tròn có dây dẫn điện, đảm bảo 2 linh kiện bất kỳ kề
nhau (trên đường tròn) đều dây dẫn nối trực tiếp. Các linh kiện được đánh số từ 1 tới N
(3<N10000).
Thiết kế ban đầu được xây dựng trên cơ sở công nghệ cũ, nên mặc dù đáp ứng yêu cầu
phẳng hoá đồ thị (không có đường dây dẫn giao nhau ngoài điểm chung có thể có ở tại linh
kiện), nhưng nếu bố trí chúng trên đường tròn thì có thể thứ tự các linh kiện theo vị trí trên
đường tròn không phải là từ 1 tới N mà là một hoán vị nào đó của các số 1, 2, …, N. Ngoài

tròn, bắt đầu từ 1 trở đi theo chiều hướng đến chân có chỉ số nhỏ hơn trong số hai chân nối
trực tiếp với nó.
Ví dụ:
CHIP.INP CHIP.OUT
5
4 3
5 2
1 3
4 2
5 3
1 4
5 4
1
3
5
2
4
Ghi chú: Cán bộ coi thi không giải thích gì thêm.