Thi thử tuyển sinh lớp 10 Chuyên Thanh Hóa 2026

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.