SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT
QUẢNG NGÃI Năm học 2008-2009

Môn: Tin học
Thời gian: 180 phút (không kể thời gian giao đề)
Ngày thi: 03/12/2008
TỔNG QUAN BÀI THI

Tên bài
Tên tệp chương trình
Dữ liệu vào
Kết quả

BÀI 1
Mã ASCII
ASCII.PAS

ASCII.DAT

BÀI 2
Đa giác
DAGIAC.PAS
DAGIAC.INP
DAGIAC.OUT

BÀI 3
Xâu gọn
XAUGON.PAS
XAUGON.INP
XAUGON.OUT

BÀI 4
Dàn đèn
DANDEN.PAS
DANDEN.INP
DANDEN.OUT

Đề thi này có 02 trang
Hãy lập trình giải các bài toán sau:

Bài 1. Mã ASCII (4 điểm)
Trong chương trình Tin học lớp 10, em đã được làm quen với bảng mã ASCII chuẩn và biết được rất nhiều công dụng của bảng mã. Trong bảng mã này, mỗi ký tự có một mã số riêng. Ta viết 65 là để biểu diễn số 65, viết #65 là biểu diễn kí tự có mã số 65, tức là ký tự ‘A’.
Yêu cầu: Sinh ra tệp có tên ASCII.DAT chứa bảng mã ASCII chuẩn.
Hạn chế kỹ thuật: Chấp nhận có một số kí tự không hiển thị được.
Bài 2. Đa giác (4 điểm)
Trong mặt phẳng toạ độ Oxy, cho đa giác N đỉnh, các đỉnh lần lượt được ghi theo thứ tự từ 1, 2, ..., N. Hãy xét tính lồi lõm của đa giác.
Dữ liệu vào: Tệp DAGIAC.INP gồm:
+ Dòng 1: Ghi số nguyên N (3(N(100)
+ Dòng thứ i trong số N dòng tiếp theo ghi 2 số nguyên cách nhau bởi 1 ký tự trắng, lần lượt là hoành độ x và tung độ y (-500( x, y( 500) của đỉnh thứ i.
Dữ liệu ra: Tệp DAGIAC.OUT ghi “DA GIAC LOI” hoặc “DA GIAC LOM”
Ví dụ:
DAGIAC.INP

DAGIAC.OUT


4
0 0
1 -2
2 1
0 4

DA GIAC LOI








Bài 3. Xâu gọn (5 điểm)
Xâu gọn S là xâu có tối đa 250 kí tự gồm các chữ cái A..Z, a..z và các số nguyên dương (không lớn hơn 50). Các số nguyên dương cho biết số lần xuất hiện của dãy kí tự trong khai triển (đầy đủ) của S, nếu kí tự xuất hiện một lần thì có thể không viết số lần xuất hiện.
Ví dụ: Xâu gọn
S : ”A2B(C2A)2D3” có dạng khai triển là “AABCCACCADDD” (có chiều dài là 12).
Yêu cầu: Cho N xâu gọn. Tính chiều dài của mỗi xâu ở dạng khai triển.
Dữ liệu vào: Tệp văn bản XAUGON.INP gồm:
Dòng 1: Ghi số N (1(N(100) số lượng xâu gọn.
N dòng tiếp theo mỗi dòng ghi 1 xâu gọn.
Dữ liệu ra: Tệp văn bản XAUGON.OUT ghi N dòng, mỗi dòng là chiều dài của xâu ở dạng khai triển tương ứng, nếu gặp xâu gọn sai cú pháp thì ghi số 0.
Ví dụ :
XAUGON.INP
XAUGON.OUT


2
A2B(C2A)2D3
A2(C2A)3D3
12
14


Bài 4. Dàn đèn (7 điểm)
Cho một bảng kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có một trong các ký tự:
".": Ô trống.
"+": Ô có chứa một đèn chưa bật sáng.
"*": Ô có chứa một đèn đã bật sáng.
Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột.
Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: Số đèn sáng trên mỗi hàng cũng như trên mỗi cột của bảng tối đa là 1.
Dữ liệu vào: Tệp văn bản DANDEN.INP
Dòng 1: Ghi hai số m, n (1 ( m, n ( 200) cách nhau một ký tự trắng
m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng
Dữ liệu ra: Tệp văn bản DANDEN.OUT
Dòng 1: Ghi số đèn có thể bật thêm
m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng sau khi đã bật sáng thêm các đèn.
Ví dụ