tailieunhanh - Đề thi Olympic Tin học sinh viên lần thứ XXIV khối Siêu cúp (Năm 2015)

Đề thi Olympic Tin học sinh viên lần thứ XXIV khối Siêu cúp (Năm 2015) cung cấp cho thí sinh các bài toán lập trình nhằm giải quyết các vấn đề sau: tô màu; cắt bánh; bật đèn; hệ thống giao thông; . Mời các bạn cùng tham khảo chi tiết nội dung đề thi! | OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XXIV 2015 Khối thi Siêu cúp Thời gian làm bài 180 phút Ngày thi 25-11-2015 Nơi thi ĐẠI HỌC KINH DOANH VÀ CÔNG NGHỆ HÀ NỘI TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Tên bài chương trình dữ liệu kết quả Tô màu PCOLOR. PCOLOR. INP PCOLOR. OUT Cắt bánh CAKE. Bật đèn TREEGAME. Hệ thống giao thông ATRAN. Chú ý Dấu được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt chương trình. Thí sinh phải nộp cả file mã nguồn của chương trình và file chương trình thực hiện chương trình đã được biên dịch ra file .exe . Hãy lập trình giải các bài sau đây Bài 1. Tô màu Cho một ma trận vuông gồm N N pixel. Các dòng và cột của ma trận được đánh số từ 1 đến N. Ta nói pixel có toạ độ i j nếu nó nằm trên giao của dòng i và cột j. Bạn cần tìm cách tô cho mỗi pixel của ma trận một trong hai màu trắng hoặc đen để thu được một ma trận hài hoà nhất có thể. Để làm điều đó bạn được cho biết cách đánh giá độ hài hoà của ma trận thông qua ba thông tin Wij là độ hài hoà đạt được nếu pixel có toạ độ i j được gán màu trắng Bij là độ hài hoà đạt được nếu pixel có toạ độ i j được gán màu đen Cijk k 0 1 2 3 là độ giảm hài hoà phải trả giá cho việc gán cho pixel liền kề với pixel i j màu khác với màu của nó o Cij0 Cij1 Cij2 và Cij3 tương ứng là trả giá cho việc gán cho pixel ở toạ độ i 1 j i j 1 i 1 j và i j 1 màu khác với màu của pixel ở toạ độ i j o Chú ý là độ giảm hài hoà đối với cặp pixel liền kề có tính đối xứng nghĩa là độ giảm hài hoà của cặp pixel liền kề a và b là bằng độ giảm hài hoà của cặp pixel liền kề b và a. Thêm vào đó nếu một pixel không có pixel liền kề nó về bên trên hay bên phải hay bên dưới hay bên trái thì độ giảm hài hoà tương ứng được qui ước là bằng 0. Độ hài hoà của ma trận sau khi gán màu cho các pixel của nó được tính bởi công thức W B C trong đó W là tổng độ hài hoà của các pixel trắng B là tổng độ hài hoà của các pixel đen và C là tổng độ giảm hài hoà của các