HSG lớp 9 TP. Hồ Chí Minh 2018-2019

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HỒ CHÍ MINH ĐỀ THI CHÍNH THỨC
(Đề thi có 02 trang)

KỲ THI HỌC SINH GIỎI LỚP 9 THCS Khóa ngày 13/3/2019
Môn thi: Tin học
Thời gian làm bài: 90 phút (không kể thời gian phát đề)

---

Tổng quan bài thi

	Tên bài	Tên chương trình	Tập tin dữ liệu	Tập tin kết quả
Bài 1	Kí tự	KITU.*	KITU.INP	KITU.OUT
Bài 2	Ma trận Bit	MTBIT.*	MTBIT.INP	MTBIT.OUT

Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++.

Hãy lập trình giải 2 bài toán sau:

Bài 1. Kí tự (10 điểm)

Cho xâu kí tự S có chiều dài tối đa 1000 kí tự gồm các kí tự chữ cái cả hoa và thường.

Yêu cầu: Hãy tìm xâu kí tự T theo thứ tự trong S gồm các kí tự hoa tăng dần dài nhất.

Dữ liệu vào: Cho trong tập tin văn bản KITU.INP có 1 dòng duy nhất gồm các kí tự.

Kết quả: Ghi vào tập tin văn bản KITU.OUT kết quả là số kí tự trong xâu T.

Ví dụ:

KITU.INP	KITU.OUT
aADbCBcdDCEefDEgFh	6

Giải thích:

Xâu S: aADbCBcdDCEefDEgFh

Xâu T tăng dần là: ABCDEF (lấy trong xâu S: A vị trí 2, B vị trí 6, C vị trí 10, D vị trí 14, E vị trí 15, F vị trí 17).

Bài 2. Ma trận Bit (10 điểm)

Cho một ma trận vuông mà mỗi phần tử là một bit bất kỳ. Mỗi hàng tính từ trái qua phải, mỗi cột tính từ trên xuống dưới và hai đường chéo chính phụ là các dãy bit có độ dài bằng nhau và đều có thể tạo thành một số nhị phân có nghĩa.

Yêu cầu: Hãy tìm trong chúng số nhị phân có giá trị lớn nhất.

Dữ liệu vào: Cho trong tập tin văn bản MTBIT.INP chỉ gồm N hàng, trên mỗi hàng ghi một dãy bit có độ dài là N bit (N ≤ 256).

Kết quả: Hiển thị trong tập tin văn bản MTBIT.OUT gồm có một dòng duy nhất ghi số nhị phân lớn nhất tìm được.

Ví dụ:

MTBIT.INP	MTBIT.OUT
010 101 001	101