USACO 2020 - Tháng 1 - Hạng Đồng

Bessie đang viết một bài luận cho lớp học viết. Vì chữ viết tay của cô khá xấu, cô quyết định đánh máy bài luận bằng một trình xử lý văn bản.

Bài luận gồm \(N\) từ (\(1\le N\le 100\)), được phân tách bởi các dấu cách. Mỗi từ dài từ \(1\) đến \(15\) ký tự và chỉ gồm các chữ cái viết hoa hoặc viết thường. Theo yêu cầu của bài tập, bài luận phải được định dạng theo một cách rất cụ thể: mỗi dòng không được chứa quá \(K\) ký tự (\(1\le K\le 80\)), không tính các dấu cách. May thay, trình xử lý văn bản của Bessie có thể đáp ứng yêu cầu này bằng chiến lược sau:

• Nếu Bessie gõ một từ và từ đó có thể nằm vừa trên dòng hiện tại, hãy đặt nó trên dòng này.
• Nếu không, hãy đặt từ đó trên dòng tiếp theo rồi tiếp tục thêm các từ vào dòng ấy.

Tất nhiên, các từ liên tiếp trên cùng một dòng vẫn phải được phân tách bởi đúng một dấu cách. Cuối mỗi dòng không được có dấu cách.

Không may, trình xử lý văn bản của Bessie vừa bị hỏng. Hãy giúp cô định dạng bài luận đúng cách!

Dữ liệu vào

Dữ liệu vào được đọc từ tệp word.in.

Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi một dấu cách.

Dòng tiếp theo chứa \(N\) từ, mỗi cặp từ liên tiếp được phân tách bởi đúng một dấu cách. Không từ nào dài hơn \(K\) ký tự, là số ký tự tối đa trên một dòng.

Dữ liệu ra

Ghi ra tệp word.out bài luận của Bessie đã được định dạng đúng cách.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

10 7
hello my name is Bessie and this is my essay

hello my
name is
Bessie
and this
is my
essay

Nguồn

• Kỳ thi: USACO 2020 January Contest, Bronze
• Tên bài: Word Processor
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=987
• Tác giả đề: Nathan Pinsker

Farmer John đang xếp \(N\) con bò của mình (\(2\le N\le 10^3\)), được đánh số \(1\ldots N\), thành một hàng để chụp ảnh. Ban đầu, FJ dự định con bò thứ \(i\) tính từ bên trái sẽ là con bò mang số \(a_i\), và đã viết hoán vị \(a_1,a_2,\ldots,a_N\) lên một tờ giấy. Không may, tờ giấy đó vừa bị Farmer Nhoj đánh cắp!

May mắn thay, FJ vẫn có thể khôi phục được hoán vị mà ông đã viết ban đầu. Trước khi tờ giấy bị đánh cắp, Bessie đã ghi lại dãy \(b_1,b_2,\ldots,b_{N-1}\) thỏa mãn \(b_i=a_i+a_{i+1}\) với mỗi \(1\le i<N\).

Dựa trên thông tin của Bessie, hãy giúp FJ khôi phục hoán vị \(a\) "nhỏ nhất theo thứ tự từ điển" có thể tạo ra \(b\). Một hoán vị \(x\) nhỏ hơn một hoán vị \(y\) theo thứ tự từ điển nếu tồn tại một chỉ số \(j\) sao cho \(x_i=y_i\) với mọi \(i<j\) và \(x_j<y_j\) (nói cách khác, hai hoán vị giống hệt nhau cho đến một vị trí nào đó, và tại vị trí ấy \(x\) nhỏ hơn \(y\)). Đề bài đảm bảo tồn tại ít nhất một hoán vị \(a\) như vậy.

Phân nhóm

• Các test từ \(2\) đến \(4\) thỏa mãn \(N\le 8\).
• Các test từ \(5\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp photo.in.

Dòng đầu tiên chứa một số nguyên \(N\).

Dòng thứ hai chứa \(N-1\) số nguyên \(b_1,b_2,\ldots,b_{N-1}\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra tệp photo.out một dòng gồm \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), cách nhau bởi dấu cách.

Ví dụ

5
4 6 7 6

3 1 5 2 4

Nguồn

• Kỳ thi: USACO 2020 January Contest, Bronze
• Tên bài: Photoshoot
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=988
• Tác giả đề: Benjamin Qi và Chris Zhang

Bessie đang chạy một cuộc đua dài \(K\) mét (\(1\le K\le 10^9\)). Cô bắt đầu chạy với vận tốc \(0\) mét mỗi giây. Trong mỗi giây, cô có thể tăng vận tốc thêm \(1\) mét mỗi giây, giữ nguyên vận tốc hoặc giảm vận tốc đi \(1\) mét mỗi giây. Chẳng hạn, trong giây đầu tiên, cô có thể tăng vận tốc lên \(1\) mét mỗi giây và chạy được \(1\) mét, hoặc giữ vận tốc ở mức \(0\) mét mỗi giây và chạy được \(0\) mét. Vận tốc của Bessie không bao giờ được giảm xuống dưới \(0\).

Bessie luôn chạy về phía vạch đích và muốn hoàn thành cuộc đua sau một số nguyên giây (tại thời điểm nguyên này, cô kết thúc ở đúng vạch đích hoặc đã vượt qua vạch đích). Hơn nữa, cô không muốn chạy quá nhanh khi về đích: tại đúng thời điểm Bessie chạy đủ \(K\) mét, cô muốn vận tốc mà mình vừa di chuyển không vượt quá \(X\) mét mỗi giây (\(1\le X\le 10^5\)). Bessie muốn biết cô có thể hoàn thành cuộc đua nhanh đến mức nào ứng với \(N\) giá trị \(X\) khác nhau (\(1\le N\le 1000\)).

Phân nhóm

• Các test từ \(2\) đến \(4\) thỏa mãn \(N=X=1\).
• Các test từ \(5\) đến \(10\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp race.in.

Dòng đầu tiên chứa hai số nguyên \(K\) và \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(X\).

Dữ liệu ra

Ghi ra tệp race.out gồm \(N\) dòng, mỗi dòng chứa một số nguyên là thời gian nhỏ nhất Bessie cần để chạy \(K\) mét sao cho khi về đích, vận tốc của cô không vượt quá \(X\).

Ví dụ

10 5
1
2
3
4
5

6
5
5
4
4

Nguồn

• Kỳ thi: USACO 2020 January Contest, Bronze
• Tên bài: Race
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=989
• Tác giả đề: Nick Wu