Market (Olympic Balkan 2000)
Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là ai, đem bán ngoài chợ. Ở
chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3
kg, 5kg…
Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải lấy con cá thứ 2 và
và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg.
Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?
Hướng dẫn:
Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng bằng S.
Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị t mà L[t]=1
Không có nhận xét nào:
Đăng nhận xét