Đầu tiên, viết chương trình để đọc dữ liệu từ hai tệp input1.inp và input2.inp, sau đó mô phỏng quá trình phục vụ suất ăn. Dưới đây là gợi ý chương trình hoàn chỉnh mẫu:

from queue import Queue

from collections import deque

# Định nghĩa lớp Stack sử dụng deque cho ngăn xếp

class Stack:

    def __init__(self):

        self.items = deque()

    def is_empty(self):

        return len(self.items) == 0

    def push(self, item):

        self.items.append(item)

    def pop(self):

        if not self.is_empty():

            return self.items.pop()

        return None

    def size(self):

        return len(self.items)

def bepan(dangkiga, dangkibo, suatan):

    doimon = [] # list chứa ID những người phải đổi món

    while not suatan.is_empty():

        tmp = suatan.pop()

        if tmp == "bò":  # nếu suất ăn lấy ra là bò

            if not dangkibo.empty():  # còn người đăng kí suất ăn bò

                dangkibo.get()

            else:

                ID_doi = dangkiga.get()

                doimon.append(ID_doi)

        elif tmp == "gà":  # nếu suất ăn lấy ra là gà

            if not dangkiga.empty():  # còn người đăng kí suất ăn gà

                dangkiga.get()

            else:

                ID_doi = dangkibo.get()

                doimon.append(ID_doi)

    return doimon

# Khởi tạo hàng đợi cho cơm gà và cơm bò

dangkiga = Queue()

dangkibo = Queue()

# Khởi tạo ngăn xếp cho các suất ăn

suatan = Stack()

# Đọc thông tin đăng kí và đưa vào 2 queue

with open("input1.inp", "r", encoding="utf8") as file1:

    for line in file1.readlines():

        id, dangki = line.strip().split()

        if dangki == "gà":

            dangkiga.put(id)

        elif dangki == "bò":

            dangkibo.put(id)

# Đọc thông tin suất ăn và đưa vào ngăn xếp

with open("input2.inp", "r", encoding="utf8") as file2:

    data = file2.read().strip().split()

    for item in data:

        suatan.push(item)

doimon = bepan(dangkiga, dangkibo, suatan)

if len(doimon) == 0:

    print("Không có người nào phải đổi món ăn")

else:

    print("Danh sách những người phải đổi món là:", doimon)

- Nhận xét về vị trí của những người phải đổi món ăn

Sau khi chạy chương trình với nhiều trường hợp dữ liệu đầu vào khác nhau, nhận xét về vị trí của những người phải đổi món ăn:

- Những người phải đổi món ăn luôn nằm trong hàng đợi ban đầu của loại suất ăn còn lại khi loại suất ăn họ đăng ký đã được phục vụ hết.

- Vị trí của những người phải đổi món ăn phụ thuộc vào thứ tự của họ trong hàng đợi. Người đầu tiên trong hàng đợi sẽ phải đổi món trước khi đến lượt họ nếu hàng đợi của suất ăn còn lại đã hết.