Đề Chung kết OLP MTTN mùa 4

Đan định nghĩa một bảng số kích thước \(3 \times 3\) được gọi là bảng đẹp nếu tổng mỗi hàng, tổng mỗi cột đều bằng nhau và bảng có ít nhất hai phần tử có giá trị khác nhau.

Yêu cầu: Cho một bảng số kích thước \(3 \times 3\), hãy kiểm tra xem bảng số có phải là bảng đẹp hay không?

Input

• Gồm ba dòng, mỗi dòng gồm ba số nguyên có giá trị tuyệt đối không vượt quá \(10^{9}\).

Output

• In một dòng chứa xâu YES hoặc NO tương ứng cho câu trả là là bảng đẹp hoặc không phải là bảng đẹp.

Example

1 2 3
2 3 1
3 1 2

YES

1 1 1
1 1 1
1 1 1

NO

Đan là người thắng cuộc trong một kì thi lập trình và được nhận các phần thưởng theo cách sau: Ban tổ chức chuẩn bị n món quà, các món quà được đánh số từ \(1\) đến \(n\), món quà thứ \(i\) \((1 \leq i \leq n)\) có khối lượng \(w_{i}\) với giá trị \(v_{i}\) và cho phép Đan chọn lấy một số món quà nhưng tổng khối lượng các món quà không được vượt quá \(S\). Đan mong muốn chọn các món quà thỏa mãn yêu cầu của Ban tổ chức mà tổng giá trị là lớn nhất. Tuy nhiên, điều này rất khó để thực hiện tối ưu. Do đó, khi chọn các món quà xong, Ban tổ chức cho Đan thêm một cơ hội, Đan có thể lập trình để tìm một phương án bỏ chọn một món quà và thay bằng một món quà chưa chọn khác mà tổng khối lượng tất cả các món quà chọn vẫn không vượt quá \(S\). Tất nhiên, Đan cũng có quyền không đổi, giữ nguyên các món quà đã chọn.

Yêu cầu: Cho thông tin các món quà và phương án mà Đan đã chọn, hãy tính tổng giá trị lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, S\) \((S \leq 10^{9})\)
• Dòng thứ \(i\) \((1 \leq i \leq n)\) trong \(n\) dòng tiếp theo chứa hai số nguyên dương \(w_{i}, v_{i}, c_{i}\) (\(w_{i},v_{i} \leq 10^{9}\); \(c_{i}\) bằng \(1\) hoặc \(0\) tương ứng món quà thứ \(i\) được chọn hoặc không được chọn trong phương án chọn trước khi được phép đổi chọn một món quà).

Dữ liệu đảm bảo tổng khối lượng các món quà mà Đan đã chọn không vượt quá \(S\).

Output

• In ra chuẩn một dòng chứa một số nguyên là tổng giá trị lớn nhất có thể đạt được.

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^{5}\).

Example

5 13
2 5 0
3 6 1
4 7 1
5 8 1
6 9 0

22

3 10
4 5 1
6 8 1
5 7 0

13

Đan mới tạo ra một trò chơi trên một vòng tròn số như sau: Ban đầu máy tính sẽ tạo ngẫu nhiên \(n\) số nguyên \(a_{0}, a_{1}, \ldots, a_{n - 1}\) và xếp lần lượt từng số lên vòng tròn theo chiều kim đồng hồ (xem ví dụ dưới đây cho vòng tròn 8 số).

Người chơi sẽ vào vai là một chú thỏ và thực hiện các hành động:

Ban đầu chú thỏ sẽ chọn một vị trí \(s\ (0 \leq s < n)\) để xuất phát.

Sau đó, chú thỏ sẽ thực hiện \(k\) lần nhảy \(123\) bắt đầu từ \(s\) theo chiều kim đồng hồ trên vòng tròn. Các vị trí tương ứng với bước nhảy \(1, 3\) chú thỏ sẽ được cộng điểm là số tại vị trí đó, các vị trí tương ứng với bước nhảy \(2\) chú thỏ bị trừ điểm là số tương ứng tại vị trí đó. Chú thỏ cần tìm cách nhảy để đạt được nhiều điểm nhất.

Ví dụ, trong hình trên, với \(s = 1\) và \(k = 2\), ba số được tô màu đỏ \((a_{1}, a_{3}, a_{4})\) tương ứng với lần nhảy \(123\) thứ nhất, ba số được tô màu xanh \((a_{5}, a_{7}, a_{0})\) tương ứng lần nhảy thứ hai.

Tổng điểm chú thỏ nhận được là: \((a_{1} - a_{3} + a_{4}) + (a_{5} - a_{7} + a_{0})\).

Một cách hình thức: Nếu tạo dãy gồm \(n\) số bắt đầu từ phần tử thứ \(s\) theo chiều kim đồng hồ ta nhận được dãy \(b_{0}, b_{1}, \ldots, b_{n - 1}\), trong đó \(b_{0} = a_{s}, b_{1} = a_{(s + 1) \% n}, \ldots, b_{n - 1} = a_{(s + n - 1) \% n}\). Khi đó, cần tìm các chỉ số \(0 \leq x_{1} < y_{1} < z_{1} < x_{2} < y_{2} < z_{2} < \ldots < x_{k} < y_{k} < z_{k} \leq n - 1\) để tổng: \((b_{x_{1}} - b_{y_{1}} + b_{z_{1}}) + (b_{x_{2}} - b_{y_{2}} + b_{z_{2}}) + \ldots + (b_{x_{k}} - b_{y_{k}} + b_{z_{k}})\) đạt giá trị lớn nhất.

Yêu cầu: Cho vòng tròn số và số nguyên dương \(k\), tính điểm lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n, k\) \((3 \times k \leq n)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{0}, a_{1}, \ldots, a_{n - 1}\) \((|a_{i}| \leq 10^{9}\) với \(0 \leq i \leq n - 1)\).

Output

• Ghi ra thiết bị ra chuẩn một số nguyên là giá trị tổng điểm lớn nhất đạt được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20, k = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 2000, k = 1\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 200\).
• Subtask \(5\) (\(20\%\) số điểm): \(n \leq 2000\).

Example

8 2
1 1 0 -1 1 1 0 -1

6

Đan rất yêu thích số học và thường tự thử thách bản thân bằng những bài toán tự nghĩ ra. Một bài toán mà Đan nghĩ ra như sau: Cho số nguyên dương \(n\) và \(k\), cần tính tổng các chữ số của các số tự nhiên không vượt quá \(n\) và chia hết cho \(k\).

Input

• Gồm hai dòng, mỗi dòng chứa hai số nguyên dương \(n,k (k \leq n)\) tương ứng với bộ cần tính.

Output

• In ra hai dòng, mỗi dòng chứa một số nguyên là tổng các chữ số của các số tự nhiên không vượt quá và chia hết cho tương ứng với bộ trong dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 10^{x}\) với \(1 \leq x \leq 12\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^{12}\).

Example

5 2
25 10

6
3