Gọi \(w\) là tổng \(1\) phân \(\left(w = \dfrac{\sum_{i = 1}^{n} a_{i}}{k}\right)\).

Subtask 1

• Duyệt tất cả các hoán vị của \(1, 2, \ldots, n\). Một hoán vị được gọi là thỏa mãn và tương ứng với duy nhất một cách chia thỏa mãn nếu có thể chia hoán vị thành \(k\) đoạn, các đoạn có tổng bằng nhau, bằng \(w\). Việc chia này được thực hiện bằng cách đi từ đầu hoán vị đến cuối, lần lượt lấy từng gói kẹo cho đến khi đúng đủ \(w\) thì tiếp tục lấy phần tiếp theo, ...

Subtask 2

• Sử dụng ý tưởng hoán vị ở subtask 1, quy hoạch động bitmask, \(f(t) =\) true/false có nghĩa là có thể xếp các gói thuộc tập \(t\) thành một đoạn đầu trong hoán thỏa mãn hay không?
• Từ \(f(t) =\) true, nếu gói \(i\) (không thuộc \(t\)) có thể xếp vào cuối đoạn hoán vị đang xây dựng tổng các gói kẹo thuộc phần hiện tại cộng với gói thứ \(i \leq w\) thì \(f(t \oplus 2^{i}) =\) true.

Subtask 3

Quy hoạch động \(f(i, a, b) =\) true/false có nghĩa là xét các gói từ \(1\) đến \(i\), có thể lấy một số gói kẹo cho vào phần \(1\) có tổng là \(a\), phần \(2\) có tổng là \(b\), tổng của phần \(3\) là tổng các gói kẹo (từ \(1\) đến \(i\)) trừ đi \(a + b\).
\(f(i, a, b) =\) true, thì \(f(i + 1, a + g_{i}, b)\) – lấy vào phần \(1\), \(f(i + 1, a, b + g_{i})\) – lấy vào phần \(2\), \(f(i + 1, a, b)\) – lấy vào phần \(3\), ba giá trị này đều sẽ nhận bằng true.

Subtask 4, 5

Lời giải với \(n\), được truy hồi về \((n - 2k)\), các gói \(n - 2k + 1\) đến \(n\) chia làm \(k\) phần, mỗi phần gồm \(2\) gói có tổng bằng nhau (gói \(n - 2k + 1\) với \(n\) một phần, $n - 2k + 2 với \(n - 1, \ldots\)). Truy hồi về \(n \leq 50\) thì dùng duyệt hoặc tham xếp nốt.