Thuận dòng
Đề bài
Mô tả
Trong nghề sắp chữ, một "dòng sông" là một chuỗi các dấu cách, tạo thành từ khoảng trống giữa các từ, kéo dài xuống qua nhiều dòng văn bản liên tiếp. Khi nhìn một trang sách từ xa, các dòng sông hiện ra như những vệt trắng chảy dọc qua khối chữ.
Nhà nghiên cứu sông nổi tiếng Flo Ng muốn cuốn sách mới về các dòng sông trên thế giới của bà chứa những dòng sông chữ dài nhất có thể. Bà định sắp văn bản bằng một phông chữ đơn cách (mọi chữ cái và dấu cách có cùng độ rộng) trong một cột căn lề trái có độ rộng cố định nào đó, giữa hai từ trên cùng một dòng có đúng một dấu cách (văn bản không căn lề phải).
Với Flo, một "dòng sông" là một dãy các dấu cách nằm trên các dòng liên tiếp, trong đó vị trí (cột) của mỗi dấu cách trong dãy (trừ dấu cách đầu tiên) chênh lệch không quá so với vị trí của dấu cách ngay phía trên nó trong dãy. Khoảng trắng ở cuối dòng không được tính là một phần của dòng sông. Các từ phải được xếp chặt nhất có thể trên các dòng: lần lượt từng từ theo thứ tự, một từ được đặt lên dòng hiện tại nếu còn vừa (tính cả dấu cách ngăn cách), ngược lại từ đó bắt đầu một dòng mới; không được ngắt một từ ra hai dòng. Độ rộng dòng được dùng phải ít nhất bằng độ dài của từ dài nhất trong văn bản.
Ví dụ, bảng dưới đây là cùng một đoạn văn bản (ví dụ thứ nhất) được sắp với hai độ rộng dòng khác nhau; các dấu cách thuộc dòng sông dài nhất được thay bằng dấu *.
| Độ rộng 14: dòng sông dài 4 | Độ rộng 15: dòng sông dài 5 |
|---|---|
The Yangtze is |
The Yangtze is |
the third |
the third |
longest river |
longest*river |
in*Asia and |
in Asia*and the |
the*longest in |
longest*in the |
the*world to |
world to*flow |
flow*entirely |
entirely*in one |
in one country |
country |
Cho một văn bản, hãy tìm độ rộng dòng tạo ra dòng sông dài nhất cho văn bản đó.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số từ của văn bản. Các dòng tiếp theo chứa các từ của văn bản. Mỗi từ chỉ gồm các chữ cái thường và chữ cái hoa, các từ trên cùng một dòng cách nhau đúng một dấu cách. Không có từ nào dài quá ký tự.
Cách các từ được chia dòng trong dữ liệu vào không liên quan tới cách sắp chữ cần tìm.
Dữ liệu ra
In ra độ rộng dòng mà với nó văn bản có dòng sông dài nhất có thể, tiếp theo là độ dài của dòng sông dài nhất đó. Nếu có nhiều độ rộng dòng cùng đạt giá trị lớn nhất này, in ra độ rộng nhỏ nhất.
Ràng buộc
- .
- Mỗi từ gồm từ đến chữ cái
a-z,A-Z.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 21 The Yangtze is the third longest river in Asia and the longest in the world to flow entirely in one country |
15 5 | Với độ rộng có dòng sông dài (bảng trên). Không độ rộng nào cho dòng sông dài hơn, và mọi độ rộng nhỏ hơn (từ tới ) chỉ cho dòng sông ngắn hơn. |
| 25 When two or more rivers meet at a confluence other than the sea the resulting merged river takes the name of one of those rivers |
21 6 | Độ rộng là độ rộng nhỏ nhất cho dòng sông dài . |
Bình luận