The sixth friend P58570


pdf   zip

Consider a world where a pandemic has imposed a new rule: No party can have more than six assistants. Given the lists of friends of each person in a group, we will call someone the sixth friend if he is not in the top five of at least another person. Being egocentric is not an option to avoid being the sixth friend, and therefore not being able to attend any party!

Can you compute the number of sixth friends in a group of people?


Input consists of several cases. Each case begins with the number of people n, followed by n lines, one per person. Every line i contains the name pi of the i-th person, his number of friends fi, and the names of his fi friends in order, from more to less favorite.

You can assume 1 ≤ n ≤ 104, that all names are different and consist of between 1 and 10 letters, and 0 ≤ fi ≤ 30. The list of friends of each person pi only includes names in {p1, …, pn}, but can contain repeated names, including pi one or more times.

For instance, among the five best friends of Joey in the sample in fact there are only Chandler, Phoebe and Rachel. Janice is the only sixth friend of the first case.


For every case, print the number of sixth friends.

Public test cases
  • Input

    Chandler 6 Monica Joey Ross Rachel Phoebe Janice
    Monica 6 Chandler Monica Rachel Phoebe Joey Janice
    Janice 3 Janice Chandler Janice
    Ross 6 Rachel Rachel Rachel Rachel Rachel Janice
    Rachel 7 Rachel Ross Monica Joey Phoebe Chandler Janice
    Phoebe 5 Joey Monica Rachel Ross Chandler
    Joey 8 Chandler Joey Chandler Phoebe Rachel Monica Ross Janice
    A 3 D D D
    B 7 B B B B B A A
    C 0
    D 2 D C


  • Information
    Joan Alemany
    Official solutions
    User solutions