زاریچ در کنار فعالیت‌های درسیش در شرکت راه‌سازی «صراط مستقیم» پیمانکار است. شهردار در صدد پیاده سازی «طرح زیباسازی» در قزوین برآمده است. قزوین دارای تعدادی تقاطع و تعدادی جاده دوطرفه بین تقاطع‌هاست. برخی از تقاطع‌ها در قزوین مهم هستند.
می‌گوییم یک شهر زیباپذیر است اگر تمامی جاده‌های آن خاکی باشد و گراف متناظر با تقاطع‌ها و جاده‌های آن ساده، همبند و بدون یال برشی باشد. به عبارتی پس از حذف کردن یک جاده دلخواه از این شهر همچنان با جاده‌های باقی‌مانده بتوان از هر تقاطع به هر تقاطع دیگر رسید (جاده‌ها می‌توانند پل یا زیرگذر باشند پس لزومی ندارد مسطح باشد).
می‌توان یک شهر زیباپذیر را با سنگفرش کردن تعدادی جاده زیبا کرد به صورتی که تعداد جاده‌های سنگفرش منتهی به تقاطع‌های مهم فرد و تعداد جاده‌های سنگفرش منتهی به باقی تقاطع‌ها زوج باشد (مشخص است برای اینکه بتوان یک شهر را زیبا کرد لازم است که تعداد تقاطع‌های مهم زوج باشد). همچنین هزینه‌ی زیباسازی یک شهر برابر است با حداقل تعداد جاده‌هایی که باید سنگفرش شوند تا شهر زیبا شود. برای مثال هزینه زیبا سازی شهری که هیچ تقاط مهمی ندارد صفر است.
زاریچ از تصمیم شهردار با خبر شده و چون صراط مستقیم به صورت انحصاری جاده‌های خاکی را سنگفرش می‌کند، می‌خواهد ببیند که شرکت چقدر پول از این پروژه دولتی به جیب می‌زند. اما او نمی‌داند که تقاطع‌ها چگونه به یکدیگر وصل شده‌اند و کدام تقاطع‌ها مهم هستند و تنها می‌داند قزوین شهری با $n$ تقاطع و زیباپذیر است.
به زوج مرتب $(G, A)$ یک سناریو می‌گوییم که در آن گراف متناظر با شهر قزوین گراف $G$ است و زیرمجموعه‌ی زوج عضوی $A$ از تقاطع‌های قزوین مهم هستند. دو سناریو مانند $(G_1, A_1)$ و $(G_2, A_2)$ متمایز هستند اگر و تنها اگر یا $G_1$ با $G_2$ یکریخت نباشد و یا یکریخت هستند و $A_1 \neq A_2$.
زاریچ مشغول بازی با نمایشگر پیکسلی‌اش است پس از شما می‌خواهد:
آ. بیشینه‌ی هزینه‌ی زیباسازی شهر قزوین را برحسب $n$ میان تمامی سناریوهای ممکن بیابید. (۳۰ امتیاز)
ب. مشخص کنید به ازای چند سناریو (باز هم برحسب $n$) هزینه زیباسازی شهر قزوین بیشینه است (به عبارتی برابر با مقدار به دست آمده در قسمت قبل است).

• سوال بعد
• سوال قبل