THT C2 Vòng Sơ loại Toàn quốc 2026 - Lần 2

Cho một số tự nhiên \(N\). Bạn được phép hoán vị (sắp xếp lại) vị trí các chữ số của \(N\) để tạo thành một số tự nhiên mới.

Yêu cầu

Hãy tìm số tự nhiên có giá trị nhỏ nhất có thể tạo thành sao cho số đó chia hết cho \(36\) và không có chữ số \(0\) vô nghĩa ở đầu. Nếu không thể tạo ra bất kỳ số nào thỏa mãn điều kiện, hãy in ra \(-1\).

Input

• Gồm một dòng duy nhất chứa số tự nhiên \(N\). Số lượng chữ số của \(N\) nằm trong khoảng từ \(1\) đến \(10^5\) chữ số.

Output

• Ghi ra một số duy nhất là kết quả của bài toán (số nhỏ nhất chia hết cho \(36\) được tạo thành). Nếu không tồn tại số thỏa mãn, in ra \(-1\).

Example

432

324

30312

10332

123

-1

Constraints

• Có \(80\%\) số test tương ứng với \(80\%\) số điểm thỏa mãn: Giá trị của \(N \leq 10^9\).
• \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho một số nguyên dương \(S\). Xét bài toán biểu diễn số \(S\) bằng tổng của các số nguyên dương phân biệt được chọn trong đoạn từ \(1\) đến \(N\) (mỗi số được sử dụng tối đa một lần).

Lưu ý: Hai cách biểu diễn được coi là khác nhau nếu và chỉ nếu tồn tại một số hạng có mặt trong cách này nhưng không có mặt trong cách kia. Ví dụ, xét các phương án biểu diễn số \(7\) là: \(7 = 3 + 4 = 4 + 3 = 1 + 2 + 4\).

• Phương án 1 (\(3 + 4\)) và phương án 2 (\(4 + 3\)) không được xem là khác nhau vì chúng có chung tập các số hạng là \(\{3, 4\}\).
• Phương án 3 (\(1 + 2 + 4\)) khác với hai phương án trên vì tập hợp các số hạng của nó là \(\{1, 2, 4\}\).

Yêu cầu: Bạn hãy tìm và in ra đúng \(K\) cách biểu diễn khác nhau cho bài toán trên.

Input

• Gồm một dòng duy nhất chứa ba số nguyên dương \(N, K, S\), các số được viết cách nhau bởi khoảng trắng.

Output

• In ra đúng \(K\) dòng, mỗi dòng là một phương án biểu diễn.
• Trên mỗi dòng, ghi danh sách các số hạng của tổng cách nhau bởi khoảng trắng, và phải kết thúc bằng số \(0\).
• Các số hạng trong cùng một dòng có thể được in ra theo thứ tự tùy ý. Các phương án biểu diễn cũng có thể in ra theo thứ tự tùy ý.
• Dữ liệu đảm bảo rằng luôn có ít nhất \(K\) phương án biểu diễn hợp lệ thỏa mãn yêu cầu của bài toán.

Example

6 4 10

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

Scoring

• Các hằng số thỏa mãn: \(1 \le N \le 10^4\); \(1 \le S \le 10^8\).
• Subtask \(1\) (\(40\%\) số điểm): \(K = 1\).
• Subtask \(2\) (\(30\%\) số điểm): \(K = 2\).
• Subtask \(3\) (\(30\%\) số điểm): \(K \le 1000\).

Cho một đồ thị đầy đủ gồm \(n\) đỉnh. Mỗi đỉnh \(i\) (\(1 \le i \le n\)) được gán một nhãn là số nguyên dương \(a_i\). Khoảng cách (hay trọng số cạnh) nối giữa hai đỉnh \(i\) và \(j\) bất kỳ được định nghĩa bằng giá trị tuyệt đối của hiệu hai nhãn: \(|a_i - a_j|\).

Yêu cầu: Hãy tìm một đường đi đi qua tất cả \(n\) đỉnh, mỗi đỉnh đi qua đúng một lần, sao cho tổng độ dài (tổng khoảng cách giữa các đỉnh kề nhau) trên đường đi này đạt giá trị lớn nhất có thể.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\), các số cách nhau bởi khoảng trắng.

Output

• Gồm một dòng duy nhất chứa \(n\) số nguyên phân biệt từ \(1\) đến \(n\), thể hiện thứ tự các đỉnh (chỉ số của đỉnh) trên đường đi tìm được. Nếu có nhiều đường đi cùng đạt tổng độ dài lớn nhất, bạn có thể in ra một phương án bất kỳ.

Example

3
1 2 3

1 3 2

Constraints

• \(1 \le n \le 30000\); \(1 \le a_i \le 10^9\).
• Subtask \(1\) (\(25\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(75\%\) số điểm): Không có ràng buộc nào thêm.

Trong hội trại năm nay, trường của Alice tổ chức một trò chơi đi tìm thông điệp. Theo bản đồ hướng dẫn của Ban tổ chức, các bạn học sinh sẽ tìm đến \(3\) địa điểm. Tại mỗi địa điểm, các bạn nhận được một phong bì chứa một tấm thiệp. Trên thiệp ghi một xâu ký tự gồm các chữ cái in thường, và cả \(3\) xâu đều có cùng độ dài \(n\).

Gọi xâu trong phong bì thứ nhất là \(X\), xâu trong phong bì thứ hai là \(Y\) và xâu trong phong bì thứ ba là \(Z\). Thông điệp mà các bạn học sinh cần tìm là \(3\) xâu \(A, B\) và \(C\) được giấu trong \(3\) xâu \(X, Y, Z\) theo quy tắc sau:

• Xâu \(X\) có dạng *A*B*;
• Xâu \(Y\) có dạng *C*A*;
• Xâu \(Z\) có dạng *B*C*.

Trong đó, dấu * đại diện cho một xâu bất kỳ, có thể là xâu rỗng. Các xâu \(A, B\) và \(C\) hoàn toàn có thể là xâu rỗng.

Ví dụ: Nếu có thông điệp \(A =\) "ab", \(B =\) "cd", \(C =\) "ef" thì:

• \(X\) có thể là "oabgcdpo" (chứa "ab" là \(A\), rồi đến "cd" là \(B\));
• \(Y\) có thể là "hefhabro" (chứa "ef" là \(C\), rồi đến "ab" là \(A\));
• \(Z\) có thể là "kcdjefgh" (chứa "cd" là \(B\), rồi đến "ef" là \(C\)).

Yêu cầu: Cho trước ba xâu \(X, Y\) và \(Z\). Hãy tìm \(3\) xâu \(A, B\) và \(C\) thỏa mãn điều kiện giấu thông điệp sao cho tổng độ dài của cả \(3\) xâu \((|A| + |B| + |C|)\) là lớn nhất có thể.

Input

• Dòng đầu tiên ghi số nguyên \(n\) (\(n \ge 2\));
• Dòng thứ hai chứa xâu \(X\);
• Dòng thứ ba chứa xâu \(Y\);
• Dòng thứ tư chứa xâu \(Z\).

(Dữ liệu đảm bảo tất cả các xâu đều có độ dài đúng bằng \(n\) và chỉ gồm các chữ cái latin in thường).

Output

• Ghi ra một số nguyên duy nhất là tổng độ dài lớn nhất của \(3\) xâu \(A, B\) và \(C\) tìm được.

Example

3
abc
cde
dea

2

4
agtb
icea
tbhc

4

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm của bài thỏa mãn: \(n \le 200\);
• \(80\%\) số test còn lại tương ứng với \(80\%\) số điểm của bài thỏa mãn: \(n \le 2000\).