Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án)

 Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
Ta cần nhận xét việc thay đổi một cạnh trên cây sẽ làm thay đổi chi phí của đỉnh khác nhưng 
những đỉnh bị thay đổi chi phí không ảnh hưởng tới thứ hạng của hai đỉnh truy vấn do chi 
phí của các con đường là dương. Sử dụng kỹ thuật xử lý offline như trên, ta có độ phức tạp 
chung của thuật toán là O(Q × logN).
- Subtask 5: 20% số test còn lại ứng với 20% số điểm: 1 ≤ N, M, P ≤ 105.
Ta cần nhận xét việc thay đổi một cạnh đồ thị tổng quát cũng có tính chất tương tự như 
trường hợp cây. Sử dụng kỹ thuật xử lý offline như trên, ta có độ phức tạp chung của thuật 
toán là O(Q x logN).
Câu 3: Thu mua nông sản (6,0 điểm)
- Subtask 1: Có 7,5% số test ứng với 7,5% số điểm thỏa mãn: ≤ 30 và 푄 ≤ 800. Mô 
phỏng lại toàn bộ các xe vận tải bằng kỹ thuật DFS.
Độ phức tạp là (푄 × 3).
- Subtask 2: 12,5% số test khác ứng với 12,5% số điểm thỏa mãn: ≤ 100 và 푄 ≤ 800.
Thí sinh tính tổng chi phí bằng cách thực hiện 푛 lần DFS từ 푛 ngôi làng. Để tính chi phí cho 
cặp ( ,푣) ta DFS từ đỉnh rồi tính chi phí cặp ( ,푣) dựa trên cặp ( , 푣) với 푣 là cha của 
trong (1).
Độ phức tạp là (푄 × 2).
- Subtask 3: 10% số test khác ứng với 10% số điểm thỏa mãn: ≤ 2000 và 푄 ≤ 800.
Với năm thứ 푗 trong 푄 năm tiếp theo, cần tính chênh lệch chi phí giữa năm thứ 푗 và năm thứ 
푗 ―1. Để làm điều này, xét các ngôi làng cùng loại nông sản với ngôi làng thứ 푗 rồi sử dụng 
kỹ thuật tìm tổ tiên chung gần nhất (LCA).
Độ phức tạp là (푄 × × log ).
- Subtask 4: 15% số test khác ứng với 15% số điểm thỏa mãn: ≤ 5000 và 푄 ≤ 8000.
Thí sinh chuẩn bị trước mảng cnt [ ][푣] là số cặp đỉnh ( , ) sao cho đường đi giữa và 
chứa cả hai đỉnh và 푣. Sau đó phần tính tổng chi phí thí sinh thực hiện như Subtask 3.
Độ phức tạp là (푄 × + 2).
- Subtask 5: 17,5% số test khác ứng với 17,5% số điểm thỏa mãn: Với mọi 2 ≤ 푖 ≤ , luôn 
 푖
tồn tại một con đường nối ngôi làng thứ 푖 và ngôi làng thứ .
 2
Nhận thấy rằng, đường đi giữa hai ngôi làng bất kỳ có không quá log +1 con đường. Do 
đó, thí sinh có thể tính chênh lệch chi phí giữa năm thứ 푗 và năm thứ 푗 ―1 bằng cách duyệt 
qua mọi tổ tiên của ngôi làng 푗, sau đó dùng cấu trúc dữ liệu cây nhị phân chỉ số (BIT).
Độ phức tạp là 푄 × log2 .
- Subtask 6: 22,5% số test khác ứng với 22,5% số điểm thỏa mãn: Với mọi 2 ≤ 푖 ≤ , luôn 
tồn tại một con đường nối ngôi làng thứ 푖 và ngôi làng thứ 푖 ―1.
Nhận thấy rằng, với hai ngôi làng 푖 và 푗 bất kỳ (1 ≤ 푖 ≤ 푗 ≤ 푛), số cặp ngôi làng ( , ) sao 
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
cho đường đi từ tới chứa cả hai đỉnh 푖 và 푗 là 푖 × (푛 ― 푗 +1). Lợi dụng điều này, ta có 
thể tính chênh lệch chi phí giữa năm thứ 푗 và năm thứ 푗 ―1 bằng cấu trúc dữ liệu cây phân 
đoạn (IT).
Độ phức tạp là (푄 × log ).
- Subtask 7: 15% số test còn lại ứng với 15% số điểm thỏa mãn: 
1 ≤ 퐾 ≤ 20;1 ≤ ,푄 ≤ 2 × 105. Sử dụng ý tưởng tương tự như các Subtask 3-6 nhưng phải 
kết hợp với kỹ thuật phân cạnh nặng nhẹ (Heavy-Light Decomposition).
Độ phức tạp là 푄 × log2 .
Lời giải chi tiết:
Mạng lưới giao thông có cấu trúc dạng cây, trong đó mỗi ngôi là là một đỉnh. Sau đây ta sẽ 
gọi "đỉnh" thay cho "ngôi làng".
 2 푊
Ta có 푊 = 푊 +2 × 2 với mọi số nguyên dương 푊. Do đó, chi phí vận tải của xe tải đi 
từ đỉnh tới đỉnh 푣 có thể hiểu như sau: Xét các đỉnh trên đường đi từ đỉnh tới đỉnh 푣:
- Mỗi đỉnh sản xuất loại nông sản thứ 푖 làm chi phí vận tải tăng thêm 푖.
- Mỗi cặp đỉnh ( , ) cùng sản xuất loại nông sản thứ 푖 làm chi phí vận tải tăng thêm 푖.
Ta ký hiệu:
+ 퐹1( ) là số cặp đỉnh ( , ) sao cho đường đi từ đến chứa đỉnh .
+ 퐹2( ,푣) là số cặp đỉnh ( , ) sao cho đường đi từ đến chứa cả hai đỉnh và 푣.
 ×( 1)
Khi đó, tổng chi phí của tất cả xe tải có thể hiểu như sau:
 2
- Mỗi đỉnh sản xuất loại nông sản thứ 푖 làm chi phí vận tải tăng thêm 푖 × 퐹1( ).
- Mỗi cặp đỉnh ( , ) cùng sản xuất loại nông sản thứ 푖 làm chi phí vận tải tăng thêm 푖 × 
퐹2( , ).
Ta tính giá trị 퐹1( ) với mọi đỉnh bằng phương pháp quy hoạch động trên cây. Coi đỉnh 1 
là gốc cây, gọi 푆( ) là số đỉnh trong cây con gốc ; giá trị 퐹2( ,푣) được xác định như sau:
- Nếu là tổ tiên của 푣, gọi là con trực tiếp của sao cho 푣 thuộc cây con gốc , khi đó 
퐹2( ,푣) = 푆(푣) × ( ― 푆( )).
- Nếu 푣 là tổ tiên của , ta làm tương tự như trên.
- Nếu và 푣 không có đỉnh nào là tổ tiên của đỉnh còn lại, 퐹2( ,푣) = 푆( ) × 푆(푣).
Tới đây, việc tính lại tổng chi phí khi một đỉnh 푗 chuyển loại nông sản từ sang ′, ta chia 
làm hai quá trình độc lập:
- Tổng chi phí giảm đi do mất đi đỉnh 푗 sản xuất nông sản loại .
- Tổng chi phí tăng lên do có thêm đỉnh 푗 sản xuất nông sản loại ′.
Việc tính lượng chi phí tăng lên hay giảm đi hoàn toàn như nhau, ta quy về bài toán sau: Cho 
đỉnh và loại 푖, tính tổng 퐹2( ,푣) với mọi đỉnh 푣 sản xuất loại nông sản 푖. Với mỗi loại 
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
nông sản, ta dùng một cây nhị phân chỉ số quản lý các đỉnh có loại nông sản này. Khi đó, bài 
toán trên có thể được giải bằng kỹ thuật Heavy-Light Decomposition.
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
 ĐỀ SỐ 4
 BỘ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI QUỐC GIA 
 THPT - NĂM HỌC 2023-2024
 ĐỀ CHÍNH THỨC Môn: TIN HỌC
 Thời gian: 180 phút (Không kể thời gian giao đề)
 TỔNG QUAN ĐỀ THI
 Tiêu đề File chương trình File dữ liệu File kết quả
Câu 4 Ba đường truyền điện WPRO.* WPRO.INP WPRO.OUT
Câu 5 Cải thiện đánh giá NETW.* NETW.INP NETW.OUT
Câu 6 Thu mua nông sản NOEL.* NOEL.INP NOEL.OUT
Dấu * được thay thế bởi PAS hoặc CPP tương ứng với ngôn ngữ lập trình Pascal hoặc 
C++.
Hãy lập trình giải các câu sau:
Câu 4: Sản xuất gỗ (7,0 điểm)
WoodPro là một nhà máy nổi tiếng chuyên sản xuất các sản phẩm về gỗ. Do nhu cầu thị 
trường ngày càng cao, nhà máy quyết định nhập khẩu một dây chuyền thông minh sản xuất 
ra hàng loạt những thanh gỗ. Mỗi một lượt sản xuất, dây chuyền sẽ nhận vào N thanh gỗ 
dạng hình trụ có cùng kích thước đáy. Các thanh gỗ được đánh số từ 1 đến N, thanh gỗ thứ 푖 
có độ dài 푖 xăng-ti-mét. Thứ tự các thanh gỗ đưa vào dây chuyền là 1,2, , . Khi dây 
chuyền bắt đầu hoạt động, các thanh gỗ được xếp nối đuôi nhau trên một băng chuyền, theo 
đúng thứ tự nhận vào. Băng chuyền này sẽ di chuyển các thanh gỗ đi theo một chiều qua hai 
công đoạn xử lý, trước tiên là công đoạn cắt rồi đến công đọan dán, mà vẫn giữ nguyên thứ 
tự của các thanh gỗ trên băng chuyền.
- Ở công đoạn cắt, có một lưỡi cắt được đặt cố định phía trên băng chuyền. Mỗi khi có thanh 
gỗ di chuyển qua, hệ thống có thể điểu khiển lưỡi cắt hạ xuống để cắt thanh gỗ thành hai 
thanh có tổng độ dài bằng độ dài của thanh gỗ trước khi cắt. Sau khi cắt, vị trí của hai thanh 
gỗ trên băng chuyền vẫn được giữ nguyên. Chi phí cho mỗi lần cắt như vậy là C.
- Ở công đoạn dán, có một máy dán được đặt cố định phía trên băng chuyền. Mỗi khi có hai 
thanh gỗ kề nhau di chuyển qua, hệ thống có thể điểu khiển máy dán hạ xuống để dán hai 
thanh gỗ này thành một thanh gỗ có độ dài bằng tổng độ dài của hai thanh gỗ trước khi dán. 
Sau khi dán, vị trí của thanh gỗ trên băng chuyền vẫn được giữ nguyên. Chi phí cho mỗi lần 
dán như vậy là D.
Tuấn là một lập trình viên của nhà máy đảm nhận nhiệm vụ lập trình cho hệ thống đối với 
yêu cầu của mỗi đơn hàng. Do mới nhận được một đơn hàng yêu cầu các thanh gỗ thành 
phẩm chỉ gồm loại độ dài L1 xăng-ti-mét hoặc loại độ dài L2 xăng-ti-mét, nhà máy giao cho 
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
Tuấn lập trình cho hệ thống để sản xuất ra các thanh gỗ thành phẩm như vậy từ N thanh gỗ 
đầu vào mà không để thừa thanh gỗ nào có độ dài khác L1 và L2.
Yêu cầu: Biết rằng luôn tồn tại một phương án sản xuất ra các thanh gỗ thành phẩm độ dài 
퐿1 và 퐿2 từ thanh gỗ đầu vào mà không thừa ra thanh gỗ nào có độ dài khác 퐿1 và 퐿2, hãy 
tính tổng chi phí ít nhất có thể dùng cho việc cắt và dán, để dây chuyền sản xuất có thể hoàn 
thành được đơn hàng.
Dữ liệu
Vào từ file văn bản WPRO.INP:
- Dòng đầu chứa năm số nguyên ,퐿1,퐿2, và lần lượt là số lượng thanh gỗ, hai loại độ dài 
các thanh gỗ thành phẩm đầu ra, chi phí cho một lần cắt và chi phí cho một lần dán 
 4 9 5
(1 ≤ ≤ 10 ;1 ≤ 퐿1,퐿2 ≤ 10 ;1 ≤ , ≤ 10 ).
- Dòng thứ hai chứa số nguyên 1, 2, , là độ dài của thanh gỗ đầu vào 
 9
(1 ≤ 푖 ≤ 10 ,∀푖 = 1,2, , ).
Dữ liệu bảo đảm luôn có phương án giải quyết theo yêu cầu đề bài.
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bản WPRO. OUT một số nguyên là tổng chi phí dùng cho việc cắt và dán tìm 
được.
Ví dụ
WPRD.INP WPRO.OUT Giải thích
3 2 5 10 4 38 - Một phương án tối ưu là dây chuyền thực hiện 3 lần cắt và 
6 5 6 thực hiện 2 lần dán như trong hình vẽ minh hoạ ở dưới.
 - Tổng chi phí là 10 + 10 + 10 + 4 + 4 = 38.
3 1 1 2 3 18 Phương án tối ưu là dây chuyền thực hiện 9 lần cắt.
3 4 5
3 12 13 2 3 6 Phương án tối ưu là dây chuyền thực hiện 2 lần dán.
3 4 5
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
Ràng buộc:
(1) Có 16% số test ứng với 16% số điểm thỏa mãn: 퐿1 = 퐿2.
(2) 16% số test khác ứng với 16% số điểm thỏa mãn: ∑푖=1  푖 ≤ 20.
(3) 16% số test khác ứng với 16% số điểm thỏa mãn: ,퐿1,퐿2 ≤ 100 và 
 푖 ≤ 100,∀푖 = 1,2, , .
(4) 16% số test khác ứng với 16% số điểm thỏa mãn: 푖 ≤ 2024,∀푖 = 1,2, , .
(5) 12% số test khác ứng với 12% số điểm thỏa mãn: 퐿1,퐿2 ≤ 2024.
(6) 12% số test khác ứng với 12% số điểm thỏa mãn: 퐿1 ≤ 2024.
(7) 12% số test còn lại ứng với 12% số điểm: Không có ràng buộc gì thêm.
Câu 5: Mạng truyền tin (7,0 điểm)
Một mạng truyền tin có máy tính, các máy tính được đánh số từ 1 đến . Có ―1 dây 
cáp, được đánh số từ 1 đến ―1. Dây cáp thứ 푖 nối máy tính 푖 với máy tính 푣푖 và có giới 
hạn truyền tải 푤푖. Các dây cáp bảo đảm từ một máy tính bất kì có thể truyền tin đến tất cả 
các máy tính còn lại theo dây cáp trực tiếp giữa chúng hoặc thông qua đường truyền tin đi 
qua một số máy tính và dây cáp nào đó. Khi hai máy tính truyền tin cho nhau, chúng sẽ luôn 
sử dụng đường truyền tin sao cho không sử dụng dây cáp nào quá một lần. Độ lớn của gói tin 
truyền đi phải không lớn hơn giới hạn truyền tải của mọi dây cáp mà nó sử dụng. Chi phí để 
truyền một gói tin giữa hai máy tính bằng kích thước của gói tin nhân với bình phương số 
lượng dây cáp trên đường truyền tin.
Người ta muốn chọn ra một máy tính để làm máy chủ. Khi đó, máy tính sẽ truyền tin đến 
tất cả các máy tính khác. Vì phải dự trù cho mọi trường hợp, ta cần phải xét chi phí truyền 
 2
tin tối đa. Chi phí truyền tin tối đa giữa máy tính và máy tính là min( , ) × ( ( , )) 
với min( , ) là giới hạn truyền tải nhỏ nhất trong số các giới hạn truyền tải của các dây cáp 
trên đường truyền tin giữa máy tính và máy tính , ( , ) là số dây cáp trên đường truyền 
tin giữa máy tính và máy tính . Chi phí vận hành mạng là tổng của chi phí truyền tin tối 
đa giữa máy tính và tất cả các máy tính khác.
Yêu cầu: Với mỗi = 1,2, , , hãy tính chi phí vận hành mạng nếu chọn máy tính làm 
máy chủ.
Dữ liệu
Vào từ file văn bản NETW.INP:
- Dòng đầu chứa một số nguyên là số lượng máy tính (1 ≤ ≤ 105).
- Dòng thứ 푖 trong số ―1 dòng tiếp theo chứa ba số nguyên 푖,푣푖 và 푤푖 cho biết có một dây 
cáp nối máy tính 푖 với máy tính 푣푖 và có giới hạn truyền tải là 푤푖(1 ≤ 푖,푣푖 ≤ ; 
 9
1 ≤ 푤푖 ≤ 10 ).
Các số trên cùng một dòng cách nhau bởi dấu cách.
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
Kết quả
Ghi ra file văn bản NETW.OUT:
- Gồm dòng, trong đó dòng thứ chứa một số nguyên là phần dư của chi phí vận hành 
mạng nếu chọn máy tính làm máy chủ trong phép chia cho 998244353.
Ví dụ
 NETW.INP NETW.OUT Minh hoạ mạng truyền tin
7 44
1 2 3 26
1 3 2 85
2 4 2 35
2 6 1 43
4 5 1 36
4 7 2 73
Giải thích
Chi phí truyền tin tối đa giữa tất cả các cặp máy tính được cho trong bảng sau:
 ∖ 1 2 3 4 5 6 7 Tổng
 1 - 3 2 8 9 4 18 44
 2 3 - 8 2 4 1 8 26
 3 2 8 - 18 16 9 32 85
 4 8 2 18 - 1 4 2 35
 5 9 4 16 1 - 9 4 43
 6 4 1 9 4 9 - 9 36
 7 18 8 32 2 4 9 - 73
Có 4 dây cáp trên đường truyền tin giữa máy tính 3 và máy tính 7 với giới hạn truyền tải là 
 2
2,3,2,2 vì vậy min(3,7) = 2 và (3,7) = 4. Chi phí truyền tin tối đa giữa 3 và 7 là 2 x 4 = 
32, do đó số ở vị trí tương ứng với r = 3 và x = 7 trong bảng trên là 32.
Chi phí vận hành nếu chọn máy tính 4 làm máy chủ là 8 + 2 + 18 + 1 + 4 + 2 = 35, do đó số 
ở cột cuối cùng ứng với r = 4 trong bảng trên là 35.
Ràng buộc
(1) Có 16% số test ứng với 16% số điểm thỏa mãn: ≤ 5000.
(2) 12% số test khác ứng với 12% số điểm thỏa mãn: 푤푖 ≤ 2 và luôn có dây cáp nối giữa 
máy tính 푖 và máy tính 푖 +1,∀푖 = 1,2, , ―1.
(3) 20% số test khác ứng với 20% số điểm thỏa mãn: 푤푖 = 1,∀푖 = 1,2, , ―1.
(4) 16% số test khác ứng với 16% số điểm thỏa mãn: 푤푖 ≤ 1000,∀푖 = 1,2, , ―1.
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
(5) 16% số test khác ứng với 16% số điểm thỏa mãn: Luôn có dây cáp nối giữa máy tính 푖 và 
máy tính 푖 +1,∀푖 = 1,2, , ―1.
(6) 20% số test còn lại ứng với 20% số điểm: Không có ràng buộc gì thêm.
Cô Tuyết chuẩn bị một bài tập đặc biệt dành cho các bạn trong đội tuyển học sinh giỏi vào 
giáng sinh năm nay. Đó là một bài tập về thứ tự từ điển với đề bài như sau.
Cho một dãy số khác rỗng = [ 1, 2, , ] thỏa mãn 푖 ≠ 푖―1,∀푖 = 2,3, , . Ta gọi một 
cách phân đoạn dãy là một cách chia dãy thành các đoạn con chứa các phần tử liên tiếp, mà 
mỗi phần tử đều thuộc đúng một đoạn con. Một cách phân đoạn dãy được coi là hợp lệ nếu 
mỗi đoạn con chỉ chứa các phần tử đôi một phân biệt.
Ví dụ, với = 10 và dãy = [1,2,4,3,2,1,2,8,6,8], thì một cách phân đoạn dãy hợp lệ là 
chia dãy thành 4 đoạn con lần lượt là [1,2,4,3],[2,1],[2,8],[6,8].
Một cách phân đoạn hợp lệ khác là chia dãy thành 5 đoạn con lần lượt là 
[1,2,4],[3,2,1],[2,8], [6], [8].
Cả hai cách phân đoạn dãy trên đều thỏa mãn mọi đoạn con chỉ chứa các phần tử đôi một 
phân biệt. Mặt khác, nếu ta chia dãy thành 4 đoạn con lần lượt là [1,2,4,3],[2,1],[2],[8,6,8] 
thì sẽ không hợp lệ bởi có hai phần tử cùng bằng 8 trong đoạn con cuối cùng. Tương tự, nếu 
ta chia dãy thành 5 doạn con lần lượt là [1],[2,4,3,2,1,2],[8],[6],[8] thì cũng không hợp lệ 
bởi có ba phần tử cùng bằng 2 trong đoạn con thứ hai.
Mỗi dãy có thể có nhiều cách phân đoạn dãy hợp lệ. Mỗi cách phân đoạn dãy được mã hóa 
bằng một dãy mã hóa phân đọan = [ 1, 2, , 퐾], với 퐾 là số lượng đoạn con, và 푖 là số 
lượng phần tử của đoạn con thứ 푖. Chẳng hạn, với = 10 và dãy = [1,2,4,3,2,1,2,8,6,8], 
thì cách phân đoạn dãy trong hình đầu tiên sẽ được mã hóa bằng dãy = [4,2,2,2].
Tương tự, cách phân đoạn dãy trong hình thứ hai sẽ được mã hóa thành dãy = [3,3,2,1,1].
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
Cô Tuyết viết lên bảng một dãy số khác rỗng = [ 1, 2, , ] thoả mãn 푖 ≠ 푖―1, 
∀푖 = 2,3, , , rồi lại viết lên bảng thêm 2 số nguyên dương và 푌. Sau đó cô gọi một bạn 
lên bảng để trả lời câu hỏi sau:
"Khi liệt kê tất cả các dãy mã hoá phân đoạn của dãy rồi sắp xếp chúng theo thứ tự từ điển 
ngược thì dãy mã hoá phân đoạn thứ và dãy mã hoá phân đoạn thứ 푌 có độ dài tiền tố 
chung dài nhất là bao nhiêu?"
Nhắc lại: Một dãy mã hoá phân đoạn 푈 = [푈1,푈2, ,푈퐾] gọi là đi trước dãy mã hoá phân 
đoạn = [ 1, 2, , ] theo thứ tự từ điển ngược nếu thoả mãn một trong hai điều kiện sau:
 • 퐾 > và 푈푖 = 푖,∀푖 = 1,2, , ;
 • Tồn tại 1 ≤ ≤ min(퐾, ) sao cho 푈푖 = 푖,∀푖 = 1,2, , ―1 và 푈 > .
Dãy số 푈 = [푈1,푈2, ,푈퐾] được gọi là tiền tố độ dài 퐾 của dãy = [ 1, 2, , ] khi và chỉ 
khi 퐾 ≤ và 푈푖 = 푖,∀푖 = 1,2, ,퐾. Lưu ý, dãy rỗng (ký hiệu là []) là tiền tố độ dài 0 của 
mọi dãy số.
Tiền tố chung dài nhất của hai dãy số 푍1 và 푍2 là dãy số có độ dài lớn nhất vừa là tiền tố của 
dãy 푍1 vừa là tiền tố của dãy 푍2.
Nhận thấy rằng nếu chỉ đặt ra câu hỏi cho một cặp số ( ,푌) thì bài toán chưa đủ khó, cô 
Tuyết quyết định thêm vào một vài tham số mới. Cô gọi 푄 bạn lần lượt lên bảng, bạn thứ 푖 sẽ 
nhận được 4 số 퐿푖,푅푖, 푖,푌푖 và có nhiệm vụ trả lời câu hỏi sau:
 ′
"Khi liệt kê tất cả các dãy mã hoá phân đoạn của dãy = [ 퐿푖, 퐿푖+1, , 푅푖] rồi sắp xếp 
chúng theo thứ tự từ điển ngược thì dãy mã hoá phân đoạn thứ 푖 và dãy mã hoá phân đoạn 
thứ 푌푖 có độ dài tiền tố chung dài nhất là bao nhiêu?"
Yêu cầu: Hãy giúp các bạn trả lời 푄 câu hỏi của cô Tuyết.
Dữ liệu
Vào từ file văn bản NOEL.INP:
- Dòng đầu chứa hai số nguyên và 푄 lần lượt là độ dài của dãy và số lượng bạn được cô 
Tuyết gọi lên bảng (1 ≤ ,푄 ≤ 2 × 105).
- Dòng thứ hai chứa số nguyên 1, 2, , (1 ≤ 푖 ≤ ,∀푖 = 1,2, , ; 푖 ≠ 푖―1, 
∀푖 = 2,3, , ).
 De-Thi.com Tổng hợp 31 Đề HSG Quốc gia môn Tin học THPT 2009-2025 (Có đáp án) - De-Thi.com
- Dòng thứ 푖 trong số 푄 dòng tiếp theo biểu diễn một câu hỏi với bốn số nguyên 퐿푖,푅푖, 푖,푌푖 
 17
(1 ≤ 퐿푖 ≤ 푅푖 ≤ ;1 ≤ 푖,푌푖 ≤ 10 ). Dũ liệu bảo đảm số lượng dãy mã hóa phân đoạn của 
 ′
dãy = [ 퐿푖, 퐿푖+1, , 푅푖] không nhỏ hơn max( 푖,푌푖).
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bản NOEL.OUT:
- Gồm 푄 dòng, trong đó dòng thứ 푖 chứa một số nguyên là độ dài tiền tố chung dài nhất của 
 ′
hai dãy mã hóa phân đoạn của dãy = [ 퐿푖, 퐿푖+1, , 푅푖], với dãy mã hóa thứ nhất có thứ tự 
từ điển ngược bằng 푖 và dãy mã hóa thứ hai có thứ tự từ điển ngược bằng 푌푖.
Ví dụ
 NOEL.INP NOEL.OUT Giải thích
10 2 2 - Trong câu hỏi đầu tiên, dãy cần xét đến là 
1 2 4 3 2 1 2 8 6 8 0 ′ = [2,4,3,2]. Tất cả các dãy mã hóa phân đoạn sắp 
2 5 6 7 xếp theo thứ tự từ điển ngược lần lươt là [3,1]; [2,2]; 
4 10 7 6 [2,1,1]; [1,3]; [1,2,1]; [1,1,2]; [1,1,1,1]. Hai dãy mã 
 hoá phân đoạn có thứ tự từ điển ngược bằng 6 và 
 bằng 7 tương ứng là 푍1 = [1,1,2] và 푍2 = [1,1,1,1]. 
 Độ dài tiền tố chung dài nhất của hai dãy 푍1 và 푍2 là 
 2 .
 - Trong câu hỏi thứ hai, dãy cần xét đến là 
 ′ = [3,2,1,2,8,6,8]. Hai dãy mã hóa phân đoạn có 
 thứ tự từ điển ngược bằng 7 và bằng 6 tương ứng là 
 푍1 = [2,4,1] và 푍2 = [3,1,1,1,1]. Độ dài tiền tố 
 chung dài nhất của hai dãy 푍1 và 푍2 là 0.
Ràng buộc
(1) Có 17,5% số test ứng với 17,5% số điểm thỏa mãn: ≤ 12 và 푄 ≤ 1024.
(2) 20% số test khác ứng với 20% số điểm thỏa mãn: 푖 = 푌푖 = 1,∀푖 = 1,2, ,푄.
 5
(3) 22,5% số test khác ứng với 22,5% số điểm thỏa mãn: 퐿푖 = 1;푅푖 = và 푖,푌푖 ≤ 10 , 
∀푖 = 1,2, ,푄.
(4) 22,5% số test khác ứng với 22,5% số điểm thỏa mãn: ≤ 2000 và 푄 ≤ 20000.
(5) 17,5% số test còn lại ứng với 17,5% số điểm: Không có ràng buộc gì thêm.
 ----------HẾT----------
 De-Thi.com