ECOO '17 R3 P2 - Family Trees - Olympiads Online Judge

ECOO '17 R3 P2 - Family Trees

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 13.0s

Memory limit: 256M

Author:

rtilikay

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}$ ~y^{th}~ child of $X$ ~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$ ~10~ test cases. Each test case starts with an integer $N$ ~N~ $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~. The next $N$ ~N~ lines each contain a family ID.

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

Output Specification

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

Sample Input

1
0.2.3
3
0
0.2.1
0.1.1

Sample Output

6
5

Note: Only $2$ ~2~ cases are shown in this sample.

Footnotes

* This means that if the size of the family is $999\,999\,999\,999$ ~999\,999\,999\,999~ you should output $999\,993\,006$ ~999\,993\,006~, the remainder after dividing $999\,999\,999\,999$ ~999\,999\,999\,999~ by $1\,000\,000\,007$ ~1\,000\,000\,007~.

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

Comments

19

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$ ~y~ will be less than 100000 and there will be less than 20 generations