Subtask 1

\(n \le 7\) nên ta có thể xét toàn bộ \(n!\) hoán vị, với mỗi hoán vị lại cho từng quả cân vào đĩa bên trái hoặc bên phải, và luôn kiểm tra xem quá trình này có hợp lệ không. Cài bằng đệ quy quay lui.

Độ phức tạp (\(n! \times 2^n\))

Subtask 2

\(n \le 14\) nên ta không thể xét toàn bộ hoán vị. Từ đó ta nghĩ cách QHĐ đếm.

Giả sử \(T\) là tập hợp các quả cân ta đã xét, cần phải biễu diễn tập \(T\) bằng cách nào đó để có thể tính \(f(T)\), từ những \(f(T')\) đã tính từ trước.
Trong tập \(T\), có một vài quả cân được xếp vào đĩa bên trái, những quả cân còn lại xếp vào đĩa bên phải. Những quả cân không thuộc tập \(T\) là những quả cân chưa được xét.

Ta biểu diễn cấu hình này dưới dạng số như sau : Nếu quả cân thứ \(i\)

• chưa được xét : chữ số thứ \(i\) là \(0\)
• nằm trên đĩa bên trái : chữ số thứ \(i\) là \(1\)
• nằm trên đĩa bên phải : chữ số thứ \(i\) là \(2\)

Như vậy mỗi cấu hình của ta có dạng một số tam phân \(n\) chữ số.

Cách thức QHĐ : từ một cấu hình \(T\), ta có thể lấy ra bớt 1 quả cân đang nằm trên đĩa trái hoặc phải để được cấu hình \(T'\) đã tính từ trước.

Độ phức tạp \(O(3^n \times n)\)

Subtask 3

Nhận xét : \(2^i > \sum{2^j}\) với \(j\) chạy từ \(0\) tới \(i-1\).

Có nhiều hướng giải, cách mình làm là QHĐ \(O(n^3)\) : Đặt \(f(a,b,m)\) là số cách để đặt các quả cân sao cho có \(a\) quả cân nằm ở đĩa bên trái, \(b\) quả cân nằm ở đĩa bên phải, và quả cân nặng nhất (nằm ở đĩa bên phải) là quả cân thứ \(m\) (\(2^{m-1}\))

Ngoài ra còn có cách làm \(O(n), O(n^2)\). Lưu ý phải cài BigNum để tính.