المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۴:سوال ۹

گردن بندهای طلا

خانمی قرار است $n$ روز در هتل اقامت کند. این خانم $k$‌ گردن‌بند دارد. هر گردن‌بند از گلوله‌های طلایی مشابه ساخته شده است. تعداد کل گلوله‌ها برابر با $n$ است می‌توان در فاصله‌ی بین گلوله‌ها، یک گردن‌بند را به دو تکه تقسیم کرد و دو گردن‌بند جدید کوتاه‌تر (به اندازه‌ی حداقل یک گلوله) ساخت.

این خانم پولی ندارد و با مدیر هتل قرار می‌گذارد که به ازای هر روز اقامت، یکی از گلوله‌های طلایی گردن‌بند‌هایش را بابت کرایه به او بدهد. او می‌خواهد پرداخت را طوری انجام دهد تا در انتهای هر روز تعدادی گردن‌بند به مدیر هتل داده باشد و مجموع گلوله‌های طلایی آن‌ها به تعداد روز‌های سپری شده او در هتل باشد. مدیر هتل به شرطی این کار را می‌پذیرد که در پایان، تعداد گردن‌بند‌های دریافتی او حداقل باشد.

برای این کار خانم احتیاج به کمک دارد. او می‌خواهد از ابتدا نقاط برش گردن‌بندها را طوری تعیین کند که این تعداد کمینه باشد و نیز آن‌که او بتواند از گردن‌بندهای به وجود آمده، هرروز تعدادی را به مدیر هتل بدهد و تعدادی را پس بگیرد، به طوری که شرایط فوق رعایت شود. فرض کنید که تعداد گلوله‌های طلای گردن‌بندها به ترتیب $a_2،a_1$، … و $a_k$ است و گلوله‌ا از گردن‌بند اول تا آخر به ترتیب از ۱ تا $n$‌شماره‌گذاری شده‌اند.

برنامه‌ای بنویسید که با دریافت اطلاعات فوق، نقاط برش در گردن‌بندها را طوری پیدا کند که پرداخت هزینه‌ی هتل با رعایت کلیه‌ی شرایط فوق ممکن شود.

ورودي

در سطر اول فایل ورودی عدد $k$ و در $k$ سطر بعد $a_i$ ها به ترتیب نوشته شده‌اند. فرض کنید در کلیه‌ی ورودی‌ها $k\leq 6$ و به ازای هر $1\leq i\leq k$ داریم $a_i \leq 13$.

خروجي

خروجی را در فایل خروجی به این صورت بنویسید: اگر تعداد مینیمم برش‌ها $p$ باشد، در سطر اول عدد $p$، پس از آن با یک سطر فاصله، در $k+p$ سطر شماره‌ی گلوله‌های قطعه گردن‌بندهای حاصل از برش‌ها و سپس با یک سطر فاصله، در $i$‌امین سطر از $n$ سطر بعدی، شماره‌ی گلوله‌هایی را که خانم باید بابت پرداخت کرایه تا روز $i$ ام بدهد بنویسید.

به مثال زیر توجه کنید. ورودی و خروجی این مثال در شکل زیر نشان داده شده است.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
2
3
5
‎2

1
4 5 6 7
2 3
8

1
2 3
1 2 3
4 5 6 7
4 5 6 7 8
1 4 5 6 7 8
2 3 4 5 6 7 8
1 2 3 4 5 6 7 8‎

ابزار صفحه