المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۱۸

دومینو‌ها

دومینو یک مستطیل $2\times 1$ است که به دو مربع تقسیم شده است. هر یک از این مربع‌ها یا سفید هستند یا بین ۱ تا ۶ نقطه را شامل می‌شوند. یک ردیف از دومینوها مطابق شکل زیر مفروض است.

تعداد نقاط در خط بالا $6+1+1+1=9$ و تعداد نقاط در خط پایین $1+5+3+2=11$ است. اختلاف بین خط بالا و خط پایین ۲ می‌باشد. این اختلاف قدر مطلق تفاضل بین دو مجموع مذکور است. هر دومینو می‌تواند در جای خود ۱۸۰ درجه بچرخد. کم‌ترین تعداد چرخش‌ها لازم برای کمینه کردن اختلاف بین خط بالا و پایین چیست؟ برای شکل بالا کافی است آخرین دومینو را بچرخانیم تا اختلاف صفر شود. در این حالت جواب ۱ خواهد بود. برنامه‌ای بنویسید که کم‌ترین تعداد چرخش‌های لازم برای کمینه کردن اختلاف بین خط‌های بالا و پایین را بیابد.

ورودی

در سطر اول فایل ورودی عدد صحیح $n$ $(1\leq n \leq 100)$ آمده است. $n$ تعداد دومینو‌ها می‌باشد.

هر یک از $n$ سطر بعدی شامل دو عدد صحیح $a$ و $b$ می‌باشند که $0\leq a,b \leq 6$ و $a$ مربوط به عدد مربع بالای دومینو و $b$ مربوط به مربع پایین دومینو است.

خروجی

برنامه‌ی شما باید در فایل خروجی یک عدد صحیح بنویسد که تعداد کم‌ترین چرخش‌های لازم برای کمینه کردن اختلاف بین سطر بالا و پایین است.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4
6 1
1 5
1 3
1 2
1

ابزار صفحه