Học sinh giỏi lớp 9 tỉnh Quảng Trị 2025-2026

Định nghĩa: Số chính phương là bình phương của các số tự nhiên.

Ví dụ: \(4, 9, 16\) là các số chính phương; \(3, 8, 10\) không phải là số chính phương.

Yêu cầu: Cho đoạn số nguyên \([a, b]\), hãy đếm số lượng số chính phương có trong đoạn \([a, b]\).

Input

• Từ tệp văn bản CAU1.INP chứa hai số tự nhiên \(a, b\) cách nhau một dấu cách (\(1 \le a \le b \le 10^9\)).

Output

• Ghi ra tệp văn bản CAU1.OUT số \(d\) là số lượng số chính phương có trong đoạn \([a, b]\).

Example

1 5

2

10 20

1

5 8

0

Scoring

Định nghĩa: Từ là tập hợp các kí tự liên tiếp nhau có trong bảng mã ASCII được viết cách nhau bởi dấu cách.

Ví dụ: Cho xâu kí tự lop 9b THCS có ba từ lop, 9b, THCS.

Yêu cầu: Cho xâu \(S\) trong đó các kí tự được lấy từ tập {'0'..'9', 'A'..'Z', 'a'..'z'} và dấu cách, hãy đếm xem có bao nhiêu độ dài khác nhau của các từ có trong xâu.

Input

• Có một dòng duy nhất chứa xâu \(S\) (có ít nhất một từ).

Output

• Dòng 1 ghi số dương \(d\) là số lượng độ dài khác nhau của các từ có trong xâu.
• Dòng thứ \(i\) trong \(d\) dòng tiếp theo mỗi dòng ghi hai số \(x\) và \(y\), trong đó \(x\) là độ dài của từ và \(y\) là số từ có độ dài tương ứng là \(x\). Giá trị \(x\) trên mỗi dòng tăng dần theo độ dài của từ.

Example

Ky thi HSG THCS 2026

3
2 1
3 2
4 2

Scoring

Có \(n\) hộp quà, các hộp quà được đánh số từ 1 đến \(n\), hộp thứ \(i\) có giá trị \(a_i\) (\(1 \le a_i \le m\)). Lớp Nam được cô giáo giao nhiệm vụ chuẩn bị \(K\) giỏ quà từ \(n\) hộp quà đã có, tuân thủ tất cả các quy tắc sau:

• Mỗi giỏ quà gồm hai hộp quà;
• Hộp quà thứ nhất được lấy từ các hộp quà có chỉ số từ 1 đến \(K\), hộp quà thứ 2 được lấy từ các hộp quà có chỉ số từ \(K+1\) đến \(n\);
• Hộp quà thứ nhất có giá trị nhỏ hơn hộp quà thứ 2.

Ví dụ: Cho các hộp quà có giá trị lần lượt như sau: 2 1 4 2 3 2 4 5 2 3. Nam có thể ghép được 4 hộp quà có giá trị 2 1 4 2 với 6 hộp quà có giá trị 3 2 4 5 2 3 tạo thành 4 giỏ quà được ghép là \(\{(2, 3), (1, 2), (4, 5), (2, 3)\}\).

Yêu cầu: Cho \(n\) hộp quà có giá trị \(a_1, a_2, ..., a_n\), hãy tìm \(K\) lớn nhất theo quy tắc trên.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \le n \le 10^5, 1 \le m \le 10^9\));
• Dòng tiếp theo ghi \(n\) số nguyên dương \(a_i\) (\(1 \le a_i \le m\));

Các số trong tệp cách nhau bởi dấu cách.

Output

• In ra số \(K\) lớn nhất tìm được, nếu không có nghiệm thì in ra -1.

Example

10 5
2 1 4 2 3 2 4 5 2 3

4

5 6
5 4 2 1 2

-1

3 3
1 2 3

1

Scoring

• Subtask \(1\) (\(2{,}0\) điểm): \(1 \le n \le 100, 1 \le m \le 10^3\)
• Subtask \(2\) (\(1{,}5\) điểm): \(100 \le n \le 5 \cdot 10^3, 1 \le m \le 10^9\)
• Subtask \(3\) (\(1{,}5\) điểm): Không ràng buộc gì thêm

Cho dãy \(A\) gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\). Một đoạn con liên tiếp của dãy \(A\) là đoạn \(a_l, a_{l+1}, ..., a_r\) với \(1 \le l \le r \le n\), giá trị đoạn con là độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của đoạn con. Giá trị của dãy số là tổng giá trị tất cả các đoạn con liên tiếp của dãy.

Yêu cầu: Với dãy số nguyên \(a_1, a_2, ..., a_n\) có \(n\) phần tử, hãy tính giá trị của dãy số.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(|a_i| \le 10^7\)). Các số cách nhau bởi dấu cách.

Output

• In ra một số nguyên duy nhất là giá trị của dãy số.

Example

3
2 4 1

8

Scoring

• Subtask \(1\) (\(1{,}5\) điểm): \(1 \le n \le 100\).
• Subtask \(2\) (\(1{,}5\) điểm): \(1 \le n \le 3000\).
• Subtask \(3\) (\(2{,}0\) điểm): Không ràng buộc gì thêm.