Tuyển sinh lớp 10 Chuyên tỉnh Hà Tĩnh 2026

Một số được gọi là số chẵn kép nếu nó là số chẵn và tổng các chữ số của nó cũng là một số chẵn. Ví dụ số \(4, 20, 26\) là số chẵn kép còn \(5, 12, 17\) không phải là số chẵn kép.

Yêu cầu

Cho hai số nguyên dương \(L\) và \(R\). Hãy cho biết từ \(L\) đến \(R\) có bao nhiêu số chẵn kép.

Input

• Một dòng duy nhất chứa hai số nguyên dương \(L\) và \(R\) (\(1 \le L \le R \le 10^{12}\)), các số ghi cách nhau bởi một dấu cách.

Output

• Một số nguyên duy nhất là số lượng số chẵn kép đếm được.

Constraints

• Có \(70\%\) số test ứng với \(70\%\) số điểm của bài thỏa mãn điều kiện: \(R \le 10^6\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm không có ràng buộc gì thêm.

Example

1 22

6

Ước chung lớn nhất của hai số nguyên dương \(a\) và \(b\) là số nguyên dương \(c\) lớn nhất mà cả \(a\) và \(b\) đều chia hết cho nó.

Cho hai số nguyên dương \(n, k\).

Yêu cầu: Hãy đếm số lượng cặp số nguyên dương \(x, y\) thỏa mãn \(1 \leq x \leq y \leq n\) và có ước chung lớn nhất lớn hơn hoặc bằng \(k\).

Input

• Một dòng duy nhất chứa hai số nguyên dương \(n, k\) (\(1 \leq k < n \leq 10^6\)), các số ghi cách nhau bởi một dấu cách.

Output

• Một số nguyên duy nhất là kết quả của bài toán.

Example

5 2

5

Scoring

• Có \(70\%\) số test ứng với \(70\%\) số điểm của bài thỏa mãn điều kiện: \(n \leq 10^3\).
• Có \(15\%\) số test ứng với \(15\%\) số điểm của bài thỏa mãn điều kiện: \(n \leq 10^6, n - k \leq 10^3\).
• \(15\%\) số test còn lại ứng với \(15\%\) số điểm không có ràng buộc gì thêm.

Trên một con đường thẳng người ta quy hoạch \(n\) vị trí để trồng cây, được đánh số từ \(1\) đến \(n\). Có \(m\) máy phun nước tự động được lắp đặt trên con đường này, máy phun thứ \(i\) (\(1 \le i \le m\)) được thiết lập để cung cấp nước cho các vị trí trong đoạn từ \(l_i\) đến \(r_i\) với lượng nước là \(v_i\) trên mỗi vị trí.

Tổng lượng nước tại một vị trí bằng tổng lượng nước của tất cả các máy phun có phạm vi hoạt động bao trùm vị trí đó.

Một vị trí trồng cây được gọi là đạt chuẩn về độ ẩm nếu tổng lượng nước tại vị trí đó không thấp hơn ngưỡng giá trị \(d\) cho trước.

Yêu cầu: Hãy đếm số lượng vị trí trồng cây đạt chuẩn về độ ẩm.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, d\) (\(1 \le n \le 10^9, 1 \le m \le 10^5, 1 \le d \le 10^{12}\)).
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l_i, r_i, v_i\) (\(1 \le l_i \le r_i \le n, 1 \le v_i \le 10^9\)).

Các số ghi trên một dòng cách nhau bởi một dấu cách.

Output

• Ghi ra một số nguyên duy nhất là kết quả của bài toán.

Example

8 2 10
1 5 7
3 8 5

3

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm của bài thỏa mãn điều kiện: \(n, m \le 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn điều kiện: \(n \le 10^6\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Trong một trò chơi điện tử, bạn An cần đi qua một con đường gồm \(n\) trạm năng lượng được đánh số từ \(1\) đến \(n\). Tại trạm thứ \(i\), An có thể nhận được \(a_i\) đơn vị năng lượng.

Tuy nhiên, để tránh quá tải, An phải tuân theo các quy tắc sau:

• An có thể chọn hoặc bỏ qua mỗi trạm;
• Không được chọn quá \(k\) trạm liên tiếp;
• An có thể không chọn trạm nào.

Yêu cầu: Hãy tính tổng năng lượng lớn nhất mà An có thể nhận được.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \le n \le 10^5, k \le n, 1 \le k \le 20\));
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^6, 1 \le i \le n\)).
  Các số ghi trên một dòng cách nhau bởi một dấu cách.

Output

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

Constraints

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn điều kiện: \(k = 1; 1 \le a_1 < a_2 < \dots < a_n\);
• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thỏa mãn điều kiện: \(k \le 2\);
• Có \(20\%\) số test ứng với \(20\%\) số điểm của bài thỏa mãn điều kiện: \(a_i > 0\) (\(1 \le i \le n\));
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Example

5 1
2 3 5 7 8

15

6 2
5 8 4 10 3 7

30