ECOO '17 R3 P2 - Family Trees

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 13.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 Specification

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 Specification

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 999\,999\,999\,999 you should output 999\,993\,006, the remainder after dividing 999\,999\,999\,999 by 1\,000\,000\,007.

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


Comments


  • 18
    ArtyKing12  commented on July 30, 2020, 10:47 p.m.

    For each test case, your program should output the minimum size of the family, modulo 1000000007

    Ah yes this family must have some awkward family unions with 1/8 of the world population attending


  • 5
    discoverMe  commented on May 14, 2019, 1:44 a.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