المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۷

تعدادی کارت داریم که روی هر یک، یک عدد نوشته‌ شده است. دستگاه کارت برگردان دستگاهی است که اگر دو کارت با عددهای $a$ و $b$ به آن بدهیم، آن‌ها را نابود کرده و یک کارت با عدد $2b$ + $2a$ تولید می‌کند. (یعنی دو کارت را به یک کارت تبدیل می‌کند.) ۷ تا کارت با شماره‌ی ۱ داریم. می‌خواهیم با چند بار استفاده از دستگاه کارت برگردان بیش‌ترین عدد ممکن را تولید کنیم.این عدد چند است؟

  1. ۲۵۶
  2. ۱۹۰
  3. ۹۴
  4. ۸۲
  5. ۵۲

پاسخ

گزینه (۲) درست است.

اگر اعداد $a \leq b \leq c \leq d$‎ مفروض باشند معلوم است بعد از سه مرحله به یک عدد خواهیم رسید که در بین همه ترکیب‌های قابل ساخت٬ ترکیب $8c+8d+4b+2a$ از همه بزر‌گ‌تر( در عدد حاصل ابتدا دو عدد $d$ و $c$ باهم ترکیب شده‌اند و سپس عدد حاصل با $b$ و در نهایت عدد جدید با $a$ ترکیب شده اند).

بنابراین الگوریتم مناست برای ساختن بزرگ‌ترین عدد ممکن به شکل زیر می‌باشد:

$$1,1,1,1,1,1,1 \longrightarrow 1,1,1,1,1,4 \longrightarrow 1,1,1,1,10 \longrightarrow 1,1,1,22 \longrightarrow 1,1,46 \longrightarrow 1,94 \longrightarrow 190$$


ابزار صفحه