Mô phỏng một semaphore đếm (counting semaphore) sau một chuỗi thao tác P (wait) và V (signal), in ra giá trị cuối và số tiến trình đang bị chặn.
Quy ước semaphore kiểu đếm với giá trị âm:
value -= 1. Nếu sau đó value < 0 thì có thêm một tiến trình bị chặn (blocked) → blocked += 1.value < 0 (đang có tiến trình chờ) thì đánh thức một tiến trình → blocked -= 1; sau đó value += 1.Khi value < 0, |value| chính bằng số tiến trình đang chờ.
Thuật toán: khởi tạo value = init, blocked = 0; duyệt từng thao tác cập nhật như trên. In value và blocked.
Ví dụ: init=1, chuỗi P P V P. value: 1→0→-1(blocked1)→0(blocked0)→-1(blocked1). In -1 1.
Dòng 1: init và k (giá trị khởi tạo và số thao tác). Dòng 2: k ký tự, mỗi ký tự là P hoặc V, cách nhau dấu cách.
−1000 ≤ init ≤ 1000; 1 ≤ k ≤ 100000; mỗi thao tác là P hoặc V.
Hai số nguyên cách nhau dấu cách: <value_cuối> <số_tiến_trình_bị_chặn>.
Ví dụ:
Đầu vào:
1 4
P P V P
Đầu ra:
-1 1
Giải thích:
Đang tải editor...