- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
می‌خواهیم سیستم پیشخوان یک رستوران را پیاده‌سازی کنیم. در این رستوران $n$ دستور داده می‌شود که از شما می‌خواهیم آن‌ها را مدیریت کنید.
منوی غذایی که از آن سفارش می‌دهند $m$ غذای مختلف دارد که اسم و قیمت آن‌ها به شما داده می‌شود.
تعداد میزهای رستوران برابر $k$ است که آن‌ها را با اعداد $1$ تا $k$ شماره‌گذاری می‌کنیم. تعداد صندلی‌های دور میز $i$ام برابر $s_i$ است. در ابتدا فرض کنید در ابتدا همه‌ی میزها آماده‌ی ارائه‌ی سرویس هستند.
ثبت سفارش
ساختار کلی این دستور به شکل زیر است.
order <food_1> <food_2> ... <seat> <timestamp>
در این درخواست مشتری سفارش تعدادی غذا می‌دهد و ما باید به این سفارش رسیدگی کنیم. رشته‌ی <food_i> ($i=1, 2, \dots$) از دو قسمت نام غذا و تعداد سفارش تشکیل شده که این دو قسمت با یک کاراکتر X از هم جدا شده‌اند. (به مثال‌ها مراجعه کنید.) در جای <seat> یک عدد به شما داده می‌شود و یعنی یک میز با حداقل این تعداد صندلی نیاز دارند. این سفارش در لحظه‌ی <timestamp> آمده است.
اگر چنین میزی در رستوران نداریم، پیام not enough seat. را چاپ کنید. (این سفارش‌ها نباید شماره بخورند و پذیرفته شوند.) ولی اگر میزی با حداقل این تعداد صندلی در رستوران موجود است، باید این سفارش را شماره بزنید و ثبت کنید.
شماره‌ی میزی را به این مشتری تخصیص دهید که حداقل تعداد صندلی مورد نیاز این مشتری را برطرف کند. همچنین این میز باید آماده ارائه سرویس شده باشد. اگر چندمیز با این ویژگی‌ها وجود داشت، میز با کمترین شماره را در قالب یک پیام please sit at table number <t>. اعلام کنید. ($t$ شماره‌ی میز مورد نظر است.)
اگر چنین میزی در رستوران بود ولی در این لحظه آماده ارائه سرویس نبود، پیام please wait for free table. را اعلام کنید و این مشتری را به لیست انتظار اضافه کنید.
خروج یک مشتری
ساختار کلی این دستور به شکل زیر است. (مواردی که داخل <> قرار دارند ورودی داده می‌شوند.)
payment <idx> <timestamp>
در اینجا مشتری که سفارش شماره‌ی <idx> را داده بود می‌خواهد از رستوران خارج شود. شما باید مجموع هزینه را به او اعلام کنید و آن مشتری پرداخت می‌کند.
اگر این مشتری هنوز غذایش را نخورده و در صف انتظار میز خالی است، پولی از آن دریافت نکنید و پیام pays after eating. را چاپ کنید.
همچنین به پرسنل رستوران اعلام می‌کنید که میزی که این سفارش را داده بودند، آماده‌ی سرویس کنند. این آماده کردن ۲ دقیقه طول می‌کشد. شما بعد از ۲ دقیقه اولین سفارشی که هنوز منتظر است و می‌تواند از آن میز استفاده کند را به میزش هدایت کنید و از صف انتظار خارج کنید.
گزارش وضعیت یک سفارش
order-status <id> <timestamp>
در این گزارش از شما می‌خواهیم وضعیت یک سفارش را در لحظه‌ی <timestamp> پیگیری کنید.
- اگر مشتری در انتظار یک میز خالی است رشته‌ی
WAITINGرا چاپ کنید. - اگر مشتری پشت یک میز در حال غذا خوردن است پیام
EATINGرا چاپ کنید. - اگر مشتری پرداخت کرده و از رستوران خارج شده پیام
DONEرا چاپ کنید.
گزارش وضعیت یک میز
table-status <table> <timestamp>
در اینجا گزارش وضعیت یک میز را در لحظه‌ی <timestamp> پیگیری کنید.
- اگر این میز آماده سرویس دهی است پیام
FREEرا چاپ کنید. - اگر این میز هنوز آماده‌ی سرویس‌دهی است پیام
PENDINGرا چاپ کنید. - اگر مشتری پشت این میز مشغول غذا خوردن است پیام
BUSYرا چاپ کنید.
گزارش کلی
general-status <timestamp>
در این گزارش از شما می‌خواهیم موارد زیر را در لحظه‌ی <timestamp> حساب و به صورت ۸ عدد که با یک فاصله از هم جدا شده‌اند چاپ کنید.
- درآمد امروز که پرداخت شده.
- درآمد تا این لحظه که سفارش داده شده ولی هنوز پرداخت نشده.
- تعداد سفارش‌های در لیست انتظار در این لحظه.
- تعداد سفارش‌هایی که در این لحظه مشغول غذا خوردن هستند.
- تعداد سفارش‌هایی که تا این لحظه با موفقیت کارشان تمام شده.
- تعداد میزهایی که الان در آماده سرویس‌دهی هستند.
- تعداد میزهایی که الان درحال آماده سازی است.
- تعداد میزهایی که الان مشتری روی آن‌ها نشسته هستند.
نکات
- در توضیحات پایین، مواردی که داخل
<>قرار دارند، باید مقدار آن‌ها را در نظر بگیرید و در بقیه موارد همان کاراکترها را در نظر بگیرید. - هر
<timestamp>در قالبhh:mm:ssداده می‌شود. در واقع فرض کنید همه‌ی سفارش‌ها در یک روز می‌آیند و تمام می‌شوند. - تمامی اعدادی که درباره‌ی محدودیت‌های آن صحبت نکردیم را بین ۱ تا ۲۰ در نظر بگیرید.
- تضمین می‌شود در یک سفارش، دو غذا با نام یکسان ظاهر نمی‌شود.
ورودی
در سطر اول ورودی، سه عدد صحیح $n$، $m$ و $k$ داده می‌شود که به ترتیب نشان دهنده‌ی تعداد اتفاقات، غذاها و میزها است.
$$1 \leq n \leq 1000, \quad 1 \leq m, k \leq 100$$
در $m$ سطر بعدی، در هر سطر یک رشته $name$ و یک عدد $cost$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. تضمین می‌شود رشته‌ی $name$ تنها شامل حروف کوچک انگلیسی است.
$$1 \leq |name| \leq 10, \quad \quad 1 \leq cost \leq 1000 , 000$$
در سطر بعدی، $k$ عدد صحیح در یک ردیف داده می‌شود که با یک فاصله از هم جدا می‌شوند. عدد $i$ام با $s_i$ است و نشان دهنده‌ی تعداد صندلی‌های میز $i$ام است.
$$1 \leq s_i \leq 15$$
در $n$ سطر بعدی، یکی از درخواست‌های بالا با فرمت گفته شده داده می‌شود. تضمین می‌شود همه‌ی ورودی‌ها به ترتیب زمانی داده می‌شوند.
| زیرمسئله | امتیاز |
|---|---|
| فقط دو دستور اول در ورودی داده می‌شود | ۵۰ |
| بدون محدودیت اضافه | ۵۰ |
خروجی
خروجی‌های درخواست‌های بالا را در یک سطر مجزا چاپ کنید.
مثال‌ها
ورودی نمونه ۱
9 3 4
pizza 120000
burger 80000
pasta 70000
2 1 4 2
order pizzaX1 burgerX3 3 12:00:00
order pizzaX2 2 14:00:00
order pastaX1 1 14:30:00
order pastaX1 1 14:45:00
payment 3 15:15:00
payment 1 15:30:00
payment 2 15:45:00
order burgerX2 1 16:00:00
payment 4 17:00:00
خروجی نمونه ۱
please sit at table number 3.
please sit at table number 1.
please sit at table number 2.
please sit at table number 4.
you should pay 70000 Toman.
you should pay 360000 Toman.
you should pay 240000 Toman.
please sit at table number 2.
you should pay 70000 Toman.
توضیح نمونه ۱
در منوی رستوران، سه غذای «پیتزا»، «برگر» و «پاستا» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۱۲۰، ۸۰ و ۷۰ هزار تومان است.
این رستوران ۴ میز دارد که دور میز اول، ۲ صندلی، دور میز دوم، ۱ صندلی، دور میز سوم ۴ صندلی و دور میز چهارم ۲ صندلی وجود دارد.
- ۳ نفر در ساعت ۱۲:۰۰ وارد رستوران می‌شوند. یک پیتزا و سه برگر سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۳ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
- ۲ نفر در ساعت ۱۴:۰۰ وارد رستوران می‌شوند. دو پتیزا سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و به میز شماره ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.)
- ۱ نفر در ساعت ۱۴:۳۰ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۳ می‌شود.)
- ۱ نفر در ساعت ۱۴:۴۵ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۴ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.)
- سفارش شماره‌ی ۳ در ساعت ۱۵:۱۵ می‌خواهد از رستوران خارج شود. پس باید ۷۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۵:۱۷ دقیقه آماده سرویس‌دهی می‌کنند.
- سفارش شماره‌ی ۱ در ساعت ۱۵:۳۰ می‌خواهد از رستوران خارج شود. پس باید ۱۲۰ هزارتومان به‌علاوه‌ی سه‌تا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۳ را تا ساعت ۱۵:۳۲ دقیقه آماده سرویس‌دهی می‌کنند.
- سفارش شماره‌ی ۲ در ساعت ۱۵:۴۵ می‌خواهد از رستوران خارج شود. پس باید دوتا ۱۲۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۱ را تا ساعت ۱۵:۴۷ دقیقه آماده سرویس‌دهی می‌کنند.
- ۱ نفر در ساعت ۱۶:۰۰ وارد رستوران می‌شود. دو برگر سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.)
- سفارش شماره‌ی ۴ در ساعت ۱۷:۰۰ می‌خواهد از رستوران خارج شود. پس باید دوتا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۷:۰۲ دقیقه آماده سرویس‌دهی می‌کنند.
ورودی نمونه ۲
16 4 2
joje 60000
kubide 70000
soltani 80000
negini 75000
2 4
general-status 08:00:00
table-status 1 08:30:00
table-status 2 09:00:00
order jojeX1 soltaniX1 kubideX2 neginiX1 4 09:30:00
table-status 1 10:00:00
table-status 2 10:30:00
order-status 1 11:00:00
order jojeX3 soltaniX2 kubideX3 7 11:30:00
order neginiX2 2 12:30:00
general-status 13:30:00
payment 1 14:00:00
general-status 14:30:00
order-status 1 15:00:00
payment 2 15:30:00
order-status 2 16:00:00
general-status 17:00:00
خروجی نمونه ۲
0 0 0 0 0 2 0 0
FREE
FREE
please sit at table number 2.
FREE
BUSY
EATING
not enough seat.
please sit at table number 1.
0 505000 0 2 0 0 0 2
you should pay 355000 Toman.
355000 150000 0 1 1 1 0 1
DONE
you should pay 150000 Toman.
DONE
505000 0 0 0 2 2 0 0
توضیح نمونه ۲
در منوی رستوران، چهار غذای «جوجه»، «کوبیده»، «سلطانی» و «نگینی» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۶۰، ۷۰، ۸۰ و ۷۵ هزار تومان است.
این رستوران ۲ میز دارد که دور میز اول، ۲ صندلی و دور میز دوم، ۴ صندلی وجود دارد.
- در ساعت ۸:۰۰ هیچ پولی نیامده و هیچ پولی قرار نیست که دریافت شود پس دو عدد اول ۰ است. چون هیچ سفارشی نیامده سه عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰اند.
- در ساعت ۸:۳۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است.
- در ساعت ۹:۰۰، وضعیت میز شماره ۲ آماده سرویس‌دهی است.
- ۴ نفر در ساعت ۹:۳۰ وارد رستوران می‌شوند. یک جوجه، یک سلطانی، دو کوبیده و یک نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۲ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
- در ساعت ۱۰:۰۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است.
- در ساعت ۱۰:۳۰، وضعیت میز شماره ۲ مشغول است.
- در ساعت ۱۱:۰۰، وضعیت سفارش اول مشغول غذا خوردن هستند.
- ۷ نفر در ساعت ۱۱:۳۰ وارد رستوران می‌شوند. سه جوجه، دو سلطانی و سه کوبیده سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با ۷ صندلی در این رستوران وجود ندارد.
- ۲ نفر در ساعت ۱۲:۳۰ وارد رستوران می‌شوند. دو نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.)
- در ساعت ۱۳:۳۰ دو سفارش آمده هنوز دریافت نشده مجموع مبلغ این سفارش‌ها ۵۰۵ هزار تومان است. چون هیچ سفارشی هنوز پرداخت نکرده، عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰ اند. چون روی هر دو میز مشغول غذا خوردن هستند سه عدد بعدی ۰ ۲ ۰ است و سه عدد آخر ۰ ۰ ۲ می‌شوند.
- سفارش شماره‌ی ۱ در ساعت ۱۴:۰۰ می‌خواهد از رستوران خارج شود. پس باید ۳۵۵ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۴:۰۲ آماده سرویس‌دهی می‌کنند.
- در ساعت ۱۴:۳۰ سفارش ۱ پرداخت شده پس مبلغ ۳۵۵ هزارتومان پرداخت شده و ۱۵۰ هزار تومان سفارش ۲ هنوز پرداخت نشده است. در این لحظه یک سفارش تمام شده و یک سفارش مشغول غذا خوردن است و هیچ سفارشی در انتظار نیست. روی یک میز مشغول غذا خوردن هستند و یک میز آماده‌ی سرویس‌دهی است.
- در ساعت ۱۵:۰۰ وضعیت سفارش ۱ انجام شده است.
- در ساعت ۱۵:۳۰ سفارش دوم پرداخت می‌کند و از رستوران خارج می‌شود. میز شماره ۱ ساعت ۱۵:۳۲ آماده سرویس‌دهی می‌شود.
- در ساعت ۱۶:۰۰ وضعیت این سفارش نیز تمام شده است.
- در ساعت ۱۷:۰۰ همه‌ی مبالغ پرداخت شده و هر دو میز آماده‌ی سرویس‌دهی و هر دو سفارش تمام شده.
ورودی نمونه ۳
25 1 1
omlet 10000
1
table-status 1 18:00:00
order omletX2 2 19:00:00
order omletX1 1 19:00:30
order omletX10 1 19:01:30
order omletX9 1 19:01:31
order omletX2 2 19:02:30
order-status 1 19:02:35
order-status 2 19:02:36
order-status 3 19:02:37
table-status 1 19:02:38
payment 2 19:03:00
payment 1 19:03:01
order-status 1 19:04:05
order-status 2 19:04:06
order-status 3 19:04:07
table-status 1 19:04:08
general-status 19:04:09
order-status 1 19:05:05
order-status 2 19:05:06
order-status 3 19:05:07
table-status 1 19:05:08
payment 2 19:05:09
table-status 1 19:06:18
table-status 1 19:07:18
general-status 19:20:00
خروجی نمونه ۲
FREE
not enough seat.
please sit at table number 1.
please wait for free table.
please wait for free table.
not enough seat.
EATING
WAITING
WAITING
BUSY
pays after eating.
you should pay 10000 Toman.
DONE
WAITING
WAITING
PENDING
10000 190000 2 0 1 0 1 0
DONE
EATING
WAITING
BUSY
you should pay 100000 Toman.
PENDING
BUSY
110000 90000 0 1 2 0 0 1
توضیح نمونه ۳
در منوی رستوران، فقط غذای «املت» وجود دارد که قیمت آن ۱۰ هزار تومان است. این رستوران فقط یک میز دارد که دور میز آن ۱ صندلی وجود دارد.
- وضعیت میز در لحظه‌ی ۱۸:۰۰:۰۰ پرسیده شد که خالی و آماده‌ی سرویس‌دهی است.
- ۲ نفر در لحظه ۱۹:۰۰:۰۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم.
- ۱ نفر در لحظه ۱۹:۰۰:۳۰ وارد رستوران می‌شوند و ۱ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود و به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
- ۱ نفر در لحظه ۱۹:۰۱:۳۰ وارد رستوران می‌شوند و ۱۰ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۲ می‌شود.)
- ۱ نفر در لحظه ۱۹:۰۱:۳۱ وارد رستوران می‌شوند و ۹ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۳ می‌شود.)
- ۲ نفر در لحظه ۱۹:۰۲:۳۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم.
- در لحظه ۱۹:۰۲:۳۵، سفارش شماره ۱ مشغول غذا خوردن است.
- در لحظه ۱۹:۰۲:۳۶، سفارش شماره ۲ در صف انتظار است.
- در لحظه ۱۹:۰۲:۳۷، سفارش شماره ۳ در صف انتظار است.
- در لحظه ۱۹:۰۲:۳۸، روی میز شماره ۱ مشغول غذا خوردن هستند. (سفارش دهنده‌ی شماره ۱)
- در لحظه ۱۹:۰۳:۰۰، سفارش شماره ۲ می‌خواهد پرداخت کند اما چون هنوز غذایش را نخورده و در صف انتظار است نباید از او پولی بگیریم.
- در لحظه ۱۹:۰۳:۰۱، سفارش شماره‌ی ۱ می‌خواهد پرداخت کند. او باید مبلغ ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۵:۰۱ آماده سرویس‌دهی می‌شود.
- در لحظه ۱۹:۰۴:۰۵، سفارش شماره ۱ مشغول خارج شده است.
- در لحظه ۱۹:۰۴:۰۶، سفارش شماره ۲ همچنان منتظر است. (چون هنوز میز آماده نشده.)
- در لحظه ۱۹:۰۴:۰۷، سفارش شماره ۳ همچنان در صف انتظار است.
- در لحظه ۱۹:۰۴:۰۸، میز شماره ۱ در حال تمیز شدن است.
- در لحظه ۱۹:۰۴:۰۹، مجموع درآمد ۱۰ هزار تومان پرداخت شده و ۱۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش کارش تمام شده است و ۲ سفارش منتظر است. یک میز در حال آماده سازی است.
- در لحظه ۱۹:۰۵:۰۵، سفارش شماره ۱ مشغول خارج شده است.
- در لحظه ۱۹:۰۵:۰۶، سفارش شماره ۲ مشغول غذا خوردن است.
- در لحظه ۱۹:۰۵:۰۷، سفارش شماره ۳ در صف انتظار است.
- در لحظه ۱۹:۰۵:۰۸، میز شماره ۱ در حال غذا خوردن است.
- در لحظه ۱۹:۰۵:۰۹، سفارش شماره‌ی ۲ می‌خواهد پرداخت کند. او باید ۱۰ تا ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۷:۰۹ آماده سرویس‌دهی می‌شود.
- در لحظه ۱۹:۰۶:۱۸، میز شماره ۱ در حال تمیز شدن است.
- در لحظه ۱۹:۰۷:۱۸، میز شماره ۱ در حال غذا خوردن است.
- مجموع درآمد ۱۱۰ هزار تومان پرداخت شده و ۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش مشغول خوردن و ۲ سفارش کارشان تمام شده است و روی یک میز مشغول غذا خوردن هستند.
ارسال پاسخ برای این سؤال