Bài toán nhà bếp được thay đối như sau: Yêu cầu người lao động xếp thành một hàng để nhận đỏ ăn, trong đó những người đăng kí suất cơm gà và những người đăng kí suất cơm bò sẽ đứng lẫn với nhau...

Với bài toán nhà bếp với quy tắc chọn suất ăn mới, cần viết chương trình để thực hiện theo quy tắc mới: mỗi người đến lượt sẽ nhận suất ăn được đưa ra từ ngăn xếp. Nếu suất ăn đó đúng với suất ăn mà họ đã đăng ký, người đó sẽ được nhận suất ăn và đưa ra khỏi hàng đợi. Nếu không, người đó sẽ quay lại cuối hàng đợi. Quá trình này tiếp tục cho đến khi tất cả mọi người đều nhận được suất ăn đúng hoặc tất cả mọi người không thể nhận được suất ăn của mình.

Gợi ý các bước giải quyết bài toán:

1. Đọc dữ liệu từ tệp input1.inp để lấy danh sách đăng ký suất ăn của người lao động.
2. Đọc dữ liệu từ tệp input2.inp để lấy danh sách các suất ăn đã chuẩn bị.
3. Sử dụng hàng đợi để mô phỏng quá trình xếp hàng nhận suất ăn.
4. Sử dụng ngăn xếp để lấy các suất ăn đã chuẩn bị.
5. Thực hiện quá trình phục vụ suất ăn theo quy tắc mới.
6. Đưa ra số lượng người không nhận được suất ăn đúng của mình.

Mẫu mã nguồn gợi ý:

from collections import deque

def read_file(filename):

    with open(filename, 'r', encoding='utf8') as file:

        return file.read().strip().split()

def serve_food(people_queue, food_stack):

    initial_queue_length = len(people_queue)

    no_change_count = 0

    served_count = 0

    while food_stack and no_change_count < len(people_queue):

        person = people_queue.popleft()

        food = food_stack.pop()

        if person == food:

            served_count += 1

            no_change_count = 0  # reset no change count as someone got their food

        else:

            people_queue.append(person)

            food_stack.append(food)  # put the food back on the stack

            no_change_count += 1

    return len(people_queue) - served_count

# Đọc dữ liệu từ file

people = read_file("input1.inp")

foods = read_file("input2.inp")

# Tạo hàng đợi cho người và ngăn xếp cho suất ăn

people_queue = deque(people)

food_stack = list(reversed(foods))

# Tính số lượng người không nhận được suất ăn của mình

unserved_people_count = serve_food(people_queue, food_stack)

print(unserved_people_count)

Chú thích mã nguồn

1. Đọc dữ liệu:
   • read_file(filename): Hàm này đọc nội dung từ tệp và trả về danh sách các từ đã tách.
   • Tệp input1.inp chứa thông tin đăng ký suất ăn của người lao động.
   • Tệp input2.inp chứa thông tin các suất ăn đã chuẩn bị.
2. Khởi tạo hàng đợi và ngăn xếp:
   • people_queue là một hàng đợi (deque) chứa danh sách người.
   • food_stack là một ngăn xếp chứa các suất ăn (được đảo ngược để mô phỏng ngăn xếp).
3. Phục vụ suất ăn:
   • serve_food(people_queue, food_stack): Hàm này thực hiện quy trình phục vụ suất ăn.
   • Sử dụng biến no_change_count để theo dõi số lần liên tiếp mà không có ai nhận được suất ăn.
   • Mỗi vòng lặp, lấy một người và một suất ăn ra.
   • Nếu suất ăn đúng với đăng ký của người đó, tăng served_count và reset no_change_count.
   • Nếu không, người đó quay lại cuối hàng đợi và suất ăn quay lại ngăn xếp, tăng no_change_count.
   • Khi no_change_count bằng độ dài hàng đợi, nghĩa là không ai có thể nhận được suất ăn của mình nữa.