COCI 2016/2017 - Contest 3 - Pohlepko

View as PDF

Submit solution

Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 3
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cậu bé Greedy được tặng một tấm bảng nhân dịp sinh nhật của cậu. Tấm bảng có ~N~ hàng và ~M~ cột, mỗi ô giao giữa hàng và cột chứa một chữ cái in thường trong bảng chữ cái tiếng Anh. Vào bữa tiệc sinh nhật, mọi người cảm thấy buồn chán và đã quyết định chơi một trò chơi trên bảng.

Trò chơi bắt đầu bằng việc đặt một đồng xu ở ô trên cùng bên trái của bảng là ô ~(1,1)~. Ở mỗi lượt chơi, người chơi phải di chuyển đồng xu xuống một ô bên dưới hoặc sang một ô bên phải, điều kiện là đồng xu đó phải vẫn còn nằm trên bảng. Trò chơi kết thúc khi đưa được đồng xu tới ô dưới cùng bên phải là ô ~(N,M)~. Trong suốt quá trình chơi, người chơi ghi lại mảng những kí tự thu được khi di chuyển đồng xu, và tạo thành được một từ. Mục tiêu của trò chơi là tạo ra được từ có thứ tự từ điển nhỏ nhất.

Những người chơi thắng cuộc sẽ nhận được phần thưởng là một túi kẹo khổng lồ. Greedy muốn thắng được túi kẹo đó bằng mọi giá, vì vậy cậu ấy nhờ bạn viết một chương trình tìm ra từ có thứ tự từ điển nhỏ nhất có thể tạo được.

Ghi chú: Thứ tự từ điển của các từ là thứ tự mà các từ đó xuất hiện trong từ điển. Nếu chúng ta có hai từ, và chúng khác nhau ở chữ cái đầu tiên, thì từ nhỏ hơn sẽ là từ có chữ cái đầu tiên xuất hiện trước trong bảng chữ cái tiếng Anh.

Input

  • Dòng đàu tiên gồm hai số nguyên ~N~ và ~M~ ~(1 \leq N, M \leq 2000)~.
  • ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ chữ cái viết thường biểu diễn tấm bảng.

Output

In ra từ có thứ tự từ điển nhỏ nhất có thể tạo được

Sample 1

Input
4 5 
ponoc 
ohoho 
hlepo 
mirko
Output
pohlepko 
Giải thích

Một trong những cách tạo được từ có thứ tự từ điển nhỏ nhất:

Sample 2

Input
4 5 
bbbbb 
bbbbb 
bbabb 
bbbbb 
Output
bbbbabbb 

Sample 3

Input
2 5 
qwert 
yuiop 
Output
qweiop

Subtask

  • ~8~ test có dữ liệu đầu vào đảm bảo rằng: tại mỗi ô, ô bên phải và ô bên dưới nó có chữ cái khác nhau
  • ~8~ test còn lại không có ràng buộc gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.