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