COCI '16 Contest 3 #2 Pohlepko

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Little Greedy got a board for his birthday. The board has N rows and M columns, and has a lowercase letter of the English alphabet in each field. During his birthday party, everyone got bored so they decided to play a simple board game.

The game begins with placing a chip on the upper left field labeled with coordinates (1, 1). In each turn, we must move the chip one field to the right or down, given the constraint that it remains on the board. The game ends with moving the chip to the lower right field of the board labeled with coordinates (N, M). During the game, we take note of the array of characters we form by moving the chip and therefore constructing a word. The goal of the game is to find the lexicographically smallest word.

The player(s) that will succeed in constructing the lexicographically smallest word get a bag of candy as a prize. Greedy wants to win the candy at any price, so he is asking you to write a programme that will find the lexicographically smallest possible word.

Please note: The lexicographic order of words is the one in which the words appear in a dictionary. If we have two words, and the words differ in the first letter, then the smaller word is the one with the letter that comes first in the alphabet.

Input Specification

The first line of input contains integers N and M, separated by space (1 \le N, M \le 2\,000).

The following N lines contain M lowercase letters of the English alphabet that represent the board.

Output Specification

You must output the lexicographically smallest word.


In test cases worth 40 points total, it will hold that, for each field, the letters located to the right and below will be different.

Sample Input 1

4 5

Sample Output 1


Explanation for Sample Output 1

One way of constructing the smallest word is illustrated in the following image:

Sample Input 2

4 5

Sample Output 2


Sample Input 3

2 5

Sample Output 3



There are no comments at the moment.