14853 - WindowedQueue   

Status  |  Limits Submit

Description

People are lining for shu cream. To make sure the customer won't be waiting too long, the shu cream store decided to serve multiple people at the same time. The number of people that the store can serve simultaneously is call the window size S. The lining queue will be divided into serveral windows accroding to the window size, where the people in the same window can be served at the same time.

For example, if the current queue is [1, 2, 3, 4, 5, 6, 7, 8] and S=2, then each window will be: [1, 2], [3, 4], [5, 6], [7, 8]. Similarly, if S=3, then each window will be [1, 2, 3], [4, 5, 6], [7, 8]. 

Now, you need to implement a data structure WindowedQueue to simulate the lining queue, which supports the following operations:

  • SET_WIN_SIZE S: Set the new window size to S 
  • INSERT ID: Add a new customer ID to the end of queue, where ID is an integer.
  • SERVE: Serve the customers in the first window and print out the customers that is served. After that, these customers will be removed from the queue, and the customers in the seoncd window will be promoted to the first window, and so on. For example, suppose that the current queue is [1, 2, 3, 4, 5, 6, 7, 8] and the window size is 3. After a SERVE operation, customers [1, 2, 3] is removed from the queue, and the second window [4, 5, 6] will become the first window. Similarly, the third window [7, 8] will become the second window.
  • LEN: Print the number of windows.
  • SHOW_QUEUE k: Print the first k windows

Initially, the queue is empty and the window size is set to 2.

Given the template:

class WindowedQueueIterator:
    def __init__(self, windowed_list):
        self.windowed_list = windowed_list
        self.index = 0
 
    def __next__(self):
        # TODO:
        # Return next window and increase self.index
        raise NotImplementedError
 
 
class WindowedQueue:
    def __init__(self, window_size=2):
        self.data = list()
        self.set_window_size(window_size)  
 
    def set_window_size(self, window_size):
        # TODO:
        # set self.window_size to window size
        raise NotImplementedError
 
    def __len__(self):
        # TODO:
        # return the number of windows
        raise NotImplementedError
 
    def __iter__(self):
        return WindowedQueueIterator(self)
 
    def insert(self, ID):
        # TODO:
        # insert ID to the end of queue
        raise NotImplementedError
 
    def serve(self):
        # TODO:
        # serve the customers in the first window, and remove these customers from the queue
        # if the queue is empty, return None
        # otherwise, return a list that contains the served customers 
        # (the order of customers should be same as the queue)
        raise NotImplementedError
 
# DO NOT modify the code below
 
num_ops = int(input())
wl = WindowedQueue()
 
for i in range(num_ops):
    op = input().split()
 
    if op[0] == "INSERT":
        ID = int(op[1])
        wl.insert(ID)
    elif op[0] == "SERVE":
        served = wl.serve()
        if served != None:
            print(f"Serve customers: {served}")
        else:
            print("No customer to be served")
    elif op[0] == "LEN":
        print(len(wl))
    elif op[0] == "SET_WIN_SIZE":
        S = int(op[1])
        wl.set_window_size(S)
    elif op[0] == "SHOW_QUEUE":
        k = int(op[1])
        it = iter(wl)
        for _ in range(k):
            if _ == k - 1:
                print(next(it))
            else:
                print(next(it), end=',')

Input

The first line contains an integer T (T <= 1000), representing the number of operations

For the next T lines, each line contain one of an operation above.

The constraints of each operations:

  • SET_WIN_SIZE S:  S <= 1000 
  • INSERT ID: ID <= 1000
  • SERVE: No extra contraint
  • LEN: No extra contraint
  • SHOW_QUEUE k: k is guaranteed to be less than or equal to the number of windows

Output

For each following operation, output the corresponding text:

  • SERVE: Output Serve customers: , followed by a list of ID of customers in the first window. If the queue is empty, output No customer to be served
  • LEN: Output an integer, representing the number of windows.
  • SHOW_QUEUE k: Output k lists, the i-th list indicates the IDs of customers in the i-th window.

Sample Input  Download

Sample Output  Download

Tags




Discuss