1157 - Máy bán hàng tự động

Đối với một dãy $p$ , ta gọi độ phủ của dãy là số $D$ lớn nhất sao cho với mọi $k$ từ $1$ đến $D$ , luôn tồn tại một dãy con của $p$ có tổng bằng $k$ . Bài toán trở thành: tìm dãy $p$ có ít phần tử nhất, sao cho độ phủ của $p$ lớn hơn hoặc bằng $C$ .

Trước hết, ta cần tìm cách xác định nhanh độ phủ của một dãy $p$ bất kì (giả sử $p_1 \leq p_2 \leq . . . \leq p_k)$ .

Ta kí hiệu $sum(p, i) = p_1 + p_2 + . . . + p_i$ (tổng $i$ phần tử đầu tiên của dãy $p$ ). Ta nhận xét rằng, khi ta thêm một phần tử $t$ vào một dãy có độ phủ $D$ thì:

Nếu $t > D + 1$ , ta không có cách nào để chọn tập con có tổng $D + 1$ . Do đó, độ phủ mới của dãy sẽ vẫn là $D$ .
Nếu $t \leq D + 1$ , với mọi $k$ từ $D + 1$ đến $D + t$ , ta có thể chuẩn bị một tập bao gồm số $t$ và tập con (của dãy cũ) có tổng $k - t$ . Do đó, độ phủ mới của dãy sẽ là $D + t$ .

Như vậy, ta có thể xác định độ phủ của dãy $p$ bằng cách xuất phát từ dãy rỗng có độ phủ $0$ , và lần lượt thêm các phần tử $p_1, p_2, . . . , p_k$ . Giả sử như đã có dãy $p_1, p_2, . . . , p[i-1]$ có độ phủ $sum(p, i - 1)$ , khi ta thêm phần tử $p_i$ :

Nếu $p_i > sum(p, i - 1) + 1$ , độ phủ của dãy $p_1, p_2, . . . , p_k$ vẫn sẽ là $sum(p, i - 1)$ . Việc thêm các phần tử $p(i + 1), p(i + 2), . . .$ cũng sẽ không làm tăng độ phủ của dãy nên ta kết luận độ phủ của dãy cả $p$ cũng là $sum(p, i - 1)$ .
Ngược lại, dãy $p_1, p_2, . . . , p_i$ sẽ có độ phủ $sum(p, i - 1) + p_i = sum(p, i)$

Nói cách khác, nếu dãy $p$ thỏa điều kiện $p_1 = 1$ và $p_i \leq sum(p, i - 1) + 1$ thì độ phủ của dãy sẽ là $sum(p, k)$ . Ta mong muốn $sum(p, k)$ càng lớn càng tốt (do ta mong muốn tìm dãy p có ít phần tử nhất), nên đáp án tốt nhất sẽ thỏa điều kiện $p_i = sum(p, i - 1) + 1$ , hay có dạng $[1, 2, 4, 8, 16, . . .]$ .

Độ phức tạp: $O(T log C)$ với $T$ là số bộ dữ liệu vào, $C$ là giá tiền tối đa của món đồ Bờm cần mua.