$k$ کلمه‌ی $w_1$، $w_2$، … و $w_k$ داده شده‌اند. طول کلمه‌ی $w_i$، $l_i$ است. می‌خواهیم این $k$ کلمه را به عنوان یک پاراگراف به بهترین صورت ممکن حروف‌چینی کنیم به طوری که طول کلیه‌ی سطرهای این پارگراف (به غیر از احتمالا سطر آخر) باشد. بین کلمات حروف‌چینی شده در یک سطر، فاصله‌ی خالی وجود خواهد داشت. اندازه‌ی واقعی هر فاصله‌ی خالی $b$ واحد است و این بهتین فاصله‌ی خالی است، اما در صورت لزوم اندازه‌ی فواصل خالی بین کلمات را می‌توانیم بزرگ‌تر و یا کوچک‌تر کنیم.

برای حروف‌چینی کلمات $w_i$، $w_{i+1}$، … و $w_j$ در یک سطر به طول $l$ (البته به شرط این که مجموع طول‌شان از $l$ کم‌تر باشد) کلیه‌ی فواصل خالی را مساوی و برابر با اندازه‌ی

$$b'=\frac{l- \sum_{k=i}^j l_k}{j-i}$$

انتخاب می‌کنیم. اگر $ b'=b$، این بهترین نحوه‌ی حروف‌چینی برای این سطر است، ولی اگر $ b'\ne b$، یک «جریمه» برای این سطر منظور می‌کنیم. جریمه‌ی حروف‌چینی سطری به طول $l$ با کلمات $w_i$، $w_{i+1}$، … و $w_j$ را $C_{ij}$ می‌نامیم که برابر است با $C_{ij}=(j-i)|b'-b|$.

بنابراین هدف، حروف‌چینی کلمات $w_1$، $w_2$، … و $w_k$ در یک پاراگراف (یعنی تعیین تعداد سطرها در این پارگراف ونیز تعیین اندازه‌ی فاصله‌ی خالی در هر سطر) است، به طوری که مجموع جریمه‌های حروف‌چینی سطرهای مختلف مینیمم شود.

ورودی برنامه‌ی شما اندازه‌های $l$ و $b$ و نیز $l_1$، $l_2$، … و $l_k$ است. عددهای $k$، $l$ و $b$ در سطر اول فایل ورودی عددهای $l_1$، $l_2$، … و $l_k$ در $k$ سطر بعد آمده‌اند. این اندازه‌ها همگی صحیح هستند و واحد آن‌ها بر حسب Pixel است. واضح است که $l_i < l$. برنامه‌ی شما باید این $k$ کلمه را به بهترین صورت ممکن (با کم‌ترین مجموع جریمه) در یک پاراگراف حروف‌چینی کند و آن را به صورت گرافیکی د رصفحه‌ی نمایش نشان دهد. (کلمه‌ی $w_i$ را به صورت خطی به اندازه‌ی $l_i$ عدد Pixel در نظر بگیرید.) خروجی برنامه شما باید شبیه شکل زیر باشد. عددهایی که در این شکل در سمت راست هر سطر نوشته شده است اندازه‌ی فاصله‌ی خالی در آن سطر است. همچنین همان‌طور که د رشکل نشان داده شده است، باید مجموع کل جریمه‌ی پاراگراف را نیز روی صفحه بنویسید.

• سوال بعد