Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

دومینو‌ها

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

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

ورودی

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

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

خروجی

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

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

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

ابزار صفحه