Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KCOIN - Trò chơi với đồng xu

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/kcoin


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ố (a1, a2, ..., aK) sao cho 1 ≤ a1 < a2 < ... < aK ≤ N. Hai cách chọn (a1, a2, ..., aK) và (b1, b2, ..., bK) khác nhau nếu tồn tại ai <> bi (1 ≤ i ≤ 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 ≤ N ≤ 109
  • 60% số test có 1 ≤ N ≤ 103
  • 80% số test có 1 ≤ N ≤ 105

Example

Input:
4

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ự.


Được gửi lên bởi:VOJ Team
Ngày:2011-12-23
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:Nguyễn Xuân Khánh

hide comments
2021-05-27 18:01:07
Tham khảo: https://vnspoj.github.io/problems/KCOIN
2012-12-24 21:29:09 nghị péo
http://en.wikipedia.org/wiki/Lucas%27_theorem
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.