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ụ:
| DANDEN.INP | DANDEN.OUT | |
| 4 5
+..*. ++.+. .++.. .++.. |
3
+..*. *+.+. .*+.. .+*.. |
——————— Hết ———————
Ghi chú: Cán bộ coi thi không giải thích gì thêm.