Kỳ thi chọn HSG Quốc gia Tin học lớp 12 THPT năm 2011  (Bấm vào liên kết phía dưới để tải xuống)

Kỳ thi chọn HSG Quốc gia Tin học lớp 12 THPT năm 2011. Ngày thứ 2, gồm 3 bài: Bài 4: Nối điểm đen trắng (BWPOINTS). Bài 5 Trò chơi chẵn lẻ (PARIGAME). Bài 6: Nâng cấp mạng (UPGRANET).

Kỳ thi chọn HSG Quốc gia Tin học lớp 12 THPT năm 2011

TỔNG QUAN NGÀY THI THỨ HAI
Hãy lập trình giải các bài toán sau:
Bài 4. (6 điểm) Nối điểm đen trắng
Trên trục số thực cho n điểm đen và n điểm trắng hoàn toàn phân biệt. Các điểm đen có toạ độ nguyên a còn các điểm trắng có toạ độ nguyên b. Người ta muốn chọn ra k điểm đen và k điểm trắng để nối mỗi một điểm đen với một điểm trắng sao cho k đoạn thẳng tạo được đôi một không có điểm chung.
Yêu cầu: Cho toạ độ của n điểm đen và toạ độ của n điểm trắng, hãy tìm giá trị k lớn nhất thoả mãn yêu cầu nêu trên.
Bài 5. (7 điểm) Trò chơi chẵn lẻ
Trò chơi chẵn lẻ là trò chơi hai đối thủ được mô t ả như sau: Xuất phát từ bảng trò chơi là một bảng vuông kích thước n × n gồm n dòng và n cột. Các dòng của bảng được đánh số từ 1 đến n, từ trên
xuống dưới. Các cột của bảng được đánh số từ 1 đến n, từ trái qua phải. Trên mỗi ô của bảng ghi một số nguyên. Hai đối thủ luân phiên thực hiện nước đi. Đối thủ đến lượt chơi của mình được phép xoá dòng cuối cùng nếu tổng các số  trên dòng đó là số chẵn hoặc là cột cuối cùng nếu tổng các số trên cột đó là số chẵn.
Đối thủ thắng cuộc là người xoá được ô cuối cùng của bảng hoặc sau khi thực hiện nước đi của mình thì tổng các số trên dòng cuối cùng và tổng các số trên cột cuối cùng của bảng đều là số lẻ.
Yêu cầu: Cho biết bảng số của trò chơi, hãy xác định xem người đi trước có cách chơi giành phần thắng hay không?
Dữ liệu: Vào từ file văn bản PARIGAME.INP:
Bài 6. (7 điểm) Nâng cấp mạng
Một hệ thống gồm n máy tính đánh số từ 1 tới n được  kết nối thành một mạng bởi m đoạn cáp mạng đánh số từ 1 tới m. Đoạn cáp mạng thứ i có thông lượng w kết nối hai máy u , v cho phép truyền dữ li ệu theo cả hai chiều giữa hai máy này. Được gọi là một đường truyền tin từ máy x tới máy x . Thông lượng của đường truyền tin được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy b ất kỳ và giữa hai máy có không quá một đoạn cáp mạng nối chúng.
Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng ∆ ( ∆ > 0) ta phải trả một chi phí đúng bằng ∆. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng c ủa m ỗi đoạn cáp i đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy u t ới máy v.
Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho  tổng chi phí nâng cấp là nhỏ nhất.

HƯỚNG DẪN CHẤM ĐỀ THI CHÍNH THỨC
Môn: TIN H ỌC
Tên bài File chương trình File dữ liệu vào File kết quả
Bài 4 Nối điểm đen trắng BWPOINTS.* BWPOINTS.INP BWPOINTS.OUT
Bài 5 Trò chơi chẵn lẻ PARIGAME.* PARIGAME.INP PARIGAME.OUT
Bài 6 Nâng cấp mạng UPGRANET.* UPGRANET.INP UPGRANET.OUT
Bài 4. Nối điểm đen trắng (6 đi ểm)
• Thuật toán tham lam trực tiếp với thời gian tính O(n ) có thể đạt 50% số điểm.
• Thuật toán tham lam với tổ chức dữ liệu tốt với thời gian tính O(n log n) có thể đạt 100% số điểm.
• Giới hạn thời gian: 1 giây.
Bài 5. Trò chơi chẵn l ẻ (7 điểm)
• Có 50% số tests ứng với 50% số điểm của bài có 1 ≤ n ≤ 50.
• Thuật toán qui hoạch động trực tiếp với thời gian tính O(n ) có thể đạt 50% số điểm.
• Thuật toán phát triển dựa trên qui hoạch động với tiền xử lý dữ liệu với thời gian tính O(n ) có thể đạt 100% số điểm.
• Giới hạn thời gian: 1 giây.

Bài 6. Nâng cấp mạng (7 điểm)
• Có 50% số tests ứng với 50% số điểm của bài có n ≤ 100.
• Thuật toán phát triển dựa trên thụât toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh với thời gian tính O(|V| + |E|) có thể đạt 50% số điểm.
• Thuật toán phát triển dựa trên thuật toán Dijkstra với hàng đợi có ưu tiên để tìm đường đi ngắn nhất giữa mọi cặp đỉnh với thời gian tính O(|V| (|V| + |E|)log |V| + |E|) có thể đạt 60% số điểm.
• Thuật toán phát triển dựa trên xây dựng cây khung thông lượng lớn nhất nhờ thu ật toán Kruskal cài đặt với cấu trúc dữ liệu các tập không giao nhau, kết hợp với tổ chức dữ liệu tìm kiếm trên cây với thời gian tính O(|E|log |V|) có thể đạt 100% số điểm.
• Giới hạn thời gian: 1 giây.
 

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap