+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ارزهای دیجیتال قیمت‌گذای متمرکزی ندارند. دارندگان ارز دیجیتال می‌توانند قیمت مورد نظر برای خرید یا فروش را شخصا در قالب یک سفارش مشخص کنند. مثلاً اگر بخواهید ۲۰ واحد ارزی مفروض به نام _FirstCoin_ را به قیمت ۵۰ تومان بخرید، پیغام شما به این شکل خواهد بود ($a$ شناسه‌ی یکتای سفارش خرید شماست که توسط سیستم تولید می‌شود): `ADD a buy FirstCoin 50.00 20` اگر زمانی قصد فروش مقداری از موجودی ارز دیجیتال خود را داشته باشد، به طور مشابه مقدار و قیمت پیشنهادی خود را به دیگران اعلام می‌کنید. مثلا برای فروش ۵۰ واحد _FirstCoin_ به قسمت ۴۵ تومان، این پیغام را خواهید فرستاد ($b$ شناسه‌ی یکتای سفارش فروش شماست که توسط سیستم تولید می‌شود): `ADD b sell FirstCoin 45.00 50` موجودی سفارش‌ها ثابت نمی‌ماند و در صورت لغو سفارش یا انجام معامله ممکن است مقداری از مبلغ آن کم شود. مثلاً در صورت فروش ۳۰ واحد از سفارش $b$ پیغام زیر توسط سیستم مخابره خواهد شد: `REM b 30` مجموعه تمامی پیغام‌های مخابره شده از این دست را اصطلاحا دفتر سفارش‌ها(Order Book) می‌گویند. می‌خواهیم برنامه‌ای به نام **تعیین قیمت** بنویسیم که با دریافت دفتر سفارش‌های چند ارز دیجیتال، «بهترین قیمت» خرید و فروش برای حجم مشخص و ثابتی از هر ارز را در هر لحظه محاسبه کند. بدیهی است که برای خرید مایلیم کمترین پول ممکن را پرداخت کنیم و هنگام فروش بیشترین پول ممکن را دریافت کنیم. معیار ما برای تعیین «بهترین قیمت» نیز همین است. برنامه مورد نظر، عددی را به عنوان حجم هدف (تعداد واحدهای ارز برای خرید یا فروش) دریافت می‌کند و سپس پیغام‌های دفتر سفارش‌ها را خط به خط خوانده و به محض این که تغییری در بهترین قیمت خرید یا فروش هر ارز در حجم مورد نظر ایجاد شود، آن را در خروجی اعلام می‌کند. توجه کنید که سفارش‌های یک ارز، کاملاً مستقل از سایر ارزها است. بنابراین تبدیل ارز در دفتر سفارش‌ها معنایی ندارد و قیمت‌های اعلام شده در خروجی برنامه صرفاً بر اساس سفارش‌های ثبت شده برای یک ارز واحد محاسبه می‌شوند. # ورودی + خط اول از ورودی برنامه، شامل دو عدد است: حجم هدف (Target) و تعداد ارزها (CoinCount) که با یک فاصله از هم جدا شده‌اند: `Target CoinCount` + خط دوم فهرستی از نام ارزهای موجود را نشان می‌دهد که با یک فاصله از هم جدا شده‌اند (نام ارزها، کاراکتر فاصله ندارد): `coin_1 coin_2 … coin_N` + در خط بعدی عدد $n$ آمده است که نشان‌دهنده‌ی تعداد پیغام‌های موجود در دفتر سفارش است. در $n$ خط بعدی و در هر خط یک پیام آمده است. دو نوع پیام در دفتر سفارش وجود دارد: 1. _ثبت سفارش_ که قالب پیغام به صورت زیر است: ‍‍‍`time ADD id type coin price size‍` | نماد | معنی | |:----:|:--------------------------------------------------------:| | time | زمان ثبت سفارش به صورت یک عدد | | ADD | یک رشته‌ی حرف ثابت که مشخص کننده پیغام ثبت سفارش است | | id | یک رشته‌ی حرفی که شناسه‌ی یکتای سفارش مورد نظر است | | type | یک رشته‌ی حرفی که نوع سفارش را مشخص می‌کند و دو مقدار دارد:‌ **sell** (فروش) و **buy** (فروش) | | coin | نام یک ارز دیجیتال به صورت یک رشته حرفی (بدون فاصله) | | price | قیمت پیشنهادی برای هر واحد ارز | | size | تعداد واحد ارز موجود در سفارش | 2. تغییر موجودی که قالب پیغام به صورت زیر است: `time REM id size` | نماد | معنی | |:----:|:--------------------------------------------------------:| | time | زمان ثبت سفارش به صورت یک عدد | | REM | یک رشته‌ی حرف ثابت که مشخص کننده پیغام تغییر موجودی است | | id | شناسه‌ی یکتای سفارش مورد نظر | | size | تعداد واحد کاهش یافته از موجودی سفارش | $$1 \leq Target \leq 200$$ $$1 \leq CoinCount \leq 20$$ $$1 \leq n \leq 100\ 000$$ $$1 \leq price \leq 200\ 000$$ $$1 \leq size \leq 200$$ # خروجی خروجی برنامه عبارت است از پیغام‌هایی به شکل زیر که خط به خط در خروجی چاپ خواهند شد: `time type coin total_price` | نماد | معنی | |:----:|:--------------------------------------------------------:| | time | زمان تعیین قیمت که باید مساوی با فيلد time در آخرین پیغام دریافت شده باشد | | type | یک رشته‌ی حرف که نوع معامله‌ی مربوطه را مشخص می‌کند و می‌تواند دو مقدار داشته باشد: buy و sell | | coin | نام ارز دیجیتال | | total_price | بهترین قیمت محاسبه شده برای خرید یا فروش | **نکات تکمیلی:** + مقدار $price$_$total$ باید به صورت عددی با دو رقم اعشار گزارش شود. برای مثال به‌جای $11.4$ باید $11.40$ نوشته شود. + در صورتی که سیستم پیشتر قیمتی برای خرید یا فروش یک ارز اعلام کرده باشد، ولی با ویرایش سفارش‌ها، جمع واحد‌های موجود در سفارش‌ها به کمتر از $target$ برسد (یعنی خرید یا فروش با حجم هدف غیرممکن شود)، فیلد $price$_$total$ با رشته‌ی حرفی `NA` پر می‌شود. + **سفارشات لزوما بر اساس زمانشان مرتب نیستند.** + اگر پس از پیغامی در دفتر سفارشات، ارزش ارز مورد نظر تغییری نکند و مقدار قبلی بماند نیازی به خروجی دادن دوباره نیست. (یعنی تنها زمانی خروجی جدید می‌دهیم که مقدار قبلی اعلام شده دیگر معتبر نباشد) ## ورودی نمونه ۱ ``` 200 1 FirstCoin 5 1003 ADD c buy FirstCoin 44.10 100 1008 ADD d buy FirstCoin 44.18 157 1009 ADD e sell FirstCoin 44.38 120 1010 REM d 80 1015 ADD g sell FirstCoin 44.27 100 ``` ## خروجی نمونه ۱ ``` 1008 sell FirstCoin 8832.56 1010 sell FirstCoin NA 1015 buy FirstCoin 8865.00 ``` پس از پیغام اول سفارش جدید برای خرید ثبت شده؛‌ ولی چون همچنان از حجم هدف کم‌تر است و تغییری در ارزش حاصل نشده، چیزی در خروجی چاپ نمی‌شود. در مرحله‌ی بعد ۲۵۷ واحد درخواست خرید ثبت شده است. با توجه به قیمت‌های پیشنهادی، بهتر است ۱۵۷ واحد را از سفارش $d$ (قیمت بیشتر) و ۴۳ واحد از سفارش $c$ انتخاب می‌کنیم که جمعا ۸۸۳۲.۵۶ تومان بهترین قیمت برای فروش محاسبه می‌شود. در مرحله‌ی بعد ۸۰ واحد از مجموع سفارش‌های خرید کم می‌شود و کلا ۱۷۷ واحد باقی می‌ماند. پس فروش ۲۰۰ واحد غیرممکن و مبلغ فروش قبلی نامعتبر است. در مرحله‌ی آخر نیز ۱۰۰ واحد از سفارش $g$ (قیمت کمتر) و ۱۰۰ واحد از سفارش $e$ می‌خریم که جمعا ۸۸۶۵ تومان پایین‌ترین قیمت فروش محاسبه می‌شود. ## ورودی نمونه ۲ ``` 1 1 FirstCoin 5 1003 ADD c buy FirstCoin 4410 100 1008 ADD d buy FirstCoin 4418 157 1009 ADD e sell FirstCoin 4438 120 1010 REM d 80 1015 ADD g sell FirstCoin 4427 100 ``` ## خروجی نمونه ۲ ``` 1003 sell FirstCoin 4410.00 1008 sell FirstCoin 4418.00 1009 buy FirstCoin 4438.00 1015 buy FirstCoin 4427.00 ```

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