Đề thi Olympic Tin học sinh viên lần thứ XV khối Cá nhân không chuyên (Năm 2006)

Đề thi Olympic Tin học sinh viên lần thứ XV khối Cá nhân không chuyên (Năm 2006) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: radar; mã hóa;... 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ứ XV khối Cá nhân không chuyên (Năm 2006) OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Cá nhân không chuyên Thời gian làm bài: 150 phút Ngày thi: 06-05-2006 N¬i thi: tr-êng §¹i häc b¸ch khoa Hµ néi Tªn file Tªn file Tªn file H¹n chÕ thêi gian Tæng ®iÓm Tªn bµi ch-¬ng tr×nh d÷ liÖu kÕt qu¶ cho mçi test cho bµi Radar RADAR.* RADAR.INP RADAR.OUT 1 giây 40 Mã hóa CODE.* CODE.INP CODE.OUT 1 giây 40Phần mở rộng “*” trong tên file chương trình nguồn được thay bằng PAS, C, CPP, hoặcjava tương ứng với ngôn ngữ được sử dụng là Pascal, C, C++, hoặc Java.H·y lËp tr×nh gi¶i c¸c bµi sau ®©y:Bài 1. RadarMột vùng biển hình chữ nhật được chia lô thành m hàng được đánh số từ 1 đến m từ trênxuống dưới và n cột được đánh số từ 1 đến n từ trái sang phải. Lô nằm ở vị trí giao của hàngp (1≤ p ≤m) và cột q (1≤ q ≤n) được gọi là lô có tọa độ (p, q). Để bảo vệ các giàn khoan dầutrên vùng biển này người ta bố trí một số radar tại một số lô. Mỗi radar có khả năng phát hiệntầu thuyền tại chính lô đó và 8 lô lân cận (4 lô chung cạnh và 4 lô chung đỉnh) kể cả trên biêncủa các lô này. Một lô trên vùng biển được coi là an toàn nếu tàu từ ngoài vùng biển trênmuốn vào trong lô đó thì dù đi theo đường đi như thế nào cũng đều bị ít nhất một radar pháthiện.Yêu cầu: Cho kích thước của vùng biển và vị trí của các lô được bố trí radar. Hãy xác địnhtổng số lô an toàn nằm trong vùng biển này.Dữ liệu: Vào từ tệp văn bản RADAR.INP có định dạng như sau: • Dòng đầu ghi hai số nguyên dương m và n (1≤ m, n ≤300) là kích thước (hàng và cột) của vùng biển. Hai số được ghi cách nhau một dấu cách. • Dòng thứ hai ghi số nguyên k (1 ≤ k ≤ m x n) là số các radar được bố trí. • Trên dòng thứ i trong k dòng tiếp theo ghi hai số nguyên dương p, q (1 ≤ p ≤ m, 1≤ q ≤ n) là tọa độ lô bố trí radar thứ i. Hai số được ghi cách nhau một dấu cách.Kết quả: Ghi ra tệp văn bản RADAR.OUT một số nguyên dương là tổng số các lô an toàntrong vùng biển. 1/2Ví dụ: RADAR.INP RADAR.OUT 8 8 23 4 1 1 2 4 4 1 4 3Bài 2. Mã hóaSử dụng giá trị sai phân là một phương pháp đơn giản để mã hóa và truyền tín hiệu số.Phương pháp này được thực hiện theo nguyên lý thay vì truyền tín hiệu thu được ở thời điểmt nào đó thì truyền sai số của nó so với tín hiệu thu được ở thời điểm ngay trước đó. Ví dụ,chúng ta có một dãy tín hiệu gốc thu được lần lượt là 0, 2, 4, 5, 4 thì dãy tín hiệu sai phân sẽlà 0, 2, 2, 1, -1. Chúng ta qui ước tín hiệu đầu tiên có giá trị là 0 và sai phân của nó cũng là 0,và trong dãy có ít nhất một tín hiệu có giá trị khác 0. Người ta nhận thấy thông thường tínhiệu sai phân biến thiên trong một miền giá trị có biên độ nhỏ hơn so với biên độ của miềngiá trị của tín hiệu gốc và do đó có thể biểu diễn các giá trị sai phân với số bit ít hơn so vớibiểu diễn tín hiệu gốc. Giả sử rằng miền giá trị của tín hiệu sai phân nằm trong đoạn [n, m] thìsẽ tồn tại một cách mã hóa để truyền một tín hiệu sai phân với số bít ít nhất là log 2 (m − n + 1) . Ở đây, log 2 (m − n + 1) là giá trị nguyên làm tròn lên của số thực log 2 (m − n + 1) (giá trị nguyên nhỏ nhất mà không nhỏ hơn log 2 (m − n + 1) ). Trong ví dụtrên, giá trị của miền tín hiệu sai phân nằm trong đoạn [-1, 2] và do đó số bit ít nhất để biểudiễn một giá trị sai phân là 2.Yêu cầu: Cho một dãy tín hiệu gốc là các giá trị nguyên, hãy tính số bít ít nhất để truyền dãysai phân của dãy tín hiệu này.Dữ liệu: Vào từ tệp văn bản CODE.INP có định dạng như sau: • Dòng đầu tiên ghi số nguyên dương m (1 < m < 1000) là số lượng tín hiệu gốc. • Trên mỗi dòng thứ i trong m dòng tiếp theo ghi một số nguyên si là giá trị của tín hiệu gốc thứ i (-215 < si < 215).Kết quả: Ghi ra tệp văn bản CODE.OUT số nguyên dương là số bit tối thiểu cần thiết đểtruyền dãy tín hiệu sai phân của dãy tín hiệu gốc này.Ví dụ: CODE.INP CODE.OUT 10 30 0 3 5 8 10 14 18 20 19 18 2/2 ...