Tuyển sinh lớp 10 Chuyên tỉnh Đắk Lắk 2026

Nam đang luyện thi vào lớp chuyên Tin của trường THPT chuyên XYZ. Chủ đề tuần này về tính chẵn, lẻ trong toán học. Trong quá trình luyện tập Nam gặp bài toán khó chưa giải ra, nội dung bài toán như sau:

Cho hai số nguyên dương \(l\) và \(r\). Hãy tính tổng tất cả các số nguyên chẵn trong đoạn \([l, r]\).

Yêu cầu: Bạn hãy giúp Nam tính tổng tất cả các số nguyên chẵn trong đoạn \([l, r]\).

Input

• Đọc dữ liệu từ bàn phím một dòng duy nhất chứa hai số nguyên dương \(l\) và \(r\) (\(1 \le l \le r \le 2 \cdot 10^9\)), mỗi số cách nhau một khoảng trắng.

Output

• Xuất ra màn hình một số nguyên là tổng tính được.

Example

2 9

20

3 3

0

Scoring

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

Để chuẩn bị cho Lễ hội sầu riêng tỉnh Đắk Lắk năm 2026, công ty ABC đã trồng một số cây xanh trên con đường MK để trang trí, mỗi loại cây được kí hiệu bằng một kí tự chữ cái tiếng Anh in thường. Dãy cây xanh liên tiếp đã trồng được mô tả thành một xâu kí tự \(S\).

Ví dụ: \(S =\) fabacb, có \(2\) cây loại a, \(2\) cây loại b, \(1\) cây loại c và \(1\) cây loại f.

Yêu cầu: Đếm số lượng từng loại cây xanh đã trồng.

Input

• Đọc dữ liệu từ bàn phím một dòng duy nhất chứa xâu \(S\), kí hiệu \(|S|\) là độ dài xâu.

Output

• Xuất ra màn hình một số dòng, mỗi dòng gồm ba phần: phần thứ nhất một kí tự chữ cái kí hiệu cho mỗi loại cây, phần thứ hai dấu hai chấm :, phần thứ ba số lượng cây tương ứng từng loại và giữa các phần không có khoảng trắng. Các loại cây được xuất ra theo thứ tự từ điển bảng chữ cái.

Constraints

• \(1 \le |S| \le 10^3\)

Example

fabacb

a:2
b:2
c:1
f:1

Trong buổi học chuyên đề về số học, thầy giáo đưa ra khái niệm số đặc biệt: một số nguyên dương \(x\) gọi là số đặc biệt nếu tổng các ước nguyên dương của \(x\) chia hết cho \(3\).

Ví dụ: \(15\) là một số đặc biệt (vì tổng các ước của \(15\) là \(1 + 3 + 5 + 15 = 24\) chia hết cho \(3\)); \(12\) không phải số đặc biệt (vì tổng các ước của \(12\) là \(1 + 2 + 3 + 4 + 6 + 12 = 28\) không chia hết cho \(3\)).

Cho trước một dãy số có \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\), thầy đưa ra \(q\) câu hỏi có dạng \(l, r, k\) với ý nghĩa số lượng số đặc biệt trong dãy con \(a_l, a_{l+1}, \dots, a_r\) (\(1 \le l \le r \le n\)) có lớn hơn hoặc bằng \(k\) hay không, nếu có thì trả lời YES, ngược lại trả lời NO. Thầy yêu cầu cả lớp lập trình trả lời \(q\) câu hỏi trên.

Yêu cầu: Hãy viết chương trình trả lời \(q\) câu hỏi của thầy giáo.

Input

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n, q\) (\(2 \le n, q \le 10^5\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5, 1 \le i \le n\)).
• \(q\) dòng tiếp theo mỗi dòng gồm \(3\) số nguyên dương \(l, r, k\) (\(1 \le l \le r \le n, 1 \le k \le 10^5\)).
• Các số trên một dòng cách nhau một khoảng trắng.

Output

• Xuất ra màn hình gồm \(q\) dòng trả lời tương ứng cho \(q\) câu hỏi của thầy giáo.

Example

5 3
19 8 3 17 18
2 5 3
4 4 1
3 3 1

YES
YES
NO

Scoring

• \(50\%\) số điểm tương ứng với số test có: \(n, q \le 10^3\).
• \(50\%\) số điểm tương ứng với số test còn lại không ràng buộc gì thêm.

Bác Nam sở hữu một khu vườn có trồng \(n\) cây, cây thứ \(i\) có độ tươi tốt hiện tại \(a_i\) và khả năng tăng trưởng \(b_i\). Hôm nay, bác Nam dự định sử dụng tổng cộng \(l\) lít nước để tưới cho các cây trong vườn. Với mỗi lít nước tưới vào cây thứ \(i\), độ tươi tốt của cây sẽ tăng thêm \(b_i\). Ngoài ra, số lít nước tưới vào mỗi cây phải là số nguyên không âm. Bác Nam đánh giá vẻ đẹp của khu vườn là độ tươi tốt nhỏ nhất trong số \(n\) cây trong vườn sau khi đã tưới nước.

Yêu cầu: Hãy giúp bác Nam tìm cách tưới nước sao cho vẻ đẹp của khu vườn là lớn nhất có thể.

Input

• Dòng thứ nhất chứa hai số nguyên \(n, l\) (\(1 \le n \le 10^5, 1 \le l \le 10^9\)) lần lượt là số lượng cây trong vườn và số lít nước dùng để tưới cây.
• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(a_i\) và \(b_i\) (\(1 \le a_i \le 10^9, 1 \le b_i \le 10^4, 1 \le i \le n\)).
• Các số trên một dòng cách nhau một khoảng trắng.

Output

• Xuất ra màn hình vẻ đẹp lớn nhất có thể của khu vườn với cách tưới cây tối ưu.

Example

2 5
3 2
100 5

13

3 5
1 5
6 2
3 3

8

Scoring

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

Cho trước số nguyên dương \(n\) và dãy số nguyên \(a_1, a_2, \dots, a_n\). Một dãy con liên tiếp \(a_l, a_{l+1}, \dots, a_r\) (\(1 \le l \le r \le n\)) được gọi là dãy số đẹp nếu mỗi phần tử trong dãy đều có số lần xuất hiện không vượt quá \(2\).

Ví dụ: \(\{1; 5; 2; 4; 3\}\), \(\{6; 10; 10; 6\}\) và \(\{9\}\) là các dãy số đẹp; \(\{3; 3; 4; 4; 4\}\), \(\{7; 7; 8; 7\}\) và \(\{100; 100; 100\}\) không phải là dãy số đẹp vì mỗi dãy đều có ít nhất một phần tử có số lần xuất hiện lớn hơn \(2\).

Yêu cầu: Hãy đếm số lượng cặp chỉ số \((l, r)\) (\(1 \le l \le r \le n\)) sao cho dãy con \(a_l, a_{l+1}, \dots, a_r\) là dãy số đẹp.

Input

• Dòng thứ nhất chứa số nguyên \(n\) (\(1 \le n \le 5 \cdot 10^5\)), số lượng phần tử của dãy.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 5 \cdot 10^5, 1 \le i \le n\)) lần lượt là các giá trị của dãy, mỗi số cách nhau một khoảng trắng.

Output

• Xuất ra màn hình một số nguyên duy nhất là số lượng cặp chỉ số \((l, r)\) thỏa mãn yêu cầu đề bài.

Example

4
1 2 1 1

9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 50, a_i \le 50\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 500, a_i \le 500\).
• Subtask \(3\) (\(15\%\) số điểm): \(n \le 5000, a_i \le 5000\).
• Subtask \(4\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.