ECOO '17 R3 P2 - Family Trees

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 30.0s
Memory limit: 256M

Author:
Problem types

Family trees are trees that show relationships between family members. They begin with a root ancestor and show that ancestor's children, then every child's children, and so on. For example, Bob, the root ancestor, can have two daughters Alice and Eve. Alice can then have two children Jenna and Brian, and Eve can have one daughter Sarah. To help find people in the tree, we give each family member a family ID, formatted as a series of integers separated by dots (e.g. 0.1, 0.2.3, 0.5.1.7 and so on).

A family ID is either:

  • 0, which represents the root ancestor.
  • X.y, where X is a valid family ID, and where this ID represents the y^{th} child of X.

For the example above, the family IDs are:

Bob 0
Alice 0.1
Jenna 0.1.1
Brian 0.1.2
Eve 0.2
Sarah 0.2.1

Family IDs can give you an idea of how big a family is. For example, if you know that someone has the ID 0.2.3, then you know there are family members with IDs 0, 0.1, 0.2, 0.2.1, and 0.2.2. Given a list of family IDs, figure out the smallest possible size of the family.

Input Specifications

The input will contain 10 test cases. Each test case starts with an integer N\ (1 \le N \le 10^5). The next N lines each contain a family ID.

For 50\% of cases, N \le 100, and the total input size will not exceed 2000 characters.

Output Specifications

For each test case, your program should output the minimum size of the family, modulo 1\,000\,000\,007 or 10^{9} + 7.^{*}

Sample Input

1
0.2.3
3
0
0.2.1
0.1.1

Sample Output

6
5

Note: Only 2 cases are shown in this sample.

Footnotes

^{*} This means that if the size of the family is 999999999999 you should output 999993006, the remainder after dividing 999999999999 by 1000000007.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments


  • 2
    discoverMe  commented on May 13, 2019, 9:44 p.m. edited

    the problem doesn't say, but you should know that y will be less than 100000 and there will be less than 20 generations


  • 1
    marshmelllo  commented on May 14, 2017, 7:38 p.m.

    Can anyone give me any hints on why I get last test cases wrong?