ZOJ Problem Set - 2591
Johnie likes watching videos very much. Recently his old uncle Arnie has died and handed him down his collection of DVDs.
Johnie loved his uncle, so he must comply with his last will. Uncle Arnie was a possionate cinema adorer, so he wanted Johnie to get the full taste of XX-th century cinematograph. So he declared in his last will that Johnie must view the films he left him in chronological order. That is, if the film A was produced in year YA and the film B in year YB where YA < YB, Johnie must watch the film A before the film B.
Films produced during one year may be watched in any order.
Johnie has already prepared to start watching the movie collection when a small problem has appeared: modern DVDs are protected with so called regional protection. That is, the world is divided into five parts, and each DVD can only be viewed in the region it is produced for.
Since DVD players are exported to different parts of the world, after the user buys the player, he is allowed to select the region he lives in. To correct occasional mistakes, the regional setting can be changed. However, to prevent changing region before watching each movie, the number of changes is limited to five.
Uncle Arnie loved movies so much, that he had five DVD players in his house, so he could view DVDs from all regions. However, Johnie is not so crazy about video yet, so he has only one DVD player. The collection of uncle Arnie contains many discs from various regions.
Help Johnie to select the set of films to watch and the order in which to do that. Initially his DVD player has no regional setting, so before watching the first film he must set its region. After that he can change the region for at most five times. Johnie wants to watch as many films as possible.
The input contains multiple test cases. The first line of the input is a single integer T (1 <= T <= 30) which is the number of test cases. T test cases follow, each preceded by a single blank line.
The first line of each test case contains n - the number of films in the collection (1 <= n <= 2000). Next n lines describe films: the name of the film in double quotes is followed by its production year and the region of the DVD. Note that uncle Arnie never had several copies of one film in his collection and no two films have the same name. Year ranges from 1870 to 2004. No film name is longer than 100 characters.
On the first line of each test case print m - the maximal number of films Johnie can watch. Next m lines must contain the names of the films in order Johnie must watch them.
Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
2 10 "Gone with the Wind" 1960 1 "The World and the War" 1991 5 "Back to the Future" 1980 1 "The Wall" 1980 2 "Titanic" 1997 3 "Hell on Earth" 1980 3 "Princess" 1980 4 "Yesterday" 1980 5 "Shadows of the Triumph" 1984 3 "Help" 1965 2 1 "Cool Film" 1900 1
9 "Gone with the Wind" "Help" "The Wall" "Back to the Future" "Princess" "Yesterday" "Hell on Earth" "Shadows of the Triumph" "Titanic" 1 "Cool Film"
Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #5