المپدیا

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

ابزار کاربر

ابزار سایت


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

هموارسازی

تعدادی کارت در $n$ دسته، در یک ردیف روی هم قرار گرفته‌اند. در هر حرکت می‌توانیم یک از دسته‌ها را انتخاب کنیم و به ازای یک عدد $m$ و با فرض این‌که دسته‌ی مورد نظر به تعداد کافی کارت دارد، $m$ کارت از این دسته به هر یک از دسته‌های همسایه‌اش بیافزاییم. هر دسته دو همسایه دارد، غیر از دسته‌های اول و آخر. می‌خواهیم با تعدادی حرکت، همه دسته‌ها را هم‌اندازه کنیم (فرض کنید این کار همیشه ممکن است).

برنامه‌ای بنویسید که سعی کند با کم‌ترین تعداد، این کار را انجام دهد.

ورودی

در سطر اول ورودی ابتدا در یک سطر تعداد دسته‌ها $(n)$ آمده است $(n\leq 200)$.

سپس در $n$ سطر بعد تعداد کارت‌های اولیه در هر دسته آمده است، که هر یک عددی کم‌تر از ۲۰۰۰ است.

خروجی

در فایل خروجی، در هر سطر یک حرکت را بنویسید، ابتدا شماره‌ي دسته، و بعد تعدادی کارتی که به هر یک از همسایه‌هایش منتقل شده است. فرض کنید کار هموارسازی با حداکثر $10^5$ انتقال ممکن است. هر چه تعداد سطرهای خروجی به مقدار بهینه نزدیک‌تر باشد، امتیاز بیش‌تری به آن تعلق می‌گیرد. اگر تعداد سطرها از $\frac{3}{2}$ مقدار بهینه بیش‌تر باشد (یا مساوی) هیچ نمره‌ای به آن تعلق نمی‌پذیرد.

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

ورودي نمونه خروجي نمونه
5
0 7 8 1 4
5 2
3 4
2 4
3 1
4 2

ابزار صفحه