Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 - Bảng B - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có đáp án + Ma trận)

Nội dung text: Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học 12 - Bảng B - Năm học 2019-2020 - SGD&ĐT Gia Lai (Có đáp án + Ma trận)

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI GIA LAI LỚP 12 CẤP TỈNH (BẢNG B) NĂM HỌC 2019 - 2020 ĐỀ CHÍNH THỨC Môn thi: TIN HỌC (Đề thi có 04 bài, 04 trang) Thời gian: 180 phút (không kể thời gian phát đề) Ngày thi: 13/12/2019 TỔNG QUAN ĐỀ THI Tên file Tên file Tên file Bài Tên bài chương trình dữ liệu vào dữ liệu ra 1 KHÔI PHỤC DỮ LIỆU Data.* Data.inp Data.out 2 GIẢI MÃ TIN NHẮN Message.* Message.inp Message.out 3 ĐỔI TIỀN Bank.* Bank.inp Bank.out 4 SỮA CHỮA BẢNG ĐÈN LED Led.* Led.inp Led.out Lưu ý: - Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++. - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. - Khi hết thời gian làm bài, tại máy tính được sử dụng để làm bài thi, thí sinh tạo một thư mục với tên là số báo danh của mình và đặt các file bài làm (file chương trình .CPP hoặc .PAS) vào thư mục vừa tạo. Sau đó tiến hành ghi nội dung thư mục này vào đĩa CD dưới sự giám sát, hướng dẫn của Cán bộ coi thi và sự chứng kiến của một thí sinh nào đó tại phòng thi. Bài 1. KHÔI PHỤC DỮ LIỆU (6.0 điểm) Kỹ sư Dennis muốn tạo ra máy SR có chức năng khôi phục dữ liệu bị nhiễu xảy ra trong quá trình truyền tin. SR nhận dữ liệu X (dữ liệu bị nhiễu) là một dãy số gồm N số nguyên dương (0<N 104). Sau đó SR tiến hành khôi phục dữ liệu gốc. Dữ liệu gốc P là một dãy số nguyên dương liên tiếp, không giảm, dài nhất trong X. Em hãy lập trình giúp Dennis chế tạo ra máy SR như trên. + Dữ liệu vào: Tệp Data.inp có nội dung gồm 2 dòng: - Dòng 1: Chứa số nguyên dương N (0<N 104) là độ dài của X. - Dòng 2: Chứa N số nguyên dương (giá trị các số [1,103]), mỗi số cách nhau một khoảng trống. + Dữ liệu ra: Tệp Data.out gồm một dòng duy nhất chứa 2 số nguyên i,j là vị trí bắt đầu và kết thúc của P trong X, mỗi số cách nhau một khoảng trống (Trường hợp có nhiều dãy P thì chọn dãy bên trái nhất trong X). Trang 1/4
2. + Ví dụ: Data.inp Data.out Giải thích 1 1 1 4 9 1 4 Chọn dãy 1 1 4 5 4 2 3 4 5 bên trái nhất của X 20 4 10 7 9 10 3 4 4 7 8 9 10 8 12 12 15 17 19 10 20 11 22 + Ràng buộc: - Có 50% số lượng Test thõa mãn điều kiện (0<N 50) - Có 50% số lượng Test thõa mãn điều kiện (50<N 104) Bài 2. GIẢI MÃ TIN NHẮN (4.0 điểm) Quỳnh và Ngân là một đôi bạn rất thân. Cả hai đều đam mê Tin học và thường xuyên trò chuyện với nhau thông qua những dòng tin nhắn. Một bữa nọ, Quỳnh muốn cuộc trò chuyện giữa hai bạn thêm thú vị nên đã mã hóa các tin nhắn của mình trước khi gửi cho Ngân. Qui tắc mã hóa tin nhắn của Quỳnh như sau: Mỗi tin nhắn là một xâu kí tự trong bảng mã ASCII có độ dài không vượt quá 255. Một kí tự trong tin nhắn ban đầu sẽ được thay thế bằng một kí tự mới, kí tự mới có được bằng cách đảo ngược các bit của kí tự ban đầu. Tuy nhiên, nếu mã ASCII của kí tự mới nằm ngoài khoảng [33,126] thì vẫn giữ nguyên kí tự ban đầu. Chẳng hạn: Kí tự ban Mã ASCII Dãy 8 bit Dãy 8 bit Mã ASCII Kí tự mới đầu tương ứng tương ứng đảo ngược tương ứng N 78 01001110 01110010 114 r a 97 01100001 10000110 134 a Theo qui tắc trên thì: - Kí tự ‘N’ sẽ được mã hóa thành kí tự ‘r’; - Kí tự ‘a’ vẫn giữ nguyên, không thay đổi. Trong vai trò là Ngân, em hãy lập trình để giải mã các tin nhắn nhận được từ Quỳnh. + Dữ liệu vào: Tệp Message.inp chứa các tin nhắn đã được mã hóa theo qui tắc trên. Mỗi tin nhắn được ghi trên một dòng. + Dữ liệu ra: Tệp Message.out chứa các tin nhắn sau khi đã được giải mã. Mỗi tin nhắn cũng được ghi trên một dòng. + Ví dụ: Message.inp Message.out Chao rgav! Chao Ngan! Chuc Fav .hi .o. .Novg ky .hi vayt Chuc ban thi tot trong ky thi nay. Goo&6uck \3 Goodluck :3 + Ràng buộc: Không có. Bài 3. ĐỔI TIỀN (6.0 điểm) DEV là một quốc gia xinh đẹp và rất phát triển. Tại quốc gia này hiện tại đang lưu hành vô hạn các tờ tiền có mệnh giá: 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000. Để có thể phù hợp với sự thay đổi của nền kinh tế, Chính phủ nước này đã phát Trang 2/4
3. hành thêm loại tiền có mệnh giá X. CBB là ngân hàng lớn nhất ở DEV, ngân hàng này đứng trước một bài toán có nội dung như sau: “Có K người muốn rút tiền tại ngân hàng CBB, người thứ i muốn rút một số tiền là P i. Hỏi ngân hàng phải đưa cho mỗi người ít nhất là bao nhiêu tờ tiền?” Em hãy lập trình giúp ngân hàng CBB giải quyết bài toán trên. + Dữ liệu vào: Tệp Bank.inp có nội dung như sau: - Dòng đầu tiên gồm 1 số nguyên X (X là mệnh giá của tờ tiền mới phát hành) - Dòng tiếp theo gồm K số nguyên Pi (Pi là số tiền người thứ i cần rút) + Dữ liệu ra: Tệp Bank.out gồm 1 dòng duy nhất chứa K số nguyên, số thứ i là kết quả (số tờ tiền ít nhất mà ngân hàng phải đưa) ứng với người thứ i trên bộ test. + Ví dụ: Bank.inp Bank.out Giải thích 1234 6 1 2 - Người thứ nhất cần dùng ít 1233 1234 1235 nhất 6 tờ (1 tờ 1000, 1 tờ 200, 1 tờ 20, 1 tờ 10, 1 tờ 2, 1 tờ 1) - Người thứ hai cần dùng ít nhất 1 tờ (1 tờ 1234) - Người thứ ba cần dùng ít nhất 2 tờ (1 tờ 1234, 1 tờ 1) + Ràng buộc: Trong tất cả các test: Gọi K là số người tham gia rút tiền: - 1 ≤ K ≤ 50. 9 - 1 ≤ X, Pi ≤ 2x10 . Trong đó, 30% số Test: 1 ≤ K ≤ 10, 1 ≤ X, Pi ≤ 10000. Bài 4. SỮA CHỮA BẢNG ĐÈN LED (4.0 điểm) Baggio là một nhân viên sửa chữa bảng đèn Led. Một bảng đèn Led là một lưới hình chữ nhật có kích thước n m ( n dòng, m cột, các đèn Led được đặt tại các ô vuông đơn vị trong lưới) và các mạch nối nối các đèn Led kề nhau (theo chiều đứng hoặc ngang). Một bảng đèn Led được gọi là hoàn chỉnh (không hỏng) nếu với hai đèn Led bất kỳ trên bảng đèn Led được nối với nhau bởi dãy các mạch nối (mạch nối đứng, mạch nối ngang). Với một bảng đèn Led bị hỏng, cần bổ sung các mạch nối để đảm bảo bảng đèn Led trở thành hoàn chỉnh. Biết rằng mạch nối đứng có chi phí là 1, mạch nối ngang có chi phí là 2. Em hãy lập trình giúp Baggio bổ sung các đoạn mạch nối vào một bảng đèn Led bị hỏng để bảng đèn Led trở thành hoàn chỉnh sao cho chi phí mạch nối là thấp nhất. + Dữ liệu vào: Tệp Led.inp có nội dung như sau: - Dòng 1: Chứa 2 số nguyên n và m (1 n,m 100) là kích thước của bảng đèn Led bị hỏng. - n dòng tiếp theo, mỗi dòng chứa m số nguyên cho biết các mạch nối còn tốt trong lưới. Chẳng hạn nếu giá trị của ô (i,j) trong lưới n m là: -0 có nghĩa là không có mạch nối giữa đèn (i,j) với đèn (i+1,j) và đèn (i,j) với đèn (i,j+1). -1 có mạch nối giữa đèn (i,j) với đèn (i+1,j) (mạch nối đứng). Trang 3/4
4. -2 có mạch nối giữa đèn (i,j) với đèn (i,j+1) (mạch nối ngang). -3 có nghĩa là có mạch nối giữa đèn (i,j) với đèn (i+1,j) và đèn (i,j) với đèn (i,j+1). + Dữ liệu ra: Tệp Led.out có nội dung gồm: - Dòng đầu tiên chứa hai số nguyên K và L, trong đó K là số mạch nối cần bổ sung trong cách bổ sung với chi phí nhỏ nhất tìm được, L là chi phí tương ứng. - K dòng tiếp theo mỗi dòng chứa 3 số nguyên i,j,d trong đó (i,j) là tọa độ đèn Led cần thêm mạch nối; d chỉ nhận một trong hai giá trị là 1 hoặc 2, với d=1 cho biết phải lắp thêm mạch nối đứng giữa đèn (i,j) với đèn (i+1,j), d=2 cho biết phải lắp thêm mạch nối ngang giữa đèn (i,j) với đèn (i,j+1). + Ví dụ: Bảng đèn Led bị hỏng có kích thước 6 Bảng đèn Led hoàn chỉnh sau khi lắp dòng 5 cột thêm mạch Led.inp Led.out 6 5 5 5 3 3 0 2 1 2 2 1 1 2 0 1 0 3 4 1 1 3 1 2 1 1 4 1 0 1 2 1 0 4 5 1 2 0 3 0 1 5 2 1 2 0 0 2 0 + Ràng buộc: - Có 50% số lượng Test thõa mãn điều kiện (1 n,m 50) - Có 50% số lượng Test thõa mãn điều kiện (51 n,m 100) ----------HẾT---------- Họ và tên thí sinh........................................................Số báo danh:................................................... Họ và tên, chữ kí của CBCT1:....................................Họ và tên, chữ kí của CBCT2:....................... Lưu ý: - Thí sinh không được sử dụng tài liệu trong lúc làm bài. - Cán bộ coi thi không giải thích gì thêm. Trang 4/4