SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 TỈNH CÀ MAU
CÀ MAU NĂM HỌC 2008-2009
- Môn: Tinhọc
- Ngày thi: 07-12-2008
- Thời gian: 180 phút
Bài1: (6 điểm)
Để mã hóa một văn bản gồm toàn chữ cái tiếng Anh người ta có thể làm như sau:
Xếp bảng chữ cái theo vòng tròn, sau đó thay mỗi kí tự bằng kí tự đứng sau nó n vò trí
trong bảng vòng tròn. Ví dụ với n =7 thì “anh” được mã hóa thành “huo”.
Bạn hãy lập chương trình nhập số tự nhiên n, sau đó
- Mã hóa một văn bản (xâu kí tự)
- Giải mã một văn bản đã mã hóa
Bài 2: (7 điểm)
Có X đòa điểm dân cư đánh số từ 1 đến X. Giữa Y cặp đòa điểm trong số X đòa điểm
nói trên có tuyến đường nối chúng. Cần xây dựng một trung tâm dòch vụ tổng hợp tại
một đòa điểm hoặc là trùng với một số các đòa điểm dân cư hay là nằm trên tuyến
đường nối hai đòa điểm nào đó, sao cho tổng khoảng cách từ trung tâm dòch vụ đến X
đòa điểm dân cư là nhỏ nhất. Ta gọi khoảng cách hai đòa điểm là độ dài đường đi ngắn
nhất nối chúng. Giả sử rằng X đòa điểm trên liên thông với nhau.
Dữ liệu: Vào từ file văn bản BAI1.INP gồm Y+1 dòng
- Dòng 1 chứa hai số X và Y
- Dòng n+1 (1<=n<=Y) ghi 3 số nguyên dương: hai số đầu là chỉ số của hai đòa
điểm dân cư được nối nhau bởi tuyến đường này, còn số thứ ba là độ dài của
tuyến đường.
Dữ liệu là các số nguyên dương
Kết quả: Xuất ra màn hình thông báo vò trí trung tâm dòch vụ là tổng khoảng cách từ
trung tâm dòch vụ đến các đòa điểm dân cư.
Nếu điểm tìm được nằm trên tuyến đường thì cần chỉ rõ hai đầu của tuyến đường và
khoảng cách từ đòa điểm xây dựng đến đầu thứ nhất.
Bài 3: (7 điểm)
Có n thành phố được đánh số từ 1 đến n. Mạng lưới giao thông giữa các thành phố là