## ECOO '17 R3 P2 - Family Trees

View as PDF

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 child of .

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 test cases. Each test case starts with an integer . The next lines each contain a family ID.

For of cases, , and the total input size will not exceed characters.

#### Output Specifications

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

#### Sample Input

1
0.2.3
3
0
0.2.1
0.1.1

#### Sample Output

6
5

Note: Only cases are shown in this sample.

#### Footnotes

This means that if the size of the family is you should output , the remainder after dividing by .

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

• commented on July 30, 2020, 6: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

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

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

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

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