96 - ZOJ Monthly, September 2010 - B
The students in Zhejiang University major in three subjects: Computer Science, Mathematics, and Chinese. But some of them don't like their majoring subjects. They want to change their majors. According to the rules of the Zhejiang University, if a student wants change his major from major A to major B, his GPA must be the highest one of all the students' in major A and higher than every students' in major B(or there is no student in major B).
Recently, there is something wrong between College of Computer Science and Department of Mathematics, the students couldn't change their majors directly between Computer Science and Mathematics. If a student wants to change from Computer Science to Mathematics, he needs to change to Chinese first.
Everyone is willing to change his major temporarily, if it can help others study in their favorite majors. The office can only deal with one application in one day. How many days it needs to take at least to satisfy all students (move all students to their favorite majors)?
The first line containing an integer n (1 <= n <= 19) indicates the number of the students.
For the following n lines, each line has the format: "Original Major","Favorite Major",G. G is a float number representing the GPA of the student
(0 <= G <= 5). It has exactly two digits after the decimal point. Any two students' GPA are different.
One integer, the minimum days it needs to takes.
2 Computer Chinese 3.50 Chinese Chinese 4.40 1 Mathematics Computer 3.00
the first case:
Author: LIANG, Jiaxing
Contest: ZOJ Monthly, September 2010