Đề bài Ma sói (Werewolf) là một trò chơi rất thịnh hành trong giới trẻ thành thị. Phiên bản Ma sói đơn giản nhất chỉ có hai vai (role): ban ngày ma sói đội lốt người sống trong làng, ban đêm hóa sói ăn thịt. Mỗi ngày làng họp lại chọn ra một “người” để bắt lại lưu đày hoang đảo vào buổi chiều.
Mỗi người chơi chỉ được buộc tội một người chơi khác là sói và sói không được buộc tội nhau. Hãy tìm số ma sói tối đa trong “ngày” hôm đó.
I/O
- Input:
stdin- Dòng đầu tiên là số người chơi 2 <= N <= 500000
- N dòng tiếp theo: dòng thứ i gồm một số <= N nghĩa là người chơi thứ i chọn đó là ma sói.
- Output:
stdout- Một số duy nhất là số ma sói tối đa khả dĩ.
Ví dụ:
stdin
3
3
1
2
stdout
1
Số sói tối đa là N-1 vì cho dù tất cả buộc tội anh thì anh cũng phải vote người khác.
Giả sử người chơi 1 là sói. Người chơi 1 vote người số 3 là ma sói, vậy nếu người chơi 1 là sói thì người thứ 3 ko phải. Người chơi 2 buộc tội người 1 vậy người thứ 2 không phải là sói. Trong cả ba trường hợp đều chỉ có thể có 1 sói.
stdin
5
2
4
2
3
4
stdout
3
Nếu người chơi 1 là sói thì chỉ có người thứ 3 và 5, hoặc người thứ 4 là sói.
Nếu người chơi 2 là sói thì chỉ có người thứ 5 là sói.
Vậy kết quả là 3.
Giới hạn
- 1/3 số điểm: N <= 15
- 2/3 số điểm: N <= 2000
Lưu ý
- Số ma sói có thể vượt quá hoặc bằng nửa số người chơi.
bài này chỉ hỏi là số ma sói tối đa có thể thôi.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?