APIO 2026 — Main Contest

APIOBike là một dịch vụ chia sẻ xe đạp mới được ra mắt tại thành phố APIO. Một vài trạm được lắp đặt khắp thành phố, giúp cho người dùng có thể mượn hoặc trả xe ở bất kỳ trạm nào. Bởi sự tiện dụng và chi phí thấp, nó đã nhanh chóng trở thành phương tiện di chuyển quan trọng nhất trong thành phố APIO. Tuy nhiên, APIOBike đã gặp phải một vấn đề thường gặp của tất cả các hãng dịch vụ chia sẻ xe: sự mất cân bằng giữa tỷ lệ mượn và trả ở những trạm khác nhau. Kết quả là một số trạm có ít xe đạp, làm cho cư dân xung quanh không thể mượn xe; một số trạm lại có quá nhiều xe, những xe thừa mà người dân xung quanh không cần.

Để giải quyết vấn đề này, APIOBike lên kế hoạch điều động một xe tải tái cân bằng mỗi đêm để phân bổ lại xe đạp giữa các trạm, đảm bảo mỗi trạm đều duy trì số lượng xe đạp phù hợp. Thành phố APIO có toàn bộ \(N\) trạm, đánh số \(0, 1, \ldots, N-1\). Thông qua quan sát, APIOBike nhận ra rằng mỗi tối, số lượng xe đạp ở trạm \(i\) luôn có giá trị \(A[i]\), và không ai mượn hoặc trả xe vào buổi tối. Công ty muốn có đúng \(B[i]\) xe ở trạm \(i\) vào mỗi sáng.

Giữa \(N\) trạm, có \(N-1\) con đường được dành cho xe tải tái cân bằng. Mỗi con đường nối giữa hai trạm khác nhau, và xe tải chỉ sử dụng những con đường này để di chuyển. Mỗi con đường có độ dài là một đơn vị. Mạng lưới trạm là liên thông, đảm bảo rằng xe tải có thể di chuyển giữa bất kỳ cặp trạm nào. Mỗi đêm, APIOBike phải điều động một xe tải tái cân bằng để đảm bảo trạm \(i\) có đúng \(B[i]\) xe. Xe tải này có thể bắt đầu ở bất kỳ trạm nào và kết thúc đường đi của nó ở bất kỳ trạm nào.

Xe tải này là rỗng khi bắt đầu quá trình cân bằng. Bất cứ khi nào xe tải ở tại một trạm, người lái xe có thể bốc bất kỳ số lượng xe đạp nào từ trạm lên xe tải, hoặc dỡ bất kỳ số lượng xe đạp nào từ xe tải xuống trạm. Xe tải và các trạm không có giới hạn sức chứa cho xe đạp nhưng số lượng xe đạp ở bất kỳ địa điểm nào phải không bao giờ xuống dưới không. Công ty muốn xác định khoảng cách di chuyển tối thiểu có thể để hoàn thành việc tái cân bằng và chiến lược tương ứng.

Chi tiết cài đặt

Bạn cần xây dựng hàm sau (khai báo trong bike.h):

std::pair<std::vector<int>, std::vector<long long>>
find_rebalancing_strategy(int N,
                          std::vector<int> A,
                          std::vector<int> B,
                          std::vector<int> U,
                          std::vector<int> V)

Tham số:

• \(N\): số lượng trạm.
• \(A\): một mảng có độ dài \(N\), trong đó \(A[i]\) là số lượng xe đạp tại trạm \(i\) mỗi buổi tối.
• \(B\): một mảng có độ dài \(N\), trong đó \(B[i]\) là số lượng xe đạp mục tiêu tại trạm \(i\) mỗi sáng.
• \(U\), \(V\): các mảng có độ dài \(N-1\) biểu thị mạng lưới đường bộ. Với mỗi \(0 \le i < N-1\), con đường thứ \(i\) kết nối trạm \(U[i]\) và trạm \(V[i]\).

Hàm này được gọi tối đa 150 000 lần với mỗi trường hợp thử nghiệm.

Giá trị trả về:

Hàm này cần trả về một cặp mảng \((X, Y)\) có độ dài bằng nhau là \(k+1\), biểu thị một chiến lược tái cân bằng:

• \(X\): chuỗi chỉ số các trạm được ghé thăm theo thứ tự thời gian.
• \(Y\): tổng số xe được vận chuyển ở mỗi trạm ghé thăm. Với mỗi \(0 \le j \le k\):
• Nếu \(Y[j] \ge 0\), tài xế dỡ xuống \(Y[j]\) xe đạp ở trạm \(X[j]\) từ xe tải, tăng số lượng xe của trạm lên \(Y[j]\).
• Nếu \(Y[j] < 0\), tài xế bốc lên \(-Y[j]\) xe đạp từ trạm \(X[j]\) lên xe tải, giảm số lượng xe của trạm đi \(-Y[j]\).

Một chiến thuật tái cân bằng hợp lệ \((X, Y)\) với khoảng cách di chuyển \(k\) phải thỏa mãn những điều kiện sau:

• Với mỗi \(0 \le j \le k\): \(0 \le X[j] < N\).
• Với mỗi \(0 \le j < k\): trạm \(X[j]\) và trạm \(X[j+1]\) được nối bởi một con đường.
• Với mỗi \(0 \le j \le k\): \(\sum_{t=0}^{j} Y[t] \le 0\).
• Với mỗi trạm \(0 \le i < N\) và mỗi bước \(0 \le j \le k\), gọi \(S_{i,j}\) là tổng của \(Y[t]\) qua tất cả các bước \(t\) mà \(0 \le t \le j\) và \(X[t] = i\):
• Số lượng xe tại trạm \(i\) không bao giờ xuống dưới không: \(A[i] + S_{i,j} \ge 0\).
• Sau khi chiến thuật được hoàn thành, mỗi trạm \(i\) phải có đúng \(B[i]\) xe đạp: \(A[i] + S_{i,k} = B[i]\).

Ràng buộc

• \(2 \le N \le 300\,000\)
• Tổng các \(N\) qua tất cả lời gọi đến hàm find_rebalancing_strategy không vượt quá \(300\,000\) với mỗi trường hợp thử nghiệm.
• \(0 \le U[i], V[i] < N\) và \(U[i] \ne V[i]\) với mỗi \(i\) sao cho \(0 \le i < N\).
• \(0 \le A[i], B[i] \le 10^9\) với mỗi \(i\) sao cho \(0 \le i < N\).
• Có thể di chuyển giữa bất kỳ cặp trạm nào.
• \(\sum_{i=0}^{N-1} A[i] = \sum_{i=0}^{N-1} B[i]\).
• Tồn tại ít nhất một giá trị \(i\) sao cho \(0 \le i < N\) và \(A[i] \ne B[i]\).

Phân nhóm

Ở đây, \(T\) là số lần gọi hàm find_rebalancing_strategy, và \(\sum N\) là tổng các \(N\) qua tất cả lời gọi đến hàm find_rebalancing_strategy.

Tính chất P: Với mỗi \(0 \le i < N-1\), \(U[i] = i\) và \(V[i] = i+1\). Với mỗi \(0 \le i < N\), \(A[i] \ne B[i]\).

• Subtask 1 (4 điểm): Các trạm và các con đường thỏa mãn tính chất P. Tồn tại duy nhất một \(i\) sao cho \(0 \le i < N\) và \(A[i] > 0\).
• Subtask 2 (11 điểm): \(T \le 10\). \(N \le 7\). Các trạm và các con đường thỏa mãn tính chất P.
• Subtask 3 (16 điểm): Các trạm và các con đường thỏa mãn tính chất P.
• Subtask 4 (9 điểm): Tồn tại duy nhất một \(i\) sao cho \(0 \le i < N\) và \(A[i] > 0\).
• Subtask 5 (24 điểm): \(\sum N \le 500\).
• Subtask 6 (15 điểm): \(\sum N \le 5000\).
• Subtask 7 (21 điểm): Không có ràng buộc nào thêm.

Ví dụ

1
4
10 1 5 0
10 0 3 3
0 1
1 2
1 3

2
2 1 3
-2 -1 3

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

6
0 2 1 2 4 2 3
-1 -1 2 0 -2 1 1

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

5
2 1 0 1 2 3
-1 1 -1 1 -1 1

Chấm điểm

Đây là bài toán dạng Batch với signature grader (bike.h). Hàm find_rebalancing_strategy của bạn sẽ được gọi tối đa 150 000 lần trong một test case.

Nếu mảng trả về \(X\) và \(Y\) có độ dài chính xác là \(k^* + 1\), trong đó \(k^*\) là khoảng cách di chuyển tối thiểu có thể, nhưng \((X, Y)\) không phải là một chiến lược hợp lệ, bạn sẽ nhận được 50% điểm số của subtask đó.

Đài Loan có mật độ núi cao dày đặc, với hơn 250 đỉnh núi cao hơn 3.000 mét. A-Ming dự định xây dựng mạng lưới robot vận chuyển hàng hóa tự động bằng cáp treo ở Dải núi Trung tâm của Đài Loan để vận chuyển bưu kiện giữa các làng mạc vùng sâu vùng xa.

Trong kế hoạch của A-Ming, mỗi mạng lưới bao gồm \(N\) nút, được đánh số từ \(0\) đến \(N - 1\). Trong số các nút này, chính xác \(K = 6\) nút là các trạm điện và \(N - K\) nút còn lại là các làng. Các nút được kết nối bằng \(N - 1\) dây cáp hai chiều, được đánh số từ \(0\) đến \(N - 2\). Với mỗi \(i\) (\(0 \le i \le N - 2\)), dây cáp \(i\) kết nối các nút \(U[i]\) và \(V[i]\). Mỗi dây cáp kết nối hai nút khác nhau, và mỗi cặp nút được kết nối bởi tối đa một dây cáp. Đảm bảo rằng giữa hai nút bất kỳ đều có thể di chuyển thông qua các dây cáp trong mạng.

Khoảng cách giữa hai nút \(a\) và \(b\) được ký hiệu là \(d(a, b)\) và được định nghĩa như sau:

• Nếu \(a = b\) thì \(d(a, b) = 0\).
• Trái lại, \(d(a, b)\) là số lượng dây cáp tối thiểu cần thiết để di chuyển từ \(a\) đến \(b\).

Ta nói rằng hệ số phân nhánh của mạng ít nhất là \(\delta\) nếu mỗi nút trong mạng được kết nối với chính xác \(1\) hoặc ít nhất \(\delta\) dây cáp. A-Ming biết một số nguyên dương \(B\) mà hệ số phân nhánh của mạng ít nhất là \(B\).

A-Ming đã chuẩn bị 100 loại dây cáp khác nhau, được đánh số từ \(0, 1, \ldots, 99\). Mỗi dây cáp trong mạng được thiết lập từ một trong những loại dây cáp đó.

Các robot sẽ di chuyển dọc theo dây cáp để thực hiện nhiệm vụ giao hàng. A-Ming muốn cài đặt một chương trình điều hướng giúp robot quay trở lại các trạm điện và tự sạc pin. Tuy nhiên, các robot có bộ nhớ cực kỳ hạn chế. Do đó, khi thiết kế chương trình điều hướng, robot chỉ điều hướng dựa trên số lượng trạm điện \(K = 6\), hệ số phân nhánh đảm bảo \(B\) và các loại dây cáp được gắn vào vị trí hiện tại của robot.

Khi một robot muốn di chuyển tại một nút \(u\) là làng được kết nối với hai hoặc nhiều dây cáp, robot trước tiên sẽ quét các dây cáp được kết nối với \(u\) theo một thứ tự bất kỳ. Sau đó, chương trình được cung cấp một danh sách chứa các loại dây cáp theo thứ tự đó. Đối với mỗi dây cáp, chương trình cần đếm số lượng trạm điện sao cho việc đi theo dây cáp đó làm giảm khoảng cách giữa robot và trạm điện.

Cụ thể, gọi \(v_1, \ldots, v_k\) (\(k \ge 2\)) là các nút được kết nối trực tiếp với \(u\) bằng một dây cáp và \(c_i\) (\(1 \le i \le k\)) là loại dây cáp nối nút \(u\) và \(v_i\). Chương trình được cung cấp \(K\), \(B\), và danh sách \(c_1, c_2, \ldots, c_k\). Với mỗi \(i\) (\(1 \le i \le k\)), chương trình phải xác định số lượng trạm điện \(p\) sao cho \(d(v_i, p) < d(u, p)\).

Nhiệm vụ của bạn là xây dựng chiến lược để phân bổ các loại cáp và thiết kế chương trình điều hướng. Điểm số của bài làm của bạn phụ thuộc vào số lượng các loại cáp khác nhau được sử dụng (xem phần Subtask và Chấm điểm để biết thêm chi tiết).

Chi tiết cài đặt

Bạn cần thực hiện hai hàm trong file navigation.h: một hàm để phân bổ loại cáp và một hàm cho chương trình điều hướng của robot. Lưu ý quan trọng: hai hàm này được gọi trong hai tiến trình riêng biệt — hàm construct_network không thể truyền thông tin trực tiếp sang hàm navigate qua biến toàn cục.

Hàm phân bổ loại cáp:

std::vector<int> construct_network(int N, int K, int B,
                                   std::vector<int> U, std::vector<int> V,
                                   std::vector<int> P)

• \(N\): số lượng nút.
• \(K\): số lượng các trạm điện.
• \(B\): hệ số phân nhánh đảm bảo tối thiểu của mạng.
• \(U\), \(V\): các mảng độ dài \(N - 1\) mô tả các sự kết nối của dây cáp.
• \(P\): một mảng độ dài \(K = 6\) mô tả các nút là trạm điện.
• Hàm này được gọi tối đa 10 000 lần cho mỗi trường hợp thử nghiệm.

Hàm này cần trả về một mảng \(T\) độ dài \(N - 1\):

• Một dây cáp thuộc loại \(T[i]\) được sử dụng để kết nối nút \(U[i]\) và \(V[i]\).
• Mỗi phần tử \(T[i]\) phải thoả mãn \(0 \le T[i] < 100\).

Hàm điều hướng của robot:

std::vector<int> navigate(int K, int B, std::vector<int> C)

• \(K\): số lượng các trạm điện.
• \(B\): hệ số phân nhánh đảm bảo tối thiểu của mạng.
• \(C\): danh sách các loại cáp của tất cả dây cáp có kết nối đến nút làng mà kết nối với ít nhất 2 dây cáp, theo thứ tự bất kỳ.
• Đảm bảo rằng độ dài của \(C\) tối thiểu là \(B\).
• Hàm này được gọi tối đa 100 000 lần với mỗi trường hợp thử nghiệm.

Hàm điều hướng không được phụ thuộc vào cấu trúc mạng ban đầu; đặc biệt, hệ thống chấm điểm có thể sắp xếp lại tất cả các lệnh điều hướng trên các mạng được xây dựng khác nhau trong cùng một trường hợp thử nghiệm.

Hàm này cần trả về một mảng \(D\):

• Độ dài mảng \(D\) phải bằng độ dài mảng \(C\).
• \(D[i]\) phải là số lượng các trạm điện mà việc đi theo dây cáp tương ứng với \(C[i]\) làm giảm khoảng cách giữa robot và trạm điện.

Ràng buộc

• \(K = 6\).
• \(K < N \le 100\,000\).
• Tổng các \(N\) qua tất cả lời gọi đến hàm construct_network không vượt quá \(100\,000\) với mỗi trường hợp thử nghiệm.
• \(0 \le U[i] < V[i] < N\) với mỗi \(0 \le i \le N - 2\).
• Luôn có thể di chuyển từ một nút bất kỳ sang một nút bất kỳ khác thông qua các dây cáp.
• \(0 \le P[0] < P[1] < \cdots < P[K-1] < N\).
• Mỗi mảng \(C\) là một hoán vị của danh sách các loại cáp được kết nối với một nút làng nào đó, nút này được kết nối với ít nhất 2 cáp.
• Tổng độ dài của mảng \(C\) qua tất cả các lời gọi đến hàm navigate không vượt quá \(200\,000\) đối với mỗi trường hợp thử nghiệm.

Phân nhóm

• Subtask 1 (6 điểm): \(B = 2\), \(N = 7\).
• Subtask 2 (14 điểm): \(B = 2\), \(U[i] = i\), \(V[i] = i + 1\) với mỗi \(i\) sao cho \(0 \le i < N - 1\) (mạng là một đường thẳng).
• Subtask 3 (20 điểm): \(B = 5\).
• Subtask 4 (20 điểm): \(B = 4\).
• Subtask 5 (40 điểm): \(B = 2\).

Ví dụ

Xét kịch bản với \(N = 9\), \(K = 6\), và \(B = 2\).

Cấu trúc của mạng được cho bởi \(U = [0, 0, 0, 2, 2, 2, 2, 7]\), \(V = [1, 2, 3, 4, 5, 6, 7, 8]\). Các trạm điện là \(P = [1, 3, 4, 5, 6, 7]\).

Lời gọi đến tiến trình đầu tiên:

construct_network(9, 6, 2, [0, 0, 0, 2, 2, 2, 2, 7],
                           [1, 2, 3, 4, 5, 6, 7, 8],
                           [1, 3, 4, 5, 6, 7])

Giả sử A-Ming xây dựng mạng bằng cách trả về:

[0, 10, 1, 2, 3, 4, 5, 5]

Trong mạng này, nút \(0\) (làng) kết nối với nút \(1\) (cáp loại \(0\)), nút \(2\) (cáp loại \(10\)), nút \(3\) (cáp loại \(1\)). Nút \(2\) (làng) kết nối với nút \(0\) (cáp loại \(10\)) và các nút \(4, 5, 6, 7\) (cáp loại \(2, 3, 4, 5\)). Nút \(7\) (trạm điện) kết nối với nút \(8\) (cáp loại \(5\)).

Lời gọi navigate từ nút 0:

navigate(6, 2, [0, 10, 1])

Phân tích khoảng cách:

• Trạm điện nút \(1\): gần nhất với chính nó — \(d(1,1) = 0 < d(0,1) = 1 < d(2,1) = d(3,1) = 2\). Đi theo cáp \((0,1)\) (loại \(0\)) làm giảm khoảng cách đến nút \(1\).
• Trạm điện nút \(3\): gần nhất với chính nó — \(d(3,3) = 0 < d(0,3) = 1 < d(2,3) = 2\). Đi theo cáp \((0,3)\) (loại \(1\)) làm giảm khoảng cách đến nút \(3\).
• Trạm điện nút \(4, 5, 6, 7\): gần nhất với nút \(2\) — \(d(2,u) = 1 < d(0,u) = 2\) với \(u \in \{4,5,6,7\}\). Đi theo cáp \((0,2)\) (loại \(10\)) làm giảm khoảng cách đến cả 4 trạm này.

Số lượng trạm điện có khoảng cách giảm khi đi theo các cáp loại \(0\), \(10\), \(1\) lần lượt là \(1\), \(4\), \(1\). Kết quả trả về:

[1, 4, 1]

Lưu ý: hàm navigate cũng có thể được gọi cho các hoán vị khác của \(C\). Ví dụ, navigate(6, 2, [1, 0, 10]) cũng là một lời gọi hợp lệ cho nút \(0\), và hàm cần trả về [1, 1, 4].

Lời gọi navigate từ nút 2:

navigate(6, 2, [10, 2, 3, 4, 5])

Kết quả trả về:

[2, 1, 1, 1, 1]

Giải thích: Đi theo cáp loại \(10\) (về phía nút \(0\)) làm giảm khoảng cách đến \(2\) trạm điện (nút \(1\) và nút \(3\)). Đi theo mỗi cáp loại \(2, 3, 4, 5\) (về phía các nút \(4, 5, 6, 7\)) đều làm giảm khoảng cách đến đúng \(1\) trạm điện tương ứng.

Trong mạng này, hàm navigate sẽ không bao giờ được gọi cho các nút khác vì: nút \(1, 3, 4, 5, 6, 7\) đều là trạm điện, và nút \(8\) chỉ được nối với duy nhất một dây cáp.

Trong trường hợp thử nghiệm này, các loại dây cáp được sử dụng là \(0, 1, 2, 3, 4, 5\) và \(10\). Do đó, \(S = 11\) được dùng để tính điểm.

Chấm điểm

Trong bất kỳ trường hợp thử nghiệm nào, nếu ít nhất một trong các điều kiện sau xảy ra, điểm số sẽ là \(0\) (thông báo Output isn't correct):

• Giá trị trả về của bất kỳ lệnh gọi nào đến construct_network không hợp lệ.
• Giá trị trả về của bất kỳ lệnh gọi nào đến navigate không chính xác.

Trái lại, gọi \(S\) là số nguyên nhỏ nhất lớn hơn tất cả các số trong mọi mảng \(T\) được trả về từ mỗi lệnh gọi construct_network. Nói cách khác, \(S\) là số nguyên nhỏ nhất sao cho tất cả các mạng được xây dựng chỉ sử dụng các loại cáp \(0, 1, \ldots, S - 1\).

Điểm của bạn cho mỗi subtask phụ thuộc vào \(S\) như sau:

Đặc biệt, trong Subtask 1, 2 và 5, bạn sẽ nhận được toàn bộ số điểm nếu \(S \le 5\), và trong Subtask 3 và 4, bạn sẽ nhận được toàn bộ số điểm nếu \(S \le 4\).

Bohan đang tổ chức một bữa tiệc. Vì anh ấy rất thích bánh hành lá, nên anh ấy quyết định mua chúng từ cửa hàng gần đó. Cửa hàng bán \(N\) loại bánh hành lá với các hương vị đôi một khác nhau, được đánh số từ \(0\) đến \(N-1\). Bohan quyết định mỗi loại sẽ mua \(N\) bánh hành lá, tổng cộng là \(N^2\) bánh hành lá. Mỗi bánh hành lá được chia thành \(K\) lát giống hệt nhau và cho vào một túi. Các túi được đánh số từ \(0\) đến \(N^2 - 1\). Gọi \(F[i]\) là hương vị bánh hành lá của túi \(i\).

Trong bữa tiệc, Bohan mời tất cả các khách cùng chơi một trò chơi. Trò chơi diễn ra như sau:

Đầu tiên, Bohan chọn \(N\) khách và đưa họ vào các phòng được đánh số \(0, 1, \ldots, N-1\) sao cho mỗi phòng chỉ có đúng một khách. Những khách còn lại sẽ ở ngoài cho đến khi trò chơi kết thúc. Tất cả \(N\) phòng đều trông giống hệt nhau, vì vậy khách không thể biết mình đang ở phòng nào.

Tiếp theo, với mỗi phòng \(i\) (\(0 \le i < N\)), Bohan vào phòng \(i\) và bí mật nói cho khách biết một số nguyên \(P[i]\), biểu thị cho một hương vị bị cấm. Anh ta có thể nói hoặc không nói cho khách biết họ đang ở phòng nào. Bohan đảm bảo rằng \([P[0], P[1], \ldots, P[N-1]]\) là một hoán vị của \([0, 1, \ldots, N-1]\).

Sau đó, có \(N\) vòng. Trong vòng thứ \(i\), Bohan lần lượt mang các túi \(0, 1, \ldots, N^2 - 1\) theo thứ tự vào phòng \(i-1\). Khi khách ở phòng \(i-1\) nhận được túi \(j\), họ sẽ biết:

• \(F[j]\), hương vị bánh hành lá có trong túi \(j\), và
• số lát bánh còn lại trong túi.

Trước khi nhận túi tiếp theo, khách ở phòng \(i-1\) phải quyết định ăn bao nhiêu lát từ túi hiện tại. Số lát họ có thể ăn phụ thuộc vào tình huống:

• Nếu \(P[i-1] \ne F[j]\), khách có thể lấy một số lượng lát bất kỳ từ túi và ăn.
• Nếu \(P[i-1] = F[j]\), khách không được phép ăn bất kỳ lát nào.

Lưu ý rằng khách không biết trước dãy \(F[0], F[1], \ldots, F[N^2-1]\).

Sau tất cả \(N\) vòng, khách bên ngoài sẽ được xem dãy các túi. Khi nhìn thấy các túi, họ sẽ biết hương vị bánh hành lá và số lượng lát còn lại trong mỗi túi. Với thông tin này, họ phải xác định giá trị của \(P[0], P[1], \ldots, P[N-1]\).

Khách mời được phép trao đổi trước khi trò chơi bắt đầu. Họ cũng biết trước giá trị của \(N\) và \(K\). Mục tiêu của bạn là thực hiện một chiến lược sao cho khách mời bên ngoài luôn có thể xác định chính xác giá trị của \(P[0], P[1], \ldots, P[N-1]\).

Chi tiết cài đặt

Đây là bài toán giao tiếp hai tiến trình (communication task). Bạn cần cài đặt ba hàm trong file party.h.

Hai hàm sau dành cho khách ở các phòng \(0, 1, \ldots, N-1\):

void init(int N, int K, int p, int r)

Giả sử khách đang ở phòng \(i\).

• N: số lượng hương vị bánh hành lá.
• K: số lát bánh hành lá của mỗi loại trước khi trò chơi bắt đầu.
• p \(= P[i]\): hương vị bị cấm ăn trong phòng \(i\).
• Nếu Bohan quyết định nói cho khách biết họ đang ở phòng nào, thì r \(= i\). Nếu không, r \(= -1\).

int strategy(int b, int f, int s)

Giả sử khách đang ở phòng \(i\).

• b: số hiệu túi hiện tại.
• f \(= F[b]\): hương vị bánh hành lá của túi \(b\).
• s: số lát bánh còn lại trong túi \(b\).
• Hàm này cần trả về một số nguyên không âm \(x\), biểu thị số lát bánh mà khách quyết định ăn.
• Nếu \(f \ne P[i]\), thì \(0 \le x \le s\).
• Nếu \(f = P[i]\), thì \(x = 0\).

Hàm sau dành cho khách bên ngoài:

std::vector<int> guess(int N, int K, std::vector<int> F, std::vector<int> S)

• N: số lượng hương vị bánh hành lá.
• K: số lát của mỗi loại bánh hành lá trước khi trò chơi bắt đầu.
• F: một mảng có kích thước \(N^2\), trong đó F[i] là hương vị của bánh hành lá trong túi \(i\).
• S: một mảng có kích thước \(N^2\), trong đó S[i] là số lát còn lại trong túi \(i\) sau tất cả \(N\) vòng chơi.
• Hàm này trả về một vector \(P\) có độ dài \(N\), trong đó \(P[i]\) là số được giao cho khách trong phòng \(i\).

Mỗi trường hợp thử nghiệm bao gồm \(T\) trò chơi độc lập.

Trong quá trình đánh giá, đối với mỗi trò chơi, sẽ có \(N+1\) tiến trình. Với mỗi \(i\) thỏa \(0 \le i < N\), tiến trình \(i\) đại diện cho khách trong phòng \(i\); tiến trình \(N\) đại diện cho khách bên ngoài. Tiến trình \((i+1)\) bắt đầu sau khi tiến trình \(i\) kết thúc.

Đối với các tiến trình từ \(0\) đến \(N-1\):

• Hàm init được gọi đúng một lần.
• Hàm strategy được gọi \(N^2\) lần sau hàm init. Đảm bảo rằng đối với lần gọi thứ \(j\), b \(= j - 1\).

Đối với tiến trình \(N\):

• Hàm guess được gọi đúng một lần.

Trình chấm có thể xen kẽ các tiến trình từ các trò chơi khác nhau, nhưng đảm bảo rằng thứ tự tương đối của các tiến trình trong mỗi trò chơi riêng lẻ được bảo toàn.

Ràng buộc

• \(1 \le T \le 400\)
• \(2 \le N \le 30\)
• Tổng của \(N^3\) trên tất cả các trò chơi trong một trường hợp thử nghiệm không vượt quá \(27\,000\)
• \(1 \le K \le N\)
• \(K \in \{1, 3, N\}\)
• \([P[0], P[1], \ldots, P[N-1]]\) là một hoán vị của \([0, 1, \ldots, N-1]\)
• \(0 \le F[j] < N\) với mỗi \(j\) thỏa mãn \(0 \le j < N^2\)
• \(i\) xuất hiện đúng \(N\) lần trong \([F[0], F[1], \ldots, F[N^2-1]]\) với mỗi \(i\) thỏa mãn \(0 \le i < N\)
• Trình chấm không thích ứng, nghĩa là các giá trị \([P[0], \ldots, P[N-1]]\) và \([F[0], \ldots, F[N^2-1]]\) được cố định trước khi hàm init được gọi lần đầu tiên

Phân nhóm

• Subtask 1 (8 điểm): \(K = 1\), \(N = 2\).
• Subtask 2 (7 điểm): \(K = 1\) và Bohan quyết định nói cho mọi người biết họ đang ở phòng nào.
• Subtask 3 (14 điểm): \(K = 1\) và \([F[i \cdot N], F[i \cdot N + 1], \ldots, F[i \cdot N + N - 1]]\) là một hoán vị của \([0, 1, \ldots, N-1]\) với mỗi \(i\) thỏa mãn \(0 \le i < N\).
• Subtask 4 (18 điểm): \(K = N\).
• Subtask 5 (21 điểm): \(K = 3\), \(N \ge 3\).
• Subtask 6 (32 điểm): \(K = 1\).

Ví dụ

Xét tình huống trong đó \(T = 1\) và \(N = 2\), \(K = 2\), \(P = [1, 0]\), \(F = [1, 0, 0, 1]\) cho một trò chơi trong trường hợp thử nghiệm.

Gọi \(S[i]\) là số lát bánh còn lại trong túi \(i\). Ban đầu, \(S = [2, 2, 2, 2]\).

Giả sử các khách xác định chiến lược dưới đây trước khi trò chơi bắt đầu:

• Đối với khách trong phòng, nếu họ được phép ăn bánh hành lá hiện tại:
• Nếu đây là chiếc bánh hành lá đầu tiên họ được phép ăn, họ sẽ ăn hết tất cả các lát còn lại.
• Nếu không, họ chỉ ăn một lát.
• Đối với khách bên ngoài:
• Nếu \(S = [0, 0, 1, 1]\), họ sẽ đoán rằng \(P = [1, 0]\).
• Nếu không, họ sẽ đoán rằng \(P = [0, 1]\).

Vòng 1 (phòng 0, \(P[0] = 1\)): Trình chấm gọi init(2, 2, 1, -1), sau đó:

Lần gọi thứ nhất và thứ tư phải trả về \(0\) vì \(P[0] = F[0] = F[3] = 1\). Sau vòng 1, \(S = [2, 0, 1, 2]\).

Vòng 2 (phòng 1, \(P[1] = 0\)): Trình chấm gọi init(2, 2, 0, -1), sau đó:

Lần gọi thứ hai và thứ ba phải trả về \(0\) vì \(P[1] = F[1] = F[2] = 0\). Sau vòng 2, \(S = [0, 0, 1, 1]\).

Khách bên ngoài: Trình chấm gọi:

Các vị khách bên ngoài đã đoán đúng hoán vị. Do đó, trường hợp thử nghiệm này được đánh giá là đúng.

Lưu ý rằng phương pháp chiến lược trong ví dụ này không phải lúc nào cũng giúp các vị khách bên ngoài đoán đúng hoán vị — đây chỉ là minh họa cơ chế hoạt động, không phải lời giải đúng cho bài toán.

Chấm điểm

Trình chấm mẫu chỉ hỗ trợ một trò chơi cho mỗi trường hợp thử nghiệm.

Định dạng đầu vào của trình chấm mẫu:

N K
P[0] P[1] ... P[N-1]
F[0] F[1] ... F[N*N-1]
reveal

• reveal bằng 0 hoặc 1.
• Nếu reveal bằng 0, trình chấm sẽ coi như Bohan không nói số phòng của ai (\(r = -1\) cho mọi khách).
• Nếu reveal bằng 1, trình chấm sẽ coi như Bohan nói số phòng của mọi người (\(r = i\) cho khách ở phòng \(i\)).

Nếu vector được trả về bởi guess khớp với \([P[0], P[1], \ldots, P[N-1]]\), trình chấm mẫu sẽ in ra Accepted. Ngoài ra, trình chấm sẽ in ra các lệnh gọi hàm đã thực hiện để phục vụ mục đích gỡ lỗi.