Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án)

 Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
 SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI OLYMPIC TRUYỀN THỐNG 30 
 THÀNH PHỐ HỒ CHÍ MINH THÁNG 4 - LẦN THỨ XXIX - NĂM 2025
 TRƯỜNG THPT CHUYÊN MÔN: TIN HỌC - KHỐI: 10
 LÊ HỒNG PHONG Thời gian: 180 phút (không kể thời gian giao đề)
 Tổng quan về đề thi
Bài Tên bài File chương trình File dữ liệu File kết quả
 1 Đường đi sắc màu CPATH.* CPATH.INP CPATH.OUT
 2 Khôi phục trọng số STREE.* STREE.INP STREE.OUT
 3 Hội thao học sinh FESTIVAL.* FESTIVAL.INP FESTIVAL.OUT
Dấu * thay thế bởi PAS hoặc CPP tương ứng với ngôn ngữ lập trình Pascal hoặc C++.
Bài 1. Đường đi sắc màu (7,0 điểm)
Alice là một cô bé rất thích các màu sắc. Một hôm cô đang lang thang trên các con phố của 
TP HCM thì gặp một con đường gạch dài gồm viên gạch liên tiếp, đánh số từ 1 đến , 
viên gạch thứ 푖 có màu là một số nguyên dương 푖 ≤ .
Cô muốn đi qua con đường này bằng cách: chọn một màu 푡, sau đó bắt đầu đi từ viên gạch 
đầu tiên có màu 푡, chỉ được bước sang các viên gạch có màu 푡 kế tiếp và kết thúc lộ trình ở 
viên gạch cuối cùng có màu 푡. Vì các viên gạch có màu 푡 có thể không nằm liên tiếp nhau mà 
có thể nằm cách nhau một khoảng và việc đi một bước quá dài có thể khiến Alice vấp ngã, 
nên Alice muốn chọn một lộ trình sao cho khoảng cách giữa hai viên gạch liên tiếp mà cô đi 
là nhỏ nhất có thể.
Nói cách khác, Alice muốn chọn một số chỉ số (푖1,푖2,,푖 ) (1 ≤ ≤ ) sao cho:
- 1 ≤ 푖1 < 푖2 < ⋯ < 푖 ≤ .
- 
 푖1 = 푖2 = ⋯ = 푖 
- Không tồn tại mà .
 1 ≤ < 푖1 = 푖1
- Không tồn tại mà .
 ≥ > 푖 = 푖 
- Giá trị = max (0,푖2 ― 푖1,푖3 ― 푖2,,푖 ― 푖 ―1) là nhỏ nhất có thể.
Yêu cầu: Biết rằng Alice được phép chọn ra một viên gạch bất kì và thay đổi màu của nó 
thành một màu từ ý với 1 ≤ ≤ . Hãy tính giá trị nhỏ nhất nếu như Alice có thể tùy ý 
thay đổi màu của tối đa một viên gạch bất kì.
Dữ liệu
Vào từ file văn bản CPATH.INP:
- Dòng đầu tiên chứa hai số nguyên dương , thể hiện số lượng viên gạch và số lượng màu 
(1 ≤ , ≤ 2 × 105).
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
- Dòng thứ hai chứa số nguyên dương, số thứ 푖 là giá trị 푖 thể hiện màu của viên gach thứ 
푖 (1 ≤ 푖 ≤ ).
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 CPATH.OUT:
- Một số nguyên duy nhất thể hiện giá trị nhỏ nhất nếu Alice có thể đổi màu của tối đa một 
viên gạch.
Ví dụ
CPATH. INP CPATH.OUT Giải thích
6 2 1 Alice đổi màu viên gạch thứ 4 thành màu 2. Sau đó chọn 
1 2 2 1 2 1 các chỉ số (2,3,4,5) với cùng màu 2 cho khoảng cách của 
 bước lớn nhất là 1.
5 2 0 Alice đổi màu viên gạch thứ 4 thành màu 2.
1 2 2 1 2 Sau đó chỉ cần chọn một chỉ số (1) với màu 1 và không 
 phải bước thêm. Khoảng cách của bước lớn nhất là 0.
Chấm điểm
Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn.
- Subtask 1 (30% số điẻm): ≤ 100; ≤ 3.
- Subtask 2 (30% số điểm): , ≤ 100.
- Subtask (30% số điểm): 푖 = (푖 mod ) + 1,∀푖 = 1,2,, .
- Subtask 4 (10% số diểm): Không có ràng buộc nào thêm.
Bài 2. Khôi phục trọng số (7,0 điểm)
Bob là một thành viên tích cực của câu lạc bộ LHP-IT. Cậu có niểm đam mê nghiên cứu đối 
với cấu trúc dữ liệu dạng cây trong đồ thị. Lần này, cậu đang quan sát một cây thú vị gồm 
đỉnh, đánh số từ 1 đến và ―1 cạnh, đánh số từ 1 đến ―1. Cạnh thứ 푖(1 ≤ 푖 ≤ ―1) 
 20
nối đỉnh 푈푖 với đỉnh 푖 có trọng số 푊푖 không âm (푊푖 < 2 ). Để đảm bảo khỏi quên, cậu đã 
đặt tên cây này là STREE, viết thông tin về cây này lên một mẩu giấy và cất nó trong ngăn 
kéo.
Một hôm, Bob lấy mẩu giấy ra để xem lại cây này thì phát hiện ra trọng số đã bị nhòe do 
không khí ẩm mốc, còn phần còn lại về số lượng đỉnh và thông tin các cạnh thì vẫn có thể 
đọc được. Cậu mong muốn tìm lại được trọng số của các cạnh trên cây. Bob ngồi ngắm nghĩ 
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
và nhớ được mẩu thông tin, mẩu thông tin thứ 푖(1 ≤ 푖 ≤ ) cho biết tổng trọng số các 
 20
cạnh trên đường đi đơn từ đỉnh 푖 đến đỉnh 푖 sau khi chia lấy dư cho 2 là 푖.
Yêu cầu: Hãy giúp Bob tìm lại trọng số của các cành trên cây STREE nếu có thể. Lưu ý, các 
mẩu thông tin của Bob đưa ra có thể mâu thuẫn nhau, hoặc không thoả mãn các ràng buộc, 
hoặc thiếu thông tin để kết luận.
Dữ liệu
Vào từ file văn bản STREE.INP:
- Dòng đầu tiên chứa số nguyên dương thể hiện số dình của cây (1 ≤ ≤ 105).
- Dòng thứ 푖 trong số ―1 dòng tiếp theo chứa hai số nguyên dương 푈푖, 푖 thể hiện canh thứ 
푖 của cây (1 ≤ 푈푖, 푖 ≤ ).
- Dòng tiếp theo chứa một số nguyên không âm thể hiện số mẩu thông tin mà Bob nhớ 
dược (0 ≤ ≤ 2 × 105).
- Dòng thứ 푖 trong số dòng tiếp theo chứa ba số nguyên 푖, 푖, 푖 thể hiện mẫu thông tin thứ 
 20
푖 mà Bob nhớ ra (1 ≤ 푖, 푖 ≤ ;0 ≤ 푖 < 2 ).
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 STREE.OUT:
- Nếu tồn tại một đáp án duy nhất hãy in ra từ UNIQUE. Tiếp theo là một dòng gồm ―1 
giá trí, giá trị thứ 푖 thể hiện trọng số 푊푖. Các số trên cùng một dòng cách nhau bởi dấu cách.
- Trái lại, hãy in ra từ INDETERMINATE.
Chấm điểm: 
Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn.
- Subtask 1 (20% số điểm): , ≤ 3 và 푊푖 ≤ 10,∀푖 = 1,2,, .
- Subtask 2 (20% só điểm): , ≤ 6 và 푊푖 ≤ 10,∀푖 = 1,2,, .
- Subtask 3 (20% số điểm): 푖 = 1,∀푖 = 1,2,, .
- Subtask 4 (20% số điểm): 푈푖 = 푖, 푖 = 푖 +1,∀푖 = 1,2,, ―1 và 푖 ≤ 푖+1 ≤ 
 푖+1 ≤ 푖,∀푖 = 1,2,, ―1.
- Subtask 5 (10% số điểm): Bậc của mọi đỉnh trên cây tối đa là 2.
- Subtask 6 (10% số điểm): Không có ràng buộc nào thêm.
Ví dụ
STREE.INP STREE.OUT Giải thích
3 UNIQUE Trọng số của hai cạnh tim lại được đểu là 1.
1 2 1 1
2 3
2
1 2 1
2 3 1
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
3 INDETERMINATE Hai mẫu thông tin tương ứng với hai phương trình:
12 푊1 = 5
23 푊1 + 푊2 = 2
2 Giải hệ phương trình ta có 푊1 = 5 và 푊2 = ―3.
1 2 5 Không thỏa măn do trọng số phải không âm.
1 3 2
3 INDETERMINATE Mẫu thông tin duy nhất cho 3 đáp án ( 푊1,푊2 ) thoả 
1 2 mān, đó là: {(0,2),(1,1),(2,0)}.
2 3
1
1 3 2
Bài 3. Hội thao học sinh (6,0 điểm)
Hội thao vui khoẻ năm nay của trường THPT LHP có học sinh tranh tài, được đánh số lần 
lượt từ 1 đến và tất cả được xếp thành một vòng tròn. Học sinh thứ 푖(1 ≤ 푖 < ) đứng bên 
trái học sinh thứ 푖 +1, học sinh thứ đứng bên trái học sinh thứ 1. Học sinh thứ 
푖(1 ≤ 푖 < ) có hai chỉ số 푖 và 푆푖 tương ứng tượng trưng cho độ khoẻ và độ mạnh.
Hội thao bao gồm nhiều vòng đấu giống nhau. Ở mỗi vòng, khi có hiệu lệnh bắt đầu, các học 
sinh sẽ cùng lúc giả vờ tấn công người ở bên phải của mình. Khi đó chỉ số độ khoẻ của tất cả 
các học sinh đồng thời bị giảm đi một lượng đúng bằng chỉ số độ mạnh của học sinh vừa giả 
vờ tấn công ở bên trái mình. Sau đó, các học sinh có chỉ số độ khoẻ nhỏ hơn hoặc bằng 0 sẽ 
bị loại ra khỏi cuộc chơi, và vòng tròn được thu hẹp lại mà vẫn giữ nguyên thứ tự. Các vòng 
đấu tiếp theo sẽ được lặp lại cho đến khi chỉ còn duy nhất một học sinh chưa bị loại, hoặc tất 
cả học sinh đều đã bị loại.
Luật chơi đặt ra các tiêu chí cụ thể để xếp hạng các học sinh. Cụ thể, giả sử có hai học sinh 
và , khi đó có thứ hạng cao hơn khi và chỉ khi:
- A là người ở lại cuối cùng, hoặc
- bị loại ở vòng đấu sau vòng đấu mà bị loại, hoặc
- Cả và cùng bị loại tại một vòng đấu, nhưng tại thời điểm bị loại có chỉ số độ khoẻ 
lớn hơn , hoặc
- Cả và cùng bị loại tại một vòng đấu, và tại thời điểm bị loại và có chỉ số độ khỏe 
giống nhau, nhưng chỉ số độ mạnh của lớn hơn chỉ số độ mạnh của .
Trong các trường hợp còn lại, có thứ hạng không cao hơn .
Xếp hạng cuối cùng của học sinh thứ 푖 là 푅푖 = 푖 +1 trong đó 푖 là số lượng học sinh 푗 trong 
 học sinh mà 푗 có thứ hạng cao hơn 푖.
Yêu cầu: Hãy tìm dãy xếp hàng 푅1,푅2,,푅 
Dữ liệu
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
Vào từ file văn bản FESTIVAL.INP:
- Dòng đầu tiên chứa một số nguyên duy nhất là số lượng học sinh (1 ≤ ≤ 106).
- Dòng thứ hai chứa số nguyên 1, 2,, mô tả chỉ số độ khỏe của học sinh 
 9
(1 ≤ 푖 ≤ 10 ).
- Dòng thứ ba chứa số nguyên 푆1,푆2,,푆 mô tả chỉ số độ mạnh của học sinh 
 9
(1 ≤ 푆푖 ≤ 10 ).
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 FESTIVAL.OUT:
- Dãy số nguyên 푅1,푅2,,푅 trên một dòng, hai số liên tiếp cách nhau bỏi một dấu cách.
Ví dụ
 FESTIVAL. INP FESTIVAL.OUT Hình minh hoạ
5 5 4 2 1 3
1 0 6 7 5 9
2 2 1 3 4
3 1 3 1
2 1 3
3 4 3
Giải thích
Ở ví dụ đầu tiên, các vòng diễn ra như sau:
 H1 H2 H3 H4 H5
 Ban đầu 10 6 7 5 9
 Vòng 1 10 ― 4 = 6 6 ― 2 = 4 7 ― 2 = 5 5 ― 1 = 4 9 ― 3 = 6
 Vòng 2 6 ― 4 = 2 4 ― 2 = 2 5 ― 2 = 3 4 ― 1 = 3 6 ― 3 = 3
 Vòng 3 2 ― 4 = ―2 2 ― 2 = 0 3 ― 2 = 1 3 ― 1 = 2 3 ― 3 = 0
 Vòng 4 × × 1 ― 3 = ―2 2 ― 1 = 1 ×
 Vòng 5 × × × 1 ×
Khi kết thúc, ta có thông tin để xếp hạng như sau:
Học sinh 1 2 3 4 5
Vòng bị loại 3 3 4 × 3
Độ khỏe ngay trước khi bị loại -2 0 -2 × 0
Độ mạnh 2 2 1 3 4
Như vậy,
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
- Xếp hạng của học sinh 1 là 1 = 1 +1 = 5, với 1 = 4 do tất cả học sinh còn lại đều có thứ 
hạng cao hơn học sinh 1;
- Xếp hạng của học sinh 2 là 2 = 2 +1 = 4, với 2 = 3 do các học sinh 3,4,5 có thứ hạng 
cao hơn học sinh 2 ;
- Xếp hạng của học sinh 3 là 3 = 3 +1 = 2, với 3 = 1 do chỉ có học sinh 4 có thứ hang 
cao hơn học sinh 3;
- Xếp hạng của học sinh 4 là 4 = 4 +1 = 1, với 4 = 0 do không có học sinh nào có thứ 
hạng cao hơn hoc sinh 4;
- Xếp hạng của học sinh 5 là 5 = 5 +1 = 3, với 5 = 2 do các học sinh 3,4 có thứ hạng cao 
hơn học sinh 5.
Chấm điểm
Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn.
- Subtask 1(20%): ≤ 100; 푖,푆푖 ≤ 100,∀푖 = 1,2,, .
- Subtask 2 (20%): ≤ 2000.
- Subtask 3 (20%) : ≤ 300000,푆1 = 푆2 = ⋯ = 푆 .
- Subtask 4 (15%) : ≤ 300000, đảm bảo chỉ có học sinh 1 là người ở lại vòng cuối cùng.
- Subtask 5 (15%): ≤ 300000.
- Subtask 6 (10%): Không có ràng buộc nào thêm.
 ----------HẾT----------
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1. Đường đi sắc màu (7,0 điểm)
- Subtask 1 (30% số điểm): ≤ 100; ≤ 3.
Duyệt qua tất cả các màu và thử tất cả các cách đổi màu và tính lại giá trị .
Độ phức tạp thời gian: 풪( × 2).
- Subtask 2 (30% số điểm): , ≤ 100.
Cần tính giá trị D một cách thông minh hơn. Nhận xét: lúc đổi vị trí 푖 thành màu thì chỉ có 
giá trị D tương ứng với màu bị thay đổi. Do đó, ta có thể duyệt qua từng màu và từng ô có 
thể đổi màu và tính lại giá trị D mới tương ứng với màu đó.
Độ phức tạp thời gian: O (N × M).
- Subtask 3(30% số điểm): 푖 = (푖mod ) + 1,∀푖 = 1,2,, .
Nhận xét dễ dàng công thức toán học, đáp án là M.
Độ phức tạp thời gian: O (1).
- Subtask 4 (10% số điểm): , ≤ 2 × 105.
Ta có nhận xét:
- Đối với mỗi màu gạch ta cần tính hai tham số là như đã nói trong đề bài và 1 là giá trị 
lớn thứ nhì trong các giá trị đóng góp vào max của D.
- Nhận thấy rằng một cách đổi màu tối ưu sẽ biến giá trị D trở thành max , .
 2 1
- Ngoài ra còn có hai cách biến đổi khác là đổi màu giá trị ban đầu thành màu khác và đổi 
màu giá trị cuối cùng. Cần xét riêng hai tình huống này.
Từ đây có thể duyệt qua mọi màu và tính được giá trị mới, đáp án là min của tất cả giá trị 
 mới.
Độ phức tạp thời gian: 풪( ).
Bài 2. Khôi phục trọng số (7,0 điểm)
- Subtask 1 (20% số điểm): , ≤ 3 và 푊푖 ≤ 10,∀푖 = 1,2,, .
Liệt kê ra các trường hợp xử lý bằng các câu lệnh rẽ nhánh ( 3 ― 4 trường hợp). Ta có thể xử 
lý khéo bằng cách xem các điều kiện như hệ phương trình có dạng 푖 × 푤1 + 푖 × 푤2 = 푖. 
Với 푖, 푖 ∈ 0,1. Ta có thể dễ dàng tính được 푤1,푤2 sao đó kiểm tra lại các điều kiện.
Độ phức tạp thời gian: ( + ).
- Subtask 2 (20% số điểm): , ≤ 6 và 푊푖 ≤ 10,∀푖 = 1,2,, .
Duyệt đệ quy 106 tìm từng cách gán và kiểm tra các điều kiện.
Độ phức tạp thời gian: (10 ―1).
- Subtask 3 (20% số điểm): 푖 = 1,∀푖 = 1,2,, .
Nhận xét, đáp án tồn tại duy nhất khi và chỉ khi:
― = ( 푖+1 ― 푖) + ( 푖 ― 푖+1) ≤ 1.
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
- Nếu hiệu = 0 thì cần xem giá trị 푖 và 푖+1 có bằng nhau hay không. Ngược lại, ta sẽ suy 
ra được giá trị của đúng một cạnh.
- A1 = 1, B1 = N, BM - AM ≤ 1.
Độ phức tạp thời gian: O (N + M)
- Subtask 4 (20% số điểm): 푈푖 = 푖, 푖 = 푖 +1,∀푖 = 1,2,, ―1 và 
 푖 ≤ 푖+1 ≤ 푖+1 ≤ 푖,∀푖 = 1,2,, ―1.
Nhận xét, đáp án tồn tại duy nhất khi và chỉ khi:
+ Mỗi đỉnh đều xuất hiện trong ít nhất một điều kiện.
+ Sau khi biết được giá trị đường đi từ 1 đến tất cả mọi đỉnh khác ta sẽ dễ dàng suy ra được 
trọng số của từng cạnh.
Độ phức tạp thời gian: ( + )
- Subtask 5 (10% số điểm): Bậc của mọi đỉnh trên cây tối đa là 2 .
Cây có dạng mảng một chiều. Giả sử ta đang giải bài toán trên mảng đánh số từ 1.
+ Đặt 푃푖 là tổng cộng dồn các cạnh nối từ 1→2,2→3,3→4,,푖 ―1→푖.
+ Ta có được 푃1 = 0. Sử dụng các dữ kiện ta có thể dễ dàng suy ra các giá trị 푃푖 còn lại.
Độ phức tạp thời gian: ( + ).
- Subtask 6 (10% số điểm): ≤ 105; ≤ 2 × 105.
Đặt 푃 là tổng trọng số từ đỉnh 1 đến đỉnh . Với mỗi bit từ 0 đến 20 , ta sẽ sử dụng các dữ 
kiện để tìm ra được bit đó của tất cả các giá trị 푃 .
Mỗi dữ kiện sẽ có dạng:
푃 + 푃 ― 2 × 푃 = 
trong đó là LCA của và . Nếu giải phương trình này theo modulo 2 ta sẽ có:
푃 + 푃 ≡ mod2.
Từ đây ta tính được bit cuối cùng của 푃 và 푃 , gọi là và .
Đặt
 ′
푃 = 2 × 푃 + 
Viết lại phương trình (1) ta có:
 ′ ′ ′
2 × 푃 + + 2 × 푃 + ― 2 × 2 × 푃 + = 
Giải hệ này modulo 4 ta có:
 ′ ′
2 × 푃 + + 2 × 푃 + ― 2 × ≡ mod4
trong đó , , đã được biết. Từ đây ta có thể giải được tất cả các hệ.
Độ phức tạp thời gian: ( + ) với hệ số thuật toán cỡ 20.
Bài 3. Hội thao học 퐬퐢퐧퐡 ( , điểm)
- Subtask (20%): ≤ 100; 푖,푆푖 ≤ 100,∀푖 = 1,2,, .
Mô phỏng lại như đề bài để tìm kết quả.
 DeThiTinHoc.net Bộ 17 Đề thi Học sinh giỏi Tin học Lớp 10 (Có đáp án) - DeThiTinHoc.net
Độ phức tạp thời gian: ( ∗ max( )).
- Subtask 2 (20%): ≤ 2000.
Nhận thấy sau mỗi vòng, nếu không có ai bị loại thì ở vòng tiếp theo lượng giảm chỉ số độ 
khỏe của mỗi người vẫn giữ nguyên cho đến khi có một người bị loại. Do đó ta có thể nhanh 
chóng bỏ qua các vòng không có người bị loại này. Cụ thể, dựa trên chỉ số độ khỏe của một 
người và chỉ số độ mạnh của người tấn công, ta có thể tính được người đó có thể trụ được 
bao nhiêu vòng cho đến khi xuất hiện một người bị loại. Từ đó ta có thể tìm được vòng gần 
nhất xuất hiện người bị loại và bỏ qua các vòng không cần thiết.
Độ phức tạp thời gian: ( 2) do mỗi lần như vậy ta loại được ít nhất một người, và độ phức 
tạp để tìm vòng tiếp theo là ( ).
- Subtask (20%): ≤ 300000,푆1 = 푆2 = ⋯ = 푆 .
Vì 푆 giống nhau nên ta có thể tính ngay được các thông tin cần thiết để xếp hạng.
Độ phức tạp thời gian: ( ).
- Subtask ퟒ (15%): ≤ 300000, đảm bảo chỉ có học sinh 1 là người ở lại vòng cuối cùng.
Do chỉ có học sinh 1 là người còn lại cuối cùng nên 푅1 = 1, và ta không cần quan tâm đến 
học sinh 1. Khi đó bài toán trở thành đường thẳng. Áp dụng ý tưởng ở Subtask 2, ta sử dụng 
std: : set 푆 để duy trì thời điểm bị loại dự kiến của mỗi người. Mỗi khi có người bị loại ta cần 
cập nhật lại 푆 : giả sử là người bị loại, ta cần cập nhật lại thời gian bị loại dự kiến của với 
 là người tiếp theo chưa bị loại trong dãy do sau khi bị loại thì sẽ bị người khác tấn 
công. Ta cũng cần thêm một std::set duy trì những người chưa bị loại để cập nhật 푆 nhanh 
chóng.
Hơn nữa ta cũng cần phải cập nhật nhanh được mảng sau mỗi lượt, ta có thể dùng cách 
như sau: Sử dụng thêm biến last 푖 với ý nghĩa là chỉ số độ khỏe của người 푖 đã được tính đến 
hết vòng last 푖 và từ thời điểm đó đến hiện tại 푖 chỉ nhận đòn từ chỉ một người duy nhất. Như 
vậy khi một người bị loại, ta chỉ cần cập nhật
+ = ― 푆퓁 ∗ (round - lastp)
+ = ― 푆 ∗ (round – lastr)
+ lastp - lastr = round 
Trong đó 퓁 là người bên trái hiện tại, là người bên phải hiện tại, round là vòng đấu hiện 
tại.
Độ phức tạp thời gian: ( log ).
- Subtask 5 (15% ): ≤ 300000.
Tương tự Subtask 4, tuy nhiên cần xử lí thêm một số trường hợp nhỏ để duy trì được vòng 
tròn (người đầu/cuối dãy bị loại).
- Subtask (10%): ≤ 106.
Tương tự Subtask 5, nhưng sử dụng linked list thay cho set với ( (1) thay cho (log ) 
 DeThiTinHoc.net