CEN254 Practice Exam 2 |
Start: May.30.2017 at 12:50:00 PM
Finish: May.30.2017 at 01:36:00 PM
The contest is finished!
• Contest scoreboard
|
Feedback | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. Question by Ibrahim Mesecan.
Running After a Thief
Police is running after a thief. They think that the thief is
trying to hide himself and very few people know him.
Possible candidates are known in the region by less
than a number given (k).
Question: Write a program that will read
list of people and a list of friendship relations. Then, the
program lists possible candidates which are known by less than k
people.
Input specification:
In the beginning, you will be given two integers:
number of people (n), and maximum number of friends (k).
Next n lines give the list of people. Following line
has an integer (m) number of connections. Each of next m lines
contains two names who know each other.
Names are at most 20 chars containing only 26 uppercase
or lowercase English letters; 1 ≤ k ≤ n ≤
5,000 and 1 ≤ m ≤ 30,000. Note that a
person cannot be the friend of himself. As in the example
Jonara knows herself too, but this is not count as another
person.
Output specification:
First show the number of possible candidates.
Then, show the list of people in each line. The order of names is
not important. You can print names in any order.
Sample Input |
Sample Output |
6 3
Nail
Klajd
Imelda
Jonara
Lori
Luela
10
Imelda Lori
Lori Nail
Jonara Imelda
Nail Luela
Klajd Nail
Jonara Lori
Klajd Imelda
Lori Jonara
Jonara Jonara
Luela Lori
|
3
Jonara
Klajd
Luela
|
|
|
People and their friendship list |
Nail ==> Lori Luela Klajd
Klajd ==> Imelda Nail
Imelda ==> Lori Klajd Jonara
Jonara ==> Lori Imelda
Lori ==> Luela Jonara Nail Imelda
Luela ==> Lori Nail
|
Explanation: Maximum number given is 3.
Lori has 4 friends; Nail and Imelda have 3 friends;
Jonara, Klajd and Luela have two friends. Thus, according
to the given criteria, Jonara,
Klajd and Luela are possible candidates.
|
Для отправки решений необходимо выполнить вход.
|