KHOÁ LUYỆN ĐỀ DÀNH CHO HS THCS GÓI SỐ 3

# KHOÁ LUYỆN ĐỀ DÀNH CHO HS THCS :::success :green_book: **GÓI NÀY GỒM CÓ**: Đề thi HSG Bến Tre các năm: - 2022 - 2023 - Chưa có đề thi năm học 2023-2024 Đề thi HSG Bình Định các năm: - 2018 - 2019 - 2020 - 2021 - 2021 - 2022 - 2022 - 2023 - Chưa có đề thi năm học 2023-2024 ::: ## :books: ĐỀ SỐ 1: ĐỀ THI HSG BẾN TRE (2022 - 2023) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BẾN TRE** ĐỀ THI HỌC SINH GIỎI CẤP TỈNH LỚP 9 NĂM HỌC 2022-2023 Môn: TIN HỌC Ngày thi: 09/03/2023 --- (Đề thi có 02 trang) Thời gian làm bài: 150 phút (không kể phát đề) ### TỔNG QUAN ĐỀ THI | Bài | Tên bài | Tên file chương trình | Tên file dữ liệu vào | Tên file kết quả | Điểm | | - | - | - | - | - | - | | 1 | TẶNG QUÀ | BAI1.PAS | QUATANG.INP | QUATANG.OUT | 5,0 | | 2 | CHIA NHÓM | BAI2.PAS | CHIANHOM.INP | CHIANHOM.OUT | 7,0 | | 3 | DÃY THUẬN NGHỊCH | BAI3.PAS | TNGH.INP | TNGH.OUT | 8,0 | ### :question: Bài 1: Tặng quà :::info Thầy dạy Tin học có $N$ phần quà (đánh số thứ tự từ $1$ đến $N$) cho $N$ thí sinh dự thi kỳ thì học sinh giỏi năm nay. Trên hộp quà thứ $i$ có ghi một số nguyên $a_i$ $(i=1..N)$. Sau khi tặng quà cho các thí sinh, thầy sẽ có thêm một phần quà may mắn cho mỗi cặp thí sinh $i,\ j$ có số trên hộp quà là $a_i,\ a_j$ $(i \neq j)$ sao cho $|a_i + a_j| = K$, với $K$ là một số nguyên dương cho trước. Một thí sinh có thể cùng có nhiều phần quà may mắn chung cặp với một thí sinh khác. ::: :::warning **Yêu cầu**: Với $N$ và dãy $a_i$ cho trước, hãy cho biết thầy dạy tin học phải chuẩn bị bao nhiêu phân quà may mắn. **Dữ liệu vào** từ file văn bản `QUATANG.INP` gồm hai dòng: - Dòng 1: Gồm 2 số $N$ và $K$ $(1 \leq N,\ K \leq 100)$. - Dòng 2: Gồm $N$ số là các số $a_i$ $(-100 \leq a_i \leq 100)$ ghi trên mỗi phần quà. Các số cách nhau khoảng, trắng hoặc xuống hàng. **Kết quả**: ghi ra file văn bản `QUATANG.OUT`, gồm 1 dòng duy nhất ghi số lượng phần quà (số cặp số) may mắn. Nếu không có kết quả ghi số $0$. ::: **Các ví dụ**: | QUATANG.INP | QUATANG.OUT | | - | - | | 7 5 4 3 4 1 4 3 4 | 4 | ### :question: Bài 2: Chia nhóm :::info Có $N$ người (đánh số thứ tự từ $1$ đến $N$) và tình trạng quen biết của $N$ người này được cho bởi mảng hai chiều $A(N,N)$ đối xứng qua đường chéo chính, trong đó $A[i,j] = A[j,i] = 1$ nếu $i$ quen $j$ và bằng $0$ nếu $i$ không quen $j$ (quy ước $A[i,j]=0$ nếu $i=j$). Hãy xét xem liệu có thể chia $N$ người đó thành 2 nhóm mà trong mỗi nhóm hai người bất kỳ đều không quen nhau? ::: :::warning **Dữ liệu vào** trong file văn bản `CHIANHOM.INP` trong đó dòng thứ nhất ghi số nguyên dương $N$ $(1 \leq N \leq 100)$, trong $N$ dòng tiếp theo, dòng thứ $i$ ghi $N$ số $A[i,1], ..., A[i,N]$, cách nhau khoảng trắng. **Kết quả** ghi ra file `CHIANHOM.OUT` như sau: - Nếu không thể chia nhóm, ghi số 0; - Nếu có thể chia nhóm, dòng thứ nhất ghi số thứ tự những người thuộc nhóm 1, dòng thứ hai ghi số thứ tự những người thuộc nhóm 2. ::: **Ví dụ**: | CHIANHOM.INP | CHIANHOM.OUT | | - | - | | 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 | 1 3 5 2 4 | ### :question: Bài 3: Dãy thuận nghịch :::info Các phím số trên điện thoại không có màn hình cảm ứng cũng là các phím dùng để nhấn các chữ cái dùng để nhắn tin (hình bên), cụ thể: ![image](https://hackmd.io/_uploads/ry4_latKR.png) 2 $\Rightarrow$ ABC, 3 $\Rightarrow$ DEF, 4 $\Rightarrow$ GHI, 5 $\Rightarrow$ JKL, 6 $\Rightarrow$ MNO, 7 $\Rightarrow$ PQRS, 8 $\Rightarrow$ TUV, 9 $\Rightarrow$ WXYZ Nam viết ra giấy một dãy ký tự và đố Bình xác định đó là dãy số nào theo cách nhắn số trên điện thoại (chỉ xem xét sự tương ứng giữa số và ký tự chứ không xem xét phải nhấn bao nhiêu lần phím đó, ví dụ cả A, B, C đều là một số 2). Bình rất nhanh chóng xác định được kết quả, không những thế Bình còn muốn xác định nhanh xem sô đó có phải là số dạng thuận nghịch hay không. Một số là thuận nghịch nếu viết theo thứ tự ngược lại cũng là chính nó. Hãy viết chương trình giúp Bình thực hiện công việc trên. ::: :::warning **Dữ liệu vào** trong file văn bản `TNGH.INP` gồm một dòng ghi một dãy ký tự (từ 'a' đến 'z' hoặc từ "A" đến "Z") gồm các chữ cái có thể là chữ hoa hoặc chữ thường, dài không quá 20 ký tự, không có khoảng trắng. **Dữ liệu ra** ghi vào file văn bản `TNGH.OUT`, ghi số $1$ nếu kết quả tương ứng là số thuận nghịch, ghi số $0$ nếu ngược lại. ::: **Các ví dụ**: | TNGH.INP | TNGH.OUT | Giải thích | | - | - | - | | CNBOBNA | 1 | CNBOBNA đổi thành dãy số là 2626262 Viết theo theo thứ tự ngược lại là chính dãy số đó. | | DNDOB | 0 | DNDOB đổi thành dãy số là 36362 Viết theo theo thứ tự ngược lại là 26363 | --- ## :books: ĐỀ SỐ 2: ĐỀ THI HSG BÌNH ĐỊNH (2018 - 2019) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS NĂM HỌC 2018-2019 Môn: TIN HỌC Ngày thi: 18/03/2019 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | TÌM SỐ | TIMSO.\* | TIMSO.INP | TIMSO.OUT | 5,0 điểm | | 2 | BỘ SỐ TAM GIÁC | TAMGIAC.\* | TAMGIAC.INP | TAMGIAC.OUT | 5,0 điểm | | 3 | LƯỢC ĐỒ HORNER | HORNER.\* | HORNER.INP | HORNER.OUT | 5,0 điểm | | 4 | ĐƯỜNG ĐI CỦA QUÂN CỜ | QUANCO.\* | QUANCO.INP | QUANCO.OUT | 5,0 điểm | ### :question: Bài 1: Tìm số :::info Cho xâu $s$ có chiều dài không quá $1000$ gồm các kí tự là chữ cái và chữ số trong đó có ít nhất 3 kí tự số. Lập chương trình xóa bỏ một số kí tự trong xâu $s$ chỉ để lại 3 kí tự số vẫn giữ nguyên thứ tự của chúng trong xâu và tạo nên số có giá trị lớn nhất. ::: :::warning **Dữ liệu vào**: Từ tập `TIMSO.INP` gồm 1 dòng chứa xâu $s$. **Dữ liệu ra**: ghi vào tệp `TIMSO.OUT` xâu $s$ chứa 3 kí tự số còn lại tạo thành số lớn nhất. ::: **Ví dụ**: | TIMSO.INP | TIMSO.OUT | | - | - | | 18HSG03 | 803 | ### :question: Bài 2: Bộ số tam giác :::info Cho dãy số $A$ gồm $n$ phần tử nguyên dương $a_1, a_2, ..., a_n$. Mỗi phần tử có giá trị không vượt quá $10^9$ và $1 < n \le 5000$. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó. ::: :::warning **Yêu cầu**: Hãy đếm xem trong dãy $A$ có bao nhiêu bộ số tam giác $(a_i,\ a_j,\ a_k)$ với $i,\ j,\ k$ đôi một khác nhau. **Dữ liệu vào** từ tệp `TAMGIAC.INP`: - Dòng đầu là số $n$ - Dòng tiếp theo là các phần tử của dãy $A$, mỗi phần tử cách nhau một dấu cách. **Kết quả** ra ghi vào tệp `TAMGIAC.OUT`: Số lượng bộ số tam giác. ::: **Ví dụ**: | TAMGIAC.INP | TAMGIAC.OUT | Giải thích | | - | - | - | | 5 4 3 1 5 7 | 3 | Ba bộ số tam giác gồm: (4, 3, 5), (4, 5, 7), (3, 5, 7). | ### :question: Bài 3: Lược đồ Horner :::info Để chia đa thức $f(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$ cho nhị thức $g(x) = x − c$ người ta thường sử dụng lược đồ Horner theo dạng bảng: | | $a_n$ | $a_{n-1}$ | $a_{n-2}$ | ... | $a_2$ | $a_1$ | $a_0$ | | - | - | - | - | - | - | - | - | | $c$ | $b_n$ | $b_{n-1}$ | $b_{n-2}$ | ... | $b_2$ | $b_1$ | $b_0$ | *Trong đó*: $b_n = a_n$, $b_{n-1} = c.b_n + a_{n-1}$, $b_{n-2} = c.b_{n-1} + a_{n-2}$, ..., $b_1 = c.b_2 + a_1$, $b_0 = c.b_1 + a_0$ Hay ta viết: $b_n = a_n$, $b_i = c.b_{i+1} + a_i$ $(i = 1..n-1)$ Khi đó ta có biến đổi đa thức: $$ f(x) = (x − c)(b_nx^{n−1} + b_{n-1}x^{n−2} + ... + b_1) + b_0 $$ Từ đó ta có kết luận: $x = c$ là nghiệm của đa thức $f(x)$ nếu $b_0 = 0$. Hãy lập chương trình nhập vào các hệ số $a_i$ của đa thức $f(x)$ và giá trị $c$, tính các hệ số $b_i$ và cho biết $c$ có là nghiệm của đa thức $f(x)$ hay không. ::: :::warning **Dữ liệu vào** trong file `HORNER.INP` có cấu trúc như sau: - Dòng đầu chứa số tự nhiên $n$ và số nguyên $c$ $(n < 100,\ |c| < 5000)$. - $n+1$ dòng tiếp theo mỗi dòng chứa một số nguyên lần lượt là các hệ số $a_i$ của đa thức $f(x)$ với $(|a_i| < 5000)$ được sắp xếp từ $a_n$ đến $a_0$. **Dữ liệu ra** là file `HORNER.OUT` có cấu trúc như sau: - Dòng đầu tiên là kết luận: `c la nghiem` hoặc `c khong la nghiem`. - $n+1$ dòng tiếp theo, liệt kê các hệ số $b_i$ sắp xếp từ $b_n$ đến $b_0$. ::: **Ví dụ**: | HORNER.INP | HORNER.OUT | | - | - | | 3 2 1 -2 3 -6 | 2 la nghiem 1 0 3 0 | | HORNER.INP | HORNER.OUT | | - | - | | 2 1 3 -2 1 | 1 khong la nghiem 3 1 2 | ### :question: Bài 4: Đường đi của quân cờ :::info Bàn cờ là một bảng hình chữ nhật có $M \times N$ ô gồm $M$ hàng, $N$ cột. Quân cờ cần thực hiện lộ trình qua $N$ ô xuất phát phát từ một ô bất kỳ của cột $1$ và kết thúc ở một ô nào đó của cột $N$. Với mỗi bước đi quân cờ chỉ được đi sang $1$ ô ở cột tiếp theo trên đường chéo (hình vẽ minh họa). Trên mỗi ô chứa một số nguyên là thời gian (tính bằng phút) mà quân cờ phải lưu lại tại ô đó. ![image](https://hackmd.io/_uploads/B1hRbEtF0.png) Bạn hãy giúp tìm một lộ trình để quân cờ hoàn thành với ít thời gian nhất. ::: :::warning **Dữ liệu vào** là file `QUANCO.INP` có cấu trúc như sau: - Dòng đầu gồm hai số nguyên dương $M$, $N$ $(0 < M, N < 300)$ - $M$ dòng tiếp theo, mỗi dòng gồm $N$ số nguyên dương $A_{ij}$ là giá trị tương ứng tại ô thuộc hàng $i$, cột $j$ trong bảng $(0 < A_{ij} < 1000)$. **Dữ liệu ra** là file `QUANCO.OUT` có cấu trúc như sau: - Dòng đầu là tổng thời gian mà quân cờ thực hiện lộ trình tốt nhất tìm được. - $N$ dòng tiếp theo, mỗi dòng gồm hai số nguyên chỉ tọa độ của $N$ ô mà quân cờ thực hiện theo lộ trình để có kết quả tốt nhất. ::: **Ví dụ**: | QUANCO.INP | QUANCO.OUT | | - | - | | 4 5 2 4 6 7 8 **1** 6 8 2 3 4 **3** 5 **2** 8 5 1 **7** 8 **2** | 15 2 1 3 2 4 3 3 4 4 5 | --- ## :books: ĐỀ SỐ 3: ĐỀ THI HSG BÌNH ĐỊNH (2020 - 2021) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH** KỲ THI CHỌN HỌC SINH GIỎI CẤP THCS NĂM HỌC 2020-2021 Môn: TIN HỌC Ngày thi: 18/03/2021 --- (Đề thi gồm 02 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | SỐ CÓ NHIỀU ƯỚC NGUYÊN TỐ NHẤT | UOCNGTO.\* | UOCNGTO.INP | UOCNGTO.OUT | 5,0 điểm | | 2 | CHỮ SỐ TẬN CÙNG | TANCUNG.\* | TANCUNG.INP | TANCUNG.OUT | 5,0 điểm | | 3 | TAM GIÁC VUÔNG LỚN NHẤT | TGVUONG.\* | TGVUONG.INP | TGVUONG.OUT | 5,0 điểm | | 4 | PHỤC HỒI DÃY SỐ | DAYSO.\* | DAYSO.INP | DAYSO.OUT | 5,0 điểm | :::danger :warning: **Chú ý**: - Phần mở rộng tên tập chương trình theo ngôn ngữ lập trình của thí sinh (`.pas`, `.cpp`). - Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thi sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm. - Thời gian chạy mỗi test của chương trình không quá 02 giây. ::: ### :question: Bài 1: Số có nhiều ước nguyên tố nhất :::info Cho trước hai số nguyên dương $A$ và $B$ $(1 < A < B < 10^5)$. Trong các số nguyên dương $X$ mà $A < X \le B$ tìm số lớn nhất có nhiều ước nguyên tố nhất. ::: :::warning **Dữ liệu vào**: từ file `UOCNGTO.INP` gồm một dòng chứa hai số nguyên dương $A$ và $B$ $(1 < A < B < 10^5)$. **Dữ liệu ra**: ghi ra file `UOCNGTO.OUT` gồm 2 số $K$, $C$ (với $A < K \le B$) thể hiện số $K$ tìm được và số ước nguyên tố $C$ của nó tương ứng với cặp số $(A,B)$. ::: **Ví dụ**: | UOCNGTO.INP | UOCNGTO.OUT | Giải thích | | - | - | - | | 2 13 | 12 2 | Vì $12 = 2.2.3$, có 2 ước nguyên tố là 2, 3 | | 1000 2000 | 1995 4 | Vì $1995 = 3.5.6.19$ | ### :question: Bài 2: Chữ số tận cùng :::info Cho hai số nguyên dương $P$ và $Q$ $(1 < P,Q < 10^9)$. Yêu cầu xác định chữ số tận cùng của số $P^Q$. ::: :::warning **Dữ liệu vào**: từ file `TANCUNG.INP` gồm một dòng chứa 2 số $P$ và $Q$ $(1 < P < Q < 10^9)$. **Dữ liệu ra**: ghi ra file `TANCUNG.OUT` gồm một dòng có một chữ số $C$ $(0 < C \le 9)$ thể hiện chữ số tận cùng của số $P^Q$ tương ứng với cặp số $(P,Q)$. ::: **Ví dụ**: | TANCUNG.INP | TANCUNG.OUT | Giải thích | | - | - | - | | 13 2 | 9 | $13^2 = 169$ (tận cùng bằng $9$) | | 26 3 | 6 | $26^3 = 17576$ (tận cùng bằng $6$) | | 2 10 | 4 | $2^{10} = 1024$ (tận cùng bằng $4$) | ### :question: Bài 3: Tam giác vuông lớn nhất :::info Cho trước hai số nguyên dương $M$ và $N$ $(M < N)$. Xác định tam giác vuông có diện tích lớn nhất với các cạnh $a,\ b,\ c$ là các số nguyên dương thỏa mãn: $M < a+b+c \le N$. ::: :::warning **Dữ liệu vào** từ file `TGVUONG.INP` gồm một dòng chứa hai số nguyên dương $M$ và $N$ cách nhau một dấu cách với $(3 < M < N < 10000)$. **Dữ liệu ra** ghi ra file `TGVUONG.OUT` chứa một số nguyên duy nhất là diện tích của tam giác vuông tìm được (định dạng 1 chữ số thập phân). Nếu không tìm được tam giác vuông nào thỏa mãn thì ghi số $0.0$. ::: **Ví dụ**: | TGVUONG.INP | TGVUONG.OUT | Giải thích | | - | - | - | | 3 20 | 6.0 | Tam giác vuông: 3, 4, 5 | | 15 20 | 0.0 | Không có tam giác vuông nào thoả mãn | ### :question: Bài 4: Phục hồi dãy số :::info Bạn An sắp xếp các số từ $1, 2, ..., n$ một cách tùy ý vào $n$ vị trí và được dãy số $P$ (hay còn gọi $P$ là một hoán vị của các số $1, 2, ..., n$). Quan sát dãy số $P$, lần lượt với mỗi giá trị $i$ $(i = 1, 2,.., n)$ An thực hiện ghi lại số các số lớn hơn $i$ và đứng bên trái $i$ trong dãy $P$ và được dãy $T$ gồm $n$ số. An đưa dãy số $T$ cho bạn Thắng và yêu cầu phục hồi dãy $P$ ban đầu từ dãy $T$ này. Em hãy lập trình giúp Thắng giải quyết bài toán này. ::: :::warning **Dữ liệu vào**: từ file `DAYSO.INP` gồm 2 dòng: - Dòng dầu chứa số tự nhiên $N$ $(1 < N < 100)$. - Dòng thứ hai chứa $N$ số tự nhiên mô tả dãy $T$, các số cách nhau 1 dấu cách. **Dữ liệu ra**: ghi ra file `DAYSO.OUT` là một dãy gồm $N$ số mô tả dãy $P$ ban đầu, các số ghi cách nhau một dấu cách. ::: **Ví dụ**: | DAYSO.INP | DAYSO.OUT | Giải thích | | - | - | - | | 4 2 1 0 0 | 3 2 1 4 | - Số 1 có 2 số lớn hơn bên trái (3, 4) - Số 2 có 1 số lớn hơn bên trái (3) - Số 3 không có số lớn hơn bên trái - Số 4 không có số lớn hơn bên trái | | 6 5 1 0 1 1 0 | 3 2 6 4 5 1 | - Số 1 có 5 số lớn hơn bên trái (3, 2, 6, 4, 5) - Số 2 có 1 số lớn hơn bên trái (3) - Số 3 không có số lớn hơn bên trái - Số 4 có 1 số lớn hơn bên trái (6) - Số 5 có 1 số lớn hơn bên trái (6) - Số 6 không có số lớn hơn bên trái | --- ## :books: ĐỀ SỐ 4: ĐỀ THI HSG BÌNH ĐỊNH (2021 - 2022) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH NĂM HỌC 2021-2022 Môn: TIN HỌC Ngày thi: 18/03/2022 --- (Đề thi gồm 03 trang) Thời gian: 150 phút (Không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | TT | Tên bài | Tên tệp bài làm | Đầu vào | Đầu ra | Điểm | | - | - | - | - | - | - | | 1 | SỐ CÓ BA ƯỚC NGUYÊN DƯƠNG | BAUOC.\* | BAUOC.INP | BAUOC.OUT | 5,0 điểm | | 2 | NGHE NHẠC | NHAC.\* | NHAC.INP | NHAC.OUT | 5,0 điểm | | 3 | CHỌN SỐ | CHONSO.\* | CHONSO.INP | CHONSO.OUT | 5,0 điểm | | 4 | RỪNG NGUY HIỂM | RUNG.\* | RUNG.INP | RUNG.OUT | 5,0 điểm | :::danger :warning: **Chú ý**: - Phần mở rộng tên tập chương trình theo ngôn ngữ lập trình của thí sinh (`.pas`; `.cpp`). - Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thi sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm. - File input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến file input và output. - Thời gian chạy mỗi test của chương trình không quá 02 giây. ::: ### :question: Bài 1: Số có ba ước nguyên dương :::info Bạn Hiền rất yêu thích toán học, đặc biệt là Số học. Một ngày nọ, trong lúc giải một bài toán số học, Hiền muốn đếm những số tự nhiên có đúng ba ước số nguyên dương trong một phạm vi nhất định. Hãy lập trình giúp bạn Hiền đếm xem có bao nhiêu số có đúng ba ước số nguyên dương khác nhau có giá trị không lớn hơn số nguyên $N$ cho trước. ::: :::warning **Dữ liệu vào**: File `BAUOC.INP` gồm một dòng ghi số nguyên dương $N$ $(N \le 10^9)$. **Dữ liệu ra**: File `BAUOC.OUT` gồm một dòng ghi một số nguyên là số lượng số có đúng ba ước nguyên dương đếm được. ::: **Ví dụ**: | BAUOC.INP | BAUOC.OUT | | - | - | | 6 | 1 | **Giải thích**: Có một số tự nhiên không lớn hơn $6$ có đúng ba ước số là số $4$ (3 ước số: 1, 2, 4). ### :question: Bài 2: Nghe nhạc :::info Tại một trung tâm thương mại, người ta lắp một băng nhạc vào một máy phát nhạc. Khách hàng muốn nghe bài hát nào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ $i$ trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ qua $i–1$ bài ghi trước đó, thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như nhau (băng nhạc ghi $N$ bài hát, được mã số từ $1$ đến $N$ có thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho, với mỗi bài hát ta biết thời lượng phát của bài đó). Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần (tần suất) như nhau. Hãy tìm cách ghi các bài trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất. ::: :::warning **Dữ liệu vào**: File `NHAC.INP` gồm 2 dòng, dòng 1 là số tự nhiên $N$ cho biết số lượng bài hát, dòng 2 là $N$ số nguyên dương thể hiện dung lượng tính theo phút của mỗi bài (mỗi số cách nhau 1 dấu cách). **Dữ liệu ra**: File `NHAC.OUT` gồm: - $N$ dòng đầu thể hiện trật tự ghi bài hát trên băng (mỗi dòng gồm 2 số nguyên dương $j$ và $d$ cách nhau bởi dấu cách, trong đó $j$ là mã số của bài hát cần ghi, $d$ là thời gian tìm và phát bài đó theo trật tự ghi này). - Dòng thứ $N+1$ ghi tổng số thời gian quay bằng nếu mỗi bài hát được phát một lần trong ngày. ::: **Ví dụ**: | MAXCETRI.INP | MAXCETRI.OUT | | - | - | | 3 8 3 4 | 2 3 3 7 1 15 25 | ### :question: Bài 3: Chọn số :::info Cho dãy số nguyên dương $a_1, a_2, ..., a_n$ và một số nguyên dương $M$. Cần xác định một dây gồm $n$ bit: $t_1, t_2, ..., t_n$ ($t_i$ bằng $1$ hoặc $0$), để có $M = t_1a_1 + t_2a_2 + ... + t_na_n$ ::: :::warning **Dữ liệu vào**: File `CHONSO.INP` gồm: - Dòng đầu tiên chứa số nguyên dương $n$ $(5 \le n \le 40)$; - $n$ dòng sau tiếp theo chứa số các số nguyên $a_i$ $(i=1..n)$ (tổng các $a_i$ không vượt quá $10^9$) - Dòng cuối cùng (dòng thứ $n+2$) chứa số nguyên $M$. **Dữ liệu ra**: File `CHONSO.OUT` thông báo dãy bit tìm được. Dữ liệu vào đảm bảo có nghiệm duy nhất. ::: **Ví dụ**: | CHONSO.INP | CHONSO.OUT | | - | - | | 7 11 **8** **23** 2 45 **7** 34 38 | 0110010 | **Giải thích** $38=8+23+7=0\cdot11+1\cdot8+1\cdot23+0\cdot2+0\cdot45+1\cdot7+0\cdot34$. ### :question: Bài 4: Rừng nguy hiểm :::info Một con hổ bị lạc trong một khu rừng nguy hiểm hình vuông, kích thước $N \times N$, mỗi địa hình được mã hoá bởi các số $0$ hoặc $1$. Mỗi lần di chuyển con hổ có thể đi một bước theo hướng Đông (Đ), Tây (T), Nam (N), Bắc (B) (hay nói cách khác là một ô chung cạnh) với kiện nó đi sang một ổ có cùng tính chất địa hình (giá trị) với ô nó đang đứng. Bạn hãy xem liệu con hổ có thể thoát khỏi khu rừng nguy hiểm này không, nếu có thì mất ít nhất là bao nhiêu bước dịch chuyển con hổ có thể thoát nguy được? ::: :::warning **Dữ liệu vào**: File `RUNG.INP` gồm: - Dòng đầu là số $N$ $(2 \le N \le 50)$. - Dòng thứ hai ghi hai số $x,\ y$ là giá trị dòng, cột của vị trí đứng ban đầu của con hổ. - $N$ dòng tiếp theo, mỗi dòng chứa $N$ số (gồm số $0$ hoặc số $1$) thể hiện cho khu rừng nguy hiểm. **Dữ liệu ra**: File `RUNG.OUT` gồm: - Dòng đầu ghi số $0$ nếu con hổ không thể tìm được lối ra. - Nếu có được lối ra thì: + Dòng đầu ghi số $1$ + Dòng thứ hai ghi số bước ngắn nhất để con hổ thoát khỏi khu rừng (tại vị trí con hổ đứng được tính là 1 bước). + Các dòng tiếp theo, mỗi dòng ghi một tọa độ nằm trên đường con hổ thoát ra (gồm chỉ số hàng và chỉ số cột, ngăn cách với nhau bởi dấu cách). Đường đi của hổ được xuất phát từ vị trí ban đầu nó đứng. ::: **Ví dụ**: | RUNG.INP | RUNG.OUT | | - | - | | 4 2 2 1 0 1 1 1 **0** 1 1 1 0 0 0 1 1 1 1 | 1 2 2 2 1 2 | | 4 2 2 1 1 1 1 1 **0** 1 1 1 0 0 1 1 1 1 1 | 0 | --- ## :books: ĐỀ SỐ 5: ĐỀ THI HSG BÌNH ĐỊNH (2022 - 2023) **SỞ GIÁO DỤC VÀ ĐÀO TẠO BÌNH ĐỊNH** KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS NĂM HỌC 2022-2023 Môn: TIN HỌC Ngày thi: 18/03/2023 --- (Đề thi có 03 trang) Thời gian làm bài: 150 phút (không kể thời gian phát đề) ### TỔNG QUAN BÀI THI | Bài | Tên bài | Tên tệp chương trình | Tên tệp dữ liệu vào | Tên tệp dữ liệu ra | Điểm | | - | - | - | - | - | - | | 1 | CẶP SỐ TƯƠNG ĐỒNG | SIMILAR.\* | SIMILAR.INP | SIMILAR.OUT | 5,0 | | 2 | HÌNH CHỮ NHẬT LỚN NHẤT | DIENTICH.\* | DIENTICH.INP | DIENTICH.OUT | 5,0 | | 3 | TRÒ CHƠI XÂU KÝ TỰ | STRGAME.\* | STRGAME.INP | STRGAME.OUT | 5,0 | | 4 | KHOANH VÙNG PHÂN LOẠI | VUONCAY.\* | VUONCAY.INP | VUONCAY.OUT | 5,0 | :::danger :warning: **Chú ý**: - Phần mở rộng tên tệp chương trình theo ngôn ngữ lập trình của thí sinh. - Khi chấm thi có xét đến thời gian xử lý bài toán của chương trình nên thí sinh không sử dụng các câu lệnh làm chậm hoặc làm dừng chương trình trong bài làm. - File input và output ở trong thư mục hiện hành, thí sinh không khai báo đường dẫn đến file input và output. - Thời gian chạy mỗi test của chương trình không quá 01 giây. - Bộ nhớ cần dùng cho mỗi test của chương trình không quá 256MB. ::: ### Bài 1: Cặp số tương đồng :::info Bạn An rất yêu thích toán học, đặc biệt là Số học. Một ngày nọ, trong lúc giải một số bài toán số học, An nhận ra có nhiều cặp sô có tổng các chữ số trong biểu diễn thập phân của chúng bằng nhau và An gọi những cặp số như thế là cặp số tương đồng. Ví dụ, cặp số 69 và 555 là cặp số tương đồng vì cả hai đều có tổng các chữ số là $6+9=5+5+5=15$. Cho hai số nguyên dương $l,\ r$. Hãy giúp An tìm xem cặp số tương đồng có giá trị trong đoạn từ $l$ tới $r$ và hiệu hai số là lớn nhất. ::: :::warning **Dữ liệu vào**: File `SIMILAR.INP` gồm một dòng chứa hai số nguyên không âm $l,\ r$ không vượt quá $10^7$. **Dữ liệu ra**: File `SIMILAR.OUT` gồm một đồng ghi một số nguyên là hiệu lớn nhất tìm được. **Giới hạn**: 50% số test có $l,\ r \leq 10^3$. ::: **Ví dụ**: | SIMILAR.INP | SIMILAR.OUT | | - | - | | 10 30 | 18 | **Giải thích**: Cặp số cân tìm là $12$ và $30$ (có tổng các chữ số là $1+2=3$). Ngoài ra, còn có một số cặp số tương đồng khác như $14$ và $23$ hay $16$ và $25$. ### Bài 2: Hình chữ nhật lớn nhất :::info Trong mặt phẳng $Oxy$ vẽ đường tròn tâm $O$ bán kính $R$. Ta xác định các hình chữ nhật có toạ độ nguyên, nằm trên hình tròn $(O,\ R)$ và có các cạnh song song với các trục toạ độ (đỉnh của hình chữ nhật nằm ở bên trong hoặc trên đường tròn). **Lưu ý**: - Hình vuông xem là hình chữ nhật có hai cạnh bằng nhau. - Điểm $M(x_0,\ y_0)$ nằm trong hoặc trên đường tròn $(O,\ R)$ khi và chỉ khi các tọa độ của nó thỏa mãn: $\sqrt{{x_0}^2 + {y_0}^2} \leq R$ ::: :::warning **Yêu cầu**: Xác định giá trị lớn nhất về diện tích trong các hình chữ nhật thỏa mãn yêu cầu trên. **Dữ liệu vào**: Từ file văn bản `DIENTICH.INP` gồm một số nguyên dương $R$ duy nhất $(R < 10^4)$. **Dữ liệu ra**: File văn bản `DIENTICH.OUT` chứa 1 số nguyên duy nhất cho biết giá trị lớn nhất về diện tích trong các hình chữ nhật. Nếu không tồn tại hình chữ nhật thì ghi số $0$. ::: **Ví dụ**: | DIENTICH.INP | DIENTICH.OUT | Giải thích | | - | - | - | | 5 | 48 | Hình chữ nhật có diện tích lớn nhất là 48 có đỉnh là: (-3;4), (-3;-4), (3;-4), (3;4) Nằm trên đường tròn $(O,5)$ ![image](https://hackmd.io/_uploads/Bkx6N8YYR.png) | | 3 | 12 | Hình chữ nhật có diện tích lớn nhất là 12 có đỉnh là: (-2;2), (-2;-2), (2;-2), (2;2) Nằm trong đường tròn $(O,3)$ ![image](https://hackmd.io/_uploads/S1haNLtt0.png) | | 1 | 0 | Không có hình chữ nhật có toạ độ nguyên nằm trong hình tròn $(O,1)$ | ### Bài 3: Trò chơi xâu ký tự :::info Bạn được cho một xâu ký tự gồm $N$ ký tự. Đầu tiên, bạn được sắp xếp lại các ký tự trong xâu theo một thứ tự bất kỳ. Sau đó, hãy chia xâu ký tự này thành chính xác $K$ xâu ký tự liên tiếp không rỗng sao cho xâu ký tự có thứ tự từ điển lớn nhất là nhỏ nhất có thể. Xâu $A$ có thứ tự từ điển nhỏ hơn xâu $B$ khi thỏa một trong các điều kiện sau: - $A$ là tiền tố của $B$ và $A$ khác $B$. - Tồn tại số $i$ $(1 \leq i \leq min(|A|,\ |B|))$ sao cho $A[i] < B[i]$ và $A[j] = B[j]$ với mọi $j$ $(1 \leq j < min(|A|,\ |B|)$. Ở đây, $|A|$ là độ dài của xâu $A$, $min(x,\ y)$ là giá trị nhỏ hơn giữa $x$ và $y$. ***Ví dụ***: - $abc$ có thứ tự từ điển nhỏ hơn $ad$. - $ab$ có thứ tự từ điển nhỏ hơn $abb$. ::: :::warning **Dữ liệu vào**: File `STRGAME.INP` gồm: - Dòng đầu tiên gồm hai số nguyên dương $N,\ K$ $(1 \leq K \leq N \leq 100)$. - Dòng thứ hai gồm xâu chứa $N$ ký tự. Các ký tự là các chữ cái tiếng Anh in thường. **Dữ liệu ra**: File `STRGAME.OUT` gồm: - Gồm một dòng duy nhất là xâu ký tự có thứ tự từ điển lớn nhất của phương án tối ưu. **Giới hạn**: - 20% số test có xâu ký tự gồm toàn ký tự $a$. - 20% số test tiếp theo có $K = N$. - 60% số test còn lại không có ràng buộc gì thêm. ::: **Ví dụ**: | STRGAME.INP | STRGAME.OUT | | - | - | | 4 2 baba | ab | | 4 2 baca | abc | **Giải thích**: - Ở ví dụ đầu tiên, ta có thể sắp xếp $baba$ thành $abab$ và chia thành hai xâu con $ab$ và $ab$. Khi đó xâu ký tự có thứ tự từ điển lớn nhất là $ab$. Ta cũng có thể sắp xếp thành $abba$ và chia thành hai xâu $abb$ và $a$, tuy nhiên phương án này sẽ cho xâu có thứ tự từ điển lớn nhất là $abb$, lớn hơn so với $ab$ ở phương án đầu tiên. - Ở ví dụ thứ hai, ta có thể sắp xếp $baca$ thành $abca$ và chia thành hai xâu con $abc$ và $a$. Khi đó xâu ký tự có thứ tự từ điển lớn nhất sẽ là $abc$. ### Bài 4: Khoanh vùng phân loại :::info Một mảnh vườn hình chữ nhật được chia thành các ô đất nhỏ gồm $M$ hàng, $N$ cột để ươm các loại cây giống khác nhau. Độ đài cạnh mỗi ô được xem là 1 đơn vị chiều dài, mỗi ô sẽ ươm một trong số các loại cây cần ươm. Để phân vùng các loại cây giống khác nhau trong khu vườn, người làm vườn tiến hành căng dây để phân biệt theo các đường ranh giới các ô đất. Dây được căng xung quanh mảnh vườn và cạnh của ô nếu 2 ô chứa cạnh đó ươm hai loại cấy khác nhau. ::: :::warning **Yêu cầu**: Tính độ đài của dây cần dùng để khoanh vùng các loại cây trong mảnh vườn theo yêu cầu. **Dữ liệu vào**: File văn bản `VUONCAY.INP` có cấu trúc như sau: - Dòng đầu chứa 2 số nguyên dương $M,\ N$ $(0 < M,\ N < 100)$. - $M$ dòng tiếp theo mỗi dòng chứa $N$ số nguyên dương. Giá trị ở dòng thứ $i$, cột thứ $j$ là $a_{ij}$ với ($1 \leq i \leq M;\ 1 \leq j \leq N$ và $1 \leq a_{ij} \leq 100$) để mô tả loại cây được ươm tại ô ở hàng $i$ cột $j$ của mảnh vườn (các giá trị giống nhau để chỉ cùng một loại cây). **Dữ liệu ra**: File văn bản `VUONCAY.OUT` chứa một số nguyên dương duy nhất cho biết chiều dài của dây được dùng khoanh vùng theo yêu cầu của người làm vườn. ::: **Ví dụ**: | VUONCAY.INP | VUONCAY.OUT | Giải thích | | - | - | - | | 4 5 ![image](https://hackmd.io/_uploads/rJ0mH8KKC.png) | 32 | - Chu vi: 18 - Dây dọc bên trong: 5 - Dây ngang bên trong: 9 Tổng cộng chiều dài dây: 32 | ---