De thi HSG Tin Tinh Quang Ngai năm học 2008 – 2009

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

Đề 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”

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.

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ụ:

——————— Hết ———————

Ghi chú: Cán bộ coi thi không giải thích gì thêm.