#OJ1078. 社交网络的好友推荐
社交网络的好友推荐
社交网络的好友推荐
Time Limit: 1 Sec Memory Limit: 16 MB
Description
Jack同学在人人网上注册了一个用户,发现人人网需要回答一些问题,而后网站根据自己的回答向自己推荐了一些具有相似回答的网友。Jack同学恰好正在学习编程,想编写一个程序来模拟这个好友推荐功能。 为了实现这一目标,Jack同学是这样设想的:假定网络中的注册用户不超过N个,每位用户注册时需回答M个问题(每个问题都是选择题,且是单选),并指定一个阈值Q。设Tom和Mary是两个注册用户,而且Tom和Mary设定的阈值分别是Q1和Q2,那么: (1)当且仅当Tom与Mary对M个问题的回答有不少于Q1个是相同答案时,才可以向Tom推荐Mary。 (2)当且仅当Tom与Mary对M个问题的回答有不少于Q2个是相同答案时,才可以向Mary推荐Tom。 现在,我们已经知道了N个用户对M个问题的答案以及设定的阈值Q,请帮Jack设计一个程序来模拟好友推荐功能。
Input
输入是多行的。第一行包含两个整数,分别是N和M的值,代表用户个数及问题个数,且0<N<=100、0<M<=20。 从第二行开始,每行表示一个用户给出的M个问题的答案。其中第一个字符串是用户名(不超过20个字符,且仅含字母、数字和下划线);之后是一个空格和M个大写字母A~Z,第j个字母表示该用户的第j个答案,而且两个字母之间用一个空格隔开;最后是一个整数,表示该用户设定的阈值。 比如在Sample Input中,有5名用户,10个问题。用户是Jack、Tom、Jackson、Mammal_1、Bill_Gates。其中Tom给出的10个问题的答案是A B C D E A B A D E,且指定的阈值是9。
Output
输出也是多行,每一行代表为一个用户推荐的好友列表。其顺序与输入顺序相同:即按照输入的用户名顺序给出为每个用户推荐的好友。 每一行的格式是:第一个字符串是用户名,之后是好友列表,两者之间用冒号隔开。好友列表是向该行指定的用户推荐的好友用户名,按照输入顺序顺次输出好友的用户名。如果该行指定的用户没有可以推荐的好友,则输出“NONE!”。 输出的对齐要求是:每行指定的用户名(即向其推荐好友的用户名)的输出宽度是所有用户中最长的用户名占用的宽度,且左对齐。好友列表中的用户名的输出宽度是用户名的实际宽度,且两两之间用逗号(半角)隔开。
Sample Input
5 10
Bill_Gates A A A A A B B B B B 3
Tom A B C D E A B A D E 9
Jackson A A A A A B B B B B 4
Mammal_1 B B B B B B B B B B 6
Jack A B A D E A B C A E 5
Sample Output
Bill_Gates:Jackson,Mammal_1,Jack
Tom :NONE!
Jackson :Bill_Gates,Mammal_1
Mammal_1 :NONE!
Jack :Tom
HINT
每个用户指定的阈值是不同的,所以可以向Tom推荐Mary,不代表可以向Mary推荐Tom。