Cơ hội thắng

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Từ một số nguyên dương ~n~ cho trước, Alice và Bob chơi trò chơi như sau:

  • Ban đầu trên bảng có số ~1~.
  • Hai người lần lượt (Alice đi trước) xóa số hiện tại ~x~ và viết số mới ~y~ sao cho:

    • ~y \le n~, và
    • hoặc ~y = x + 1~, hoặc ~y = 2x~.
  • Nếu đến lượt một người mà không thể viết được số mới hợp lệ thì người đó thua.

Alice nhận thấy không phải mọi giá trị ~n~ đều giúp cô ấy thắng nếu cả hai cùng chơi tối ưu.

Yêu cầu

Cho hai số ~a, b~, hãy đếm xem có bao nhiêu giá trị nguyên ~n~ khác nhau trong đoạn ~[a, b]~ sao cho nếu chọn ~n~ đó để chơi thì Alice thắng (với chiến thuật tối ưu cho cả hai).

Dữ liệu

Một dòng chứa hai số nguyên ~a~ và ~b~.

Kết quả

In ra một số nguyên: số lượng giá trị ~n~ trong ~[a,b]~ mà Alice có chiến thuật thắng.

Ví dụ

Ví dụ 1

Input

8 10

Output

2

Giải thích

Ví dụ 1
  • Với ~n = 8~, Alice có thể thắng (ví dụ một ván: ~1 \to 2 \to 3 \to 6 \to 7 \to 8~, Alice đi các bước 1,3,5).
  • Với ~n = 9~, nếu cả hai chơi tối ưu thì Alice thua.
  • Với ~n = 10~, Alice lại có chiến thuật thắng.

Do đó trong đoạn ~[8,10]~ có đúng ~2~ giá trị giúp Alice thắng là ~8~ và ~10~.

Ràng buộc và chấm điểm

Ràng buộc
  • ~1 \le a \le b \le 10^{18}~

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.