9837번 - Weather 다국어

It is interesting if we can predict the weather for the future N days. Let A, B, . . . , Z stand for 26 different weather types. Denote the weather types of the future N days be W[1], . . . , W[N] where W[i] ∈ {A, B, . . . , Z}.

Assume that the meteorologists have a break-through result and they create a machine which can report a list of N − d + 1 weather patterns where each weather pattern is the weather types for d consecutive days. For example, assume N = 10 and d = 3. Suppose the sequence of N = 10 days of weather types is CRSCCCRSRR. (S, C, and R stand for sunny day, cloudy day, and rainy day, respectively.) Then, the machine will report N − d + 1 = 8 weather patterns in alphabetical order. For example, for the above weather sequence, the machine will output: CCC, CCR, CRS, CRS, RSC, RSR, SCC, and SRR. (Note that some weather patterns may occur more than once.)

In this task, for a fixed N and d, given the list of weather patterns generated by the machine, your aim is to compute a weather type for the first day and a weather type for the N-th day, such that both are consistent with the patterns reported by the machine. For the above example, you need to report C, R.

Your program must read from the standard input N − d + 2 lines. The first line contains two integers N and d separated by spaces, where 3 ≤ N ≤ 1000 and 3 ≤ d ≤ 20. Each of the next N − d + 1 lines contains weather patterns.

Your program must write two characters which represents the weather type of day 1 and day N to the standard output. There is no space in between the characters.

We can formulate the problem as a graph problem. We create a graph G such that every weather pattern P[1] P[2] . . . P[d] corresponds to an edge between two nodes P[1] . . . P[d − 1] and P[2] . . . P[d]. The problem of reconstructing the weather sequence is equivalent to finding a path covering all edges in G.