+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- امین یک متن حاوی $n$ کلمه دارد و می‌خواهد آن‌ها را مرتب کند برای این کار یک عدد صحیح $w$ انتخاب کرده و می‌خواهد آن را در سطر‌هایی که ظرفیت حداکثر $w$ کاراکتر دارند، بنویسد. برای نوشتن این کلمات **به ترتیب داده شده** آن‌ها را یادداشت می‌کنیم. از کلمه اول شروع کرده و آن را در ابتدای سطر اول می‌نویسیم. از آن به بعد برای هر کلمه اگر تونستیم آن را با حفظ یک فاصله (یک کاراکتر *space* یا `' '`) از کلمه قبل در همان سطر بنویسیم (با توجه به ظرفیت آن سطر) این کار را انجام می‌دهیم و در غیر این صورت کلمه در ابتدای سطر بعدی نوشته خواهد شد و این روند ادامه پیدا می‌کند. می‌خواهیم اشکالاتی که در کوچک یا بزرگ بودن حروف وجود دارد را برطرف کنیم. یعنی همه حروف نوشته شده باید کوچک باشند به جز حرف اولِ کلمه‌ی اول جملات. می‌دانیم که جملات با کلماتی ختم می‌شوند که در انتهای آن‌ها `.` ، `؟` یا `!` داشته باشند. حال می‌خواهیم همه این سطرها را جاستیفای کنیم! یعنی تعداد تقریباً مساوی فاصله بین کلمات هر سطر قرار دهیم تا کلمه‌ی آخر هر سطر به انتهای آن سطر برسد. اگر یک کلمه در یک سطر باشد آن را در ابتدای سطر می‌نویسیم و بقیه سطر را با کاراکتر *space* پرکنیم. در غیر این صورت فرض کنید $m$ کلمه در یک سطر داشته باشیم. می‌خواهیم در بین $m-1$ فاصله ایجاد شده توسط این$m$ کلمه تعدادی کاراکتر *space* قرار دهیم به طوری که اختلاف تعداد *space*های موجود در این فواصل حداکثر برابر یک باشد، همچنین کلمه آخر به انتهای سطر رسیده باشد. به عبارت دیگر برای هر سطر عددی مانند $k$ وجود دارد که فاصله بین کلمات آن سطر همگی $k$ یا $k + 1$ باشد. فرض کنید برای اینکار باید $r$ از فاصله‌ها $k + 1$ اسپیس، و $m-1-r$ تا $k$ تا اسپیس داشته باشند، می‌خواهیم $\lfloor \frac{r}{2}\rfloor$ تا از فواصل $k + 1$تایی بین کلمات ابتدایی سطر باشد و $\lceil \frac{r}{2} \rceil$ تا از فواصل $k + 1$تایی بین کلمات انتهایی سطر باشد. در نهایت تعداد کاراکترهای چاپ شده در هر سطر باید دقیقاً $w$ باشد. با احتساب فاصله‌ها (یا همان *space*ها) # ورودی در ورودی به شما $t$ مثال داده می‌شود. $$1 \le t \le 100 $$ در هر مثال در سطر اول عدد $n$ و عدد $w$ داده می‌شود و در سطر دوم $n$ کلمه با فاصله از هم داده می‌شود.$$1 \le n \le 100$$ $$2 \le w \le 2\ 000 $$ هر کلمه رشته حداکثر ۲۰ کاراکتری است که از حروف کوچک و بزرگ انگلیسی تشکیل شده است، به انتهای برخی از کلمات حداکثر یکی از کاراکترهای `.` یا `؟` یا `!` یا`,` چسبیده است. تضمین می‌شود آخرین کلمه با یکی از کاراکترهای `.` یا `؟` یا `!` ختم می‌شود. تضمین می‌شود مقدار $w$ از طول بزرگ‌ترین کلمه داده شده در هر مثال کمتر نخواهد بود. # خروجی خروجی خواسته شده در مسئله را مطابق مثال‌ها چاپ کنید. برای نشان دادن ابتدا و انتهای خطوط از کارکتر `|` مطابق با مثال‌ها استفاده کنید. # مثال ## ورودی نمونه ۱ ``` 2 2 6 caReEr dAyS! 6 10 Are You Ready For This Question? ``` ## خروجی نمونه ۱ ``` |Career| |days! | |Are you| |ready for| |this | |question? | ``` ## ورودی نمونه ۲ ``` 1 34 20 this is going to be a big sample to show how you should solve this problem. I hope this sample can show you what you want. please, try to solve this problem. love you! ``` ## خروجی نمونه ۲ ``` |This is going to be| |a big sample to show| |how you should solve| |this problem. I hope| |this sample can show| |you what you want.| |Please, try to solve| |this problem. Love| |you! | ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19679/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> در ابتدا حروف انگلیسی بزرگ در تمام کلمات را به حروف کوچک تبدیل کنیم. سپس حرف اول کلمه اول متن و حرف اول (در صورت وجود) بعد از هر کاراکتر `.`، `!` یا `؟` را به بزرگ تغییر می‌دهیم. در واقع آغاز یک جمله را از پایان جمله قبلی تشخیض می‌دهیم. </details> <details class="blue"> <summary>راهنمایی ۲</summary> بعد از درست کردن کوچک یا بزرگ بودن کلمات مطابق با الگوریتم گفته شده در سوال کلمات را در خطوط مختلف می‌ریزیم. حال برای **هر خط** مطابق با الگوریتم بیان شده در سوال تعدادی فاصله بین کلمات قرار می‌دهیم تا به رشته مطلوب دست پیدا کنیم. </details> <details class="blue"> <summary>راهنمایی ۳</summary> فرض کنید کلمات در یک تست داده شده $s_1, s_2, s_3, \dots, s_n$ باشد. ``` for i from 1 to n: change upper_case letter of s[i] to lower_case change first letter of s[0] to upper_case for i from 1 to n - 1: if s[i] ends with '.' or '!' or '?': change first letter of s[i + 1] to upper_case for i from 1 to n: if can add s[i] to this_line without exceed w: add s[i] to this_line else: add this_line to all_lines make this_lines clear for each line in all_lines: justify(line, w) ``` حال فرض کنید می‌خواهیم برای یک خط دستور `justify` را پیاده سازی کنیم. اکنون فرض کنید $l_1, l_2, l_3 \dots, l_m$ کلمات یک خط باشد. ``` if m = 1: print '|' + l[1] + ' ' * (w - (length of l[1])) + '|' else: spaces = w - (sum of length l[i] for all i from 1 to m) for i from 1 to m - 1: x[i] = floor(spaces / (m - 1)) remaining_space = space % (m - 1) for i from 1 to floor(m / 2): x[i] = x[i] + 1 for i from 1 to ceil(m / 2): x[m - i] = x[m - i] + 1 print '|' for i from 1 to m - 1: print l[i] print ' ' * x[i] print l[m] + '|' ``` </details>

حل سؤال در بانک سؤالات