Bài toán Bữa tối các triết gia (Dining Philosophers) với N triết gia ngồi quanh bàn tròn, đánh số 0..N−1. Giữa hai triết gia kề nhau có một chiếc đũa; đũa i nằm bên TRÁI triết gia i (và bên phải triết gia (i−1+N) mod N). Mỗi triết gia cần cả hai đũa kề mới ăn được.
Cho một dãy thao tác: mỗi thao tác là P x (triết gia x cố lấy đũa để ăn) hoặc R x (triết gia x ăn xong, trả lại hai đũa).
Khi P x: nếu cả đũa trái (x) và đũa phải ((x+1)%N) đều đang rảnh thì triết gia x lấy được cả hai và bắt đầu ăn (đánh dấu hai đũa bận); ngược lại triết gia x không lấy được (không thay đổi gì). Một triết gia đang ăn nhận thêm P cũng coi như thất bại.
Khi R x: nếu triết gia x đang ăn thì trả lại hai đũa (đánh dấu rảnh); nếu không đang ăn thì bỏ qua.
In ra số lần lấy đũa thành công (số lần một triết gia bắt đầu ăn).
Ví dụ: N=2. P 0 thành công (lấy đũa 0 và 1). P 1 thất bại (đũa bận). R 0 trả. P 1 thành công. Tổng 2 lần.
Dòng đầu: N Q (số triết gia, số thao tác). Q dòng tiếp, mỗi dòng: thao tác (P hoặc R) và chỉ số triết gia.
2 ≤ N ≤ 100000; 1 ≤ Q ≤ 100000; 0 ≤ x < N.
Một số nguyên: số lần lấy đũa thành công.
Ví dụ:
Đầu vào:
2 4
P 0
P 1
R 0
P 1
Đầu ra:
2
Giải thích:
Đang tải editor...