فهرست مندرجات
سوالات ۱۲ و ۱۳
یک کلمه درون یک پرونده‌ی متنی داده شده است و می‌خواهیم با کم‌ترین تعداد اعمال کپی (Copy) و درج (Paste) تعداد مشخصی نسخه از آن ایجاد کنیم.
در هر مرحله می‌توانیم تعداد دل‌خواهی از کلمات نوشته‌شده درون پرونده را در حافظه کپی کنیم و یا کلمات درون حافظه را در پرونده درج کنیم. (مثل کپی و پیست در ویرایشگرها، می‌توان یک بار کپی کرد و سپس چند بار درج کرد.)
هر کپی 1 واحد و هر درج نیز ۱ واحد هزینه دارد.
سوال ۱۲
با حداقل چند واحد هزینه می‌توانیم دقیقا ۹۹ کلمه‌ی دیگر مشابه با کلمه‌ی اول ایجاد کنیم؟
- ۲۰
- ۱۰
- ۱۳
- ۲۲
- ۱۴
پاسخ
گزینه (۳) درست است.
اگر یک بار کپی و یک بار پیست کنیم در نهایت با ۱۴ حرکت می‌توان به عدد صد رسید. اما اگر در ابتدا یک بار کپی و دو بار پیست کنیم، سپس یک بار کپی و دو بار پیست کنیم، و سپس یک بار کپی و سه بار پیست کنیم به عدد ۳۶ می‌رسیم. حال اگر ۳۲ کلمه را کپی کنیم و دو بار پیست کنیم ۱۰۰ کلمه خواهیم داشت و تعداد حرکات ۱۳ تا شده است.
برای اثبات کمینه بودن پاسخ سوال بعدی را ببینید.
سوال ۱۳
با ۱۴ واحد هزینه حداکثر چند کلمه (با احتساب کلمه‌ی اولیه) می‌توان ایجاد کرد؟
- ۱۶۲
- ۱۰۰
- ۸۱
- ۲۴۳
- ۱۲۸
پاسخ
گزینه (۱) درست است.
کافی است $f(k)$ را بیش‌ترین تعداد کلمه با $k$ واحد هزینه تعریف کنیم. به سادگی می‌توان دید که: $$f(2)=2, f(3)=3, \ldots, f(n)= \max_k\{kf(n-k)\}$$ بنابراین به دست می‌آید: $$f(12)=81,f(13)=108,f(14)=162$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
