HSG lớp 12 Hải Dương 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO HẢI DƯƠNG ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT CẤP TỈNH NĂM HỌC 2023 - 2024 Môn thi: Tin học
Ngày thi: 25/10/2023
Thời gian làm bài: 180 phút, không tính thời gian phát đề
(Đề thi gồm 05 câu, 04 trang)

---

Tổng quan về các bài thi trong đề

Câu	Tên bài	Tên file chương trình	Dữ liệu nhập từ	Kết quả in ra	Điểm
1	Diện tích	BAI1.*	Bàn phím	Màn hình	2,5
2	Trao thưởng	BAI2.*	Bàn phím	Màn hình	2,5
3	Trắc nghiệm tâm lí	BAI3.*	Bàn phím	Màn hình	2,0
4	Kế hoạch thi đấu	BAI4.*	BAI4.INP	BAI4.OUT	1,5
5	Robot	BAI5.*	BAI5.INP	BAI5.OUT	1,5

Ghi chú: Dấu ’*’ trong tên file chương trình được thay thế bằng PAS, CPP, PY tùy thuộc vào ngôn ngữ lập trình được sử dụng là Pascal, C++, Python.

Viết các chương trình giải các bài toán sau:

Câu 1 (2,5 điểm): Diện tích

Một mảnh vườn hình chữ nhật có chiều dài và chiều rộng là a và b. Người ta làm hai lối đi vào khu vườn, mỗi lối song song với một chiều của hình chữ nhật với độ rộng của cả hai lối đi đều bằng c (phần gạch chéo trong hình bên).

Cho các giá trị a, b, c. Hãy tính tổng diện tích phần còn lại của hình chữ nhật (phần trắng).

Dữ liệu: Nhập từ bàn phím ba số nguyên dương a, b, c (1 ≤ a, b ≤ 10⁹, 1 ≤ c < min(a, b)) cách nhau bằng dấu trống (space).

Kết quả: In ra màn hình một số nguyên là diện tích phần còn lại tìm được.

Ví dụ:

Dữ liệu nhập	Kết quả in ra
4 5 1	12

Ghi chú: Bài thi được chấm qua 10 tests, mỗi test 0,25 điểm.

Câu 2 (2,5 điểm): Trao thưởng

Để chuẩn bị kỷ niệm ngày Nhà giáo Việt Nam (20/11) Đoàn trường có tổ chức giải chạy marathon cho học sinh trong toàn trường. Giải chạy có n học sinh tham gia. Kết quả xếp hạng theo thành tích từ cao xuống thấp và được đánh số từ 1 đến n. Ban tổ chức trao thưởng cho học sinh tham gia như sau: Bạn xếp thứ n được 1 phần quà, các bạn còn lại sẽ nhận được số phần quà theo qui tắc: bạn xếp thứ i có số phần quà nhiều hơn bạn xếp thứ i + 1 là a.

Hãy cho biết Ban tổ chức cần chuẩn bị bao nhiêu phần quà để trao thưởng?

Dữ liệu: Nhập từ bàn phím hai số nguyên dương n và a (n ≤ 10⁹, a ≤ 5) cách nhau bằng dấu trống (space).

Kết quả: In ra màn hình một số nguyên là số phần quà mà Ban tổ chức cần chuẩn bị.

Ví dụ:

Dữ liệu nhập	Kết quả in ra
5 3	35

Ghi chú: Bài thi được chấm qua 10 tests, mỗi test 0,25 điểm trong đó:

• 4 test n ≤ 1000
• 3 test 1000 < n ≤ 10⁶
• 3 test 10⁶ < n ≤ 10⁹

Câu 3 (2,0 điểm): Trắc nghiệm tâm lí

Trắc nghiệm tâm lí là phương pháp thông dụng để có thể đoán nhận được tính cách của mỗi người trong cuộc sống và cũng là một trò chơi khá phổ biến trên truyền hình. Trong một trò chơi như vậy được phát trên kênh VTV. Trước tiên, ban tổ chức phát cho mỗi khán giả ngồi xem trực tiếp một phiếu thăm dò trong đó có các câu hỏi trắc nghiệm. Tất cả các phương án trả lời đều có điểm và mỗi người sau khi trả lời xong sẽ được tổng điểm là một số nguyên dương. Có m người tham gia cuộc chơi trên sân khấu. Với người chơi thứ i, sau khi nghe người dẫn chương trình đọc các câu hỏi trắc nghiệm sẽ đưa ra hai số nguyên s_i và f_i với ý nghĩa rằng những khán giả có tổng điểm nằm trong đoạn [s_i, f_i] sẽ là những người có tính cách phù hợp với mình nhất.

Yêu cầu: Viết chương trình tính xem mỗi người chơi sẽ tìm thấy bao nhiêu khán giả có tính cách phù hợp với mình nhất.

Dữ liệu: Nhập từ bàn phím bao gồm:

• Dòng đầu tiên chứa số nguyên n (0 < n ≤ 10⁵) là số khán giả.
• Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁵) là tổng điểm của mỗi khán giả.
• Dòng thứ ba chứa số nguyên m (1 ≤ m ≤ 10⁵) là số người chơi.
• m dòng tiếp theo, dòng thứ i chứa hai số nguyên s_i, f_i (1 ≤ s_i ≤ f_i ≤ 10⁵) là khoảng điểm của những người có tính cách phù hợp nhất với người i nhất (1 ≤ i ≤ m).

Hai số nguyên liên tiếp trên cùng một dòng cách nhau bằng dấu trống (space)

Kết quả: In ra màn hình gồm m dòng, dòng thứ i ghi một số nguyên là số lượng khán giả có tính cách phù hợp với người thứ i nhất (1 ≤ i ≤ m).

Ví dụ:

Dữ liệu nhập	Kết quả in ra
5 7 2 4 5 3 2 1 4 3 10	3 4

Ghi chú: Bài thi được chấm qua 8 tests, mỗi test 0,25 điểm. Trong đó:

• 5 test có n, m ≤ 5000
• 3 test có 5000 < n, m ≤ 10⁵

Câu 4 (1,5 điểm): Kế hoạch thi đấu

Nam là một vận động viên quần vợt chuyên nghiệp. Trong một hệ thống thi đấu quần vợt, người ta tổ chức n giải đấu đánh số từ 1 đến n. Giải đấu thứ i được tổ chức vào ngày thứ a_i (ngày Ban tổ chức ra quyết định là ngày thứ 1) và mỗi vận động viên tham gia được cộng điểm thưởng là b_i. Để đảm bảo sức khỏe, huấn luyện viên quyết định hai giải đấu mà Nam chọn tham dự phải cách xa nhau ít nhất là k ngày (|a_i − a_j| ≥ k nếu Nam tham dự cả giải thứ i và giải thứ j).

Bạn hãy giúp Nam chọn lựa các giải thi đấu sao cho tổng số điểm thưởng là nhiều nhất.

Dữ liệu: Nhập vào từ file văn bản BAI4.INP chứa các dòng dữ liệu sau:

• Dòng đầu tiên là hai số nguyên n và k cách nhau một dấu trống (space) (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100)
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (1 ≤ a_i ≤ 10⁹) là ngày thi đấu của các giải 1, 2, …, n; mỗi số cách nhau một dấu trống (space). Dữ liệu cho đảm bảo a₁ < a₂ < a₃ < … < a_n.
• Dòng thứ ba chứa n số nguyên b₁, b₂, …, b_n (1 ≤ b_i ≤ 10⁴) là số điểm thưởng của các giải 1, 2, …, n; mỗi số cách nhau một dấu trống (space).

Kết quả: Ghi ra file văn bản BAI4.OUT

• Một số nguyên duy nhất là tổng số điểm thưởng lớn nhất mà Nam có thể có được.

Ví dụ:

BAI4.INP	BAI4.OUT
5 2 1 2 3 4 5 1 5 1 5 1	10

Ghi chú: Bài được chấm qua 6 tests, mỗi test 0,25 điểm. Trong đó:

• 3 tests có n ≤ 5000
• 3 test có 5000 < n ≤ 10⁵

Câu 5 (1,5 điểm): Robot

Một robot cứu hỏa xuất phát tại trạm cứu hỏa A cần đến thị trấn Z (nơi xảy ra hỏa hoạn) để làm nhiệm vụ cứu hỏa. Đường đi của robot là một đường thẳng, khi xuất phát robot cách thị trấn Z một khoảng là L đơn vị độ dài và robot chứa P đơn vị năng lượng; cứ đi mỗi đơn vị khoảng cách robot phải tốn 1 đơn vị năng lượng. Trên con đường từ trạm cứu hỏa A đến thị trấn Z có N trạm cung cấp năng lượng được đánh số từ 1 đến N. Trạm cung cấp năng lượng thứ i cách thị trấn Z một khoảng bằng D_i đơn vị độ dài và có khả năng cung cấp tối đa C_i đơn vị năng lượng.

Robot cần đến thị trấn nhanh nhất để kịp thời cứu hỏa nên cần giảm thiểu tối đa việc dừng lại tại các trạm cung cấp để tiếp thêm năng lượng nếu có thể. Giả thiết rằng robot không có giới hạn về lượng năng lượng nạp thêm tại các trạm cung cấp.

Yêu cầu: Xác định số lượng tối thiểu các trạm cung cấp năng lượng mà robot phải dừng lại tiếp thêm năng lượng để có thể đến được thị trấn Z.

Dữ liệu: Nhập vào từ file văn bản BAI5.INP chứa các dòng dữ liệu sau:

• Dòng đầu tiên chứa số T (T ≤ 5) là số lượng bộ dữ liệu;
• Sau đó là T nhóm dòng, mỗi nhóm là một bộ dữ liệu có dạng:
  • Dòng 1: chứa số nguyên dương N (1 ≤ N ≤ 10⁵) là số trạm cung cấp năng lượng.
  • Trong N dòng tiếp theo, mỗi dòng chứa hai số D_i và C_i (1 ≤ D_i ≤ 10⁶, 1 ≤ C_i ≤ 1000) là khoảng cách từ trạm cung cấp thứ i đến thị trấn Z và khả năng cung cấp năng lượng của trạm ấy. Dữ liệu đảm bảo D₁ > D₂ > ⋯ > D_N.
  • Dòng cuối của nhóm chứa hai số nguyên L và P (D₁ ≤ L ≤ 10⁶, 2 ≤ P ≤ 10⁶) là khoảng cách từ trạm cứu hỏa A đến thị trấn Z và lượng năng lượng của robot lúc xuất phát.
  • Các số trên cùng dòng cách nhau ít nhất một dấu trống (space).

Kết quả: Ghi ra file văn bản BAI5.OUT gồm T dòng, mỗi dòng ghi số lượng tối thiểu các trạm cung cấp năng lượng cần dừng lại để tiếp thêm năng lượng sao cho robot có thể đến được thị trấn Z ứng với mỗi bộ dữ liệu. Với bộ dữ liệu mà robot không thể đến được thị trấn Z thì ghi −1. Thứ tự in kết quả là thứ xuất hiện của bộ dữ liệu trong file BAI5.INP.

Ví dụ:

BAI5.INP	BAI5.OUT
2 3 6 4 4 3 2 6 8 4 1 3 1 5 3	1 -1

Ghi chú: Bài thi được chấm 6 tests, mỗi test đúng 0.25 điểm. Trong đó:

• Có 4 test có 1 ≤ N ≤ 100;
• Có 2 test có 100 < N ≤ 10⁵.

---

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.