Số não nhỏ nhất để Heidi sống
Có người tham dự một buổi chia kho báu, gồm Heidi và "kẻ ăn não" (zombie). Trong rương có một số lượng não nguyên không âm cho trước.
Buổi chia diễn ra như sau: người đề xuất hiện tại đưa ra một cách phân chia (số lượng não, có thể bằng , cho từng người dự). Tất cả mọi người (kể cả người đề xuất) bỏ phiếu. Nếu ít nhất một nửa số người dự đồng ý (so với tổng — vậy cần phiếu thuận), đề xuất được thông qua và buổi chia kết thúc. Ngược lại, người đề xuất bị giết, số người dự giảm đi , và người tiếp theo trở thành người đề xuất; quy trình lặp lại với người.
Mỗi zombie hành xử như sau theo thứ tự ưu tiên giảm dần:
- Trên hết, mỗi zombie muốn sống sót.
- Nếu chắc chắn sống sót dù bỏ phiếu thế nào, nó muốn nhận được càng nhiều não càng tốt.
- Khi vẫn không phân biệt được, zombie thích giết người đề xuất hơn (tức bỏ phiếu chống).
Heidi là người đề xuất đầu tiên và chỉ cần sống sót (có thể tay trắng cũng được). Mọi người tham dự đều hành động tối ưu và biết tất cả thông tin về tình huống.
Hãy tìm số não nhỏ nhất phải có sẵn trong rương để Heidi có thể sống sót.
Dữ liệu vào
Một dòng duy nhất chứa một số nguyên — số người dự (gồm cả Heidi).
Dữ liệu ra
In ra một số nguyên duy nhất: số não nhỏ nhất trong rương để Heidi sống sót.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 | 0 | Chỉ mình Heidi, cô tự bỏ phiếu thuận cho đề xuất bất kỳ. |
| 3 | 1 | Heidi cần thêm phiếu thuận. Cô tặng não cho một zombie mà nếu cô bị giết sẽ ra về tay trắng — zombie đó đồng ý. |
| 99 | 49 | Heidi cần phiếu (gồm phiếu chính cô); cần mua chuộc zombie với não mỗi người. |
Bình luận