+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌خواهیم سیستم سفارش گرفتن و تخصیص راننده‌ها به سفارش‌ها را برای اسنپ باکس شبیه سازی کنیم. در ابتدا هیچ راننده و یا سفارشی نداریم. در هر مرحله یا یک راننده به سیستم اضافه می‌شود یا یک سفارش در سیستم ثبت می‌شود یا یک راننده درخواست می‌کند که یک سفارش به او تخصیص شود. هر راننده بعد از تخصیص یک سفارش مرحله به مرحله گزارش می‌دهد که فرآیند ارسال این سفارش از فرستنده به گیرنده در کدام مرحله قرار دارد. از شما می‌خواهیم با دریافت این اطلاعات این سامانه را شبیه سازی کنید. همچنین سیستم شبیه ساز شما باید قابلیت پاسخ دادن به درخواست‌هایی که در پایین تر تعریف کردیم را داشته باشد. <details class="green"> <summary> **راننده** </summary> راننده (`DRIVER`) سفارش را از فرستنده تحویل گرفته و به گیرنده تحویل می‌دهد. برای هر راننده ویژگی‌‌های زیر تعریف می‌شود: ### نام (`USERNAME`): یک رشته که فقط شامل حروف کوچک و بزرگ انگلیسی و ارقام است و حداکثر شامل ۲۵ کاراکتر می‌شود. ### نوع وسیله (`SERVICE-CATEGORY`): وسیله‌ی نقلیه راننده را نشان می‌دهد و مقدار آن همواره یکی از موارد زیر است. + موتور (`BIKE`) + وانت (`VAN`) + کامیون (`TRUCK`) ### میزان اعتبار (`CREDIT`): یک عدد حسابی است که مقدار پولی که راننده در حساب اسنپ خود دارد را نشان می‌دهد. میزان سرمایه اولیه هر راننده به صورت پیشفرض برابر صفر است. میزان اعتبار هر راننده بعد از تحویل یک سفارش (یعنی زمانی که وضعیت سفارش به `DELIVERED` تغییر کند.) به اندازه $80$% هزینه سفارش افزایش پیدا می‌کند. ### موقعیت مکانی (`POSITION`): موقعیت مکانی هر راننده به صورت یک زوج مرتب $(x, y)$ است که $x$ و $y$ دو عدد صحیح هستند. برای نمایش و دریافت یک `POSITION` ابتدا یک `(` سپس عدد $x$ بلافاصله `,` سپس با یک فاصله عدد $y$ و بلافاصله `)` نمایش داده می‌شود. به طور مثال موقعیت مکانی یک راننده می‌تواند به صورت `(57, 31)` یا `(0, -74)` باشد اما `(0 , -74)` یا `( 57 31)` نمایش قابل قبولی نیست. ### وضعیت (`STATUS`): بطور کلی راننده دارای دو وضعیت زیر است: + آزاد (`FREE`) + مشغول (`BUSY`) اگر یک راننده در حال انجام دادن یک سفارش باشد یعنی در حال رفتن به سمت فرستنده برای دریافت محموله (به عبارت دیگر محموله تخصیص یافته به آن در حالت `ARRIVED` باشد.) یا در حال رفتن به سمت گیرنده برای تحویل محموله (به عبارت دیگر سفارش تخصیص‌یافته به آن در حالت `PICKUP` باشد.) باشد؛ راننده در وضعیت `BUSY` و اگر هیچ سفارشی به این راننده تخصیص نشده یا همه سفارش‌هایی که به او تخصیص شده را تحویل داده است (یعنی وضعیت سفارش‌های تخصیص‌یافته `DELIVERED` باشد.) وضعیت راننده `FREE` است. </details> <details class="green"> <summary> **سفارش** </summary> برای هر سفارش (`ORDER`) ویژگی‌‌های زیر قابل تعریف است: ### نوع وسیله (`SERVICE-CATEGORY`): وسیله‌ی مورد نیاز برای جابه‌جایی این سفارش را نشان می‌دهد و مقدار آن همواره یکی از موارد زیر است. + موتور (`BIKE`) + وانت (`VAN`) + کامیون (`TRUCK`) ### موقعیت مکانی فرستنده (`STARTING-POSITION`): موقعیت مکانی فرستنده به صورت یک زوج مرتب $(x, y)$ است که $x$ و $y$ دو عدد صحیح هستند. نمایش و دریافت موقعیت مکانی فرستنده مشابه موقعیت مکانی راننده است. ### موقعیت مکانی گیرنده: (`FINISHING-POSITION`): موقعیت مکانی گیرنده به صورت یک زوج مرتب $(x, y)$ است که $x$ و $y$ دو عدد صحیح هستند. نمایش و دریافت موقعیت گیرنده مشابه موقعیت مکانی راننده است. ### هزینه (`COST`): هزینه هر سفارش با توجه به فرمول زیر محاسبه می‌شود: فرض کنید $(x, y)$ موقعیت مکانی فرستنده و $(x', y')$ موقعیت مکانی گیرنده باشد. اگر تعداد سفارش‌هایی که هم اکنون منتظر راننده **با همین نوع وسیله** هستند (یعنی وضعیت آن‌ها `PENDING` است.) **شامل همین سفارش**، برابر $k$ باشد این هزینه برابر است با: $$cost = (k + |x - x'| + |y - y'|) \times 100 $$ توجه کنید بعد تحویل هر سفارش $80$% هزینه به اعتبار (`CREDIT`) راننده اضافه می‌شود و $20$% باقی مانده به حساب اسنپ باکس اضافه می‌شود. (با توجه به رابطه بالا این دو عدد همواره عدد صحیح خواهند بود.) ### شماره سفارش (`ORDER-ID`): شماره یک سفارش $n$ است اگر $n$امین سفارشی باشد که با موفقیت در سیستم ثبت شده باشد. ### وضعیت (`STATUS`): وضعیت هر سفارش چهار حالت دارد: + `PENDING`: هنوز راننده‌ای به این سفارش تخصیص داده نشده است. + `ARRIVED`: یک راننده به این سفارش تخصیص داده شده و به سمت فرستنده این سفارش در حال حرکت است. + `PICKUP`: راننده این سفارش را از فرستنده تحویل گرفته و در حال حرکت به سمت گیرنده است. + `DELIVERED`: سفارش با موفقیت به گیرنده تحویل داده شده است. </details> منظور از فاصله بین دو نقطه $(x, y)$ و $(x', y')$ در این سوال برابر است با: $$|x - x'| + |y - y'|$$ از شما می‌خواهیم درخواست‌های زیر را برای این سامانه پیاده سازی کنید: <details class="blue"> <summary> **درخواست** `ADD-DRIVER` </summary> این درخواست به معنی اضافه شدن یک راننده (`DRIVER`) به سیستم است. ``` ADD-DRIVER <DRIVER-USERNAME> <POSITION> <SERVICE-CATEGORY> ``` به جای `<DRIVER-USERNAME>` یک رشته که نشان دهنده نام راننده، به جای `<POSITION>` موقعیت مکانی فعلی راننده که یک زوج مرتب از اعداد صحیح است و به جای `<SERVICE-CATEGORY>` نوع وسیله راننده که یک رشته برابر `BIKE` یا `VAN` یا `TRUCK` است قرار دارد. برای مثال یک نمونه از این درخواست به صورت زیر خواهد بود: `ADD-DRIVER shahin021 (13, 74) BIKE` بعد از دریافت این نوع درخواست، در صورتی که این نام برای راننده‌ای دیگر قبلاً استفاده شده است عبارت `user previously added` را چاپ کنید و در صورتی که نام راننده قبلاً در سیستم ثبت نشده عبارت `user added successfully` را چاپ کنید. میزان اعتبار یک راننده در لحظه اضافه شدن به سیستم برابر صفر است. وضعیت یک راننده بعد از اضافه شدن به سیستم `FREE` است چون هنوز هیچ سفارشی به او تخصیص نشده است. </details> <details class="blue"> <summary> **درخواست** `CREATE-ORDER` </summary> این درخواست به معنی اضافه شدن یک سفارش (`ORDER`) به سیستم است. ``` CREATE-ORDER <SERVICE-CATEGORY> <START-POSITION> <FINISH-POSITION> ``` به جای `<SERVICE-CATEGORY>` یک رشته که نوع وسیله‌ای که برای انجام این سفارش نیاز است قرار دارد و مقدار آن برابر `BIKE` یا `VAN` یا `TRUCK` است. منظور از `<START-POSITION>` موقعیت مکانی فرستنده سفارش است، همچنین منظور از `<FINISH-POSITION>` موقعیت مکانی گیرنده سفارش است. هر دو این مقدار‌ها به صورت یک زوج مرتب از اعداد صحیح به همان روش توضیح داده شده آمده است. برای مثال یک نمونه از این درخواست به صورت زیر خواهد بود: `CREATE-ORDER TRUCK (-100, 100) (100, -100)` بعد از دریافت این درخواست، در صورتی که `<START-POSITION>` برابر `<FINISH-POSITION>` باشد عبارت `invalid order` و در غیر این صورت شماره این سفارش را برای این سفارش ثبت و سپس چاپ کنید. هزینه این سفارش (`COST`) در این لحظه، از فرمول توضیح داده شده محاسبه می‌شود. همچنین وضعیت (`STATUS`) یک سفارش بلافاصله بعد از ایجاد `PENDING` خواهد بود. </details> <details class="blue"> <summary> **درخواست** `ASSIGN-NEXT-ORDER` </summary> این درخواست به معنی تقاضا یک راننده برای تخصیص به نزدیک‌ترین سفارش است. ``` ASSIGN-NEXT-ORDER <USERNAME> ``` در صورتی که راننده‌ای به چنین اسمی نداریم عبارت `invalid driver name` را چاپ کنید. در صورتی که وضعیت این راننده `BUSY` است عبارت `driver is already busy` را چاپ کنید. در صورتی که سفارشی در وضعیت `PENDING` با وسیله یکسان با راننده وجود ندارد عبارت `there is no order right now` را چاپ کنید. در صورتی که هیچ کدام از حالت‌های بالا پیش نیامد سفارشی با وضعیت `PENDING` را انتخاب می‌کنیم که کمترین فاصله با موقعیت مکانی فعلی راننده را دارد. اگر چند سفارش با فاصله برابر وجود داشتند سفارشی را انتخاب می‌کنیم که زودتر به سیستم اضافه شده است. سپس عبارت زیر را چاپ می‌کنیم. ``` <ORDER-ID> assigned to <USERNAME> ``` که `ORDER-ID` به معنی شماره سفارش تخصیص یافته به راننده با نام `USERNAME` است. بعد از این تخصیص وضعیت (`STATUS`) راننده به `BUSY` و وضعیت (`STATUS`) سفارش به `ARRIVED` تغییر خواهد کرد. </details> <details class="blue"> <summary> **درخواست** `GET-DRIVER` </summary> در این درخواست وضعیت یک راننده پرسیده می‌شود. ``` GET-DRIVER <USERNAME> ``` در صورتی که راننده‌ای به چنین اسمی نداریم عبارت `invalid driver name` را چاپ کنید. در غیر این صورت، ابتدا `STATUS` این راننده را چاپ کنید (یعنی در صورت مشغول بودن رشته `BUSY` و در غیراین صورت رشته `FREE` را چاپ کنید.). سپس با یک فاصله موقعیت مکانی فعلی راننده را چاپ کنید سپس با یک فاصله اعتبار حساب راننده را چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `ORDER-UPDATE` </summary> در این دستور یک راننده تغییر وضعیت سفارش خود را اعلام می‌کند. ``` ORDER-UPDATE <STATUS> <DRIVER-USERNAME> <ORDER-ID> ``` در صورتی که راننده‌ای به چنین اسمی در سیستم وجود ندارد عبارت `invalid driver name` را چاپ کنید. در صورتی که شماره سفارش تخصیص یافته به این راننده برابر `ORDER-ID` نیست عبارت `wrong order-id` را چاپ کنید. در صورتی که تغییر وضعیت قابل قبول نیست عبارت `invalid status` و در غیر این صورت عبارت `status changed successfully` را چاپ کنید. توجه کنید وضعیت یک سفارش به صورت زیر تغییر می‌کند: `PENDING -> ARRIVED -> PICKUP -> DELIVERED` پس تغییر وضعیت، قابل قبول است اگر به **دقیقاً به مرحله بعدی** برود. (به طور مثال نباید وضعیت یک سفارش در یک مرحله از `PENDING` به `PICKUP` تغییر کند یا نباید وضعیت یک سفارش به وضعیت فعلی خودش تغییر کند.) زمانی که وضعیت یک سفارش به حالت `DELIVERED` تغییر می‌کند. 80 درصد هزینه سفارش به حساب راننده اضافه می‌شود و 20 درصد باقی مانده به حساب شرکت اضافه می‌شود. (تضمین می‌شود هزینه‌ای که باید به حساب راننده یا شرکت اضافه شود عدد صحیح است.) در صورتی که وضعیت سفارش به `PICKUP` تغییر کند موقعیت مکانی راننده به موقعیت مکانی فرستنده سفارش تغییر می‌کند. در صورت تغییر وضعیت سفارش به `DELIVERED` وضعیت راننده به `FREE` و موقعیت مکانی راننده به گیرنده سفارش تغییر می‌کند. </details> <details class="blue"> <summary> **درخواست** `GET-ORDER` </summary> در این درخواست وضعیت یک سفارش را پیگیری می‌کنیم. ``` GET-ORDER <ORDER-ID> ``` در صورتی که چنین سفارشی وجود ندارد عبارت `invalid order` و در غیر این صورت در یک خط ابتدا وضعیت (`STATUS`) این سفارش سپس با یک فاصله نام (`USERNAME`) راننده‌ای که در حال ارسال این سفارش است و در نهایت با یک فاصله، هزینه (`COST`) ارسال این سفارش را چاپ کنید. اگر این سفارش به هیچ راننده‌ای تخصیص پیدا نکرده است عبارت `None` را به جای نام راننده چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `GET-ORDER-LIST` </summary> در این درخواست لیست تمام سفارش‌هایی که وضعیتشان برابر `<STATUS>` است را چاپ کنید. ``` GET-ORDER-LIST <STATUS> ``` شماره تمام سفارش‌هایی که وضعیت (`STATUS`) آن‌ها برابر `<STATUS>` است را در یک خط با یک فاصله بین شماره‌ها چاپ کنید. اگر هیچ سفارشی در این وضعیت نبود کلمه `None` را چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `GET-DRIVER-LIST` </summary> در این درخواست لیست تمام راننده‌هایی که وضعیتشان برابر `<STATUS>` است را چاپ کنید. ``` GET-DRIVER-LIST <STATUS> ``` نام تمام راننده‌هایی که وضعیت (`STATUS`) آن‌ها برابر `<STATUS>` است را با یک فاصله بین نام‌ها در یک خط چاپ کنید. اگر هیچ راننده‌ای در این وضعیت نبود کلمه `None` را چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `GET-NEAR-DRIVER` </summary> در این درخواست `COUNT` تا نزدیک ترین راننده به نقطه `<POSITION>` با وضعیت `FREE` را می‌پرسیم. ``` GET-NEAR-DRIVER <POSITION> <COUNT> ``` این لیست را به ترتیب فاصله چاپ کنید (یعنی نام رانند‌ه‌ای که فاصله‌ی کمتری با نقطه‌ی موردنظر دارد، باید قبل از نام راننده‌ای که فاصله‌ی بیشتری با نقطه‌ی موردنظر دارد، چاپ شود.). اگر دو راننده فاصله یکسانی داشتند راننده‌ای که زودتر به سیستم اضافه شده را زودتر چاپ کنید. در صورتی که تعداد راننده‌ها کمتر از `COUNT` بود همه راننده‌های قابل قبول را چاپ کنید. در صورت خالی بودن لیست `None` چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `GET-CNT-ORDER` </summary> در این درخواست تعداد سفارشاتی که محل فرستنده یا گیرنده (بستگی به `START` یا `FINISH` بودن درخواست) که از نقطه `POSITION` فاصله حداکثر `DISTANCE` دارند را چاپ کنید. ``` GET-CNT-ORDER <POSITION> <DISTANCE> <START/FINISH> ``` دقت کنید که `<START/FINISH>‍`، همواره یکی از مقادیر `START` یا `FINISH` را داراست. </details> <details class="blue"> <summary> **درخواست** `GET-NEAREST-PENDING-ORDER` </summary> شماره (`ORDER-ID`) نزدیک ترین سفارش با وضعیت `PENDING` که فرستنده آن به `POSITION` است را چاپ کنید. ``` GET-NEAREST-PENDING-ORDER <POSITION> ``` اگر چنین سفارشی وجود نداشت کلمه `None` و در غیر این صورت شماره سفارش را چاپ کنید. </details> <details class="blue"> <summary> **درخواست** `GET-COMPANY` </summary> در این درخواست سود شرکت را از سفارش‌های تحویل داده شده تا این لحظه چاپ کنید. ``` GET-COMPANY ``` پاسخ همواره به صورت یک عدد صحیح است. </details> # ورودی در هر سطر از ورودی یکی از انواع درخواست‌های تعریف شده داده می‌شود. قدرمطلق همه اعداد داده شده حداکثر $1000$ و تعداد درخواست‌ها در این سوال حداکثر $100$ خواهد بود. # خروجی در هر سطر خروجی عبارت متناسب با درخواست‌ها را به ترتیب چاپ کنید. در آخرین خط ورودی تنها کلمه `END` برای نشان دادن پایان دستورات نوشته می‌شود. # مثال + توجه کنید که خروجی خط $i$ام، مربوط به ورودی خط $i$ام می‌باشد. ## ورودی نمونه ۱ ``` terminal ADD-DRIVER Ali (10, 10) VAN ADD-DRIVER GHoLI (0, 0) BIKE ADD-DRIVER Ali (45, 90) VAN CREATE-ORDER VAN (18, 10) (-33, 66) ASSIGN-NEXT-ORDER Ali GET-DRIVER GHoLI GET-DRIVER Ali ORDER-UPDATE DELIVERED ali 1 ORDER-UPDATE PICKUP Ali 1 ORDER-UPDATE DELIVERED Ali 1 GET-ORDER 1 GET-ORDER-LIST ARRIVED GET-ORDER-LIST DELIVERED GET-DRIVER-LIST FREE GET-NEAR-DRIVER (5, -21) 3 GET-CNT-ORDER (-40, -80) 100 START GET-CNT-ORDER (0, 0) 100 FINISH GET-NEAREST-PENDING-ORDER (20, 20) GET-COMPANY END ``` ## خروجی نمونه ۱ ``` terminal user added successfully user added successfully user previously added 1 1 assigned to Ali FREE (0, 0) 0 BUSY (10, 10) 0 invalid driver name status changed successfully status changed successfully DELIVERED Ali 10800 None 1 Ali GHoLI GHoLI Ali 0 1 None 2160 ``` ## ورودی نمونه ۲ ``` terminal ADD-DRIVER Mohammad021 (-142, 21) TRUCK ADD-DRIVER kami (20, 20) VAN ADD-DRIVER 00MOHSEN (0, 128) TRUCK ADD-DRIVER kami (30, 30) BIKE ADD-DRIVER SaMi (55, -2) BIKE GET-DRIVER 00MOHSEN CREATE-ORDER TRUCK (0, 0) (100, 18) CREATE-ORDER BIKE (19, -38) (-40, 127) CREATE-ORDER VAN (16, 16) (-75, 75) ASSIGN-NEXT-ORDER SaMi CREATE-ORDER TRUCK (-10, 100) (-11, 100) ASSIGN-NEXT-ORDER 00MOHSEN ASSIGN-NEXT-ORDER SaMi GET-DRIVER sami GET-DRIVER SaMi ORDER-UPDATE DELIVERED 00MOHSEN 3 ORDER-UPDATE PICKUP 00MOHSEN 4 ORDER-UPDATE DELIVERED 00MOHSEN 4 GET-DRIVER 00MOHSEN GET-ORDER 2 GET-ORDER 3 GET-ORDER-LIST PENDING GET-ORDER-LIST ARRIVED GET-DRIVER-LIST BUSY GET-DRIVER-LIST FREE GET-NEAR-DRIVER (78, 29) 2 GET-NEAR-DRIVER (-70, 50) 1 GET-CNT-ORDER (0, 0) 133 FINISH GET-CNT-ORDER (-29, 101) 77 START GET-NEAREST-PENDING-ORDER (17, 23) GET-NEAREST-PENDING-ORDER (0, 0) GET-COMPANY ORDER-UPDATE PICKUP SaMi 2 ORDER-UPDATE DELIVERED SaMi 2 GET-COMPANY END ``` ## خروجی نمونه ۲ ``` terminal user added successfully user added successfully user added successfully user previously added user added successfully FREE (0, 128) 0 1 2 3 2 assigned to SaMi 4 4 assigned to 00MOHSEN driver is already busy invalid driver name BUSY (55, -2) 0 wrong order-id status changed successfully status changed successfully FREE (-11, 100) 240 ARRIVED SaMi 22500 PENDING None 15100 1 3 2 SaMi Mohammad021 kami 00MOHSEN kami 00MOHSEN Mohammad021 2 1 3 1 60 status changed successfully status changed successfully 4560 ```

حل سؤال در بانک سؤالات