المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی تابستان:متفرقه:سوال ۱۶

اعداد دور دایره

$n>3$ عدد صحیح دور دایره چیده شده‌اند و روی کمان بین هر دو عدد متوالی یکی از دو علامت + یا - نوشته شده است. بازیکن می‌تواند یکی از حرکات زیر را انتخاب کرده و روی دایره انجام دهد:

  • دو عدد متوالی را روی دایره انتخاب کند (این دو را $a$ و $b$ می‌نامیم که $b$ در جهت ساعت‌گرد بعد از $a$ قرار دارد، عدد قبل از $a$ را $c$ و عدد بعد از $b$ را $d$ می‌نامیم) و عمل نوشته شده بینشان را روی $a$ و $b$ (به‌ترتیب) انجام دهد ($a+b$ یا $a-b$) و عدد حاصل را به‌جای هر دو قرار دهد و اگر $c-d$ بیش‌تر از صفر بود روی کمان بین $a$ و $b$ علامت + وگرنه - بگذارد.
  • در هر مرحله یکی از اعداد صفر را (در صورت وجود) انتخاب کرده، از دایره حذف کند و روی کمان حاصل از اتصال دو کمان قبل علامت + قرار دهد.

ثابت کنید به ازای هر دایره‌ی داده شده به شکل بالا، دنباله‌ای از اعمال بالا وجود دارد که پس از آن تعداد اعداد روی دایره برابر ۳ خواهد بود.


ابزار صفحه