trang chủ / đề bài / icpcwf18_f

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á 1 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 n (2≤n≤2500), 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á 80 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

  • 2≤n≤2500.
  • Mỗi từ gồm từ 1 đến 80 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 15 có dòng sông dài 5 (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 15 (từ 8 tới 14) 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 21 là độ rộng nhỏ nhất cho dòng sông dài 6.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0