Earth Worms | MatCom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Warmup1

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

B - Earth Worms

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
Biologists are studying a certain, interesting kind of earth worm. Each worm can be seen as a line of cells of different types. When a worm is born, it only consists of a single cell.  Every day, exactly $1$ cell of the entire worm will grow and change into $2$ cells. It is rather easy to determine the age of any such worm, since it's simply one less than the number of cells the worm has.

During a worm's growth, a cell does not change into any $2$ arbitrary cells; each worm has a set of "growth rules" (encoded in its DNA) that it obeys. A growth rule can be expressed as $A \rightarrow BC$, where $A$, $B$ and $C$ are uppercase letters (with letters $A-T$), representing different types of the worm's cells. The rule $A \rightarrow BC$ means that in one day, any single cell $A$ can be grown into the $2$ adjacent cells $BC$, in that order. Note that the rule $I \rightarrow JK$ is different from the rule $I \rightarrow KJ$. Different worms may have a different set of growth rules.

The worms have now thrown the scientists for a loop. Due to some unknown reason, some worms have mutated into a new kind of specimen. This new kind of worm has the exact same properties, except that during its growth, multiple parts of its body can grow at the same time. That is, every day any (at least one, at most all) of its cells can grow; each cell that grows will grow into exactly $2$ cells (obeying growth rules similar to their older cousins).

As a result of the mutation, it is no longer trivial to determine the age of a worm. In fact, the exact age of some worms cannot be determined. As a simple example, if a worm has growth rules: $A \rightarrow BC$, $B \rightarrow AC$, $C \rightarrow AB$, and the worm's current cell structure is $ACAB$, the worm can be either $2$ or $3$ days old ($A \rightarrow BC \rightarrow ACAB$, or $A \rightarrow BC \rightarrow ACC \rightarrow ACAB$). Your task is to find out the youngest possible age of any given mutated worm.
</div>

Input

Output

Sample test(s)

Input

3 ABC BAC CAB ACAB 1 AAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 2 PAA AAA AAAAAAAAAAAAAAAP 1 BAB AAAAAAB 0

--- Showing first 30 lines (click "Copy" to get full content) ---

Output

2 6 -1 6

--- Showing first 30 lines (click "Copy" to get full content) ---

Matcom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Warmup1

Ended

B - Earth Worms

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

Input

Output

Sample test(s)