Một nhóm bạn có \(N\) người được đánh số từ \(1\) đến \(N\) và có \(M\) quan hệ đối lập. Mỗi quan hệ đối lập được mô tả bởi hai số nguyên phân biệt \(x\), \(y\) (\(1\leq x, y\leq N\)) cho biết người \(x\) và người \(y\) luôn có quan điểm khác nhau trong tất cả các lần bỏ phiếu. Người \(a\) được gọi là đồng quan điểm với người \(b\) nếu tồn tại số nguyên dương \(L\) lẻ và một dãy \(u_1\), \(u_2\),..., \(u_L\) sao cho \(u_1=a\), \(u_L=b\) và có quan hệ đối lập giữa \(u_i\) và \(u_{i+1}\) với mọi \(i=1,2,...,L-1\). Người \(a\) được gọi là ngược quan điểm với người \(b\) nếu tồn tại số nguyên dương \(C\) chẵn và một dãy \(u_1\), \(u_2\),..., \(u_C\) sao cho \(u_1=a\), \(u_L=b\) và có quan hệ đối lập giữa \(u_i\) và \(u_{i+1}\) với mọi \(i=1,2,...,C-1\). Không tồn tại hai người nào vừa đồng quan điểm vừa ngược quan điểm. Ngoài ra, với mọi \(a\), số người ngược quan điểm với \(a\) luôn lớn hơn hoặc bằng \(1\) và bé hơn hoặc bằng hai lần số người đồng quan điểm với \(a\).

Nhóm bạn này vừa bỏ phiếu để quyết định một thay đổi quan trọng. Kết quả thu được là một dãy \(A=A[1],A[2],...,A[N]\) trong đó \(A[i]\) bằng \(1\) hoặc \(0\) tương ứng là người thứ \(i\) tán thành hay phản đối. Dãy \(A\) thỏa mãn điều kiện hai người có quan hệ đối lập thì luôn bỏ phiếu khác nhau. Là thư ký của buổi họp, Alice được giao nhiệm vụ tính toán và đưa ra kết quả bỏ phiếu là đạt hay không đạt, tương ứng là số người tán thành có nhiều hơn số người phản đối hay không. Để đảm bảo tính khách quan, cô đã nhờ sự giúp đỡ của Bob qua điện thoại. Bob và cô đã phối hợp làm việc như sau:

• Đầu tiên, Alice cho Bob biết \(N\) và danh sách các quan hệ đối lập trong nhóm bạn nhưng không cho biết dãy \(A\).
• Kế đến, Alice thêm một phần tử \(A[0]=0\) vào đầu dãy \(A\), dùng để lưu kết quả bỏ phiếu.
• Sau đó, Bob sẽ đọc các phép toán cho Alice thực hiện.
• Cuối cùng, Alice lấy \(A[0]\) làm kết quả bỏ phiếu, \(A[0]\) bằng \(1\) hoặc \(0\) tương ứng là đạt hay không đạt, các giá trị còn lại của dãy \(A\) là không quan trọng.

Alice chỉ thực hiện được các phép toán xử lý bit đơn giản: andbit, orbit, notbit, nandbit, norbit với chi phí cần để thực hiện tương ứng là cand, cor, cnot, cnand, cnor. Các phép toán này được định nghĩa trong bảng sau:

Yêu cầu: Hãy lập trình giúp Bob đưa ra dãy các phép toán dể giải quyết vấn đề của Alice.

Tương tác:

Hệ thống cung cấp thư viện votelib.h chứa các hàm sau:

1

void andbit(int i, int j, int k)

Hàm này tính giá trị (\(A[i]\) andbit \(A[j]\)) và lưu vào \(A[k]\).

1

void orbit(int i, int j, int k)

Hàm này tính giá trị (\(A[i]\) orbit \(A[j]\)) và lưu vào \(A[k]\).

1

void notbit(int i, int j)

Hàm này tính giá trị (notbit \(A[i]\)) và lưu vào \(A[j]\).

1

void nandbit(int i, int j, int k)

Hàm này tính giá trị (\(A[i]\) nandbit \(A[j]\)) và lưu vào \(A[k]\).

1

void norbit(int i, int j, int k)

Hàm này tính giá trị (\(A[i]\) norbit \(A[j]\)) và lưu vào \(A[k]\).

Giá trị các tham số \(i\), \(j\), \(k\) truyền vào trong các hàm trên cần thỏa mãn \(0\leq i, j, k\leq N\) và có thể bằng nhau.

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

1
2
3
4
5
6
7
8
9

void solve(
    int N,
    const vector<pair<int, int>> &E,
    int cand,
    int cor,
    int cnot,
    int cnand,
    int cnor
)

Hàm này nhận đầu vào số \(N\) là số người trong nhóm bạn, danh sách \(E\) mô tả các mối quan hệ đối lập, trong đó (E[i].first, E[i].second) mô tả một quan hệ đối lập (\(0\leq i\leq M)\), và các chi phí tính toán cand, cnor, cnot, cnand, cnor của các hàm tương ứng. Hàm solve cần gọi đến các hàm đã cho trong thư viện votelib.h sao cho khi kết thúc hàm solve, giá trị của \(A[0]\) chính là kết quả bỏ phiếu.

Lưu ý:

• Hàm solve được gọi không quá 20 lần, mỗi lần gọi tương ứng với một bộ dữ liệu vào.
• Hàm này cần cài đặt trong file vote.cpp.
• Trong file vote.cpp thí sinh cần khai báo thư viện bằng dòng lệnh #include "votelib.h" ở đầu file.

Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần. Tuy nhiên, các hàm tự tạo không được phép đặt tên là main. File vote.cpp sẽ được biên dịch cùng với thư viện votelib.h.

Đính kèm

Thí sinh được cung cấp file mẫu vote.cpp mô tả cấu trúc hàm cần viết và file votelib.h phục vụ cho quá trình thử nghiệm. Để thử nghiệm, thí sinh lưu file này vào cùng thư mục với file vote.cpp, sau đó biên dịch và chạy file vote.cpp. Lưu ý, file votelib.h chỉ nhằm mục đích thử nghiệm cho thí sinh trong quá trình làm bài, sẽ không được dùng để chấm bài và cũng không mô tả cách thức hoạt động của trình chấm.

Ví dụ

Với hàm solve được gọi như sau: solve(7, {{1, 2}, {1, 3}, {4, 6}, {4, 7}, {5, 7}}, 3, 3, 3, 3, 3), nhóm bạn có \(7\) người và \(5\) mối quan hệ đối lập: (1, 2), (1, 3), (4, 6), (4, 7), (5, 7). Trong ví dụ này, người \(1\) ngược quan điểm với người \(6\) và người \(7\). Nếu những người \(2\), \(3\), \(4\), \(5\) tán thành và những người \(1\), \(6\), \(7\) phản đối thì kết quả bỏ phiếu là đạt và hàm solve cần thiết phải đặt được \(A[0]\) bằng \(1\).

Ràng buộc

• \(2\leq N\leq 327\).
• \(1\leq M\leq N\cdot(N-1)/2\).
• \((cand, cor, cnot, cnand, cnor)\) chỉ thuộc một trong các khả năng \((3, 3, 3, 3)\), \((10, 10, 10, 1, 10)\), \((10, 10, 10, 10, 1)\), \((10, 10, 10, 2, 2)\), \((2, 10, 1, 10, 10)\), \((10, 2, 1, 10, 10)\).

Subtask

• Subtask 1 (5 điểm): \(N\leq 3\).
• Subtask 2 (20 điểm): \(N\leq 7\).
• Subtask 3 (35 điểm): \(cand=cor=cnot=cnand=cnor=3\).
• Subtask 4 (15 điểm): \(cand=cor=cnot=cnor=10\); \(cnand=1\).
• Subtask 5 (25 điểm): Không có ràng buộc gì thêm.

Chấm điểm

Gọi \(P\) là tổng chi phí thực hiện lớn nhất trong số các lần gọi hàm solve. Điểm của thí sinh sẽ là:

• \(100\%\) nếu \(P\leq 7100\);
• \(100\% \cdot \frac{7100}{P}\) nếu \(7100 < P \leq 10^5\).
• \(0\%\) nếu \(P > 10^5\).