问题 3903 --运动会 (sport.pas/c/cpp)

3903: 运动会 (sport.pas/c/cpp)

题目描述

  

    小F和大F开了一所幼儿园,春天到了,幼儿园要举办一场运动会!

    幼儿园里有N个小朋友,运动会里有M个项目可供选择,每个小朋友都对M个项目有一定的喜好程度。对于第i个小朋友,他第j喜欢的项目是aij。并且保证对于每个小朋友,他都不会有两个一样喜欢的项目。

    幼儿园的园长小F和副园长大F对运动会的事情头疼不已,她们希望玩的人数最多的项目玩的人数最少,否则她们在最受欢迎的项目举行时会忙不过来。她们希望从M个项目中选出若干个项目在运动会中举行(可以全选,但不能一个也不选),每个小朋友会且仅会玩一个项目,并且他玩的项目一定是举行的项目中他最喜欢的。

    很不幸,今天幼儿园停电了,电脑不能用,小F和大F决定将这个问题交给聪明的你,请你求出玩的人数最多的项目玩的人数的最小值。

输入

1行两个整数NM,表示小朋友的个数和备选运动项目的个数。

2N+1行,每行M 个整数。第i+1行的第j个整数表示aij,表示第i个小朋友第j喜欢的项目。保证ai1..aiM1..M的一个排列。

输出

一个整数,表示玩的人数最多的项目玩的人数的最小值。

样例输入输出

输入#1 复制
4 5
5 1 3 4 2
2 5 3 1 4
2 3 1 4 5
2 5 4 3 1
输出#1 复制
2
输入#2 复制
3 3
2 1 3
2 1 3
2 1 3
输出#2 复制
3

提示

【样例1解释】
一种最优方案是选择举行1,3,4 三个项目,这样的话,4个小朋友玩的项目分别是1,3,3,4,玩的人数最多的项目是3,有2个人玩,所以答案是2。

【样例2解释】
由于无论怎么选择举行的项目,3个小朋友玩的项目都是同一个,所以答案一定是3。

对于30%的数据,M<=16。

对于另外30%的数据,N<=3。

对于100%的数据,1 <= N,M <= 200。

序号 标题 作者 发表时间 费用 订购数 操作