Thi thử đợt 3 tuyển sinh lớp 10 Chuyên KHTN 2026

Cho một dãy gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) và một số nguyên dương \(k\).
Hãy tìm tổng của tất cả các phần tử trong dãy chia hết cho \(k\). Nếu không có phần tử nào chia hết cho \(k\), in ra \(0\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) (\(1 \le n \le 10^5, 1 \le k \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng của các phần tử chia hết cho \(k\).

Example

5 3
6 7 9 2 12

27

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Một cửa hàng có \(4\) loại nguyên liệu và \(4\) công thức. Mỗi nguyên liệu có một chỉ số chất lượng \(a_i\) và mỗi công thức có một hệ số khó \(b_j\). Khi kết hợp nguyên liệu \(i\) với công thức \(j\), điểm thành phẩm được tính bằng công thức:

Bạn được chọn đúng một nguyên liệu và đúng một công thức. Hãy tìm điểm thành phẩm lớn nhất có thể.

Input

• Dòng thứ nhất chứa \(4\) số nguyên \(a_1, a_2, a_3, a_4\) (\(-10^9 \le a_i \le 10^9\)).
• Dòng thứ hai chứa \(4\) số nguyên \(b_1, b_2, b_3, b_4\) (\(-10^9 \le b_j \le 10^9\)).

Output

• In ra một số duy nhất là điểm thành phẩm lớn nhất có thể.

Example

3 -2 5 1
3 -5 7 1

35

Scoring

• Thời gian: \(1\) giây, Bộ nhớ: \(256\) MB.
• Subtask \(1\) (\(20\%\) số điểm): \(-10 \le a_i \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(-10^3 \le a_i \le 10^3\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Bạn có ba chiếc cốc có dung tích lần lượt là \(A, B\) và \(C\) lít. Ban đầu, cốc \(1\) chứa đầy nước (\(A\) lít), cốc \(2\) và cốc \(3\) đều rỗng.

Bạn được cho một danh sách gồm \(N\) thao tác. Mỗi thao tác có dạng u v (\(1 \le u, v \le 3, u \neq v\)), nghĩa là rót nước từ cốc \(u\) sang cốc \(v\). Khi rót, bạn rót cho đến khi cốc \(u\) hết nước hoặc cốc \(v\) đầy, tùy điều kiện nào xảy ra trước.

Hãy in ra lượng nước trong ba cốc sau khi thực hiện xong tất cả các thao tác.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(A, B, C\) (\(1 \le A, B, C \le 10^9\)) — dung tích của ba cốc.
• Dòng thứ hai chứa một số nguyên dương \(N\) (\(1 \le N \le 10^5\)) — số lượng thao tác.
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le 3, u \neq v\)).

Output

• In ra ba số nguyên trên một dòng, cách nhau bởi dấu cách: lượng nước trong cốc \(1\), cốc \(2\) và cốc \(3\).

Example

10 7 3
5
1 2
2 3
3 1
2 3
1 2

0 7 3

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

3 3 0

Scoring

• \(30\%\) số test có ràng buộc bổ sung: tất cả thao tác chỉ liên quan đến cốc \(1\) và cốc \(2\) (\(u, v \in \{1, 2\}\)).
• \(30\%\) số test khác có ràng buộc bổ sung: \(N \le 100\).
• \(40\%\) số test còn lại không có ràng buộc bổ sung.

Một nông trại có \(N\) thửa ruộng xếp thành một hàng, thửa thứ \(i\) có giá trị thu hoạch là \(a_i\) (có thể âm, nghĩa là thửa đó bị sâu bệnh và gây thiệt hại nếu thu hoạch).

Bạn muốn chọn một số thửa để thu hoạch sao cho tổng giá trị lớn nhất có thể. Tuy nhiên, sau khi thu hoạch một thửa, máy gặt cần thời gian bảo trì nên bạn phải bỏ qua ít nhất \(K\) thửa liền kề tiếp theo trước khi thu hoạch thửa tiếp.

Nói cách khác, nếu bạn thu hoạch thửa \(i\), thửa tiếp theo bạn được phép thu hoạch sớm nhất là thửa \(i + K + 1\). Bạn cũng có thể chọn không thu hoạch thửa nào (tổng \(= 0\)).

Hãy tìm tổng giá trị thu hoạch lớn nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \le N \le 10^6, 0 \le K \le N-1\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_n\) (\(-10^9 \le a_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng giá trị thu hoạch lớn nhất.

Example

5 1
3 1 5 2 8

16

6 2
5 -3 4 -1 6 2

11

4 1
-5 -3 -1 -4

0

Scoring

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

Kiên đang đi du lịch trên hòn đảo cá nhân của Khôi Anh. Ở giữa hòn đảo có một ngôi đền trông rất đẹp, Kiên rất mong muốn được vào tham quan nhưng ngay trước cổng vào có \(T\) câu đố. Mỗi câu đố cho hai số nguyên \(0 \le L \le R \le 10^{100000}\), yêu cầu tìm số số tự nhiên \(x\) thỏa mãn \(2^x\) có cùng số dư với \(x^2\) khi chia cho \(7\) và \(L \le x \le R\).

Tuy nhiên, Kiên lại không giỏi trong việc giải những câu đố nên nhờ bạn giúp. Bạn hãy giúp Kiên nhé.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương subtask_id (\(1 \le \text{subtask\_id} \le 4\)) và số lượng câu đố \(T\) (\(1 \le T \le 100\)).
• \(T\) dòng tiếp theo mỗi dòng gồm \(2\) số tự nhiên \(L, R\) (\(0 \le L \le R \le 10^{100000}\)).

Output

• In ra \(T\) dòng, mỗi dòng gồm \(1\) số nguyên là số lượng giá trị \(x\) thỏa mãn điều kiện của câu đố tương ứng.

Example

1 2
0 20
36 67

6
9

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0 \le L \le R \le 10^5\).
• Subtask \(2\) (\(20\%\) số điểm): \(0 \le L \le R \le 10^{18}\) và \(R - L + 1 \le 10^5\).
• Subtask \(3\) (\(50\%\) số điểm): \(0 \le L \le R \le 10^{18}\).
• Subtask \(4\) (\(10\%\) số điểm): \(0 \le L \le R \le 10^{100000}\).

Trong lúc dạo quanh trên hòn đảo của Khôi Anh, Kiên phát hiện một căn hầm bỏ hoang đầy bí ẩn với vô vàn những viên đá quý lấp lánh. Tuy nhiên, Kiên chỉ mang theo một chiếc túi nhỏ chứa được tối đa \(S\) kg, trong khi căn phòng lại có tới \(n\) viên đá quý với viên thứ \(i\) có khối lượng \(w_i\) kg và có giá trị là \(v_i\) tiền. Vì muốn kiếm tiền nhưng lười biếng, Kiên nhờ bạn hãy giúp anh ấy chọn đá vào túi sao cho mỗi viên đá chỉ được lấy một lần mà đồng thời kiếm được nhiều lợi nhuận nhất.

Input

• Dòng đầu gồm 3 số \(subtask\_id, n, S\) là số thứ tự của subtask, số viên đá trong phòng và tải trọng tối đa của túi (\(1 \le subtask\_id \le 3\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) gồm một cặp số \((w_i, v_i)\) biểu thị khối lượng và giá trị của từng viên đá.

Output

• In ra một số thực là số tiền tối đa có thể kiếm được, làm tròn đến 6 chữ số sau dấu phẩy.

Constraints

• Subtask 1 (20% số điểm): \(n, S, w_i, v_i\) là các số nguyên. \(1 \le n \le 100, 0 \le S \le 10^5, 1 \le w_i, v_i \le 10^9\).
• Subtask 2 (40% số điểm): \(n\) là số nguyên. \(S, w_i, v_i\) là các số thực. \(1 \le n \le 100, 0 \le S \le 10^5, 1 \le w_i, v_i \le 10^9\). Tuy nhiên, trong \(n\) giá trị là số thực \(w_i\), luôn tồn tại \(n - 1\) giá trị \(w_i\) là số nguyên. Các số thực có tối đa 6 chữ số thập phân sau dấu phẩy.
• Subtask 3 (40% số điểm): \(n\) là số nguyên. \(S, w_i, v_i\) là số thực. \(1 \le n \le 36, 0 \le S \le 10^{18}, 1 \le w_i, v_i \le 10^9\). Các số thực có tối đa 6 chữ số thập phân sau dấu phẩy.

Example

1 5 67
67 90
40 61
26 41
66 101
6 7

102.000000