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:
Nguyễn Xuân Khánh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Please read the guidelines before commenting.



  • -4
    nt2309   commented on Oct. 22, 2022, 9:11 a.m.

    j