Đề thi chọn HSG văn hóa Cấp Cụm Tin học 11 - Năm học 2022-2023 - Sở GD&ĐT Bắc Giang

Nội dung tài liệu: Đề thi chọn HSG văn hóa Cấp Cụm Tin học 11 - Năm học 2022-2023 - Sở GD&ĐT Bắc Giang

1. SỞ GD&ĐT BẮC GIANG ĐỀ THI CHỌN HỌC SINH GIỎI VĂN HÓA CẤP CỤM CỤM TRƯỜNG THPT THÀNH PHỐ NĂM HỌC 2022 – 2023 MÔN THI: TIN HỌC 11 (Thời gian làm bài 150 phút, không kể thời gian giao đề) TỔNG QUAN VỀ ĐỀ THI Tên bài Tên chương trình Tên tệp dữ liệu vào Tên tệp kết quả Bài 1: Xâu đối xứng XAUDX.* XAUDX.INP XAUDX.OUT Bài 2: Cặp số bạn bè BANBE.* BANBE.INP BANBE.OUT Bài 3: Đoạn con DOANCON.* DOANCON.INP DOANCON.OUT Bài 4: Du lịch DULICH.* DULICH.INP DULICH.OUT Chú ý: 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/C++. Bài 1 (5 điểm): Xâu đối xứng XAUDX.* Cho xâu X có độ dài không quá 103 kí tự, chỉ chứa các kí tự trong tập {?, A, B, C, , Z}. Trong đó, mỗi kí tự “?” có thể được thay bằng một trong các kí tự “A”, “B”, “C”, , “Z”. Ví dụ xâu “A?DA”, ta có thể tạo được các xâu “AADA”, “ABDA”, “ACDA”, “ADDA”, , “AZDA”. Trong đó xâu “ADDA” là xâu đối xứng. Yêu cầu: Cho xâu X, hãy tìm xâu đối xứng có thứ tự từ điển nhỏ nhất có thể tạo được từ xâu X. Dữ liệu vào: đọc từ tệp XAUDX.INP - Một dòng là xâu X. Kết quả: ghi ra tệp XAUDX.OUT - In ra xâu tìm được hoặc ghi ra 0 nếu không tìm được. XAUDX.INP XAUDX.OUT A??DA ADADA ABC? 0 Bài 2 (7 điểm): Cặp số bạn bè BANBE.* Một cặp số nguyên dương được gọi là số bạn bè nếu tổng các ước số của số này bằng chính số kia. Ví dụ: Số 220 và 284 là cặp số bạn bè vì, - Tổng các ước số của 220 là 1+2+4+5+10+11+20+22+44+55+110 = 284. - Tổng các ước số của 284 là 1+2+4+71+142 = 220. Số 1184 và 1210 cũng là hai số bạn bè. Yêu cầu: Hãy viết chương trình kiểm tra xem 2 số nhập vào có phải là số bạn bè hay không. Dữ liệu vào: đọc từ tệp BANBE.INP - Hai số nguyên A, B cách nhau một khoảng trắng (1 ≤ a, b ≤ 105). Kết quả: ghi ra tệp BANBE.OUT - In ra YES nếu A, B là hai số bạn bè hoặc in ra NO nếu không phải. BANBE.INP BANBE.OUT 220 284 YES 28 40 NO
2. Bài 3 (5 điểm): Đoạn con DOANCON.* Cho dãy số A gồm n số nguyên A1, A2, A3, , An và 2 số nguyên k và m. Yêu cầu: Tìm số cách chọn ra một đoạn con gồm m phần tử liên tiếp của dãy A mà tất cả các phần tử trong đoạn con đều không lớn hơn giá trị k. Dữ liệu vào: đọc từ tệp DOANCON.INP - Dòng đầu tiên gồm 3 số nguyên n (1 ≤ n ≤ 105), k (1 ≤ k ≤ 109) và m (1 ≤ m ≤ n); 9 - Dòng thứ hai gồm n số nguyên A1, A2, A3, , An (1 ≤ Ai ≤ 10 ). Kết quả: ghi ra tệp DOANCON.OUT - Ghi ra một số nguyên là số cách chọn đoạn con thỏa mãn yêu cầu, nếu không tồn tại đoạn con thỏa mãn yêu cầu thì ghi 0. DOANCON.INP DOANCON.OUT 10 6 3 3 2 3 6 8 3 1 1 2 7 0 4 5 3 4 0 3 5 7 1 2 Bài 4 (3 điểm): Du lịch DULICH.* Công ty du lịch Tre Việt tổ chức một tour du lịch xuyên Việt qua N thành phố, mỗi thành phố đi qua đúng một lần, bắt đầu từ thành phố 1 và kết thúc tại thành phố 1 (như vậy thành phố 1 được thăm 2 lần: lần đầu tiên và lần cuối cùng). Các thành phố được đánh số từ 1 đến N lần lượt từ Bắc vào Nam. Hành trình bắt đầu xuất phát từ thành phố 1, tour du lịch đi theo hướng Nam đến thành phố N (thành phố cực nam). Sau đó tour du lịch đi theo hướng Bắc từ thành phố N quay lại thành phố 1. Tìm hành trình qua đủ N thành phố sao cho tổng chi phí là thấp nhất. Dữ liệu: đọc từ tệp DULICH.INP: - Dòng đầu chứa N là số thành phố của tour du lịch (3 ≤ N ≤ 100); - Trong N dòng tiếp theo, mỗi dòng ghi N số ai1, ai2, ..., ain với aij là chi phí đi từ thành phố i đến thành phố j (aii = 0). Kết quả: ghi ra tệp DULICH.OUT - Dòng đầu ghi S là tổng chi phí của tour du lịch; - Dòng thứ 2 ghi N+1 số bắt đầu từ 1 thể các thành phố lần lượt trên hành trình (kết thúc cũng là thành phố 1). DULICH.INP DULICH.OUT 3 12 0 5 7 1 3 2 1 4 0 2 6 1 0 ----- Hết ----- Thí sinh không được sử dụng tài liệu. Cán bộ coi thi không giải thích gì thêm.