HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN254 Practice Exam 2 > problem:


1. 51131 - Running After a Thief

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

Guest
• Review clarifications (1)

Contest problems

• 1. 51131 - Running After a Thief
• 2. 51132 - Problem Solving Competit...

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.



Для отправки решений необходимо выполнить вход.

www.contester.ru