Chọn đội tuyển HSG quốc gia Tuyên Quang 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TUYÊN QUANG ĐỀ CHÍNH THỨC
(Mỗi ngày thi có 03 trang)

ĐỀ 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: 11 và 12 tháng 9 năm 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 (11/9/2025)

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu	Tệp kết quả	Điểm
Bài 1	CALO	CALO.*	CALO.INP	CALO.OUT	7
Bài 2	DÃY CON	DAYCON.*	DAYCON.INP	DAYCON.OUT	7
Bài 3	TẬP ĐỈNH	TAPDINH.*	TAPDINH.INP	TAPDINH.OUT	6

Bài thi được làm trên ngôn ngữ lập trình Pascal, C++ hoặc Python; phần mở rộng .* là PAS, CPP hoặc PY.

Bài 1. CALO

Khi trở về làng của mình sau chiến thắng oanh liệt tại Đại hội võ lâm, Dế Mèn được dân làng nô nức ra chào đón. Không những thế, dân làng còn tiếp đón Dế Mèn bằng một bữa tiệc thịnh soạn.

Trên bàn tiệc có tất cả n món ăn được đánh số từ 1 đến n. Món ăn thứ i có hàm lượng calo aᵢ và độ cay bᵢ.

Yêu cầu: Hãy lập trình giúp Dế Mèn chọn ra các món ăn liên tiếp sao cho tổng calo thu được lớn nhất có thể và không được chọn món ăn nào có độ cay vượt quá k.

Dữ liệu: Vào từ tệp CALO.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên dương n, k (n ≤ 10⁷; k ≤ 10⁹);
• Dòng thứ i trong n dòng sau chứa hai số nguyên dương aᵢ, bᵢ (aᵢ, bᵢ ≤ 10⁹; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp CALO.OUT một số nguyên duy nhất là tổng calo lớn nhất có thể của các món ăn được chọn.

Ví dụ:

CALO.INP	CALO.OUT	Giải thích
6 5 3 6 7 4 4 5 8 7 5 3 3 2	11	Chọn món ăn thứ 2 và thứ 3

Ràng buộc:

• Có 60% số test tương ứng 60% số điểm của bài có n ≤ 10²;
• Có 20% số test tương ứng 20% số điểm của bài có 10² < n ≤ 10³;
• Có 20% số test tương ứng 20% số điểm của bài có 10³ < n ≤ 10⁷.

Bài 2. DÃY CON

Tuyên và Quang chơi một trò chơi liên quan đến dãy số như sau:

Tuyên có k chiếc bút với màu mực khác nhau từ màu 1 đến màu k. Tuyên viết ra giấy một dãy gồm n số nguyên dương a₁, a₂, …, aₙ. Phần tử thứ i được viết bởi chiếc bút có màu mực bᵢ (1 ≤ bᵢ ≤ k; 1 ≤ i ≤ n).

Quang dùng bút xóa đi một số các phần tử của dãy a (cũng có thể không cần phải xóa phần tử nào) sao cho các phần tử còn lại chỉ được viết bằng một màu mực tạo thành một dãy con tăng dần dài nhất.

Yêu cầu: Hãy lập trình giúp Quang giải quyết bài toán trên.

Dữ liệu: Vào từ tệp DAYCON.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên dương n, k (n ≤ 10⁵; k ≤ 10);
• Dòng thứ i trong n dòng sau chứa hai số nguyên dương aᵢ, bᵢ (aᵢ ≤ 10⁹; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp DAYCON.OUT một số nguyên duy nhất là độ dài của dãy con dài nhất tìm được (số lượng phần tử còn lại nhiều nhất).

Ví dụ:

DAYCON.INP	DAYCON.OUT
5 3 3 2 2 1 6 2 7 3 6 2	2

Ràng buộc:

• Có 30% số test tương ứng 30% số điểm của bài có n ≤ 20;
• Có 30% số test tương ứng 30% số điểm của bài có k = 1;
• Có 20% số test tương ứng 20% số điểm của bài có n ≤ 10³;
• Có 20% số test tương ứng 20% số điểm của bài không có thêm ràng buộc gì.

Bài 3. TẬP ĐỈNH

Ta đã biết rằng một đồ thị gồm hai tập: tập cạnh E và tập đỉnh V. Thông thường người ta hay đặt tên các đỉnh của tập V là 1, 2, … nhưng Bờm thì lại không đặt như vậy, cậu ta sử dụng quy luật sau đây để đặt tên cho các đỉnh của đồ thị.

• Ban đầu, tập đỉnh V chỉ có một phần tử là 2 (V = {2});
• Bờm tiếp tục lấy các đỉnh khác theo qui tắc. Nếu i là đỉnh của đồ thị thì 2 * i + 1 và 3 * i cũng là đỉnh của đồ thị. Lưu ý tập đỉnh V mà Bờm xây dựng là vô hạn số đỉnh.

Yêu cầu: Cho K truy vấn, truy vấn thứ i gồm hai số nguyên dương uᵢ và vᵢ. Bạn cần lập trình để trả lời câu hỏi “Có bao nhiêu đỉnh thuộc tập V nằm trong đoạn [uᵢ; vᵢ]?”

Dữ liệu: Vào từ tệp TAPDINH.INP có cấu trúc như sau:

• Dòng 1: Chứa một số nguyên dương K (K ≤ 10⁶);
• Dòng thứ i trong K dòng sau, mỗi dòng chứa hai số nguyên dương uᵢ, vᵢ (uᵢ ≤ vᵢ ≤ 10⁷).

Kết quả: Ghi ra tệp TAPDINH.OUT gồm K dòng, dòng thứ i gồm một số nguyên là số lượng đỉnh cần tìm của truy vấn thứ i (1 ≤ i ≤ K).

Ví dụ:

TAPDINH.INP	TAPDINH.OUT	Giải thích
2 1 6 2 20	3 7	Ta có: V = {2; 5; 6; 11; 13; 15; 18; 23; ...}

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài có K = 1; u₁ = v₁;
• Có 30% số test tương ứng với 30% số điểm của bài có K = 1;
• Có 40% số test tương ứng với 40% số điểm còn lại không có thêm ràng buộc gì.

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

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu	Tệp kết quả	Điểm
Bài 4	SONG CA	SONGCA.*	SONGCA.INP	SONGCA.OUT	7
Bài 5	MUA KẸO	MUAKEO.*	MUAKEO.INP	MUAKEO.OUT	7
Bài 6	KHÁM PHÁ VŨ TRỤ	VUTRU.*	VUTRU.INP	VUTRU.OUT	6

Bài thi được làm trên ngôn ngữ lập trình Pascal, C++ hoặc Python; phần mở rộng .* là PAS, CPP hoặc PY.

Bài 4. SONG CA

Để chuẩn bị cho tiết mục hát song ca tại lễ khai mạc Thế vận hội lần này có tất cả n ca sĩ đã ghi âm giọng hát của mình và gửi cho ban tổ chức. Qua thiết bị đo, giọng hát của ca sĩ thứ i có độ cao là một số nguyên dương aᵢ.

Ban tổ chức muốn chọn ra 2 ca sĩ có độ cao của giọng hát bằng nhau để thể hiện tiết mục song ca nói trên.

Yêu cầu: Hãy lập trình cho biết có bao nhiêu cách chọn khác nhau.

Dữ liệu: Vào từ tệp SONGCA.INP có cấu trúc như sau:

• Dòng 1: Chứa một số nguyên dương n (2 ≤ n ≤ 10⁶).
• Dòng 2: Chứa n số nguyên dương a₁, a₂, …, aₙ (aᵢ ≤ 10⁹; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp SONGCA.OUT một số nguyên dương duy nhất là số cách chọn tìm được.

Ví dụ:

SONGCA.INP	SONGCA.OUT	Giải thích
6 2 7 7 3 7 2	4	Cách 1: Chọn ca sĩ thứ 1, 6 Cách 2: Chọn ca sĩ thứ 2, 3 Cách 3: Chọn ca sĩ thứ 2, 5 Cách 4: Chọn ca sĩ thứ 3, 5

Ràng buộc:

• Có 60% số test tương ứng 60% số điểm của bài có n ≤ 10³;
• Có 20% số test tương ứng 20% số điểm của bài có n ≤ 10⁶; aᵢ ≤ 10⁶; 1 ≤ i ≤ n;
• Có 20% số test tương ứng 20% số điểm của bài không có thêm ràng buộc gì.

Bài 5. MUA KẸO

Để chuẩn bị cho chuyến đi ôn thi học sinh giỏi quốc gia dài ngày sắp tới, Cuội được mẹ cho đi siêu thị để mua kẹo (thói quen của Cuội là khi suy nghĩ làm bài tập thường hay ăn kẹo).

Trong siêu thị có n loại kẹo, được đánh số từ 1 đến n. Các loại kẹo được bày bán từ trái sang phải, thông thường các loại kẹo có hương vị giống nhau sẽ được để gần nhau. Vì vậy, Cuội quyết định nếu chọn mua loại kẹo thứ i thì nhất định sẽ không mua lᵢ loại kẹo ở ngay bên trái và rᵢ loại kẹo ở ngay bên phải của loại kẹo thứ i. Trong trường hợp có ít hơn lᵢ loại kẹo ở bên trái hoặc ít hơn rᵢ loại kẹo ở bên phải của loại kẹo i thì tất cả các loại kẹo ở phía đó vẫn không được mua nếu Cuội chọn mua loại kẹo thứ i.

Yêu cầu: Hãy lập trình cho biết Cuội có thể chọn tối đa bao nhiêu loại kẹo để mua.

Dữ liệu: Vào từ tệp MUAKEO.INP có cấu trúc như sau:

• Dòng 1: Chứa số nguyên n là số lượng loại kẹo bán trong siêu thị (1 ≤ n ≤ 2.10⁵);
• Dòng thứ i trong n dòng sau, mỗi dòng chứa hai số nguyên lᵢ và rᵢ (0 ≤ lᵢ, rᵢ ≤ n; ∀i = 1..n).

Kết quả: Ghi ra tệp MUAKEO.OUT một số nguyên duy nhất là số lượng kẹo tối đa mà Cuội có thể chọn để mua.

Ví dụ:

MUAKEO.INP	MUAKEO.OUT	Giải thích
3 0 2 1 0 1 0	1	Chọn được nhiều nhất một loại kẹo: loại 1 hoặc loại 2 hoặc loại 3
5 1 2 1 0 0 1 2 1 1 0	3	Chọn được nhiều nhất ba loại kẹo gồm các loại: 2, 3, 5

Ràng buộc:

• Có 20% số test tương ứng 20% số điểm của bài có rᵢ = 0; 1 ≤ i ≤ n;
• Có 30% số test tương ứng 30% số điểm của bài có n ≤ 10³;
• Có 20% số test tương ứng 20% số điểm của bài có lᵢ, rᵢ ≤ 2; 1 ≤ i ≤ n;
• Có 30% số test tương ứng 30% số điểm của bài không có thêm ràng buộc gì.

Bài 6. KHÁM PHÁ VŨ TRỤ

Tí và Tèo là hai phi hành gia của trung tâm vũ trụ Quốc Tế. Họ đang tham gia một sứ mệnh quan trọng: khám phá các hành tinh xa xôi để thu thập năng lượng phục vụ cho Trái đất.

Có n hành tinh được đánh số từ 1 đến n mà Tí và Tèo có thể hạ cánh. Khi khám phá hành tinh thứ i, họ sẽ thu được xᵢ đơn vị năng lượng nếu xᵢ > 0 hoặc sẽ mất đi xᵢ đơn vị năng lượng nếu xᵢ < 0 do điều kiện khắc nghiệt.

Tuy nhiên, không phải hành tinh nào cũng có thể đến ngay lập tức. Một số hành tinh chỉ có thể hạ cánh sau khi đã khám phá xong một hành tinh khác. Cụ thể, với mỗi hành tinh thứ i có tham số pᵢ (0 ≤ pᵢ < i), nếu pᵢ = 0 thì có thể khám phá hành tinh i bất kỳ lúc nào mà không phụ thuộc vào hành tinh khác, ngược lại nếu pᵢ ≠ 0 thì muốn đến hành tinh i, họ phải đến hành tinh pᵢ trước.

Ban đầu, con tàu vũ trụ của Tí và Tèo có s đơn vị năng lượng. Trong suốt hành trình, năng lượng trên tàu không bao giờ được âm. Mục tiêu của họ là khám phá một số hành tinh sao cho tổng lượng năng lượng thu được là lớn nhất có thể.

Yêu cầu: Hãy lập trình giúp Tí và Tèo tính toán lượng năng lượng tối đa mà họ có thể thu được sau chuyến khám phá các hành tinh.

Dữ liệu: Vào từ tệp VUTRU.INP có cấu trúc như sau:

• Dòng 1: Chứa hai số nguyên n, s (1 ≤ n ≤ 3 × 10⁵; 0 ≤ s ≤ 10⁹);
• Dòng thứ i trong n dòng sau mỗi dòng gồm hai số nguyên xᵢ, pᵢ (|xᵢ| ≤ 10⁹; 0 ≤ pᵢ < i; i = 1, 2, …, n).

Kết quả: Ghi ra tệp VUTRU.OUT một số nguyên duy nhất là năng lượng tối đa có thể thu được.

Ví dụ:

VUTRU.INP	VUTRU.OUT	Giải thích
6 1 3 0 -3 1 -5 0 2 1 6 3 -4 5	6	+ Khám phá hành tinh 1: năng lượng từ 1 → 4 + Khám phá hành tinh 4 (phụ thuộc hành tinh 1): năng lượng từ 4 → 6 + Khám phá hành tinh 3: năng lượng từ 6 → 1 + Khám phá hành tinh 5 (phụ thuộc hành tinh 3): năng lượng từ 1 → 7 Do đó: Tổng năng lượng thu được: 7 − 1 = 6.

Ràng buộc:

• Có 13% số test tương ứng 13% số điểm của bài có s = 10⁹;
• Có 14% số test tương ứng 14% số điểm của bài có n ≤ 2000; pᵢ = 0 hoặc pᵢ = i − 1; i = 1..n;
• Có 16% số test tương ứng 16% số điểm của bài có pᵢ = 0 hoặc pᵢ = i − 1; i = 1..n;
• Có 26% số test tương ứng 26% số điểm của bài có n ≤ 2000;
• Có 31% số test tương ứng 31% số điểm của bài không có thêm ràng buộc gì.

---

Hết