المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۲۸

سؤال ۲۸

ترکیب دو دنباله‌ی مرتب $A$ و $B$ به ترتیب با اندازه‌های $n$ و $m$ یک دنباله‌ی مرتب به‌ اندازه‌ی $n+m$ تولید می‌کند و این کار به‌ اندازه‌ی $m+n$ هزینه دارد. (مثلاً اگر $A=(1,2,3,5)$ و $B=(4,6)$ باشد $C=(1,2,3,4,5,6)$ ترکیب این دو دنباله و هزینه‌ی تولید آن ۶ است). برای ترکیب سه دنباله، ابتدا دو تای آن‌ها را باهم ترکیب و دنباله‌ی حاصل را با دنباله‌ی سوم ترکیب می‌کنیم. بدیهی است که انتخاب دو دنباله‌ی اول در کل هزینه‌ی ترکیب مؤثر است. حال فرض کنید ۷ دنباله به‌اندازه‌های ۴، ۵، ۶، ۷، ۸، ۸، و ۱۰ داریم. کم‌ترین هزینه‌ی کل برای ترکیب این ۷ دنباله چه قدر است؟

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

پاسخ

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

ابتدا توجه می‌کنیم که برای ترکیب سه دنباله با طول‌های $a$،$b$ و $c$ ابتدا دو تا از آن‌ها مانند $a$،$b$ را ترکیب کرده(که حاصل دنباله به طول $a+b$ و با هزینه $a+b$ می‌شود) و سپس دنباله‌های حاصل را با دنباله سوم ترکیب می‌کنیم که حاصل دنباله‌ای به طول $a+b+c$ شده ولی هزینه آن $(a+b)+c$ می‌شود که در کل مجموع هزینه‌ها برابر $2(a+b)+c$ می‌شود. برای آن که کل هزینه‌ها مینیمم شود کافی است هر یکاز دو عدد $a$ و $b$ از عدد $c$ کم‌تر یا مساوی باشند. بنابراین در هر دسته‌ای که حداقل ۳ دنباله داشته باشد ابتدا دنباله‌های با طول مینیمم را با هم ترکیب می‌کنیم٬ که به جدول زیر خواهیم رسید:


ابزار صفحه