Đề 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! | 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. 1 giây 40 Mã hóa CODE. 1 giây 40 Phần mở rộng trong tên file chương trình nguồn được thay bằng PAS C CPP hoặc java 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. Radar Mộ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ên xuố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àng p 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ầu trê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ện tầ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ên củ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ên muố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át hiệ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 định tổ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 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 một số nguyên dương là tổng số các lô an toàn trong vùng biển. 1 2 Ví dụ 8 8 23 4 1 1 2 4 4 1 4 3 Bài 2. Mã hóa Sử 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
