| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14853 | WindowedQueue |
|
| 14854 | Min-Max Priority Queue |
|
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 toSINSERT ID: Add a new customerIDto the end of queue, whereIDis 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 is3. After aSERVEoperation, 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 firstkwindows
Initially, the queue is empty and the window size is set to 2.
Given the template:
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 <= 1000INSERT ID:ID <= 1000SERVE: No extra contraintLEN: No extra contraintSHOW_QUEUE k:kis guaranteed to be less than or equal to the number of windows
Output
For each following operation, output the corresponding text:
SERVE: OutputServe customers:, followed by a list ofIDof customers in the first window. If the queue is empty, outputNo customer to be servedLEN: Output an integer, representing the number of windows.SHOW_QUEUE k: Outputklists, the i-th list indicates theIDs of customers in the i-th window.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A min-priority-queue is a data structure that you can insert element to it and delete element from it. However, you can't delete arbitrary element in a min-priority-queue, you can only delete the element with minimum value in it. Similarly, you can only delete the element with maximum value in a max-priority-queue.
In this problem, you are going to maintain a min-priority-queue and a max-priority-queue, which support the following operations:
INSERTval: Insert a element val to bothmin-priority-queue andmax-priority-queueDELETE M: Delete an element from themax-priority-queueDELETE m: Delete an element from themin-priority-queueITER M: Print out the elements in themax-priority-queue, in insertion orderITER m: Print out the elements in themin-priority-queue, in insertion orderINTER: Print how many number are both in themin-priority-queue and themax-priority-queue
Originally, both max-priority-queue and min-priority-queue are empty.
Given the template:
from abc import ABC, abstractmethod
class BasicPQ(ABC):
def __init__(self):
self.data = list()
def insert(self, val):
# TODO
# insert an element with value val into the priority queue
raise NotImplementedError
@abstractmethod
def delete(self):
raise NotImplementedError
def __iter__(self):
self.index = 0
return self
def __next__(self):
# TODO
# if there is a next (in the insertion order) value in self.data, return it and increase self.index
# otherwise, raise StopIteration
raise NotImplementedError
class MinPQ(BasicPQ):
def delete(self):
# TODO
# delete the minimum value in the priority queue
raise NotImplementedError
class MaxPQ(BasicPQ):
def delete(self):
# TODO
# delete the maximum value in the priority queue
raise NotImplementedError
def Inter(max_pq, min_pq):
# TODO
# return the number of elements that are in both min-priority-queue and max-priority-queue
rase NotImplementedError
# DO NOT change the code below
num_ops = int(input())
min_pq = MinPQ()
max_pq = MaxPQ()
for i in range(num_ops):
op = input().split()
if op[0] == "INSERT":
val = int(op[1])
min_pq.insert(val)
max_pq.insert(val)
elif op[0] == "DELETE":
if op[1] == "M":
max_pq.delete()
else:
min_pq.delete()
elif op[0] == "ITER":
if op[1] == "M":
it = iter(max_pq)
print("Elements in the max-priority-queue:", end=' ')
for i in it:
print(i, end=' ')
print()
else:
it = iter(min_pq)
print("Elements in the min-priority-queue:", end=' ')
for i in it:
print(i, end=' ')
print()
elif op[0] == "INTER":
print(Inter(max_pq, min_pq))
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:
INSERT val: val<= 1000, allvals are distinctDELETE M: It is guaranteed that themax-priority-queue must be non-emptyDELETE m: It is guaranteed that themin-priority-queue must be non-emptyITER M: It is guaranteed that themax-priority-queue must be non-emptyITER m: It is guaranteed that themin-priority-queue must be non-emptyINTER: No extra constraint
Output
For each following operation, output the corresponding text:
ITER M: OutputElements in the max-priority-queue:, followed by the elements in themax-priority-queue. A space should be added right after each element.ITER m: OutputElements in the min-priority-queue:, followed by the elements in themin-priority-queue. A space should be added right after each element.INTER: Output a number, representing the number of elements that are both in themin-priority-queue and themax-priority-queue