2026 Đề thi thử TS10 Thanh Hóa & Ninh Bình

Trong giờ Tin hôm nay, thầy giáo có bài toán đố cả lớp. Cho số tự nhiên \(N\), hãy lập trình tính tổng sau:

Input

• Một số nguyên \(N\) (\(2 \le N \le 10^{18}\)).

Output

• Một số duy nhất là kết quả của bài toán (làm tròn đến \(5\) chữ số thập phân).

Example

3

0.66667

2

0.50000

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(N \le 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\). Với mỗi số \(a_i\), Bờm được phép thực hiện một trong ba thao tác sau:

• Cộng thêm \(1\): \(a_i = a_i + 1\);
• Trừ đi \(1\): \(a_i = a_i - 1\);
• Giữ nguyên: \(a_i = a_i\).

Với dãy số nguyên \(a_1, a_2, \dots, a_n\) đã cho, sau khi thực hiện đúng một thao tác trên mỗi số \(a_i\) (\(i = 1 \dots n\)), liệu Bờm có thể tạo ra được một dãy không giảm hay không?

Input

• Dòng đầu chứa số nguyên dương \(T\) là số bộ test (\(T \le 3\)).
• Trong mỗi bộ test:
  • Dòng thứ nhất chứa duy nhất một số nguyên dương \(n\) (\(2 \le n \le 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Ghi ra \(T\) dòng là đáp án tương ứng của \(T\) bộ test. In YES nếu Bờm có thể tạo ra một dãy không giảm, ngược lại in NO.

Example

2
5
1 2 1 1 2
4
1 4 2 1

YES
NO

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(T = 1\) và \(a_2 = a_3 = \dots = a_n\).
• Subtask \(2\) (\(30\%\) số điểm): \(T = 2\) và \(n \le 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(T = 3\) và không có ràng buộc gì thêm.

Sau khi học lập trình một thời gian Bờm đã thi đậu vào đội tuyển dự thi học sinh giỏi cấp tỉnh. Bờm ôn luyện rất chăm chỉ, quyết tâm đạt một giải trong kỳ thi này nhưng trong quá trình ôn luyện Bờm học không giỏi về xử lý dãy số, các bài xử lý dãy số nâng cao càng làm Bờm gặp khó khăn nhiều hơn.

Trong các bài xử lý dãy số có bài tìm dãy con liên tiếp có độ dài bất kỳ sao cho tổng giá trị các phần tử dãy con đạt giá trị lớn nhất. Bờm chưa tìm ra được cách giải tối ưu, nhờ các bạn lập trình viên hỗ trợ tiếp Bờm giải quyết bài toán nhé.

Bài tìm dãy con mà Bờm chưa tìm ra cách tối ưu như sau:
Cho một dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\) và hai số nguyên \(U, V\) (\(1 \le U \le V \le N\)). Hãy tìm một dãy con liên tiếp của dãy \(A\) có tổng giá trị các phần tử đạt giá trị lớn nhất và có độ dài \(D\) với \(U \le D \le V\) (Độ dài của dãy con là số lượng phần tử trên dãy con đó).

Input

• Dòng đầu chứa \(3\) số nguyên dương \(N, U, V\) (\(1 \le U \le V \le N \le 10^5\)).
• Dòng thứ hai chứa dãy số nguyên \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\) (\(|A_i| \le 10^9, 1 \le i \le N\)).

Output

• Một số nguyên duy nhất là tổng giá trị các phần tử trên dãy con tìm được.

Example

6 2 2
-2 3 1 2 5 4

9

5 2 3
-4 3 -2 -6 5

1

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(U = V\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Có một cửa hàng cho thuê \(N\) thiết bị âm thanh. Để thuê hết \(N\) thiết bị, khách hàng có thể chia chúng thành nhiều nhóm, trong mỗi nhóm được tính tiền theo một trong hai chính sách sau:

• Nếu trong nhóm đó thuê từ \(3\) thiết bị trở lên thì sẽ được miễn phí "1 thiết bị" có giá nhỏ nhất.
• Nếu trong nhóm đó thuê ít hơn \(3\) thiết bị thì tất cả thiết bị của nhóm đó đều được giảm giá \(q\%\).

Hãy tìm cách chia nhóm sao cho tổng số tiền phải trả là ít nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(q\) (\(N \le 10^6, q < 100\)) lần lượt là số lượng thiết bị và mức giảm giá.
• Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1, A_2, A_3, \dots, A_n\) (\(A_i \le 10^6\), \(A_i\) chia hết cho \(100\)) lần lượt là số tiền cần phải bỏ ra để thuê của các thiết bị.

Output

• In ra một số nguyên duy nhất là tổng số tiền ít nhất để thuê hết \(N\) thiết bị.

Example

6 10
1000 100 900 100 800 100

2100

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 3, 100 \le A_i \le 1000\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Một mã đẹp là một số nguyên dương. Với mỗi mã đẹp biểu diễn trong hệ thập phân (không có số \(0\) ở đầu), gọi:

• \(M\) là chữ số lớn nhất trong các chữ số của mã đẹp;
• \(m\) là chữ số nhỏ nhất trong các chữ số của mã đẹp.

Một mã đẹp được gọi là hợp lệ nếu:

• \(m \neq 0\);
• \(M\) chia hết cho \(m\).

Yêu cầu: Cho danh sách gồm \(n\) mã đẹp. Hãy đếm số lượng mã đẹp hợp lệ trong danh sách.

Input

• Dòng 1: Số nguyên dương \(n\) (\(1 \leq n \leq 10^5\)).
• Dòng 2: \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(10 \leq a_i \leq 10^{18}\)).

Output

• Ghi ra một số nguyên duy nhất là số lượng mã đẹp hợp lệ.

Example

5
15 26 356 73 4368

3

Nhân dịp Đại lễ 30/4/2026, một lớp 9 tổ chức trang trí hành lang bằng các bông hoa giấy mini. Lớp chuẩn bị được \(n\) cánh hoa, cánh thứ \(i\) có độ dài \(a_i\) (đơn vị: cm).

Một bông hoa giấy mini hợp lệ được tạo thành khi và chỉ khi:

• Gồm đúng \(3\) cánh hoa;
• Ba cánh có cùng độ dài;
• Mỗi cánh hoa chỉ được sử dụng không quá một lần.

Các cánh không được cắt ngắn, ghép thêm hoặc thay đổi độ dài.

Yêu cầu: Cho độ dài của \(n\) cánh hoa, hãy xác định:

• \(x\): số bông hoa giấy mini tối đa có thể kết được;
• \(y\): tổng số cánh hoa chưa được sử dụng sau khi tạo số hoa tối đa.

Input

• Dòng 1: Số nguyên dương \(n\) (\(1 \le n \le 10^6\)).
• Dòng 2: \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 2000\)).

Output

• Ghi ra hai số nguyên \(x\) và \(y\) cách nhau một dấu cách.

Example

10
5 7 5 5 7 7 7 8 8 8

3 1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(1 \le n \le 10^3, 0 \le a_i \le 10^3\).
• Subtask 2 (\(30\%\) số điểm): \(1 \le n \le 10^5, 0 \le a_i \le 10^3\).
• Subtask 3 (\(40\%\) số điểm): \(1 \le n \le 10^6, 0 \le a_i \le 2000\).

Trong quá trình khai quật tại một ngôi đền cổ, các nhà khoa học đã gặp một dòng văn bản hấp dẫn được khắc vào một tảng đá lớn. Ý nghĩa của dòng văn bản dường như là từ một ngôn ngữ cổ xưa bí ẩn liên quan đến một bảng chữ cái chỉ gồm ba ký tự C, A, và R. Mặc dù các nhà khoa học không thể giải mã văn bản nhưng CAR là mẫu từ yêu thích của các nhà khoa học, và họ tự hỏi có bao nhiêu lần cụm kí tự CAR xuất hiện trong dòng văn bản đó.

Các nhà khoa học không phiền lòng nếu có những kí tự khác xen kẽ trong CAR, miễn rằng các kí tự xuất hiện theo thứ tự đúng là C, A, R. Các nhà khoa học cũng không ngại nếu các lần xuất hiện khác nhau của CAR có chung một số chữ cái. Ví dụ, CAR xuất hiện một lần trong CRAR, hai lần trong CCAR, và tám lần trong CCAARR.

Yêu cầu: Em hãy giúp các nhà khoa học đếm xem có bao nhiêu lần cụm kí tự CAR xuất hiện trong dòng văn bản đã gặp.

Input

• Dòng đầu tiên gồm một số nguyên duy nhất \(n \le 10^5\).
• Dòng thứ hai chứa một chuỗi gồm \(n\) ký tự C, A, hay R.

Output

• Ghi ra một số nguyên duy nhất là số lần cụm kí tự CAR xuất hiện như một dãy con (các kí tự không nhất thiết phải liên tục) trong chuỗi input.

Example

6
CCAARR

8

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(3 \le n \le 10^2\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Bài 4: Tìm phòng khách sạn

Nhân dịp Đại lễ 30/4/2026, tỉnh Ninh Bình sẽ đón lượng lớn khách du lịch quốc tế đến tham quan các địa điểm nổi tiếng như Tràng An, Tam Cốc – Bích Động, chùa Bái Đính, đền Trần, chùa Tam Chúc... Một công ty du lịch muốn lựa chọn một chuỗi khách sạn liên tiếp trên cùng một tuyến đường để đặt phòng cho một đoàn khách nước ngoài. Mỗi khách sạn được đánh giá bởi một số nguyên thể hiện mức chuẩn phục vụ quốc tế (được mã hóa bằng một số nguyên).

Để thuận tiện trong công tác tổ chức, công ty yêu cầu: Phải tồn tại một số nguyên \(d > 1\) sao cho tất cả các khách sạn trong dãy được chọn đều có mức chuẩn phục vụ chia hết cho \(d\).

Yêu cầu: Tìm độ dài lớn nhất của một dãy khách sạn liên tiếp thỏa mãn điều kiện trên. Nếu không tồn tại dãy nào thỏa mãn, in ra \(0\).

Input

• Dòng 1: Số nguyên dương \(T\) là số bộ test (\(3 \le T \le 10^4, 1 \le n \le 10^6\)).
• Với mỗi test gồm:
  • Dòng 1: Số nguyên dương \(n\) là số khách sạn trên tuyến đường.
  • Dòng 2: \(n\) số nguyên \(a_i\) (mức chuẩn phục vụ của từng khách sạn).

Output

• Với mỗi test, ghi ra một số nguyên trên một dòng là độ dài lớn nhất của dãy khách sạn liên tiếp tìm được. Nếu không tồn tại dãy thỏa mãn điều kiện, in ra \(0\).

Constraints

• \(|a_i| \le 10^6\).
• Tổng các giá trị \(n\) trong toàn bộ file không vượt quá \(10^6\).

Example

3
4
6 9 5 7
5
6 12 18 7 14
10
4 8 12 5 9 3 6 15 18 21

2
3
6

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 1000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Tại cửa hàng bánh nổi tiếng X, có \(n\) khách hàng đang xếp hàng mua bánh, được đánh số từ \(1\) đến \(n\) theo đúng thứ tự xếp hàng. Khách hàng thứ \(i\):

• Muốn mua \(a_i\) chiếc bánh.
• Sẵn sàng chờ tối đa \(t_i\) phút.

Thời gian phục vụ mỗi khách hàng là đúng \(1\) phút. Tại mỗi thời điểm, cửa hàng chỉ có thể phục vụ tối đa một khách hàng. Cửa hàng bắt buộc phải phục vụ khách theo đúng thứ tự xếp hàng. Chủ cửa hàng có thể từ chối phục vụ một số khách hàng.

Nếu khách hàng thứ \(i\) không được bắt đầu phục vụ trước hoặc tại thời điểm \(t_i\) thì khách hàng đó sẽ rời đi và không mua hàng.

Yêu cầu: Hãy xác định tổng số bánh lớn nhất mà cửa hàng có thể bán được.

Input

• Dòng \(1\) ghi số nguyên dương \(n\) (\(1 \le n \le 10^4\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(a_i, t_i\) (\(1 \le a_i \le 10^5, 0 \le t_i \le 10^4\)).

Output

• Ghi ra một số nguyên duy nhất là tổng số bánh lớn nhất có thể bán được.

Example

6
8 0
50 2
10 1
40 3
30 3
100 5

220

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 1000, 0 \le t_i \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 5000, 0 \le t_i \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le n \le 10^4, 0 \le t_i \le 10^4\).