VO 12 Bài 3 - Trò chơi với đồng xu
View as PDF
Submit solution
Points:
0.41 (partial)
Time limit:
0.38s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Pirate đi shopping ở Nhật Bản và sưu tập được rất nhiều đồng xu Nhật. Khi về nhà, anh đem các đồng xu ra chơi với em gái.
Trò chơi diễn ra như sau:
- Đầu tiên, Pirate chọn ra ~N~ đồng xu để chơi và chọn thêm một số nguyên ~K~ từ 0 đến ~N~.
- Trong mỗi lượt chơi, Pirate hoặc em gái của mình sẽ đưa ra một cách chọn ~K~ đồng xu sao cho cách chọn đó không trùng với bất cứ cách chọn nào đã được sử dụng trước đó.
- Đến lượt của mình, ai không đưa ra được cách chọn nào nữa thì thua.
Pirate là một người anh mẫu mực nên anh luôn nhường em gái đi trước và luôn giành phần thua cho mình. Các bạn hãy tính xem có bao nhiêu cách chọn K để Pirate thua nhé.
Lưu ý: Một cách chọn ~K~ đồng xu là một bộ K số ~(a_{1}, a_{2}, \dots, a_{K})~ sao cho ~1 \le a_{1} < a_{2} < \dots < a_{K} \le N~. Hai cách chọn ~(a_{1}, a_{2}, \dots, a_{K})~ và ~(b_{1}, b_{2}, \dots, b_{K})~ khác nhau nếu tồn tại ~a_{i} \neq b_{i}~ ~(1 \le i \le K)~.
Input
- Một số nguyên ~N~ duy nhất.
Output
- Một số nguyên duy nhất thể hiện số cách chọn ~K~ để Pirate thua.
Giới hạn
- ~1 \le N \le 10^{9}~
- ~60\%~ số test có ~1 \le N \le 10^{3}~
- ~80\%~ số test có ~1 \le N \le 10^{5}~
Sample Input
4
Sample Output
2
Giải thích
Có 2 cách chọn ~K~ thỏa mãn là 0 và 4. Với ~K = 0~, chỉ có một cách chọn các đồng xu (không chọn đồng xu nào cả) nên Pirate sẽ thua. Với ~K = 4~ cũng tương tự.
Comments
xin downvote
This comment is hidden due to too much negative feedback. Show it anyway.