F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5172. -- [Jsoi2014]学生选课

5172: [Jsoi2014]学生选课

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 132  Solved: 16
[Submit][Status][Discuss]

Description

进入大学以后,学生们将面临选课,有N个学生需要选课,学校里有三个老师JYY,YJY,YYJ。第一年里,每个学生
们都选择了其中一位老师。经过了一年的学习,学生之间相互都有一定的印象,每个同学会根据自己的印象给另外
N-1个学生从好到坏排序。第二年的选课开始了,每个学生需要选择老师,可能是因为被坑多了,每一位同学都想
换一个老师。这时需要你来调度同学们选课,使得上同一堂课的学生之间印象最坏的最好。

Input

文件第一行包含一个整数N。
第2到N+1行,每行有N个正整数。
其中第i+1行提供第i个同学的信息,其中第一个整数Ai,值为0,1,2中的一个,表示第一年第i个同学选的老师。
接下来N-1个数字,是1,2,…,i-1,i+1,…,N的一个排列,表示第i个同学对其他同学印象从好到坏的排序。

Output

输出文件包含一行一个整数,为最小的非负整数T,满足:
1、所有同学选择了和第一年不同的老师。
2、所有选择同一个老师的学生间彼此印象都是前T好的。
N≤1000

Sample Input

6
0 2 3 4 5 6
0 1 3 4 5 6
1 6 5 4 2 1
2 6 5 3 2 1
1 1 2 3 4 6
2 1 2 3 4 5

Sample Output

4
六名同学分别选择老师1,2,0,0,2,0。
此时老师0的课中同学六对同学四的印象为第4好,所以答案T为4。并且找不到更小的T。

HINT

Source

[Submit][Status][Discuss]

HOME Back