Idyllic Instagram
Time limit1sMemory limit512 MB
Delete the fewest photos from a reading-order sequence so that no row of three contains photos from different trips, then print the remaining sequence in rows of three.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Array, Implementation
- Solved
- No attempts yet
Problem
Alenka decided to become the next Instagram sensation. She immediately opened a new profile (@TheRealAlenka), and now she only needs 190 million more followers to overtake some Portuguese footballer. She decided to follow the so-called travelgram trend, meaning she will post only travel photos on her profile. She went in order, first Cape Town in 1997, then Setubal in 1998, all the way to this year's summer vacation in the capital of Azerbaijan. Unfortunately, she gathered a measly 100 million followers, so she turned to Mr. Malnar for help.
On Instagram, photos are arranged in several rows, and each row consists of at most three photos. The photos are ordered by the moment of posting, with the newest post in the top-left corner and each subsequent one following the so-called reading order: first left to right, then top to bottom. Mr. Malnar immediately noticed that the photos are overlapped incorrectly, that is, there are rows containing photos from different trips.
Photos from trips A and B are correctly overlapped in the left figure, but not in the right one.
Help Alenka delete the smallest possible number of photos from her Instagram profile so that the remaining photos are correctly overlapped. When a photo is deleted, the next photo by posting time takes its place, and so on until the oldest post shifts by one position.
Determine the final appearance of Alenka's Instagram profile.
Input
The first line contains a natural number n (1 ≤ n ≤ 105), the number of Alenka's posts.
The remaining lines contain a total of n uppercase English letters, at most three per line. These lines represent the current appearance of Alenka's Instagram profile, where each letter represents one photo, and the same letters mean that the corresponding photos were taken on the same trip.
You may assume that the input data matches the problem statement, that is, only the last line may contain fewer than three photos, and the order of posts will match the chronological order of Alenka's trips.
Output
In the first line, print the number of Alenka's posts in the final version of her profile.
In the remaining lines, print the photos that make up Alenka's profile in the identical format as in the input data. If there are multiple correct solutions, print any of them.
Hint
Explanation of the second sample:
