LQDOJ CUP 2025 - Final Round

Cho hai số nguyên dương \(n\) và \(k\) (\(3 \le n \le 20\), \(k < 2^n\)). Ta dựng một cây nhị phân hoàn hảo có độ cao \(n\), đồng nghĩa với việc nó sẽ có \(2^n - 1\) đỉnh. Ban đầu tất cả các cạnh của cây đều được tô màu đỏ. Sau đó, ta thực hiện tuần tự \(k\) thao tác, mỗi thao tác ta được phép chọn một trong hai loại biến đổi sau đây vào cây:

1. Chọn một đỉnh \(u\) không phải nút lá. Tô màu xanh vào cạnh nối \(u\) với nút con bên trái của \(u\).
2. Chọn một đỉnh \(u\) không phải nút lá. Tô màu xanh vào cả hai cạnh nối \(u\) với nút con bên trái và bên phải của \(u\).

Lưu ý rằng ta có thể chọn cùng một đỉnh \(u\) cho nhiều thao tác khác nhau. Nếu một cạnh đã được tô màu xanh thì sau khi tô màu xanh lần nữa, nó vẫn sẽ mang màu xanh.

Yêu cầu: Gọi \(B\) là tập hợp các cạnh được tô màu xanh sau khi thực hiện xong tất cả \(k\) thao tác. Hãy tính số lượng tất cả các tập \(B\) khả dĩ khác nhau. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9 + 7\).

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương \(n\) và \(k\) (\(3 \le n \le 20\), \(k < 2^n\)).

Output

• In ra một số duy nhất là phần dư trong phép chia số lượng tập hợp cần tìm cho \(1000000007\) (\(10^9 + 7\)).

Example

3 1

6

Scoring

• Subtask \(1\) (\(17.5\) điểm): \(n \le 3\).
• Subtask \(2\) (\(25\) điểm): \(n \le 10\).
• Subtask \(3\) (\(32.5\) điểm): \(n \le 15\).
• Subtask \(4\) (\(25\) điểm): \(n \le 20\).

Mario đã cứu được công chúa. Trước mặt họ là một hồ lớn dạng lưới \(n \times m\) ô vuông (đánh số hàng từ \(1\) đến \(n\), cột từ \(1\) đến \(m\)). Trên một số ô có cọc và các ô còn lại là nước. Hồ nước thoả mãn rằng với mọi ô nước \((x, y)\), tồn tại ít nhất một cọc ở một trong các ô \((x + 1, y + 1)\); \((x + 1, y - 1)\); \((x - 1, y + 1)\); \((x - 1, y - 1)\). Mỗi cọc mang một trong hai màu trắng hoặc đen.

Biết rằng Mario đang đứng trên cọc tại ô \((1, 1)\) và công chúa đang đứng trên cọc tại ô \((1, 2)\). Từ ô \((x, y)\) có cọc, nhân vật có thể nhảy qua \(1\) ô có cọc khác ở các vị trí: \((x + 2, y)\); \((x - 2, y)\); \((x, y + 2)\); \((x, y - 2)\); \((x + 2, y + 2)\); \((x + 2, y - 2)\); \((x - 2, y + 2)\); \((x - 2, y - 2)\).

Hai nhân vật có nhiệm vụ thăm tất cả các cọc hiện có trên hồ (mỗi cọc được ghé thăm bởi ít nhất một người). Biết rằng với dữ liệu đầu vào, việc thăm hết các cọc là khả thi.

Khi nhiệm vụ hoàn tất, tất cả các ô nước sẽ mọc lên các cọc, biến cả hồ thành bình địa \(n \times m\) toàn cọc, sẵn sàng cho lễ cưới. Các cọc vừa mọc lên đều chưa có màu; Mario sẽ tô màu trắng hoặc đen cho chúng. Các cọc đã có màu ban đầu phải được giữ nguyên.

Yêu cầu: Công chúa có \(q\) khu vực yêu thích, mỗi khu vực là một hình vuông \(2 \times 2\) xác định bởi tọa độ góc trên–trái \((r_i, c_i)\) (\(1 \le r_i < n\), \(1 \le c_i < m\)). Với mỗi khu vực \(2 \times 2\) này, không được phép tô toàn đen, toàn trắng, hoặc đan xen kiểu bàn cờ vua (hai màu xen kẽ theo ô chéo). Hãy giúp Mario tìm một phương án tô màu hợp lệ cho các cọc sau khi chúng mọc lên. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Input

• Dòng đầu chứa hai số nguyên \(n, m\) (\(2 \le n, m \le 1000\)).

• Mỗi dòng trong số \(n\) dòng tiếp theo chứa một xâu \(m\) ký tự mô tả trạng thái ban đầu của hồ:

  • . — ô nước (chưa có cọc).
  • W — ô có cọc màu trắng.
  • B — ô có cọc màu đen.

  Bảo đảm ô \((1, 1)\) và \((1, 2)\) là ký tự W hoặc B.

• Dòng tiếp theo chứa số nguyên \(q\) (\(0 \le q \le (n - 1)(m - 1)\)).

• Mỗi dòng trong số \(q\) dòng tiếp theo chứa hai số nguyên \(r_i, c_i\) là tọa độ góc trên–trái của một khu vực \(2 \times 2\) yêu thích (\(1 \le r_i < n\), \(1 \le c_i < m\)).

Output

• In ra \(n\) dòng, mỗi dòng là một xâu \(m\) ký tự gồm W hoặc B, biểu diễn phương án tô màu cuối cùng.
• Nếu không tồn tại cách tô màu thoả mãn, in ra -1.

Example

3 2
WB
..
BW
2
2 1
1 1

WB
WW
BW

Scoring

• Subtask \(1\) (\(10\) điểm): \(n \times m \le 20\).
• Subtask \(2\) (\(10\) điểm): \(n = 2\).
• Subtask \(3\) (\(15\) điểm): \(n \le 10\).
• Subtask \(4\) (\(15\) điểm): \(n \le 15\).
• Subtask \(5\) (\(20\) điểm): Dữ liệu đảm bảo các cọc nằm trên cùng cột thì có màu giống nhau.
• Subtask \(6\) (\(30\) điểm): Không có ràng buộc nào thêm.

Chính phủ đang triển khai một dự án quy hoạch giao thông quốc gia, bao gồm \(n\) tỉnh thành độc lập. Hiện tại, giữa các tỉnh chưa có tuyến đường nào được xây dựng.

Bộ Giao thông đã đề xuất \(m\) tuyến đường hai chiều tiềm năng. Mỗi tuyến nối hai tỉnh khác nhau và cần một khoản kinh phí nhất định để thi công. Tỉnh \(i\) có thể tự huy động tối đa \(c_i\) tỷ đồng cho dự án. Tuyến đường thứ \(j\) nối giữa hai tỉnh \(v_j\) và \(u_j\), với chi phí thi công là \(w_j\) tỷ đồng. Các tỉnh có thể góp ngân sách lại để cùng xây dựng đường. Khi hai tỉnh (hoặc hai cụm tỉnh đã kết nối) xây xong một tuyến đường, họ trở thành một liên vùng chung, và toàn bộ ngân sách còn lại của liên vùng sẽ được hợp nhất.

Nguyên tắc tài chính khi xây dựng:

• Một tuyến đường chỉ có thể được xây nếu tổng ngân sách hiện có của hai liên vùng liên quan lớn hơn hoặc bằng chi phí \(w_j\).
• Sau khi xây xong, hai liên vùng được hợp nhất, và ngân sách còn lại bằng tổng hai bên trừ đi \(w_j\).

Yêu cầu: Xác định xem có thể chọn một tập hợp các tuyến đường và sắp xếp thứ tự thi công sao cho tất cả các tỉnh đều được kết nối giao thông với nhau hay không. Nếu có thể, hãy đưa ra thứ tự các tuyến cần thi công.

Input

• Dòng đầu chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^6\), \(0 \le m \le 10^6\)) là số tỉnh thành và số tuyến đường được đề xuất.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \ldots, c_n\) (\(1 \le c_i \le 10^6\)) là ngân sách hiện có của mỗi tỉnh.
• Mỗi dòng trong \(m\) dòng tiếp theo chứa ba số nguyên \(v_i, u_i, w_i\) (\(1 \le v_i, u_i \le n\), \(1 \le w_i \le 10^6\)) là hai tỉnh được nối và chi phí thi công tuyến đường giữa chúng (các tuyến đường được đánh số thứ tự từ \(1\) đến \(m\) theo thứ tự xuất hiện).

Output

• Nếu không thể thi công đủ tuyến để kết nối toàn bộ đất nước, in ra -1.
• Nếu có thể:
  • Dòng đầu tiên in ra số lượng tuyến đường \(q\) được thi công.
  • Dòng tiếp theo in ra \(q\) số nguyên là chỉ số của các tuyến đường theo đúng thứ tự thi công.

Example

3 2
2 2 10
1 2 5
2 3 8

2
2 1

Scoring

• Subtask \(1\) (\(10\) điểm): \(n, m \le 10\).
• Subtask \(2\) (\(15\) điểm): \(n, m \le 10^5\) và \(c_i = 1\).
• Subtask \(3\) (\(15\) điểm): \(n, m \le 10^5\) và tất cả \(w_i\) bằng nhau.
• Subtask \(4\) (\(15\) điểm): \(n, m \le 10^3\).
• Subtask \(5\) (\(20\) điểm): \(n, m \le 10^5\).
• Subtask \(6\) (\(25\) điểm): Không có ràng buộc nào thêm.

Mỗi chiếc chìa khóa có \(n\) rãnh đánh số từ \(0\), rãnh thứ \(i\) có độ sâu \(A[i]\) là một số nguyên không âm \(60\)-bit.
Bạn muốn đánh ra một chiếc chìa sơ cua, nhưng vì nhìn bằng mắt thường không thể xác định vẽ lại chính xác độ sâu của từng rãnh, vì thế phải đưa vào dụng cụ đo. Nói cách khác, ban đầu bạn không biết giá trị của mảng \(A\).

Dụng cụ đo có hai chế độ:

• AND i1 i2 i3: bạn sẽ chọn ra ba vị trí rãnh thỏa mãn \(0 \le i_1 < i_2 < i_3 < n\), và chìa khóa sẽ trả về \(A[i_1] \ \& \ A[i_2] \ \& \ A[i_3]\) là giá trị của phép AND ba số.
• OR i1 i2 i3: bạn sẽ chọn ra ba vị trí rãnh thỏa mãn \(0 \le i_1 < i_2 < i_3 < n\), và chìa khóa sẽ trả về \(A[i_1] \ | \ A[i_2] \ | \ A[i_3]\) là giá trị của phép OR ba số.

Biết rằng:

• Mỗi số nguyên không âm \(60\)-bit \(X\) luôn tồn tại một bộ số nhị phân \((x_{59}, x_{58}, x_{57}, \dots, x_1, x_0)\) duy nhất sao cho \(\forall i, 0 \le i < 60 : 0 \le x_i \le 1\) và

  \[ X = \sum_{i=0}^{59} (x_i \cdot 2^i) \]

• Giả sử hai số \(X\) và \(Y\) có bộ số tương ứng là \((x_{59}, x_{58}, x_{57}, \dots, x_1, x_0)\) và \((y_{59}, y_{58}, y_{57}, \dots, y_1, y_0)\). Khi đấy:

  • \(Z = X \ \& \ Y\) được biểu diễn bởi bộ số \((z_{59}, z_{58}, z_{57}, \dots, z_1, z_0)\) thỏa mãn \(\forall i, 0 \le i < 60\): \(z_i = 1\) nếu \(x_i = 1\) và \(y_i = 1\), ngược lại \(z_i = 0\).
  • \(Z' = X \ | \ Y\) được biểu diễn bởi bộ số \((z'_{59}, z'_{58}, z'_{57}, \dots, z'_1, z'_0)\) thỏa mãn \(\forall i, 0 \le i < 60\): \(z'_i = 0\) nếu \(x_i = 0\) và \(y_i = 0\), ngược lại \(z'_i = 1\).
• Phép AND và OR đều có tính chất giao hoán và kết hợp: \(X \ \& \ Y = Y \ \& \ X\) và \((X \ \& \ Y) \ \& \ Z = X \ \& \ (Y \ \& \ Z)\), tương tự với phép OR.

Có \(\tau\) chiếc chìa khóa như vậy. Với mỗi chìa khóa, bạn hãy tìm cách dùng ít lần đo nhất để xác định được chính xác hình dáng của các rãnh khóa.

Tương tác

Bạn cần cài đặt hàm vector<long long> keyDuplication(int n), mỗi lần gọi hàm tương ứng với một chiếc chìa khóa có \(n\) rãnh bạn cần xác định độ sâu. Hàm cần trả về một vector<long long> gồm \(n\) phần tử, phần tử thứ \(i\) của vector có giá trị bằng \(A[i]\).

Trong cài đặt của hàm keyDuplication, bạn được phép gọi tới một trong hai hàm sau thuộc thư viện andor.h:

• long long AND(int i1, int i2, int i3) nhận vào ba vị trí theo thứ tự \(i_1, i_2, i_3\), với điều kiện \(0 \le i_1 < i_2 < i_3 < n\), và trả về \(A[i_1] \ \& \ A[i_2] \ \& \ A[i_3]\).
• long long OR(int i1, int i2, int i3) nhận vào ba vị trí theo thứ tự \(i_1, i_2, i_3\), với điều kiện \(0 \le i_1 < i_2 < i_3 < n\), và trả về \(A[i_1] \ | \ A[i_2] \ | \ A[i_3]\).

Khi chấm bài, với mỗi test, hàm keyDuplication sẽ được gọi \(\tau\) lần, mỗi lần gọi tương ứng với một trường hợp chìa khóa cần xác định.

Lưu ý

• Thí sinh cần có dòng lệnh khai báo thư viện #include "andor.h" ở dòng đầu tiên của chương trình.
• File mã nguồn của thí sinh không được chứa hàm main. Việc viết hàm main có thể gây ra lỗi biên dịch cho bài làm của thí sinh.
• Thí sinh có thể định nghĩa thêm hàm hoặc khai báo thêm các biến toàn cục nếu cần.
• Thí sinh không được đọc dữ liệu từ thiết bị vào chuẩn hay bất cứ tệp tin nào, cũng như không được in ra thiết bị ra chuẩn hay bất kì tệp tin nào.
• Thí sinh sẽ nhận được kết quả chấm là Wrong Answer nếu như tham số truyền vào hàm AND hoặc hàm OR không hợp lệ, hay kết quả trả về của hàm keyDuplication không chính xác.
• Tải chương trình mẫu và môi trường biên dịch.

Giới hạn

• \(\tau \le 20000\).
• \(0 \le A[i] < 2^{60}\).
• Tổng số rãnh của \(\tau\) chiếc chìa khóa không quá \(10^5\).

Chấm điểm

Chương trình chấm mẫu nhận vào dữ liệu đầu vào theo mẫu sau:

• Dòng đầu tiên chứa duy nhất số \(\tau\), là số lượng chiếc chìa khóa cần xác định của bộ test.
• Tiếp theo là \(\tau\) bộ dữ liệu, mỗi bộ dữ liệu gồm hai dòng:
  • Dòng đầu tiên chứa duy nhất số \(N\) là số rãnh của chiếc chìa khóa.
  • Dòng thứ hai lần lượt chứa \(N\) số \(A[0], A[1], \dots, A[n - 1]\) lần lượt là độ sâu của \(N\) rãnh chìa khóa.

Chương trình chấm mẫu sẽ in ra \(\tau\) dòng, dòng thứ \(i\) cho biết chiếc chìa khóa thứ \(i\) đã được đoán đúng hay sai.

• Subtask \(1\) (\(15\) điểm): \(A[0] = A[1]\) với mọi chiếc chìa khóa.
• Subtask \(2\) (\(20\) điểm): \(0 \le A[i] \le 1\) với mọi rãnh chìa khóa.
• Subtask \(3\) (\(30\) điểm): Tổng số rãnh của \(\tau\) chìa khóa \(\le 200\).
• Subtask \(4\) (\(35\) điểm): Tổng số rãnh của \(\tau\) chìa khóa \(\le 10^5\).

Với mỗi chiếc chìa khóa, giả sử bạn đoán đúng độ sâu của cả \(N\) rãnh thông qua \(\beta\) phép đo lường. Giám khảo đã ấn định trước \(5\) số \(\alpha_1 \le \alpha_2 \le \alpha_3 \le \alpha_4 \le \alpha_5 < N^3\).

• Nếu \(\beta \le \alpha_1\), hệ số điểm của chìa khóa đó là \(100\%\).
• Nếu \(\alpha_1 < \beta \le \alpha_2\), hệ số điểm của chìa khóa đó là \(80\%\).
• Nếu \(\alpha_2 < \beta \le \alpha_3\), hệ số điểm của chìa khóa đó là \(50\%\).
• Nếu \(\alpha_3 < \beta \le \alpha_4\), hệ số điểm của chìa khóa đó là \(30\%\).
• Nếu \(\alpha_4 < \beta \le \alpha_5\), hệ số điểm của chìa khóa đó là \(20\%\).
• Nếu \(\alpha_5 < \beta\), hệ số điểm của chìa khóa là \(10\%\).

Điểm của test là mức hệ số điểm nhỏ nhất của các lần đoán chìa khóa trong test đó.
Giá trị các rãnh chìa khóa là cố định từ trước khi thực hiện các câu hỏi.

Giải thích

Giả sử ta phải xác định chiếc chìa khóa có \(N = 6\) và \(A = [12, 23, 34, 45, 56, 67]\). Khi đó, hàm keyDuplication(6) được gọi.

Giả sử trong trường hợp này hàm gọi tới các hàm sau:

• AND(1, 3, 5) trả về \(1\).
• OR(0, 2, 3) trả về \(47\).

Cuối cùng, hàm trả về mảng {12, 23, 34, 45, 56, 67}.

Cho dãy \(A\) gồm \(N\) phần tử \(A_1, A_2, \dots, A_N\). Bạn được phép thay đổi vị trí các phần tử trong dãy \(A\) một cách tùy ý.
Hãy biến đổi dãy \(A\) sao cho sau khi biến đổi:

• Không tồn tại hai phần tử liên tiếp nào có cùng giá trị.

Với một dãy \(A\) bất kỳ, gọi

với mỗi cặp chỉ số \(i < j\) sao cho \(A_i = A_j\) và không tồn tại chỉ số \(k\) với \(i < k < j\) thỏa mãn \(A_i = A_k = A_j\).
Nói cách khác, với mỗi giá trị xuất hiện trong dãy, ta xét các vị trí xuất hiện của nó theo thứ tự tăng dần. Với mỗi hai lần xuất hiện liên tiếp của cùng một giá trị, ta tính hiệu chỉ số \(j - i\) và lấy giá trị lớn nhất trong tất cả các hiệu này. Nếu không tồn tại cặp chỉ số \(i, j\) thỏa mãn (tức là mọi phần tử đều phân biệt), khi đó \(D = 0\).

Yêu cầu: Hãy biến đổi dãy \(A\) (tức là chọn một hoán vị của các phần tử trong dãy ban đầu) sao cho:

• Không có hai phần tử liên tiếp bằng nhau;
• Giá trị \(D\) thu được là nhỏ nhất có thể.

Nếu không tồn tại cách biến đổi thỏa mãn điều kiện không có hai phần tử liên tiếp bằng nhau, hãy in ra \(-1\).

Input

• Dòng đầu tiên chứa một số nguyên dương \(T\) là số bộ dữ liệu (\(1 \le T \le 100\)).
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm mô tả một bộ dữ liệu theo định dạng sau:
  • Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 5\cdot 10^5\)).
  • Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le N\)).

Dữ liệu đảm bảo tổng các giá trị \(N\) trong tất cả các bộ dữ liệu không vượt quá \(10^6\).

Output

Với mỗi bộ dữ liệu:

• Nếu không tìm được cách biến đổi thỏa mãn điều kiện không tồn tại hai phần tử liên tiếp nào có cùng giá trị, in ra một dòng duy nhất chứa số \(-1\).
• Ngược lại, in ra hai dòng:
  • Dòng thứ nhất chứa giá trị \(D\) nhỏ nhất tìm được.
  • Dòng thứ hai chứa \(N\) số nguyên dương là dãy \(A\) sau khi biến đổi (một hoán vị của dãy ban đầu) thỏa mãn các điều kiện đề bài.

Example

1
6
3 3 3 2 2 1

2
3 2 3 2 3 1

1
6
3 3 3 2 2 1

3
3 2 1 3 2 3

1
6
3 3 3 2 2 1

2
3 3 3 1 2 2

Scoring

Với mỗi bộ dữ liệu:

• Nếu cả thí sinh và ban giám khảo đều không tìm được cách biến đổi thỏa mãn, thí sinh được \(100\%\) số điểm cho bộ dữ liệu đó.
• Nếu cả thí sinh và ban giám khảo đều tìm được cách biến đổi thỏa mãn, gọi \(D_j\) là giá trị \(D\) trong lời giải của ban giám khảo, \(D_p\) là giá trị \(D\) trong lời giải của thí sinh.
  • Nếu \(D_p = D_j\):
    • Nếu thí sinh đưa ra được một cách biến đổi thỏa mãn (với đúng giá trị \(D_p\)), thí sinh được \(100\%\) số điểm.
    • Ngược lại, thí sinh được \(20\%\) số điểm.
  • Nếu \(D_p \neq D_j\):
    • Nếu thí sinh đưa ra được một cách biến đổi thỏa mãn (với đúng giá trị \(D_p\)), thí sinh được \(f(D_p, D_j) = (60 - \log_N ((D_p + 1)/(D_j + 1)) \cdot 60)\%\) số điểm.
    • Ngược lại, thí sinh được \(0\) điểm.
• Nếu ban giám khảo tìm được kết quả nhưng thí sinh không tìm được, thí sinh được \(0\) điểm cho bộ dữ liệu đó.

Điểm của thí sinh cho mỗi test là điểm nhỏ nhất mà thí sinh nhận được trên tất cả các bộ dữ liệu của test đó.

• Subtask 1 (\(4\) điểm): \(A_i \neq A_j\) với mọi \(i \neq j\) (\(1 \le i, j \le n\)).
• Subtask 2 (\(9\) điểm): \(N \le 10\).
• Subtask 3 (\(12\) điểm): \(A_i \le 2\), \(\forall i = 1..n\).
• Subtask 4 (\(17\) điểm): với mọi giá trị \(x\), số lần xuất hiện của \(x\) trong dãy \(A\) là như nhau.
• Subtask 5 (\(21\) điểm): \(A_i \le 3\), \(\forall i = 1..n\).
• Subtask 6 (\(17\) điểm): \(N \le 5000\).
• Subtask 7 (\(20\) điểm): Không có ràng buộc nào thêm.