SỞ GIÁO DỤC VÀ ĐÀO TẠO
NGHỆ AN

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12
NĂM HỌC 2009 - 2010



Môn thi: TIN HỌC - THPT BẢNG B
Thời gian: 180 phút (không kể thời gian giao đề)
(Đề thi gồm 02 trang)

Bài 1. (7,0 điểm) Rút gọn xâu
Cho một xâu S chỉ gồm các chữ cái in thường với độ dài tối đa 250 ký tự. Em hãy viết chương trình để tạo ra xâu SG từ xâu S bằng cách xóa các ký tự liên tiếp giống nhau trong xâu S và chỉ để lại một kí tự đại diện trong đoạn đó.
Dữ liệu vào: Đọc từ file văn bản XAUGON.INP chứa xâu S chỉ gồm các chữ cái in thường.
Kết quả: Ghi ra file văn bản XAUGON.OUT là xâu SG tìm được.
Ví dụ:
XAUGON.INP
XAUGON.OUT

hhooocccsssiiiiinnnhhh
hocsinh



Bài 2. (7,0 điểm) Dãy số đặc biệt
Dãy số A1, A2,..., AN được gọi là dãy số đặc biệt nếu nó thoả mãn các điều kiện:
Là dãy số giảm dần;
Với mỗi Ai thì Ai hoặc là số nguyên tố hoặc là ước của một trong các số từ A1 đến Ai-1.
Em hãy tìm dãy số đặc biệt dài nhất bắt đầu từ N.
Dữ liệu vào: Từ file văn bản DAYSO.IN là một số nguyên dương N (N < 10000).
Kết quả: Ghi ra file văn bản DAYSO.OUT là dãy số tìm được, các số ghi cách nhau bởi dấu cách.
Ví dụ:
DAYSO.IN
DAYSO.OUT

12
12 11 7 6 5 4 3 2 1


Bài 3. (6,0 điểm) Vườn trường
Vườn trường là một hình chữ nhật gồm một số khoảnh trồng các loại cây khác nhau. Nó được mô tả là một lưới ô vuông sao cho mỗi ô của lưới được xem như chỉ có 2 trạng thái: hoặc là diện tích trồng cây, hoặc không phải. Hưởng ứng cuộc vận động xây dựng trường "Xanh - Sạch - Đẹp" học sinh khối 12 muốn quét vôi xung quanh các bức tường rào của các khoảnh vườn này. Mỗi cạnh ô vuông của lưới được quét vôi nếu nó là cạnh chung của 2 ô khác trạng thái (các cạnh thuộc biên của lưới không được tính). Lập trình tính tổng chiều dài cần quét vôi của các khoảnh vườn (theo đơn vị cạnh ô lưới).
Dữ liệu vào: Đọc từ file văn bản VUON.INP gồm:
- Dòng đầu ghi hai số nguyên dương M, N (M, N ( 200 lần lượt là số dòng và cột của lưới);
- Dòng thứ i trong số M dòng tiếp mô tả trạng thái của N ô lưới tương ứng của dòng i gồm N số: 0 (là đất trống) hoặc 1 (là diện tích trồng cây) theo đúng thứ tự các ô trong lưới.
Kết quả: Ghi ra file văn bản VUON.OUT gồm một dòng ghi giá trị tổng chiều dài cần quét vôi.

Ví dụ:
VUON.INP

VUON.OUT

6 11
0 0 0 1 1 0 0 0 0 0 0
0 0 1 1 1 1 0 1 0 0 0
0 0 0 1 0 0 1 1 1 1 0
0 1 0 0 0 1 1 0 1 1 0
0 1 1 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 1 1 1

43


Chú ý:
- Các số trên cùng một dòng của file dữ liệu và file kết quả ghi cách nhau ít nhất một dấu cách.
- Tên file chương trình của bài 1, bài 2, bài 3 phải được ghi lên đĩa với tên tương ứng là bai1.pas, bai2.pas, bai3.pas.

--- Hết ---


Họ và tên thí sinh: ............................................................................. Số báo danh: ...................