STONE - Trò chơi bốc đá
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: phamhuuthien

Hôm nay không mưa nên Nam quyết định sang nhà An chơi. Trong sân nhà An có một đống đá rất to. Hai đứa mới nghĩ ra một trò chơi như sau: lần lượt mỗi đứa bốc ra một số lượng đá nhất định. Đứa nào bốc ra viên đá cuối cùng thì thắng. Đứa nào thắng thì đập vêu mỏ đứa kia (*ách).

Tuy nhiên, mỗi lần bốc thì chỉ được bốc ra 1, hoăc 2, hoặc 4, hoặc 8, hoặc 2i viên đá thôi nhé. Chứ không phải muốn bốc bao nhiêu là bốc đâu à. Vậy, nếu chơi trước thì Nam nên bốc ra bao nhiêu viên để đảm bảo chiến thắng?

Input: n (số nguyên dương không quá 1021 thể hiện tổng số viên đá)

Output: x (số nguyên thể hiện số viên đá Nam nên bốc ra khi chơi trước, -1 nếu chơi sao cũng thua) Nếu có nhiều đáp án thì in ra đáp án nhỏ nhất (haha)

Ví dụ

  • input
    8
    output
    2

Ban đầu có 8 viên đá. Nếu Nam bốc hết 8 thì thắng luôn. Nhưng mà vì bốc 2 viên cũng thắng nên đáp án sẽ là 2. Cụ thể, bốc 2 còn 6 nên An có thể bốc 1, 2 hoặc 4.

Nếu An bốc 1: Còn 5, Nam bốc 2, còn 3. Lúc này An bốc 1 hay 2 đều thua cả.

Nếu An bốc 2: Còn 4, Nam bốc 4 win luôn.

Nếu An bốc 4: Còn 2, Nam bốc 2 win luôn.

Back to Top