HSG lớp 9 Nghệ An 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC
(Đề thi gồm 4 trang)

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2023 - 2024
Môn thi: Tin học
Thời gian làm bài 150 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Bộ nhớ tối đa	Thời gian
Hình chữ nhật đẹp	B1.*	B1.INP	B1.OUT	1024MB	1 giây
Bốc số	B2.*	B2.INP	B2.OUT	1024MB	1 giây
Xếp gạch	B3.*	B3.INP	B3.OUT	1024MB	1 giây
Thẻ bài	B4.*	B4.INP	B4.OUT	1024MB	1 giây

Phần mở rộng .* được thay thế bằng Pas, Cpp, Py ứng với các ngôn ngữ lập trình Pascal, C++, Python.

Câu 1. Hình chữ nhật đẹp (6.0 điểm)

Trong giờ hình học, An được thầy giáo dạy về công thức tính diện tích của hình chữ nhật và hình vuông. An thấy hình vuông rất đẹp nên cậu định nghĩa một hình chữ nhật “đẹp” là hình chữ nhật có các đặc điểm sau:

• Độ dài hai cạnh là các số nguyên dương.
• Diện tích bằng diện tích của một hình vuông có độ dài cạnh là một số nguyên dương.

An đã phát biểu định nghĩa này trước lớp và thách đố bài toán như sau:

“Cho số nguyên dương x. Tìm số nguyên dương y nhỏ nhất để x và y là độ dài hai cạnh của một hình chữ nhật “đẹp”.“

Yêu cầu: Giúp cả lớp tìm số nguyên dương y thỏa mãn bài toán của An.

Dữ liệu: Nhập từ tệp văn bản B1.INP, gồm một dòng duy nhất chứa số nguyên dương x.

Kết quả: Ghi ra tệp văn bản B1.OUT, gồm một dòng duy nhất chứa số nguyên dương y.

Ví dụ:

B1.INP	B1.OUT
4	1
6	6
8	2

Giới hạn:

• 90% số test tương ứng với 90% số điểm thỏa mãn 1 ≤ x ≤ 10⁶;
• 10% số test tương ứng với 10% số điểm thỏa mãn 10⁶ < x ≤ 10¹².

Câu 2. Bốc số

Nhân dịp năm mới Giáp Thìn, An tham gia lễ hội đầu năm thường niên của làng. Lễ hội có nhiều trò chơi thú vị thu hút sự chú ý của An, cậu chơi trò chơi đầu tiên là “Bốc số”.

Luật chơi của trò chơi rất đơn giản: ở mỗi lượt chơi, An bốc từ thùng một lá thăm, mỗi lá thăm gồm 2 phần:

• Phần đầu lá thăm là một dãy có độ dài N kí tự gồm các chữ số từ 1 đến 9.
• Phần sau lá thăm ghi số 0 hoặc 1, cách phần đầu một khoảng trống.

Công việc của An là xóa đi một hoặc một vài kí tự của phần đầu lá thăm sau đó viết các kí tự còn lại theo đúng thứ tự ban đầu (từ trái qua phải) để thu được một số nguyên dương lớn nhất thỏa mãn:

• Chia hết cho 5 nếu phần sau lá thăm là 0.
• Chia hết cho 3 nếu phần sau lá thăm là 1.

Yêu cầu: Hãy giúp An hoàn thành trò chơi.

Dữ liệu: Nhập từ tệp B2.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương t là số lần bốc thăm của An (1 ≤ t ≤ 100).
• t dòng tiếp theo, dòng thứ i ghi một dãy có độ dài N (1 ≤ N ≤ 100) kí tự gồm các chữ số từ 1 đến 9 và một số k (phân biệt bằng dấu cách trống) đại diện cho lá thăm thứ i.

Kết quả: Ghi ra tệp B2.OUT gồm t dòng, dòng thứ i chứa kết quả của lần bốc thăm thứ i (dữ liệu đầu vào luôn đảm bảo có kết quả).

Ví dụ:

B2.INP	B2.OUT
4 2433514 0 5295284 0 12324524 1 5321 1	24335 5295 1324524 531

Giới hạn:

• 60% số test tương ứng 60% số điểm thoả mãn k = 0;
• 20% số test tương ứng 20% số điểm thoả mãn 1 ≤ N ≤ 18;
• 20% số test tương ứng 20% số điểm không có ràng buộc gì thêm.

Câu 3. Xếp gạch

Sau khi tham gia trò chơi “Bốc số”, An tiếp tục tham gia trò chơi “Xếp gạch”. Ban tổ chức cho trước n chồng gạch được xếp thành một hàng ngang và đánh số từ 1 đến n. Số viên gạch ở các chồng lần lượt là a₁, a₂, …, aₙ.

An cần thực hiện m lượt chơi tương ứng với dãy số nguyên dương b₁, b₂, …, b_m đã biết trước. Ở lượt thứ i (1 ≤ i ≤ m), An được quyền thực hiện chỉ một trong hai lựa chọn:

• Bỏ qua không sử dụng giá trị bᵢ.
• Xếp thêm bᵢ viên gạch lên chồng gạch thứ j (1 ≤ j ≤ n) nếu tất cả các chồng gạch thứ j, j + 1, j + 2, …, n chưa từng được xếp thêm viên gạch nào trong các lượt trước đó.

Trò chơi dừng lại khi hết lượt hoặc An đã thực hiện xếp thêm gạch ở chồng thứ n. Khi đó ban tổ chức sẽ đếm số gạch ở mỗi chồng và lấy số gạch ở chồng ít nhất làm điểm số của An.

Cách chơi của An là tối ưu nhất nên cậu đã đạt được số điểm tối đa của trò chơi.

Yêu cầu: Hãy tìm ra số điểm An đạt được.

Dữ liệu: Nhập từ tệp B3.INP gồm 3 dòng:

• Dòng 1: ghi hai số nguyên dương n và m lần lượt là số chồng gạch ban đầu và số lượt chơi của An.
• Dòng 2: ghi n số nguyên không âm a₁, a₂, …, aₙ (aᵢ ≤ 10⁸) mô tả số gạch ở các chồng ban đầu.
• Dòng 3: ghi m số nguyên dương b₁, b₂, …, b_m (bᵢ ≤ 10⁸) mô tả các giá trị của ban tổ chức đưa trước cho An, bᵢ là giá trị được sử dụng ở lượt thứ i.

Kết quả: Ghi ra tệp B3.OUT gồm 1 dòng chứa số điểm An đạt được.

Ví dụ:

B3.INP	B3.OUT	Giải thích
5 3 2 5 1 4 6 1 3 4	4	An bỏ qua lượt 1; An xếp 3 viên gạch vào chồng gạch thứ nhất ở lượt 2; An xếp 4 viên gạch vào chồng gạch thứ ba ở lượt 3. Khi đó số gạch ở các chồng gạch lần lượt là 5; 5; 5; 4; 6 nên số điểm đạt được là 4.

Giới hạn:

• 40% số test tương ứng 40% số điểm thoả mãn m = 1, 1 ≤ n ≤ 10²;
• 30% số test tương ứng 30% số điểm thoả mãn m = 2 và 10² < n ≤ 10³;
• 30% số test tương ứng 30% số điểm thoả mãn 10³ < n, m ≤ 10⁵.

Câu 4. Thẻ bài

Sau khi hoàn thành 2 trò chơi thú vị của lễ hội, An cảm thấy rất hứng thú và cậu quyết định chơi trò chơi cuối trước khi về. An chọn trò chơi có thưởng của lễ hội do một ông giáo về hưu trong làng chủ trì.

Ông giáo xếp các ống tre gồm hai màu xanh hoặc đỏ thành một hoặc hai hàng ngang.

Ông giáo có 10⁶ thẻ bài được xếp thành một chồng, được đánh số từ 1 đến 10⁶ theo thứ tự từ trên xuống dưới. Bắt đầu trò chơi, An bốc lần lượt các thẻ bài từ trên xuống dưới của chồng bài và chọn không bỏ thẻ bài này vào bất kì ống tre nào (kể cả trong những lượt bốc sau) hoặc bỏ thẻ bài đó vào một ống tre thỏa mãn các yêu cầu:

• Mỗi ống tre chứa đúng một thẻ bài duy nhất.
• Thẻ số chẵn chỉ được bỏ vào ống màu xanh, thẻ số lẻ chỉ được bỏ vào ống màu đỏ.
• Chỉ được bỏ thẻ bài vào ống tre thứ i khi các ống tre 1, 2, …, i − 1 của hàng đó đã được bỏ thẻ bài.

Trò chơi kết thúc khi An đã bỏ thẻ bài vào tất cả các ống tre mà ông giáo xếp ra. Điểm thưởng của An đạt được là số thẻ bài còn lại trong chồng bài ban đầu.

Với sự thông minh của mình thì trò chơi của ông giáo đã không làm khó được An và cậu đã đạt được số điểm cao nhất của trò chơi.

Yêu cầu: Hãy tìm số điểm mà An đạt được.

Dữ liệu: Nhập từ tệp B4.INP có cấu trúc:

• Dòng 1: Ghi số k bằng 1 hoặc 2 thể hiện số lượng hàng ngang ông giáo xếp ra.
• Dòng 2: Ghi một chuỗi có độ dài không quá 5000 kí tự, gồm hai loại kí tự B và R (B tương ứng với ống tre màu xanh và R tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ nhất.
• Dòng 3: tùy vào giá trị của k, cụ thể:
  • k = 1: bỏ trống
  • k = 2: ghi một chuỗi có độ dài không quá 5000 kí tự, gồm hai loại kí tự B và R (B tương ứng với ống tre màu xanh và R tương ứng với ống tre màu đỏ) mô tả hàng ống tre thứ hai.

Kết quả: Ghi ra tệp B4.OUT gồm 1 dòng chứa số điểm cao nhất có thể đạt được.

Ví dụ:

B4.INP	B4.OUT	Giải thích
1 BRR	999995	An bỏ các thẻ theo thứ tự là 2; 3; 5 nên số điểm của An là 10⁶ − 5 = 999995.
2 BRR BBB	999992	An bỏ các thẻ ở hai hàng theo thứ tự là 2; 3; 5 và 4; 6; 8 nên số điểm của An là 10⁶ − 8 = 999992.
2 BRBRB RBRB	999990	An bỏ các thẻ ở hai hàng theo thứ tự là 2; 3; 6; 7; 10 và 1; 4; 5; 8 nên số điểm của An là 10⁶ − 10 = 999990.

Giới hạn:

• 20% số test tương ứng 20% số điểm thoả mãn k = 1;
• 30% số test tương ứng 30% số điểm thoả mãn k = 2 và dòng 2 có các kí tự giống nhau;
• 50% số test tương ứng 50% số điểm thoả mãn k = 2 và không ràng buộc gì thêm.