[2024] CÁC ĐỀ THI (P1)

# TỔNG HỢP CÁC ĐỀ THI HSG CẤP THCS NĂM 2024 ## ĐỀ SỐ 1: Sở GD&ĐT Khánh Hoà **SỞ GIÁO DỤC VÀ ĐÀO TẠO KHÁNH HOÀ** KỲ THI CHỌN HỌC SINH GIỎI THCS CẤP TỈNH NĂM HỌC 2023-2024 Môn: TIN HỌC Ngày thi: 07/12/2023 --- (Đề thi có 04 trang) Thời gian làm bài: 150 phút (không kể thời gian phát đề) ### TỔNG QUAN VỀ ĐỀ 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 kết quả | Thời gian | Điểm | | - | - | - | - | - | - | - | | 1 | Đếm gạo | DEMGAO.\* | DEMGAO.INP | DEMGAO.OUT | 1 giây/test | 6,0 | | 2 | Từ dài | TUDAI.\* | TUDAI.INP | TUDAI.OUT | 1 giây/test | 5,0 | | 3 | Cửa sổ | CUASO.\* | CUASO.INP | CUASO.OUT | 1 giây/test | 5,0 | | 4 | Số nguyên tố toàn diện | SNTOTD.\* | SNTOTD.INP | SNTOTD.OUT | 1 giây/test | 4,0 | Dấu * được thay thế bởi `PAS` hoặc `CPP` hoặc `PY` của ngôn ngữ lập trình được sử dụng tương ứng là Pascal hoặc C++ hoặc Python. Các số trên cùng một dòng trong tệp dữ liệu vào/ra được ghi cách nhau ít nhất một dấu cách. ### Bài 1: ĐẾM GẠO :::info Nấm là cô bé đáng yêu và tốt bụng. Cô bé đặc biệt thích truyện cổ tích. Vì thế, đêm qua, Nấm nằm mơ về nàng Lọ Lem. Trong giấc mơ, Lọ Lem không bị mụ dì ghẻ bắt phân loại các loại đậu nữa mà bắt nhặt gạo. Có rất nhiều gạo trong kho, các hạt gạo đã được đánh số thứ tự là số nguyên liên tiếp từ $a$ tới $b$. Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số $k$ cho trước. Đồng thời sau khi nhặt xong phải trả lời cho mụ biết số lượng hạt gạo nhặt được. Việc nhặt gạo thì quá đơn giản, chỉ trong tích tắc bầy chim đã giúp nàng nhặt xong. Bây giờ nhiệm vụ của Nấm là đếm số lượng hạt gạo đã nhặt được. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy. Nấm rất muốn có câu trả lời cho Lọ Lem. ::: **Yêu cầu**: Hãy trả lời giúp Nấm, nếu hoàn thành phần việc của mình, Nấm sẽ đếm được bao nhiêu hạt gạo? **Dữ liệu vào**: Từ tệp văn bản **`DEMGAO.INP`** gồm ba số nguyên dương $a$, $b$ và $k$ ghi trên cùng 1 dòng $(1 \leq a \leq b \leq 10^{18};\ 1 \leq k \leq 10^{18})$. **Kết quả**: Ghi ra tệp văn bản **`DEMGAO.OUT`** một số nguyên duy nhất là kết quả cần tìm. **Ví dụ**: | DEMGAO.INP | DEMGAO.OUT | Giải thích | | - | - | - | | 3 10 5 | 2 | Hai hạt gạo được nhặt là hạt có số thứ tự 5 và hạt gạo số thứ tự 10. | | 6 9 5 | 0 | Không có hạt gạo nào thoả mãn yêu cầu cần nhặt. | **Ràng buộc**: + 70% số test tương ứng với 70% số điểm có $1 \leq a \leq b \leq 10^6$. + 30% số test còn lại tương ứng 30% số điểm không có ràng buộc gì thêm. ### Bài 2: TỪ DÀI :::info Một từ được định nghĩa là một hoặc một dãy các kí tự liên tiếp nhau và không chứa dấu cách (kí tự trắng). Độ dài của một từ là số kí tự có trong từ đó. Cho xâu gồm các kí tự 'A'..'Z', 'a'..'z', '0'..'9', kí tự trắng (dấu cách). ::: **Yêu cầu**: Tìm độ dài của từ có nhiều ký tự nhất và từ tương ứng với độ dài đó. **Dữ liệu vào**: Từ tệp văn bản **`TUDAI.INP`** gồm 1 dòng duy nhất chứa xâu (độ dài xâu không quá 255 kí tự và trong xâu chứa ít nhất một từ). **Kết quả**: Ghi ra tệp văn bản **`TUDAI.OUT`** gồm 2 dòng: + Dòng 1: Ghi độ dài của từ có nhiều kí tự nhất (độ dài lớn nhất). + Dòng 2: Ghi từ có độ dài lớn nhất. **Lưu ý**: nếu có nhiều từ có cùng độ dài nhất thì ghi từ có độ dài lớn nhất sau cùng trong xâu. **Ví dụ**: | TUDAI.INP | TUDAI.OUT | | - | - | | Khanh Hoa que huong toi | 5 huong | ### Bài 3: CỬA SỔ :::info Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiểu một cửa số hình chữ nhật. Hiện tại, Tí còn dư $n$ que tính, các que tính được đánh số thứ tự từ $1$ tới $n$, que thứ $i$ có độ dài $a_i$ (đơn vị đo chiều dài). Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que tính. ::: **Yêu cầu**: Hãy cho biết chu vi của cửa sổ lớn nhất mà Tí có thể ghép được. ***Lưu ý**: Không bẻ gãy hay chấp nối để thay đổi chiều dài que tính và hình vuông cũng được xem là hình chữ nhật.* **Dữ liệu vào**: Từ tệp văn bản **`CUASO.INP`** gồm 2 dòng: + Dòng đầu chứa số nguyên dương $n$ $(1 \leq n \leq 10^9)$. + Dòng thứ hai chứa $n$ số nguyên dương $a_i$ $(1 \leq a_i \leq 10^6;\ 1 \leq i \leq n)$. **Kết quả**: Ghi ra tệp văn bản **`CUASO.OUT`** số nguyên duy nhất là chu vi lớn nhất của cửa số có thể ghép được. Nếu không thể ghép được thì ghi -1. **Ví dụ**: | CUASO.INP | CUASO.OUT | Giải thích | | - | - | - | | 7 3 8 4 3 8 1 1 | 22 | Có 3 cách ghép thành cửa số là cửa sổ có chiều dài và chiều rộng như sau: $(8,3)$; $(3,1)$; $(8,1)$. Chu vi lớn nhất là $(3 + 8) \times 2 = 22$ | | 5 4 9 1 9 3 | -1 | Không thể ghép thành cửa sổ nào cả. | **Ràng buộc**: + 30% số test tương ứng với 30% số điểm có $n \leq 50$. + 40% số test tương ứng với 40% số điểm có $50 < n \leq 1000$. + 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm. ### Bài 4: SỐ NGUYÊN TỐ TOÀN DIỆN :::info Hôm nay, An được học về số nguyên tố. Số nguyên tố là số có đúng hai ước nguyên dương là $1$ và chính nó. Ví dụ số $17$ là số nguyên tố nhưng số $16$ thì không. Vốn là người có nhiều ý tưởng sáng tạo, An đưa ra một khái niệm mới gọi là “số nguyên tố toàn diện”. Một số nguyên dương $x$ gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời 3 điều kiện sau: + $x$ là số nguyên tố. + Lần lượt bỏ đi các chữ số bên phải của $x$ thì phần còn lại của nó vẫn là số nguyên tố. + Thêm vào bên phải của một trong các chữ số từ $0$ tới $9$, số thu được cũng là số nguyên tố. Ví dụ số $313$ là số nguyên tố toàn diện vì: + $313$ là số nguyên tố. + Bỏ đi số $3$ bên phải ta còn số $31$ là số nguyên tố, bỏ tiếp số $1$ ta còn số $3$ cũng là số nguyên tố. + Thêm số $7$ vào sau $313$ ta được số $3137$ là số nguyên tố. ::: **Yêu cầu**: Cho dãy $A$ gồm $n$ số nguyên dương $a_1, a_2,..., a_n$ và $m$ câu hỏi. Mỗi câu hỏi có dạng $(u,v)$ với ý nghĩa: Đếm số lượng số nguyên tố toàn diện trong dãy $A$ từ vị trí $u$ với $v$. **Dữ liệu vào**: Từ tệp văn bản **`SNTOTD.INP`** gồm: + Dòng đầu chứa số nguyên $n$ $(1 \leq n \leq 10^5)$. + Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2,..., a_n$ $(1 \leq a_i \leq 10^6;\ 1 \leq i \leq n)$. + Dòng thứ ba chứa số nguyên $m$ là số lượng câu hỏi $(1 \leq m \leq 10^5)$. + $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $u,\ v$ $(1 \leq u \leq v \leq n)$. **Kết quả**: Ghi ra tệp văn bản **`SNTOTD.OUT`** $m$ dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra trong tệp dữ liệu vào. **Ví dụ**: | SNTOTD.INP | SNTOTD.OUT | Giải thích | | - | - | - | | 6 59 12 57 53 23 313 3 1 3 2 5 3 6 | 1 1 1 | - Có 1 số nguyên tố toàn diện là 59 trong đoạn từ 1 tới 3. - Có 1 số nguyên tố toàn diện là 23 trong đoạn từ 2 tới 5. - Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn từ 3 tới 6. | **Ràng buộc**: + 70% số test tương ứng với 70% số điểm có $1 \leq n \leq 10^3$; $1 \leq a_i \leq 10^3$; $1 \leq m \leq 10^3$ + 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm. ----- HẾT ----- - Giám thị không giải thích gì thêm. --- ## ĐỀ SỐ 2: Phòng GD&ĐT Huyện Bảo Thắng (Lào Cai) **PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN BẢO THẮNG** KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP HUYỆN NĂM HỌC 2023-2024 Môn: TIN HỌC --- (Đề thi gồm có 04 trang, 05 câu) Thời gian làm bài: 150 phút (không kể thời gian giao đề) ### TỔNG QUAN BÀI THI | Câu | Tên chương trình | File dữ liệu vào | File dữ liệu ra | Điểm | | - | - | - | - | - | | Câu 1 | CAU01.\* | CAU01.INP | CAU01.OUT | 5,0 | | Câu 2 | CAU02.\* | CAU02.INP | CAU01.OUT | 5,0 | | Câu 3 | CAU03.\* | CAU03.INP | CAU03.OUT | 4,0 | | Câu 4 | CAU04.\* | CAU04.INP | CAU04.OUT | 4,0 | | Câu 5 | CAU05.\* | CAU05.INP | CAU05.OUT | 2,0 | *Lưu ý*: - Dấu \* trong phần tên chương trình tương ứng với ngôn ngữ lập trình mà thí sinh sử dụng, ví dụ `PAS`, `CPP`, `Py`... - Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. - Thời gian chạy mỗi test không quá 0.2 giây (0.2s). ### Câu 1: :::info Số $A$ được gọi là anh em với số $B$ nếu tổng các ước của $A$ bằng $B$ hoặc tổng các ước của $B$ bằng $A$. Chú ý ở đây ta quy định rằng cặp $(A, B)$ và cặp $(B, A)$ chỉ tính là một cặp, $A$ khác $B$. ::: **Yêu cầu**: Nhập vào số tự nhiên $N$ $(N \leq 3 \times 10^5)$. Đếm số cặp anh em trong đoạn $[1,N]$. **Dữ liệu vào**: Đọc từ tệp **`CAU01.INP`** gồm một dòng duy nhất chứa số tự nhiên $N$. **Dữ liệu ra**: Ghi ra tệp **`CAU01.OUT`** gồm một dòng duy nhất chứa số cặp số anh em trong đoạn $[1,N]$. **Ví dụ**: | CAU01.INP | CAU01.OUT | Giải thích | | - | - | - | | 10 | 5 | Trong đoạn $[1,10]$ có 5 cặp số anh em là $(2,3)$; $(3,4)$; $(4,7)$; $(5,6)$; $(7,8)$ | - Có 80% test có $N \leq 10^4$; Có 20% test có $10^5 \leq N \leq 3 \times 10^5$ ### Câu 2: :::info Nhập vào 2 số tự nhiên $A$, $B$. Hãy đếm xem trong đoạn $[A, B]$ có bao nhiêu số nguyên tố? ::: **Dữ liệu vào**: Đọc từ tệp **`CAU02.INP`** gồm một dòng duy nhất chứa 2 số tự nhiên $A$, $B$ cách nhau bởi một khoảng trắng, $A \leq B \leq 10^7$; **Dữ liệu ra**: Ghi ra tệp **`CAU02.OUT`**, gồm một dòng duy nhất chứa số lượng số nguyên tố trong đoạn $[A, B]$ **Ví dụ**: | CAU02.INP | CAU02.OUT | Giải thích | | - | - | - | | 1 10 | 4 | Có bốn số nguyên tô trong đoạn $[1,10]$ là: 2, 3, 5, 7 | - Có 80% test có $1 \leq A \leq B \leq 10^5$; Có 20% test có $10^6 \leq A \leq B \leq 10^7$. ### Câu 3: :::info Trong một trò chơi chiến tranh trên máy tính, quân đội của bạn và quân đội của đối phương đều có $N$ chiến binh. Mỗi chiến binh đều được biết đến qua một số đo sức mạnh. Quân đội của bạn có thể chiến thắng nều mỗi chiến binh của bạn có thể tiêu diệt được ít nhất một chiến binh của đối phương. Chiến binh $A$ tiêu diệt được chiến binh $B$ khi và chỉ khi số đo sức mạnh của $A$ lớn hơn hẳn $B$. ::: **Yêu cầu**: Biết số đo sức mạnh cụ thể của các chiến binh của cả hai bên. Hãy cho biết đội quân của bạn có thể chiến thắng hay không. **Dữ liệu vào**: Đọc từ tệp **`CAU03.INP`** gồm 3 dòng: - Dòng thứ nhất chứa số nguyên $N$ là số chiến binh trong mỗi đội quân. - Dòng thứ hai chứa $N$ số nguyên dương $(a_1,\ a_2,...,\ a_n)$ mô tả số đo sức mạnh của mỗi chiến binh trong đội quân của bạn. - Dòng thứ ba chứa $N$ số nguyên dương $(b_1,\ b_2, ...,\ b_n)$ mô tả số đo sức mạnh của mỗi chiến binh trong đội quân của đối phương. **Ràng buộc**: - $0 < N \leq 10^5$ - $1 \leq a_i,\ b_i \leq 10^9,\ i=1..N$ **Dữ liệu ra**: Ghi ra tệp **`CAU03.OUT`** gồm một dòng duy nhất: Ghi ra chữ **Yes** nếu quân đội của bạn có thể chiến thắng theo mô tả của đề bài, ngược lại in ra chữ **No**. **Ví dụ**: | CAU03.INP | CAU03.OUT | Giải thích | | - | - | - | | 5 2 3 5 4 6 1 3 2 5 4 | Yes | Quân đội của bạn có thể giành chiến thắng nên in ra chữ Yes | | 5 2 2 5 4 6 1 3 2 5 4 | No | Quân đội của bạn không thể giành chiến thắng nên in ra chữ No | ### Câu 4: :::info Một xâu được gọi là đối xứng nếu nó không có ít hơn một kí tự và nếu ta đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ: 'A', 'TET', 'CAOOAC' là các xâu đối xứng, còn 'ABC', 'CAGHYD' là các xâu không đối xứng. ::: **Yêu cầu**: Cho xâu kí tự $S$, có chiều dài $N$ $(1 \leq N \leq 1000)$. Hãy tìm chiều dài xâu con đối xứng dài nhất của $S$. Xâu con của xâu $S$ là dãy các kí tự liên tiếp nhau trong $S$. **Dữ liệu vào**: Đọc từ tệp **`CAU04.INP`** gồm hai dòng: - Dòng đầu ghi giá trị $N$ là độ dài của xâu $S$. - Dòng thứ hai gồm $N$ kí tự liên tiếp, các kí tự chỉ gồm các chữ cái tiếng Anh in hoa. **Dữ liệu ra**: Ghi ra tệp **`CAU04.OUT`** gồm một dòng duy nhất chứa độ dài xâu con đối xứng dài nhất. **Ví dụ**: | CAU04.INP | CAU04.OUT | Giải thích | | - | - | - | | 18 IK**ACOBEGIGEBOCA**HTM | 13 | Độ dài xâu con đối xứng dài nhất là 13 | | 19 IKACOB**EGIGE**MHB**EGIGE** | 5 | Độ đài xâu con đối xứng dài nhất là 5 | ### Câu 5: :::info Tranh thủ trong giờ ra chơi, hai bạn Nam và Bình rủ nhau chơi trò tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên bảng, cứ như vậy hai bạn viết được một dãy gồm $N$ số $a_1,\ a_2,...,\ a_N$. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì đã đến giờ học. Thầy vào lớp, sẵn thấy dãy số trên bảng, thầy đã đặt ra câu đố: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất. Vì dãy số có quá nhiều số nên cả lớp nhìn hoa cả mắt mà vẫn chưa tìm ra được đáp án. Em hãy lập trình giải giúp các bạn trong lớp nhé. ::: **Dữ liệu vào**: Đọc từ tệp **`CAU05.INP`** có dạng như sau: - Dòng đầu tiên ghi số nguyên $N$ $(1 \leq N \leq 10^5)$ - Dòng thứ hai ghi dãy số nguyên $a_1,\ a_2,...,\ a_N$ $(|a_i| \leq 1000,\ i=1..N)$ **Dữ liệu ra**: Ghi ra tệp **`CAU05.OUT`** gồm một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy: **Ví dụ**: | CAU05.INP | CAU05.OUT | Giải thích | | - | - | - | | 10 2 -9 4 1 -3 5 8 -7 3 1 | 15 | Chọn các phần tử: 4, 1, -3, 5, 8 | Có 30% test có $N \leq 400$; Có 30% test có $10^3 < N \leq 10^4$; Có 40% test có $10^5 < N \leq 10^6$. ----- HẾT ----- **Lưu ý**: - Thí sinh chỉ được sử dụng máy vi tính không có kết nối mạng khi làm bài - Giám thị không giải thích gì thêm. --- ## ĐỀ SỐ 3: Phòng GD&ĐT Thành phố Vinh (Nghệ An) **PHÒNG GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ VINH** KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2023-2024 Môn: TIN HỌC --- (Đề thi gồm có 03 trang) Thời gian làm bài: 150 phút (không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | Câu | Tên bài | File chương trình | File dữ liệu | File kết quả | Thời gian | Bộ nhớ | Điểm | | - | - | - | - | - | - | - | - | | 1 | Trồng cây xanh | CAYXANH.\* | CAYXANH.INP | CAYXANH.OUT | 1 giây | 1024MB | 6,0 | | 2 | Tìm số nguyên tố lớn nhất | NTMAX.\* | NTMAX.INP | NTMAX.OUT | 1 giây | 1024MB | 5,0 | | 3 | Khen thưởng theo giờ làm việc | CHIAGIO.\* | CHIAGIO.INP | CHIAGIO.OUT | 1 giây | 1024MB | 5,0 | | 4 | Chọn phòng | CHONPHONG.\* | CHONPHONG.INP | CHONPHONG.OUT | 1 giây | 1024MB | 4,0 | Dấu * được thay thế bởi `PAS` hoặc `CPP`, `PY` của ngôn ngữ lập trình sử dụng tương ứng là là Pascal hoặc C/C++, Python. ### Câu 1: TRỒNG CÂY XANH :::info Để chuẩn bị cho Lễ kỉ niệm 60 năm thành lập Thành phố, công ty Cây Xanh đã cho trồng lại toàn bộ cây xung quanh khu vực Quảng Trường, tiêu chí lựa chọn cây được đưa ra như sau: Trong số $n$ cây có ở vườn ươm, sẽ chọn các cây có chiều cao tương ứng với nhau chênh lệch không quá $m$ (cm) so với chiều cao $l$ của một cây cho trước. ::: **Dữ liệu vào**: Đọc từ file văn bản **`CAYXANH.INP`** gồm: - Dòng đầu gồm 3 số $n,\ l,\ m$ $(n \leq 10^5;\ l,m \leq 10^9)$, gồm $m$ cây để lựa chọn, chiều cao $l$ cho trước và độ chênh lệch $m$. - Dòng sau gồm $n$ số nguyên dương $a_i$ là chiều cao của $n$ cây để lựa chọn $(a_i \leq 10^9)$. **Dữ liệu ra**: Ghi ra file văn bản **`CAYXANH.OUT`** gồm: một số nguyên duy nhất cho biết số cây được lựa chọn để trồng. **Ví dụ**: | CAYXANH.INP | CAYXANH.OUT | | - | - | | 7 50 20 60 20 40 30 80 90 45 | 4 | ### Câu 2: TÌM SỐ NGUYÊN TỐ LỚN NHẤT :::info Cho xâu ký tự $S$ có $n$ ký tự chỉ gồm chữ cái, chữ số. Em hãy thực hiện hai thao tác sau: - Thao tác 1: Đếm các ký tự là ký tự số trong xâu $S$; - Thao tác 2: Tìm số $A$ trong xâu ký tự $S$ là số nguyên tố lớn nhất. Số $A$ là tất cả các ký tự số liên tiếp trong xâu ký tự $S$ và không có số $0$ vô nghĩa. ::: **Dữ liệu vào**: Đọc vào từ file văn bản **`NTMAX.INP`** gồm một xâu ký tự $S$. **Dữ liệu ra**: Ghi ra file văn bản **`NTMAX.OUT`** gồm: - Dòng 1 ghi số lượng các ký tự là ký tự số trong xâu $S$. - Dòng 2 ghi ra số nguyên tố $A$ lớn nhất, nếu không có số nguyên tố ghi ra số $0$. **Ví dụ**: | NTMAX.INP | NTMAX.OUT | Giải thích | | - | - | - | | G00101E11bin000Bik47dabEl | 13 101 | - Có 13 ký tự số trong xâu - Số A nguyên tố lớn nhất là 101 | | Cds12cd44bcd | 4 0 | | | Hocsinhgioi | 0 0 | | ### Câu 3: KHEN THƯỞNG THEO GIỜ LÀM VIỆC :::info Trong một công ty sản xuất thức ăn nhanh làm việc theo dây chuyền, số giờ làm việc của các công nhân hàng tháng được tổ trưởng tính và ghi ra bảng thành 1 dãy số theo thứ tự vị trí của từng công nhân. Cuối tháng, tổ trưởng muốn khen thưởng các nhóm công nhân có tổng số giờ làm việc bằng nhau. Các công nhân trong nhóm được sắp xếp đứng liên tiếp gần nhau (số lượng công nhân trong các nhóm có thể khác nhau). Em hãy giúp tổ trưởng chia thành nhiều nhóm nhất sao cho các nhóm đều có tổng số giờ làm việc bằng nhau. ::: **Dữ liệu vào**: Đọc vào từ file văn bản **`CHIAGIO.INP`** gồm: - Dòng đầu ghi số $n$ (số lượng công nhân, $n<100$) - Các dòng còn lại ghi các số $a_1,\ a_2,...,\ a_n$ (số giờ làm việc của từng công nhân hàng tháng), các số trên cùng một dòng cách nhau một dấu cách trống. **Dữ liệu ra**: ghi ra file văn bản **`CHIAGIO.OUT`**, gồm $K+1$ dòng ($K$ là số nhóm công nhân chia được nhiều nhất) như sau: - Dòng đầu ghi hai số $K$ và $S$ ($S$ là tổng số giờ làm việc của các nhóm). - $K$ dòng còn lại mỗi dòng ghi số giờ của mỗi công nhân trong từng nhóm được chia, các số trên cùng một dòng cách nhau một dấu cách trống. **Ví dụ**: | CHIAGIO.INP | CHIAGIO.OUT | | - | - | | 6 6 5 1 10 8 3 | 3 11 6 5 1 10 8 3 | | 5 3 6 9 1 8 | 3 9 3 6 9 1 8 | ### Câu 4: CHỌN PHÒNG :::info Để đưa đoàn học sinh tham dự kỳ sinh học sinh giỏi cấp Tỉnh được tổ chứ tại thành phố A. Thầy Nam được huyện cử đi cùng $K$ học sinh. Trước khi đi, Thầy tham khảo một khách sạn để đặt phòng cho Thầy và học sinh. Khách sạn có tổng cộng $N$ phòng đánh số từ $1$ đến $N$ trải dài trên một hành lang. Vì để không gian cho học sinh xem lại bài đêm trước ngày thi nên mỗi em sẽ ở trong một phòng khác nhau. Trước khi Thầy chọn khách sạn để đặt phòng thì một số phòng đã có người thuê. Trạng thái của $N$ phòng được biểu diễn băng xâu nhị phân $S$. Kí tự $S_i = 0$ cho biết phòng thứ $i$ đang trống, $S_i = 1$ cho biết phòng thứ $i$ đã có người thuê. Thầy quyết định đặt $K + 1$ phòng trống với yêu cầu để có thể dễ dàñg quản lý học sinh vì vậy khách sạn phải tìm cho Thầy các căn phòng sao cho khoảng cách căn phòng của bạn học sinh xa nhất đến căn phòng của Thầy là nhỏ nhất có thể. ::: **Dữ liệu vào**: - Dòng đầu tiên gồm 2 số nguyên dương $N,\ K$ $(1 \leq K < N \leq 10^5)$. - Dòng thứ hai gồm xâu nhị phân $S$. - Dữ liệu đảm bảo số phòng trống lớn hơn $K$. **Dữ liệu ra**: In ra giá trị nhỏ nhất có thể của khoảng cách từ căn phòng bạn học sinh xa nhất đến căn phòng của Thầy Nam. **Ví dụ**: | CHONPHONG.INP | CHONPHONG.OUT | | - | - | | 15 10 000001000000000 | 6 | | 10 2 0000000000 | 1 | ----- HẾT ----- --- ## ĐỀ SỐ 4: Phòng GD&ĐT Huyện Tuyên Hoá (Quảng Bình) **PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN TUYÊN HOÁ** KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 NĂM HỌC 2023-2024 Môn: TIN HỌC --- (Đề thi gồm có 03 câu, 02 trang) Thời gian làm bài: 150 phút (không kể thời gian giao đề) ### TỔNG QUAN ĐỀ THI | STT | Tên bài | File bài làm | File đầu vào | File đầu ra | Điểm | | - | - | - | - | - | - | | Câu 1 | Ước số chung lớn nhất | UCLN.\* | UCLN.INP | UCLN.OUT | 3,0 | | Câu 2 | Tập các ký tự đại diện | KTDD.\* | KTDD.INP | KTDD.OUT | 3,5 | | Câu 3 | Chia bánh | CAKE.\* | CAKE.INP | CAKE.OUT | 3,5 | Sử dụng ngôn ngữ lập trình Pascal hoặc C++ hoặc Scratch để lập trình giải các bài toán sau: ### Câu 1: ƯỚC SỐ CHUNG LỚN NHẤT :::info Cho ba số nguyên dương $a,\ b,\ c$. Hãy xét xem $c$ có phải là ước số chung lớn nhất của $a$ và $b$ hay không? ::: **Dữ liệu vào**: Cho trong file **`UCLN.INP`**, có cấu trúc như sau: Dòng 1: Ghi 3 số nguyên dương theo thứ tự là $a,\ b,\ c$ $(0 < a, b, c < 32767)$. Các số được chỉ cách nhau ít nhất 1 dấu cách trống. **Dữ liệu ra**: Ghi ra file **``UCLN.OUT``**, theo cấu trúc như sau: Dòng 1: Nếu $c$ là ước số chung lớn nhất của $a$ và $b$ thì ghi ra số $1$, ngược lại thì ghi ra số $0$. **Ví dụ**: | UCLN.INP | UCLN.OUT | | - | - | | 10 15 5 | 1 | | 12 9 4 | 0 | ### Câu 2: TẬP CÁC KÝ TỰ ĐẠI ĐIỆN :::info Cho một xâu ký tự $St$ gồm các ký tự được lấy từ tập: 'a'...'z'. Người ta định nghĩa: tập $X$ (gồm các ký tự $x_1,\ x_2,...,\ x_n$) là tập ký tự đại diện của xâu $St$ nếu thỏa mãn đồng thời 3 điều kiện: + Mọi ký tự $x_i$ thuộc tập $X$ phải có xuất hiện trong xâu $St$ $(1 \leq i \leq n)$; + Với mọi ký tự $x_i$ và ký tự $x_j$ thuộc tập $X$ thì $x_i \neq x_j$ $(1 \leq i,j \leq n)$; + Tập $X$ có nhiều phần tử nhất. **Ví dụ**: Với xâu $St$ = 'abaadcc' Khi đó, tập ký tự đại diện là $X$ = {'a', 'b', 'c', 'd'}. ::: **Yêu cầu**: Tìm tập ký tự đại diện $X$ của xâu $St$ đã cho. **Dữ liệu vào**: Cho trong file văn bản **`KTDD.INP`**, có cấu trúc như sau: Dòng 1: Ghi xâu ký tự $St$ ($St$ khác rỗng, có không quá 255 ký tự). **Dữ liệu ra**: Ghi ra file văn bản **`KTDD.OUT`**, theo cấu trúc như sau: Dòng 1: Ghi các ký tự thuộc tập $X$ tìm được (các ký tự được ghi cách nhau 1 dấu cách trống}. **Ví dụ**: | KTDD.INP | KTDD.OUT | | - | - | | abaadcc | a b c d | *Lưu ý: Các ký tự trong file dữ liệu ra không bắt buộc phải ghi đúng theo thứ tự xuất hiện của ký tự trong file dữ liệu vào.* ### Câu 3: CHIA BÁNH :::info Có một cái bánh trung thu hình tròn. Bánh được viền quanh bởi $N$ quả dâu và quả sim $(1 < N \leq 255)$. ::: **Yêu cầu**: Tìm cách cắt bánh bằng một nhát dao để được hai phần sao cho số lượng quả dâu ở phần này bằng số lượng quả dâu ở phần kia và số lượng quả sim ở phần này bằng số lượng quả sim ở phần kia. **Dữ liệu vào**: Cho trong file **`CAKE.INP`**, có cấu trúc như sau: - Dòng 1: Ghi số $N$ là số lượng quả dâu và quả sim ở trên viền bánh. - Dòng 2: Ghi dãy gồm $N$ ký tự '**D**' hoặc '**S**' ghi liền nhau. Các vị trí gắn quả trên bánh được đánh số từ $1$ đến $N$ bắt đầu từ ký tự đầu tiên, theo chiều kim đồng hồ. **Dữ liệu ra**: Ghi ra file **`CAKE.OUT`**, có cấu trúc như sau: - Dòng 1: Nếu không có cách chia thì ghi số $-1$. Nếu có cách chia thì ghi hai số nguyên dương $a,\ b$ $(a < b)$ cho biết các quả ở các vị trí từ $a$ đến $b$ là các quả thuộc cùng một trong hai phần bánh. **Ví dụ**: | CAKE.INP | CAKE.OUT | | - | - | | 6 DSSSDS | 3 5 | | 5 DSDDS | -1 | *Chú ý: Có thể có nhiều cách chia bánh, chỉ cần đưa ra một cách chia đúng.* ----- HẾT ----- --- ## ĐỀ SỐ 5: Trường PTDTNT THCS - Huyện Con Cuông (Nghệ An) **PHÒNG GIÁO DỤC VÀ ĐÀO TẠO HUYỆN CON CUÔNG - TRƯỜNG PTDTNT THCS** KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TRƯỜNG NĂM HỌC 2023-2024 Môn: TIN HỌC --- (Đề thi gồm có 03 câu, 02 trang) Thời gian làm bài: 150 phút (không kể thời gian giao đề) ### TỔNG QUAN BÀI THI | STT | Tệp chương trình | Tệp dữ liệu vào | Tệp dữ liệu ra | Giới hạn thời gian | Điểm | | - | - | - | - | - | - | | Bài 1 | KNTO.\* | KNTO.INP | KNTO.OUT | 1 giây | 6,0 | | Bài 2 | SWAPMIN.\* | SWAPMIN.INP | SWAPMIN.OUT | 1 giây | 5,0 | | Bài 3 | UOCCHANLE.\* | UOCCHANLE.INP | UOCCHANLE.OUT | 1 giây | 5,0 | | Bài 4 | DDSORT.\* | DDSORT.INP | DDSORT.OUT | 1 giây | 4,0 | Em hãy sử dụng ngôn ngữ lập trình Pascal hoặc C/C++ đề giải các bài tập sau: ### Câu 1: KHÔNG NGUYÊN TỐ :::info Cho $P$ là tập hợp các ước số không nguyên tố của số nguyên dương $n$. Hãy tìm số phần tử của tập hợp $P$. ::: **Dữ liệu**: được cho trong tệp văn bản **`KNTO.INP`** gồm: Một dòng duy nhất là giá trị của $n$ $(1 \leq n \leq 10^{14})$ **Kết quả**: ghi ra tệp văn bản **`KNTO.OUT`** gồm: Một dòng duy nhất là số phần tử của $P$ **Ví dụ**: | KNTO.INP | KNTO.OUT | | - | - | | 180 | 15 | | 20 | 4 | **Giới hạn**: - Có 60% test tương ứng 60% số điểm thoã mãn $n \leq 10^6$ - Có 40% test tương ứng 40% số điểm thoã mãn $10^6 \leq n \leq 10^{14}$ ### Câu 2: TRÁO ĐỔI CHỮ SỐ ĐỂ ĐƯỢC SỐ NHỎ NHẤT :::info Cho một số nguyên dương $N$ $(N \leq 10^9)$. Hãy tìm cách tráo đổi vị trí các chữ số để nhận được số có giá trị nhỏ nhất. ::: **Dữ liệu**: được cho trong tệp văn bản **`SWAPMIN.INP`** gồm: Số nguyên dương $N$ $(N \leq 10^9)$ **Kết quả**: ghi ra tệp văn bản **`SWAPMIN.OUT`** gồm: Số nhỏ nhất có thể nhận được khi tráo đổi các vị trí chữ số của $N$. *Chú ý*: Không đưa ra chữ số '0' ở bên trái mỗi số tìm được. **Ví dụ**: | SWAPMIN.INP | SWAPMIN.OUT | | - | - | | 1302 | 123 | ### Câu 3: ƯỚC CHẴN LẺ :::info Mẹ bảo An dạy cho em Bình học toán, làm quen với khái niệm Ước số. An thây em mình khá thông minh, việc kiểm tra một số có phải là ước của số nguyên dương $n$ hay không có vẻ quá đơn giản đối với nó. Vì vậy An ra yêu cầu mới, với số nguyên dương $n$, cần đếm số lượng ước dương của $n$. Cuối cùng hãy kiểm tra số lượng các ước của $n$ là số lẻ hay chẵn. *Ví dụ*: - $n = 3$ thì số lượng ước là chẵn vì $3$ có 2 ước là $1$ và $3$. - $n = 4$ thì số lượng ước là lẻ vì $4$ có 3 ước là $1$, $2$, và $4$. ::: **Dữ liệu vào**: từ file văn bản **`UOCCHANLE.INP`** - Dòng 1 chứa một số nguyên dương $t$ $(1 \leq t \leq 100)$, số lượng số $n$ cần kiêm tra. - $t$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương $n$ $(n \leq 10^{18})$ **Kết quả** ghi ra file văn bản **`UOCCHANLE.OUT`** - Gồm $t$ dòng, mỗi dòng ghi ra kết quả “**CHAN**” hoặc “**LE**” tương ứng với số lượng ước của số nguyên $n$ cần kiểm tra là số chẵn hoặc số lẻ. **Ví dụ**: | UOCCHANLE.INP | UOCCHANLE.OUT | | - | - | | 5 1 7 6 4 8 | LE CHAN CHAN LE CHAN | ### Câu 4: DÃY ĐẠI DIỆN SẮP XẾP :::info Cho dãy số nguyên $A$ gồm $N$ số hạng $A_1,\ A_2,...,\ A_N$. Nếu có nhiều số hạng trong dãy bằng nhau thì xóa các số hạng đó và chỉ để lại một số hạng. Sắp xếp dãy sau khi xóa thì ta được dãy đại diện sắp xếp của dãy $A$. *Ví dụ*: $A = \{5, 2, 1, 1, 2, 2, 3\}$. Dãy đại diện sắp xếp là: $\{1, 2, 3, 5\}$. ::: **Dữ liệu** cho trong file **`DDSORT.INP`** gồm: - Dòng đầu ghi số nguyên dương $N$ $(N \leq 200000)$. - Dòng sau ghi $N$ số nguyên $A_1,\ A_2,...,\ A_N$ $(|A_i| \leq 10^9)$. **Kết quả** ghi ra file **`DDSORT.OUT`** gồm dãy đại diện sắp xếp của dãy $A$. **Ví dụ**: | DDSORT.INP | DDSORT.OUT | | - | - | | 7 5 2 1 1 2 2 3 | 1 2 3 5 | ----- HẾT ----- ---