+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- احمد مسئول برگزاری یک سری مسابقات سنگین شده است. او از این کار جدید خیلی خوشحال است ولی برگزاری چنین مسابقاتی خیلی سخت است و نیاز به یک برنامه‌نویس خبره برای نوشتن سیستم مدیریت آن دارد، برای همین او از شما می‌خواهد تا سیستمی طراحی کنید که این مسابقات را مدیریت کند. مسابقات به این شکل برگزار می‌شود که در هر لحظه تعدادی بازیکن در مسابقات وجود دارند که می‌خواهند با یکدیگر بازی کنند. هم‌چنین تعدادی درخواست بازی در هر زمان وجود دارد که در پایین توضیح داده می‌شود. هر بازیکن یک قدرت ($s_i$) و یک جنبه، ($g_i$) دارد. اگر کسی تعداد بازی‌هایی که باخته است بیشتر از جنبه‌اش شود،‌ از مسابقات انصراف می‌دهد. همچنین اگر کسی تقلب کند، از مسابقات حذف خواهد شد و به تبع آن، درخواست‌هایش نیز نادیده گرفته می‌شوند. بازی‌ها تنها با توافق طرفین انجام می‌شود،‌ یعنی زمانی یک بازی شکل می‌گیرد که هر دو طرف راضی باشند که با حریفی با ویژگی‌های فعلی رقابت کنند. نحوه ایجاد بازی‌ها هم بدین‌گونه است که بازیکن‌ها درخواست بازی می‌دهند و اگر شرایط لازم برای آن درخواست را داشتند، درخواستشان اجرا می‌شود و در غیر این صورت نادیده گرفته می‌شود. اجرا شدن درخواست‌های بازی به شکل زیر است: 1. در هر مرحله یک مجموعه از درخواست‌های بازی، از افراد مختلف وجود دارد. 2. وقتی درخواست جدیدی ثبت‌ می‌شود، بررسی می‌شود که آیا با درخواست‌های قبلی مطابقت دارد یا نه. اگر مطابقت نداشت به مجموعه اضافه می‌شود. 3. اگر درخواست جدید با چند مورد از درخواست‌های صف انتظار مطابقت داشت، اولویت انتخاب به ترتیب با موارد زیر است (در صورت تساوی بازیکنان در یک زمینه به اولویت بعدی نگاه می‌کنیم): + بازیکن درخواست‌کننده امتیاز کمتری داشته باشد. امتیاز آن بازیکن در زمان ایجاد درخواست مد نظر است و امتیاز فعلی آن اهمیتی ندارد. + بازیکن درخواست‌کننده جنبه بیشتری داشته باشد. + درخواست مورد نظر قدیمی‌تر باشد، یعنی در زمان زودتری ایجاد شده باشد. می‌دانیم در بازی بازیکن‌های $x$ و $y$، اگر قدرت بازیکن $x$ را $ g_x $ و قدرت بازیکن $y$ را $ g_y $ در نظر بگیریم، بازیکنی که زودتر درخواست بازی را داده است می‌برد، اگر و تنها اگر، باقی‌مانده تقسیم عدد $g_x \times g_y$ بر $ g_x + g_y $ بزرگتر از $ |g_x - g_y| $ باشد. در انتها نیز برنده‌ بازی به اندازه قدرت بازیکن مقابل،‌ امتیاز دریافت می‌کند و تغییری در امتیاز بازنده ایجاد نمی‌شود. می‌دانیم هر دقیقه‌ای که می‌گذرد، یک اتفاق جدید می‌افتد و نتیجه آن بر مسابقات در همان دقیقه اعمال می‌شود. در هر دقیقه از بازی یکی از اتفاقات زیر رخ می‌دهد: 1. بازیکنی به اسم $s$، با قدرت $g$ و جنبه $k$ به بازی اضافه می‌شود. دقت کنید که امتیاز هر بازیکن زمان اضافه شدن به بازی صفر است (اسم‌های بازیکن‌ها متمایز است). 2. کمیته مسابقات متوجه تقلب بازیکنی با نام $s$ می‌شود. 3. بازیکنی با نام $s$ درخواست بازی عمومی می‌کند، یعنی اگر شخص دیگری درخواستی داده که $s$، شامل شرایط آن می‌شود، با او بازی می‌کند. 4. بازیکنی با نام $s$ درخواست بازی با بازیکنی که امتیاز آن حداقل $l$ و حداکثر $r$ است را می‌کند. برای پیگیری این درخواست توسط کمیته مسابقات، این بازیکن باید حداقل ۵ امتیاز داشته باشد و پس از اجرای این درخواست هم ۲ امتیاز از این بازیکن کم می‌شود. (دقت کنید موقعی که درخواست پذیرفته می‌شود، امتیاز کسر نمی‌شود و زمانی که بازی انجام می‌شود، امتیاز موردنظر کسر می‌شود). 5. بازیکنی با نام $s$ درخواست بازی اختصاصی با بازیکنی به اسم $t$ را می‌کند. برای اینکه درخواست بازیکن پذیرفته شود، باید حداقل ۱۰ امتیاز داشته باشد و پس از اجرای این درخواست (انجام بازی)، ۳ امتیاز از بازیکن کسر می‌شود. می‌دانیم که وقتی این درخواست صورت می‌گیرد، بازیکنی با نام $t$ حتما در مسابقات حاضر است. 6. جدول رده‌بندی را تا لحظه فعلی چاپ کنید، بدین شکل که ابتدا در یک خط عبارت `scoreboard:` را چاپ کنید. سپس بازیکن‌ها بر اساس اولویت‌های زیر مرتب مرتب کنید و اسم آن‌ها به ترتیب در خطوط جداگانه خروجی دهید: + بازیکن امتیاز بالاتری داشته باشد. + قدرت بازیکن کمتر باشد. + جنبه بازیکن بیشتر باشد. + تعداد درخواست‌های مورد قبول بازیکن تا بدین‌جا کمتر باشد. (اجرا شدن درخواست‌ها برایمان اهمیتی ندارد و فقط وارد شدن آن‌ها به صف انتظار برایمان مهم است) + اسم بازیکن از نظر کتابخانه‌ای کوچکتر باشد. (برای آشنایی با ترتیب کتاب‌خانه‌ای می‌توانید به این [لینک](https://en.wikipedia.org/wiki/Lexicographical_order) مراجعه کنید) به موارد زیر هم در هنگام پیاده‌سازی توجه کنید: + اگر کسی از مسابقات انصراف دهد یا حذف شود، دیگر در جدول رده‌بندی چاپ نمی‌شود و اجازه بازی جدید ندارد. همچنین اگر درخواست جدیدی بدهد، نادیده گرفته می‌شود و درخواست‌های قبلی او نیز از صف انتظار حذف خواهند شد. + اگر یکی از درخواست‌ها شرایط مدنظر کمیته را نداشت لازم نیست چیزی چاپ کنید و صرفا آن درخواست حذف می‌شود. + نام افراد حاضر در مسابقه با هم متمایز است. # ورودی با ظاهر شدن عبارت `start` در ورودی مسابقات شروع می‌شود. پس از شروع مسابقات،‌ هر خط نشان‌دهنده بروز یکی از ۶ اتفاق ممکن در صورت سوال است. قالب اتفاقات مختلف به صورت زیر است ($i$امین قالب مربوط به $i$امین نوع اتفاق در بازی است): 1. `add $s$ $g$ $k` 2. `$s$ cheats` 3. `$s$ competes everybody` 4. `$s$ competes between $l$ $r$` 5. `$s$ competes $t$` 6. `print scoreboard` تضمین می‌شود هر خط از ورودی دقیقا با یکی از قالب‌های ارائه شده همخوانی دارد. همچنین اسامی بازیکنان تنها از حروف کوچک انگلیسی تشکیل شده است و همه اعداد نیز از صفر تا هزار هستند. با ظاهر شدن عبارت `end` ورودی پایان می‌یابد. تعداد خطوط ورودی‌ حداکثر هزارتاست. # خروجی به ازای هر بار درخواست شماره ۶، جدول رده‌بندی را به صورت کامل چاپ کنید. # مثال ## ورودی نمونه ۱ ``` start print scoreboard add ali 10 1 add ahmad 0 0 print scoreboard ahmad competes everybody ahmad competes everybody ali competes everybody ali competes everybody add erfan 100 0 erfan competes everybody print scoreboard erfan competes between 0 100 print scoreboard ahmad competes between 0 100 print scoreboard ahmad competes everybody print scoreboard end ``` ## خروجی نمونه ۱ ``` scoreboard: scoreboard: ahmad ali scoreboard: erfan ali scoreboard: erfan ali scoreboard: erfan ali scoreboard: erfan ali ``` در ابتدا که هیچ شرکت‌کننده‌ای وجود ندارد. پس از آن دو بازیکن به نام‌های علی و احمد به مسابقات اضافه می‌شوند که قدرت آن‌ها به ترتیب برابر ده و صفر می‌باشد و لذا احمد که قدرت کمتری دارد، در رده‌بندی بالاتر است. پس از آن احمد دو بار درخواست رقابت عمومی می‌دهد و درخواست‌هایش پذیرفته شده و داخل صف انتظار قرار می‌گیرند. سپس علی درخواست رقابت عمومی می‌دهد و این درخواست او با درخواست اول احمد مطابقت پیدا کرد و آن دو به رقابت پرداختند. در این‌جا چون احمد در ابتدا درخواست داده بود و شرط گفته شده در صورت سوال برقرار نبود، علی برنده بازی می‌شود و چون جنبه احمد صفر است و تعداد باخت‌هایش بیشتر از جنبه‌اش شده است، از مسابقات انصراف می‌دهد. البته با این برد، علی امتیاز خاصی به دست نمی‌آورد چون قدرت احمد برابر صفر بوده است. پس از آن علی یک بار دیگر درخواست بازی ارائه می‌دهد ولی چون درخواستی در صف انتظار وجود ندارد (درخواست احمد پس از حذف او از صف حذف شده است)، باید منتظر درخواست دیگری بماند. حال بازیکنی جدید به نام عرفان و با قدرت صد به بازی اضافه می‌شود و درخواست یک بازی عمومی را می‌کند و چون درخواستش با درخواست علی مطابقت دارد، این دو وارد بازی می‌شوند. چون علی درخواست‌کننده اول بوده و همچنین شرط گفته شده در صورت سوال برقرار نیست، پس عرفان برنده بازی می‌شود و ده امتیاز به دست می‌آورد و در جدول رده‌بندی در صدر قرار می‌گیرد. حال عرفان یک درخواست بازی جدید ثبت می‌کند و چون امتیاز اون بیشتر مساوی پنج است، درخواستش به صف انتظار می‌رود ولی از آن‌جایی که پس از او فقط احمد درخواست می‌دهد و درخواست‌های او توسط کمیته مسابقات نادیده گرفته می‌شوند، دیگر بازی صورت نمی‌گیرد و جدول رده‌بندی مسابقات تا انتها ثابت می‌ماند.

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