Bakery algorithm (Lamport): mỗi tiến trình muốn vào vùng găng bốc một số lớn hơn mọi số đang phát. Tiến trình được phục vụ theo thứ tự (số, pid) tăng dần — số nhỏ trước, nếu trùng số thì pid nhỏ trước.
i bốc số = max(các số đã phát) + 1 (nếu chưa ai phát thì max = 0).(số, pid) tăng dần — đó là thứ tự phục vụ.In từng dòng pid số theo thứ tự phục vụ.
3 yêu cầu theo thứ tự pid 2, 1, 3. Số bốc: pid2→1, pid1→2, pid3→3. Sắp theo (số,pid): (1,2),(2,1),(3,3). In 2 1, 1 2, 3 3.
Dòng 1: n — tổng số tiến trình.
Dòng 2: k — số tiến trình yêu cầu vào.
Tiếp k dòng: pid theo thứ tự bốc số.
1 ≤ n ≤ 100; 1 ≤ k ≤ n; pid phân biệt, 0 ≤ pid < n.
k dòng: pid số theo thứ tự phục vụ (số, pid) tăng dần.
Ví dụ:
Đầu vào:
3
3
2
1
3
Đầu ra:
2 1
1 2
3 3
Giải thích:
Đang tải editor...