المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱۱:سوال ۷

وزنه‌ها

۱۳۸۰ وزنه با وزن‌های $x_1$، $x_2$، … و $x_{1380}$‌ داریم. می‌دانیم وزن هیچ دو وزنه‌ای برابر نیست، اما وزن هیچ کدام از وزنه‌ها را نمی‌دانیم. تنها اطلاعی که از وزنه‌ها داریم این است که اگر وزنه‌ها را بر حسب وزن آن‌ها از سبک به سنگین بچینیم و به دنباله‌ی وزنه‌های $x'_1$، $x'_2$، … و $x'_{1380}$‌ برسیم.

الف) به ازای $i$ های زوج، $x_i= x'_i$

ب) به ازای $i$ های فرد، اگر $x_i= x'_j$ آن‌گاه $x_j= x'_i$.

وزنه‌ی $y$ داده شده است. می‌خواهیم با کم‌تر از ۲۵ مقایسه مشخص کنیم آیا $y$‌ با هیچ کدام از وزنه‌های $x_1$، $x_2$، … و $x_{1380}$ هم‌وزن است یا خیر. روشی برای این کار ارائه کنید. توجه کنید که هر مقایسه عبارت است از قرار دادن دو وزنه در دو کفه‌ی یک ترازوی دو کفه‌ای.


ابزار صفحه