Đề Thi HSG Tin 11 Sở GD Quảng Nam 2023-2024 Có Đáp Án

TỔNG QUAN ĐỀ THI

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à Free Pascal hoặc C++.

Câu 1. (6,0 điểm) SPORT

Một Sư đoàn A có chiến sĩ, các chiến sĩ có chỉ số thể lực tương ứng theo thứ tự . Để chuẩn bị cho hội thao hàng năm giữa các Sư đoàn với nhau, Sư đoàn A tổ chức một hội thi để chọn ra các đội có kết quả cao nhất để tham gia hội thao. Sau một thời gian huấn luyện về thể lực, Sư đoàn cần chọn ra các đội gồm các chiến sĩ có chỉ số thể lực hoàn hảo để tham gia hội thao.

Chỉ số thể lực hoàn hảo là đội gồm 3 chiến sĩ có vị trí là , độ chênh lệch thể lực giữa 2 chiến sĩ trong đội là sao cho và .

Yêu cầu: Hãy đếm số đội có thể tham gia hội thao của sư đoàn A.

Dữ liệu vào: Đọc từ tệp SPORT.INP

• Dòng đầu tiên là số .
• Dòng tiếp theo ghi số nguyên .

Kết quả ra: Ghi ra tệp SPORT.OUT

• Ghi ra một số duy nhất là số đội nhiều nhất có thể chọn.

Ví dụ:

Giới hạn:

• Subtask 1: 40% test có 1
• Subtask 2: 30% test có
• Subtask 3: 30% test có

Bài 2. (7,0 điểm) GAME

Trong giờ học Toán, thầy giáo của An có ra một trò chơi để tạo không khí vui tươi và đoàn kết các bạn trong lớp. Trò chơi có nội dung như sau: cho dãy gồm số nguyên không âm, nhiệm vụ của các bạn trong lớp là hãy chia dãy thành k + 1 đoạn khác rỗng, để thu được k+1 đoạn, người chơi cần lặp lại các bước sau đây lần:

Bước 1. Chọn một đoạn tuỳ ý với nhiều hơn một phần tử (đầu tiên người chơi chỉ có một đoạn, đó chính là dãy ban đầu).

Bước 2. Chọn một vị trí nào đó ở giữa đoạn đã chọn để chia nó ra làm hai đoạn mới khác rỗng.

Mỗi lần thực hiện xong hai bước này người chơi nhận được một điểm số bằng tích của hai tổng các số trong hai đoạn mới chia ra.

Yêu cầu: Với cách chơi như trên, bạn hãy lập trình giúp An tìm ra cách để đạt được tổng điểm lớn nhất.

Dữ liệu vào: Đọc từ tệp GAME.INP gồm:

- Dòng đầu tiên chứa hai số nguyên dương và

- Dòng thứ hai chứa n số nguyên không âm a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁴, 1 ≤ i ≤ n) là các phần tử của dãy số.

Kết quả ra: Ghi vào tệp GAME.OUT

Một số nguyên duy nhất là tổng điểm lớn nhất mà bạn đạt được.

Ví dụ:

Giải thích ví dụ:

Trong ví dụ bạn có thể giành được 108 điểm theo cách sau:

- Đầu tiên bạn có dãy số (1, 3, 4, 0, 2, 3, 4) gồm 1 đoạn. Bạn chia dãy ra thành hai đoạn sử dụng điểm chia sau phần tử thứ sáu và nhận được: (1 + 3 + 4 + 0 + 2 + 3) × 4 = 52 điểm.

- Bạn đang có hai đoạn (1, 3, 4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ hai và nhận được: (1 + 3) × (4 + 0 + 2 + 3) = 36 điểm.

- Bạn đang có ba đoạn (1, 3), (4, 0, 2, 3), (4). Bạn chia dãy sau phần tử thứ tư và nhận được: (4 + 0) × (2 + 3) = 20 điểm.

Như vậy, sau 3 bước thực hiện nói trên bạn chia dãy số thành 4 đoạn (1, 3), (4, 0), (2, 3), (4) và nhận được: 52 + 36 + 20 = 108 điểm.

Giới hạn:

• Subtask 1: Có 60% số test có n ≤ 300;
• Subtask 2: Có 40% số test có n ≤ 3000.

Bài 3. (7,0 điểm) MEGA

Đất nước Mega được mệnh danh là vùng đất có rất nhiều đảo đẹp và yên bình. Hàng năm có rất nhiều tàu thuyền khắp nơi trên thế giới ghé thăm đất nước Mega để tham quan, du lịch và kinh doanh. Để phát triển kinh tế, giao thương và thu hút đầu tư nước Mega đã kêu gọi sự đầu tư của nhiều công ty lớn trên thế giới đến xây dựng các cảng biển. Đến thời điểm hiện tại đã xây dựng được cảng biển, các cảng này được kết nối với nhau với hệ thống giao thông đường thủy gồm m đường 2 chiều, đảm bảo sự giao thương giữa 2 cảng bất kỳ (trực tiếp hoặc gián tiếp thông qua cảng trung gian). Giữa 2 cảng bất kỳ có không quá một đường đi trực tiếp.

Việc đầu tư, vận hành, bảo trì các cảng này được giao cho 2 công ty lớn là Greek (G) và Yamato (Y) độc quyền đảm nhận. Các tàu thuyền hoạt động trên các cảng này đều thuộc quyền sở hữu của 2 công ty trên thực hiện. Các tàu thuyền khi vận chuyển hàng và người từ cảng này sang cảng khác thì chủ thuyền phải trả chi phí là 1 đơn vị tiền tệ, ngoài ra tàu thuyền khi đi qua cảng mà không phải do công ty mình quản lý thì chủ thuyền phải trả thêm 3 đơn vị tiền tệ. Tất nhiên, khi vận chuyển hàng hóa và người, chủ thuyền bao giờ cũng chọn con đường ứng với tổng chi phí nhỏ nhất.

Yêu cầu: Cho biết 𝑛, 𝑚 và mạng giao thông trong Mega, hãy giúp công ty G và Y tính tổng chi phí vận chuyển hàng giữa tất cả các cảng biển thuộc tập đoàn của họ.

Dữ liệu vào: Đọc từ tệp MEGA.INP có cấu trúc:

• Dòng đầu tiên chứa hai số nguyên 𝑛, 𝑚.
• Dòng thứ hai chứa xâu gồm 𝑛 ký tự, mỗi ký tự là 𝐺 hoặc 𝑌, ký tự thứ 𝑖 cho biết cảng 𝑖 thuộc tập đoàn 𝐺 hay 𝑌.
• Tiếp theo là 𝑚 dòng, mỗi dòng chứa hai số nguyên 𝑖, 𝑗 xác định đường nối cảng 𝑖 với cảng 𝑗.

Kết quả ra: Ghi ra tệp MEGA.OUT có cấu trúc:

• Gồm một dòng chứa hai số tương ứng là tổng chi phí vận chuyển hàng giữa tất cả các cảng thuộc tập đoàn và .

Ví dụ:

Giới hạn:

• Subtask 1: Có 60% số test có
• Subtask 2: Có 40% số test có

------------ 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.

- Họ và tên thí sinh:......................................................; Số báo danh...........................

(Bản hướng dẫn này gồm 02 trang)

TỔNG QUAN VỀ ĐỀ THI

HƯỚNG DẪN CHẤM

Bài thi được chấm bằng phần mềm Themis (theo cấu hình đã cài đặt sẵn)

Bài 1. (6.0 điểm) SPORT: gồm có 40 test; mỗi test 0,15 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Bài 2. (7.0 điểm) GAME: gồm có 35 test, mỗi test 0.2 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Bài 3. (7.0 điểm) MEGA: gồm có 40 test; mỗi test 0,175 điểm, thời gian 1 giây, bộ nhớ 1024 MB

Lưu ý: Trường hợp bài làm thí sinh bằng điểm nhau, Hội đồng chấm thi, Tổ chấm thống nhất điều chỉnh thời gian bài thi của thí sinh để xếp giải.

---------------HẾT---------------