Bộ dự đoán nhánh 2-bit saturating counter có 4 trạng thái: 0,1 = dự đoán không nhảy (N), 2,3 = dự đoán nhảy (T). Mỗi lần rẽ nhánh: nếu kết quả thực là nhảy (T) thì tăng bộ đếm (tối đa 3), nếu không nhảy (N) thì giảm (tối thiểu 0). Dự đoán được đưa ra trước khi cập nhật, dựa trên trạng thái hiện tại.
Cho trạng thái khởi tạo và một dãy kết quả thực, hãy đếm số lần dự đoán đúng.
Khởi tạo trạng thái 2 (dự đoán T), dãy T T N: lần 1 dự đoán T, thực T → đúng (→3); lần 2 dự đoán T, thực T → đúng (→3); lần 3 dự đoán T, thực N → sai (→2). Đúng 2/3.
Dòng 1: trạng thái khởi tạo init (0..3). Dòng 2: chuỗi các ký tự T/N (kết quả thực, không có khoảng trắng).
0 ≤ init ≤ 3, độ dài chuỗi 1..10^5, chỉ gồm T và N.
Một dòng: số lần dự đoán đúng.
Ví dụ:
Đầu vào:
2
TTN
Đầu ra:
2
Giải thích:
Đang tải editor...