Tuyển sinh lớp 10 Chuyên tỉnh Bắc Ninh 2026

Tài là học sinh giỏi toán và ham học hỏi. Tài rất thích thú với những cặp số đặc biệt. Cặp số đặc biệt là những cặp số có tổng chia hết cho \(3\).

Cho một dãy \(a\) gồm \(n\) số nguyên dương. Tài muốn biết trong dãy \(a\), có bao nhiêu cặp chỉ số \((i, j)\) với \((1 \le i < j \le n)\) sao cho tổng \(a_i + a_j\) chia hết cho \(3\).

Yêu cầu: Bạn hãy giúp bạn Tài đếm xem có bao nhiêu cặp số này nhé.

Input

• Dòng 1: Chứa số nguyên dương \(n\) (\(1 < n \le 10^5\)).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^6, 1 \le i \le n\)). Các số cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất là số lượng cặp số của dãy \(a\) có tổng chia hết cho \(3\).

Example

7
3 6 8 5 3 5 7

6

5
5 6 8 4 3

3

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 < n \le 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): \(10^3 < n \le 10^5\).

Nhân dịp chào mừng ngày thành lập Đoàn TNCS Hồ Chí Minh, Đoàn trường tổ chức vẽ một bức tranh khổng lồ trên tường rào. Bức tường được chia sẵn thành \(n\) phần liên tiếp nhau. Do độ khó khác nhau, phần tường thứ \(i\) cần thời gian là \(a_i\) phút để vẽ xong. Có \(K\) nhóm học sinh câu lạc bộ mỹ thuật được giao nhiệm vụ hoàn thiện bức tranh này.

Để hoàn thành bức tranh, thầy Bí thư Đoàn trường quyết định chia \(n\) phần tường này thành đúng \(K\) đoạn liên tiếp nhau (mỗi nhóm phụ trách vẽ một đoạn, mỗi đoạn có thể gồm nhiều phần liên tiếp). Thời gian vẽ xong một đoạn là tổng thời gian vẽ các phần trong đoạn đó. Thời gian để hoàn thành bức tranh bằng thời gian vẽ của đoạn lâu nhất trong một cách chia.

Yêu cầu: Bạn hãy giúp thầy Bí thư Đoàn trường tìm thời gian hoàn thành bức tranh nhanh nhất.

Ví dụ: Cho bức tường có \(n = 4\), thời gian lần lượt vẽ các phần là: \(1, 2, 3\) và \(4\) phút. Với \(K = 3\) thì có các cách chia như sau:

• Cách 1: \((1), (2), (3, 4)\): Thời gian hoàn thành bức tranh là \(7\) phút;
• Cách 2: \((1), (2, 3), (4)\): Thời gian hoàn thành bức tranh là \(5\) phút;
• Cách 3: \((1, 2), (3), (4)\): Thời gian hoàn thành bức tranh là \(4\) phút.

Vậy thời gian hoàn thành bức tranh nhanh nhất là \(4\) phút.

Input

• Dòng 1: Chứa hai số nguyên dương \(n\) và \(K\).
• Dòng 2: Chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^9\)). Các số cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất thỏa mãn yêu cầu của bài toán.

Example

4 3
1 2 3 4

4

Scoring

• \(30\%\) số điểm tương ứng số test có \(n \le 10^3\) và \(K = 2\).
• \(40\%\) số điểm tương ứng số test khác có \(n \le 10^3\) và \(K = 3\).
• \(30\%\) số điểm tương ứng số test khác có \(n \le 10^5\) và \(K \le n\).

Cho hình chữ nhật kích thước \(m \cdot n\) (\(m\) hàng, \(n\) cột) được chia thành lưới các ô vuông đơn vị. Các hàng được đánh số từ \(1\) đến \(m\), từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\), từ trái qua phải. Ô nằm trên hàng \(i\), cột \(j\) gọi là ô \((i, j)\) và chứa giá trị \(a_{i,j}\) (\(1 \le a_{i,j} \le 10^6, 1 \le i \le m, 1 \le j \le n\)). Gọi trọng số của một hình vuông con được tính bằng giá trị của số nhỏ nhất trong hình vuông con đó.

Yêu cầu: Với số nguyên dương \(k\) cho trước, hãy tìm trọng số lớn nhất trong số các hình vuông con kích thước \(k \cdot k\).

Input

• Dòng 1: Chứa ba số nguyên dương \(m, n, k\) (\(1 \le m, n \le 1000; k \le m; k \le n\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương \(a_{i,j}\), thể hiện lưới hình chữ nhật. Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất thoả mãn yêu cầu bài toán.

Example

4 6 2
1 3 2 3 3 4
2 2 2 2 2 3
3 5 4 3 2 4
4 5 6 5 3 5

4

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(1 \le m, n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(100 < m, n \le 1000\).

Nhân dịp kỷ niệm 100 năm ngày thành lập công ty, để ghi nhận sự cống hiến của các thành viên, công ty tổ chức chương trình trao thưởng cho tất cả các nhân viên. Ban tổ chức chuẩn bị sẵn \(n\) hộp phần thưởng, mỗi hộp được đặt trên một bàn, các bàn đánh số từ \(1\) đến \(n\). Trên hộp phần thưởng thứ \(i\) (\(i = 1 \dots n\)) có dán nhãn là \(a_i\) và trong đó có phần thưởng trị giá \(w_i\).

Nhân viên có thể chọn một hay nhiều hộp phần thưởng liên tiếp hay không liên tiếp từ hộp phần thưởng ở bàn \(1\) đến bàn \(n\), hộp phần thưởng chọn sau phải có nhãn lớn hơn nhãn trên hộp phần thưởng chọn trước, tức là:

Yêu cầu: Bạn hãy giúp nhân viên chọn cho mình các hộp phần thưởng để có tổng trị giá là lớn nhất.

Input

• Dòng 1: Chứa số nguyên dương \(n\) (\(n \le 5 \cdot 10^5\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) (\(i = 1 \dots n\)) chứa hai số nguyên dương \(a_i\) (\(a_i \le 10^9\)) và \(w_i\) (\(w_i \le 10^9\)). Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

• Một số nguyên duy nhất thỏa mãn yêu cầu bài toán.

Example

4
1 5
1 3
5 6
5 7

12

Scoring

• Subtask 1 (60% số điểm): \(n \le 10^3\).
• Subtask 2 (40% số điểm): \(10^3 < n \le 5 \cdot 10^5\).