Đề 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!
Nội dung trích xuất từ tài liệu:
Đề thi Olympic Tin học sinh viên lần thứ XXIV khối Siêu cúp (Năm 2015) 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.??? CAKE.INP CAKE.OUT Bật đèn TREEGAME.??? TREEGAME.INP TREEGAME.OUT Hệ thống giao thông ATRAN.??? ATRAN.INP ATRAN.OUTChú ý:  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àuCho 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. Tanó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ỗipixel 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ôngtin:  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 cặp pixel liền kề khác màu. Chú ý là độ giảm hài hoà của mỗi cặppixel liền kề được tô màu khác nhau chỉ tham gia vào tổng C đúng một lần.OLP2015 – Đề thi khối Siêu cúp 1/5Yêu cầu: Tìm cách tô màu cho các pixel sao cho độ hài hoà của cả ma trận pixel thu được là lớnnhất.Dữ liệu: Vào từ file văn bản PCOLOR.INP:  Dòng đầu tiên chứa số nguyên N, 1 ≤ N ≤ 100,  N dòng tiếp theo, mỗi dòng chứa N số nguyên, trong đó phần tử thứ j của dòng thứ i là Wij;  Tiếp đến là N dòng, mỗi dòng chứa N số nguyên, trong đó phần tử thứ j của dòng thứ i là Bij;  Cuối cùng là N*N dòng, mỗi dòng có bốn số nguyên, trong đó dòng thứ (i-1)*N+j của nhóm dòng cuối cùng này chứa các số Cij0 Cij1 Cij2 Cij3.  1 ≤ Wij, Bij, Cijk ≤ 100.Kết quả:Ví dụ: 2 24 1 10 2 2 10 1 3 3 0 1 1 0 0 0 1 1 1 53 0 0 1 0 0 53Giải thích: Cách tô màu tốt nhất được mô tả trong hình vẽ bên cạnh.Tổng độ hài hoà là: W + B – C = 10 + (10+3+3) – (1+1) = 24.Để ý rằng chi trả cho việc tô khác màu các pixel (2, 1) và (2, 2) là rất lớn, nên tasẽ phải cố gắng tô chúng bởi cùng màu, trong đó màu đen là lựa chọn tốt hơn.Bài 2. Cắt bánhNhân dịp OLPSV lần thứ 24, Long mua một cái bánh đặc biệt thật to để mời Duy và Lâm thưởng thức.Bánh có dạng hình tròn rất đều và cân xứng nhưng rất cứng và lại giòn dễ vỡ nên rất khó cắt. Vì vậy,khi làm bánh người ta đã cứa sẵn ở một số vị trí trên bánh để người dùng có thể cắt được dễ dàng theonhững vị trí đã cứa sẵn.Chiếc bánh mà Long mua đã được cứa ở n vị trí. Các vết cứa chia chiếc bánh hình tròn ra thành n hìnhquạt (xem hình vẽ minh hoạ phía dưới). Trọng lượng miếng bánh giữa vị trí cứa thứ i và vị trí thứ i+1là một số nguyên ai với 1 ≤ i < n; trọng lượng miếng bánh giữa vị trí cứa thứ n và vị trí thứ 1 là một sốnguyên an.OLP2015 – Đề thi khối Siêu cúp 2/5Để đảm bảo tính thẩm mỹ của những miếng bánh được cắt mời hai ông bạn chí cốt, Long chỉ cắt ở đúng3 vị trí cứa để thu được 3 phần bánh. Là người am hiểu về luật chia công bằng, Long muốn tìm cáchcắt bánh sao cho trọng lượng của phần nhỏ nhất trong ba phần là lớn nhất.Yêu cầu: Cho dãy trọng lượng a1, a2, …, an, hãy tìm cách cắt ở đúng ba vị trí cứa sao cho trọng lượngcủa phần bánh nhỏ nhất trong ba phần là lớn nhất.Dữ liệu: Vào từ file văn bản CAKE.INP:  Dòng đầu tiên chứa một số nguyên dương n (n ≤ 106);  Dòng thứ i trong số n dòng tiếp theo chứa số nguyên dương ai (ai ≤ 109), i = 1, 2, …, n.Kết quả: Ghi ra file văn bản CAKE.OUT một số nguyên duy nhất là trọng lượng của phần bánh nhỏnhất.Ví dụ: ...