در لیگ فوتبال $n$ تیم وجود دارند و هر دو تیمی با هم یک بازی انجام دادهاند. در هر بازی، در صورتی که دو تیم با هم مساوی کنند هر دو یک امتیاز و در غیر این صورت تیم برنده 3 امتیاز کسب میکند.
به شما جدول امتیازیات پس از اتمام تمام بازیها داده شده است ، شما باید تعداد حالاتی که میتواند نتیجه بازیها باشد را بهدست آورید.
در سطر اول ورودی عدد $1 \leq n \leq 8$ و در سطر بعدی $n$ عدد آمده است که امتیاز تیمها را نشان میدهد.
در تنها سطر خروجی پاسخ سؤال را چاپ نمایید.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 3 3 | 2 |
پاسخ
برای حل این سوال از backtrack استفاده میکنیم. $n$ در این سوال در بیشترین حالت $۸$ است، پس $n$ کوچک است اما واضح است که complete search جواب نمیدهد و از محدوده زمانی خارج است. بدین منظور باید backtrack خود را بهینه optimize ) )کنیم. نکته کلیدی در حل این سؤال این است که امتیاز هر تیم را در اختیار داریم و اگر تعداد بردهای یک نفر را $w$ و مساویها را $d$ بگیریم میدانیم که (امتیاز آن تیم برابر $3w + d$ است) و میدانیم که مجموع بازیهای آن تیم $n-1$ است یعنی $w + d \leq n-1$ است و $w$ و $d$ هر کدام یک عدد صحیح نامنفی هستند. به ازای $n = ۸$ تعداد کل حالات برای یک تیم (منظور از حالات، تعداد بردها،تساویها و باختهاست) که در $2$ معادله بالا صدق کند حداکثر $3$ حالت است. پس ابتدا برای هر تیم این حالات را بهدست آورده و بر حسب این تعداد، از تیمی که کمترین حالت را دارد.
backtrack خود را شروع میکنیم. به ازای تیم $i$ که هماکنون در backtrack بررسی میکنیم، کافیست از بین تیمهایی که هنوز وضعیتشان معلوم نشده (یعنی در backtrack به آن نرسیدیم) مقداری را برای بردن تیم $i$ از آنها، مقداری را برای تساوی با تیم $i$ (و باقی باخت تیم $i$ به آنها) انتخاب کنیم به طوری که تعداد بردها و تساویهای $i$ و در نتیجه امتیاز i درست شود. ایده مهم دیگر برای بهینهسازی این است که اگر در جایی از backtrack تیمی وجود داشت که امتیاز هم اکنونش از امتیاز نهایی آن تیم بیشتر بود یا تیمی وجود داشت که به هر ترتیبی بازیهای باقیمانده (که هنوز آنها را مشخص نکردیم) را انجام دهد باز هم نمیتواند امتیاز مطلوب را بهدست آورد، دیگر آن شاخه از backtrack را انجام نداده و برمیگردیم. در اصطلاح به این کار bound میگویند. نکتهای که باید به آن توجه کرد این است که هر چه قدر در هنگام bound کردن زمان بگذاریم در backtrack مسیر کمتری طی میکنیم ولی زمانی که در هنگام bound کردن هم مصرف میکنیم باعث میشود تا زمان کل برنامه زیاد شود. در واقع یک trade-off بین این دو است که با نوشتن برنامه و اجرا و تست آن به ازای ورودیهای مختلف به بهینهسازی خوبی دست پیدا کنید.