Chọn đội tuyển HSG quốc gia Đắk Lắk 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐẮK LẮK ĐỀ CHÍNH THỨC
(Mỗi ngày thi có 03 trang, 03 bài)

KỲ THI LẬP ĐỘI TUYỂN DỰ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT Năm học 2025 - 2026
Môn thi: Tin học - Ngày thi: 17/9/2025 và 18/9/2025
Thời gian làm bài: 180 phút mỗi ngày (không kể thời gian giao đề)

---

Ngày thi thứ nhất (17/9/2025)

Bài	Tệp bài làm	Tệp dữ liệu vào	Tệp dữ liệu ra	Điểm
Bài 1: Số học	Bai1.*	BAI1.INP	BAI1.OUT	6
Bài 2: Tổ hợp tên lửa	Bai2.*	BAI2.INP	BAI2.OUT	7
Bài 3: Tham quan	Bai3.*	BAI3.INP	BAI3.OUT	7

Kí tự ’*’ được thay bằng ‘CPP’ nếu sử dụng ngôn ngữ lập trình C/C++, được thay bằng ‘PY’ nếu sử dụng ngôn ngữ lập trình Python.

Bài 1. Số học (6 điểm)

An là một học sinh giỏi Toán, đặc biệt rất đam mê các bài toán số học. Trong bài tập lần này, thầy giáo giao cho An một bài toán tưởng chừng như rất dễ nhưng lại mang đến cho An một thử thách mới. An nhận được một dãy A gồm N số nguyên a₁, a₂, … a_N. Bài toán đặt ra là với mỗi aᵢ (1 ≤ i ≤ N), hãy tìm số nguyên x (1 ≤ x ≤ aᵢ) có số lượng ước nguyên dương lớn nhất. Nếu có nhiều số x thỏa mãn yêu cầu thì chọn số có giá trị nhỏ nhất. Mặc dù đã giải xong, nhưng An muốn kiểm tra lại kết quả này đã chính xác hay chưa.

Yêu cầu: Là một học sinh giỏi môn Tin học, em hãy lập trình tính kết quả bài toán để giúp An đối chiếu.

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

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 10⁵);
• N dòng tiếp theo, dòng thứ i chứa số nguyên dương aᵢ (aᵢ ≤ 10¹⁸).

Dữ liệu ra: Ghi ra tệp BAI1.OUT gồm N dòng:

• Dòng thứ i ghi hai số nguyên dương, số thứ nhất là số x tìm được ứng với số aᵢ, số thứ hai là số lượng ước nguyên dương của x. Hai số cách nhau một khoảng trắng.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
2 19 200	12 6 180 18	Với a₁ = 19, trong các số từ 1 đến 19, ta tìm được số 12 và 18 đều có số lượng ước nhiều nhất là 6 ước.

Giới hạn:

• Có 25% số test tương ứng 25% số điểm với N ≤ 10², aᵢ ≤ 10³;
• Có 25% số test tương ứng 25% số điểm với N, aᵢ ≤ 10³;
• Có 30% số test tương ứng 30% số điểm với aᵢ ≤ 10⁶;
• Có 20% số test tương ứng 20% số điểm không có giới hạn gì thêm.

Bài 2. Tổ hợp tên lửa (7 điểm)

Một đơn vị quân đội hiện có N tên lửa được đánh số từ 1 đến N, tên lửa thứ i có sức công phá là aᵢ (1 ≤ aᵢ ≤ 10⁹). Nhờ hệ thống tình báo tinh vi, họ đã biết rằng, để tiêu diệt được các mục tiêu của đối phương thì cần phải sử dụng tổ hợp tên lửa có tổng sức công phá không nhỏ hơn P. Vì tên lửa là loại vũ khí công nghệ cao, rất đắt đỏ, nên họ muốn sử dụng nó một cách tối ưu nhất. Để chuẩn bị cho trận chiến, họ cần rà soát lại và đánh giá vai trò của từng tên lửa.

Với tên lửa thứ i, họ xét mọi tổ hợp có chứa nó mà có thể tiêu diệt được mục tiêu. Nếu sau khi bỏ tên lửa thứ i ra khỏi các tổ hợp đó, mà tồn tại một tổ hợp không còn tiêu diệt được mục tiêu thì tên lửa thứ i cần phải được đưa ngay vào thế sẵn sàng chiến đấu. Ngược lại, nếu sau khi bỏ tên lửa thứ i ra, mỗi tổ hợp còn lại vẫn còn đủ sức công phá mục tiêu thì tên lửa thứ i chưa cần đưa vào thế sẵn sàng. Biết rằng, sau khi loại bỏ tên lửa thứ i, tổ hợp còn lại nếu không còn tên lửa nào thì vẫn được tính là một tổ hợp tên lửa có sức công phá bằng 0.

Yêu cầu: Hãy cho biết những tên lửa nào cần được đưa ngay vào thế sẵn sàng chiến đấu.

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

• Dòng đầu tiên chứa hai số nguyên dương N, P (N, P ≤ 5.10³);
• Dòng thứ hai chứa N số nguyên aᵢ (1 ≤ i ≤ N) là sức công phá của các tên lửa.

Dữ liệu ra: Ghi ra tệp BAI2.OUT một dòng duy nhất là số thứ tự của các tên lửa cần đưa ngay vào thế sẵn sàng chiến đấu theo thứ tự từ nhỏ đến lớn, các số cách nhau một khoảng trắng.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
4 9 5 4 2 6	1 2 4	- Các tổ hợp chứa tên lửa thứ nhất mà có thể tiêu diệt mục tiêu là: {5; 4}, {5; 6}, {5; 4; 2}, {5; 4; 6}, {5; 2; 6}, {5; 4; 2; 6}. Tồn tại tổ hợp {5; 4} khi bỏ tên lửa thứ nhất thì sức công phá còn lại là 4 nên không tiêu diệt được mục tiêu, nên cần đưa tên lửa thứ nhất vào thế sẵn sàng chiến đấu. - Các tổ hợp chứa tên lửa thứ ba mà có thể tiêu diệt mục tiêu là: {5; 4; 2}, {5; 2; 6}, {4; 2; 6}, {5; 4; 2; 6}. Khi bỏ tên lửa thứ ba thì các tổ hợp này vẫn tiêu diệt được mục tiêu, nên chưa cần đưa tên lửa thứ ba vào thế sẵn sàng.

Giới hạn:

• Có 20% số test tương ứng 20% số điểm với N ≤ 20;
• Có 40% số test tương ứng 40% số điểm với N, P ≤ 400;
• Có 40% số test tương ứng 40% số điểm không có giới hạn gì thêm.

Bài 3. Tham quan (7 điểm)

Sau sáp nhập, tỉnh mới trở nên rộng lớn hơn với sự kết hợp giữa rừng và biển, các địa điểm tham quan cũng phong phú và đa dạng hơn, có những bãi biển trong xanh thơ mộng và cũng có những khu du lịch sinh thái mang bản sắc của núi rừng Tây Nguyên. Nhân dịp kỷ niệm 80 năm Quốc Khánh, nhà trường tổ chức cho các em học sinh giỏi môn Tin học đi tham quan các địa điểm du lịch đặc trưng của tỉnh nhà. Ban tổ chức chọn được N địa điểm tham quan và đánh số từ 1 đến N. Có N − 1 con đường hai chiều nối trực tiếp các địa điểm với nhau. Con đường thứ i nối hai địa điểm uᵢ và vᵢ (1 ≤ uᵢ, vᵢ ≤ N; uᵢ ≠ vᵢ), các con đường này luôn đảm bảo sự đi lại giữa hai địa điểm tham quan bất kỳ.

Chuyến tham quan diễn ra trong N − 1 ngày, ngày thứ i đoàn tham quan xuất phát từ địa điểm i và kết thúc tại địa điểm i + 1, có thể đi qua các địa điểm trung gian khác sao cho lộ trình di chuyển là ngắn nhất. Mỗi ngày, đoàn tham quan di chuyển qua một địa điểm (tính cả địa điểm xuất phát và địa điểm kết thúc) sẽ được tặng một món quà lưu niệm đặc trưng của địa phương. Hỏi sau khi kết thúc chuyến tham quan, đoàn đã nhận được bao nhiêu món quà của từng địa điểm?

Yêu cầu: Tại mỗi địa điểm, hãy tính số lượng quà mà đoàn tham quan đã nhận được.

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

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 4.10⁵);
• N − 1 dòng tiếp theo, dòng thứ i chứa hai số nguyên dương uᵢ và vᵢ cách nhau một khoảng trắng thể hiện có con đường nối trực tiếp giữa hai điểm uᵢ và vᵢ.

Dữ liệu ra: Ghi ra tệp BAI3.OUT gồm N dòng, dòng thứ i ghi một số nguyên cho biết số lượng quà mà đoàn tham quan đã nhận được tại địa điểm thứ i.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
5 5 4 2 5 1 3 5 1	3 2 2 2 4	Cây: 1 nối 3 và 5; 5 nối 2 và 4. Lộ trình tham quan trong 4 ngày: - Ngày 1: 1 → 5 → 2 - Ngày 2: 2 → 5 → 1 → 3 - Ngày 3: 3 → 1 → 5 → 4 - Ngày 4: 4 → 5

Giới hạn:

• Có 25% số test tương ứng 25% số điểm với N ≤ 10;
• Có 25% số test tương ứng 25% số điểm với N ≤ 10³;
• Có 50% số test tương ứng 50% số điểm không có giới hạn gì thêm.

Ngày thi thứ hai (18/9/2025)

Bài	Tệp bài làm	Tệp dữ liệu vào	Tệp dữ liệu ra	Điểm
Bài 4: Mã kiểm soát	Bai4.*	BAI4.INP	BAI4.OUT	6
Bài 5: Trang sức	Bai5.*	BAI5.INP	BAI5.OUT	7
Bài 6: Nâng cấp thành phố	Bai6.*	BAI6.INP	BAI6.OUT	7

Kí tự ’*’ được thay bằng ‘CPP’ nếu sử dụng ngôn ngữ lập trình C/C++, được thay bằng ‘PY’ nếu sử dụng ngôn ngữ lập trình Python.

Bài 4. Mã kiểm soát (6 điểm)

Giáo sư Việt sau một thời gian dài nghiên cứu đã chế tạo ra được một phiên bản robot mới. Phiên bản robot này tích hợp trí tuệ nhân tạo, có khả năng học hỏi và ngày càng trở nên thông minh hơn. Mặc dù rất tâm huyết với phiên bản robot mới này, nhưng Giáo sư sợ rằng đến một lúc nào đó robot có khả năng thực hiện những hành vi ngoài sự kiểm soát của con người.

Để dự phòng trường hợp xấu nhất xảy ra, Giáo sư bí mật tích hợp một mã kiểm soát vào “bộ não” của robot. Một khi mã này được kích hoạt, robot sẽ dừng hoạt động ngay lập tức. Tuy nhiên nếu mã này bị lộ thì sẽ bị kẻ xấu lợi dụng phá hoại robot. Vì vậy mã này được Giáo sư giấu trong một dãy A gồm có N số nguyên không âm a₁, a₂, …, a_N. Mã kiểm soát là một đoạn con gồm các số liên tiếp và đoạn này xuất hiện nhiều lần nhất trong dãy A, nếu có nhiều đoạn con cùng có số lần xuất hiện nhiều nhất thì mã là đoạn có độ dài lớn nhất, nếu vẫn có nhiều đoạn con thỏa mãn thì mã là đoạn xuất hiện cuối cùng.

Yêu cầu: Cho dãy số nguyên A, hãy tìm vị trí bắt đầu và vị trí kết thúc của mã kiểm soát mà Giáo sư đã giấu vào dãy A.

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

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 10⁵).
• Dòng thứ hai chứa N số nguyên không âm a₁, a₂, …, a_N (aᵢ ≤ 10⁹).

Dữ liệu ra: Ghi ra tệp BAI4.OUT hai số nguyên lần lượt là vị trí bắt đầu và vị trí kết thúc của mã kiểm soát. Hai số cách nhau một khoảng trắng.

Ví dụ:

BAI4.INP	BAI4.OUT
12 3 0 4 1 9 7 5 4 1 9 7 5	8 12

Giới hạn:

• Có 25% số test tương ứng 25% số điểm với N ≤ 200;
• Có 25% số test khác tương ứng 25% số điểm với N ≤ 2000;
• Có 25% số test khác tương ứng 25% số điểm với N ≤ 10⁵, 0 ≤ aᵢ ≤ 1;
• Có 25% số test còn lại tương ứng 25% số điểm với N ≤ 10⁵.

Bài 5. Trang sức (7 điểm)

Nữ hoàng Elizabeth của vương quốc Alpha rất thích sưu tầm các loại trang sức, trong đó nổi bật nhất là bộ sưu tập gồm N viên đá quý, được đánh số từ 1 đến N. Vào bữa tiệc sinh nhật của mình, Nữ hoàng dự định sẽ mang một bộ trang sức thật lộng lẫy gồm có một chiếc vòng cổ và X chiếc nhẫn. Các chiếc nhẫn được đánh số từ 1 đến X. Vì vậy Nữ hoàng đã thuê một thợ kim hoàn chọn X viên đá quý trong số này để đính vào các chiếc nhẫn (mỗi chiếc nhẫn được đính một viên đá quý) và chọn Y viên đá quý để đính vào chiếc vòng cổ. Biết rằng viên đá quý i nếu được đính vào chiếc nhẫn j sẽ có độ lộng lẫy aᵢⱼ, còn nếu được đính vào chiếc vòng cổ sẽ có độ lộng lẫy bᵢ.

Người thợ kim hoàn rất phân vân chưa biết chọn và đính những viên đá quý như thế nào để bộ trang sức Nữ hoàng mang là lộng lẫy nhất vào ngày hôm ấy.

Yêu cầu: Hãy tính độ lộng lẫy tối đa của bộ trang sức được Nữ hoàng mang vào bữa tiệc sinh nhật.

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

• Dòng đầu tiên chứa ba số nguyên dương N, X, Y (2 ≤ N ≤ 10⁵; X ≤ 7; Y, X + Y ≤ N);
• Dòng thứ hai chứa N số nguyên dương b₁, b₂, …, b_N lần lượt là độ lộng lẫy của viên đá quý thứ i nếu được gắn vào chiếc vòng cổ (bᵢ ≤ 10⁹);
• Dòng thứ i trong N dòng tiếp theo chứa X số nguyên dương aᵢⱼ mô tả độ lộng lẫy của viên đá quý i nếu được gắn vào chiếc nhẫn j (1 ≤ i ≤ N; 1 ≤ j ≤ X; aᵢⱼ ≤ 10⁹).

Dữ liệu ra: Ghi ra tệp BAI5.OUT một số nguyên duy nhất là độ lộng lẫy tối đa của bộ trang sức.

Ví dụ:

BAI5.INP	BAI5.OUT	Giải thích
4 1 2 6 3 5 2 3 2 4 3	14	Viên đá thứ tư được đính vào nhẫn, hai viên đá thứ nhất và thứ ba được đính vào vòng cổ. Tổng độ lộng lẫy là: 3 + 6 + 5 = 14

Giới hạn:

• Có 25% số test tương ứng sẽ 25% số điểm với N ≤ 7;
• Có 25% số test tương ứng 25% số điểm với X = 1;
• Có 25% số test tương ứng 25% số điểm với b₁ = b₂ = ⋯ = b_N;
• Có 25% số test tương ứng 25% số điểm không có giới hạn gì thêm.

Bài 6. Nâng cấp thành phố (7 điểm)

Vương quốc Alpha nổi tiếng với hệ thống giao thông thần kỳ. Vương quốc có N thành phố được đánh số từ 1 đến N. Thành phố i được gán một giá trị gọi là năng lượng đặc trưng aᵢ (1 ≤ i ≤ N). Giữa hai thành phố u, v bất kỳ (u ≠ v) đều có một con đường hai chiều nối trực tiếp với chi phí di chuyển là aᵤ × aᵥ.

Nhà vua muốn quản lý và cải tạo hệ thống giao thông này. Ông đã đưa ra danh sách gồm M yêu cầu, thuộc hai loại:

1. Nâng cấp thành phố: Thay đổi năng lượng của thành phố u thành giá trị mới là k.
2. Truy vấn hành trình: Tính toán chi phí nhỏ nhất để đi từ thành phố u đến thành phố v.

Yêu cầu: Hãy thực hiện lần lượt M yêu cầu của nhà vua, khi gặp loại truy vấn hành trình hãy đưa ra chi phí nhỏ nhất để đi từ thành phố u đến thành phố v trong truy vấn đó.

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

• Dòng đầu tiên chứa số nguyên dương N, M (N, M ≤ 10⁵);
• Dòng thứ hai chứa N số tự nhiên a₁, a₂, …, a_N (aᵢ ≤ 10⁶);
• M dòng tiếp theo, mỗi dòng thể hiện một trong hai loại yêu cầu có dạng:
  • 1 u k: Thay đổi năng lượng thành phố u thành giá trị k (0 ≤ k ≤ 10⁶);
  • 2 u v: Tìm chi phí nhỏ nhất để đi từ thành phố u đến thành phố v (1 ≤ u, v ≤ N).

Dữ liệu ra: Ghi ra tệp BAI6.OUT như sau: Với mỗi yêu cầu loại 2 (truy vấn hành trình) ghi ra một số nguyên duy nhất trên một dòng thể hiện chi phí nhỏ nhất để đi từ thành phố u đến thành phố v.

Ví dụ:

BAI6.INP	BAI6.OUT
4 3 2 6 3 4 2 4 1 1 2 1 2 1 4	8 6

Giới hạn:

• Có 25% số test tương ứng 25% số điểm với N, M ≤ 200;
• Có 25% số test khác tương ứng 25% số điểm với N, M ≤ 700;
• Có 25% số test khác tương ứng 25% số điểm với N ≤ 100 và có nhiều nhất 10 truy vấn loại 1;
• Có 25% số test khác tương ứng 25% số điểm không có giới hạn gì thêm.

---

Hết