Warp Speed
Input: Standard Input
Output: Standard Output
In the not-so-distance future, space
engineers can invent a new technology for traveling through space and name it as
“warp-drive”. This warp-drive can make a spaceship travel faster than light
speed. It works by bending an amount of distance in space and make a ship
travel through that bended space in a single “hop”. And since the time spent
for each hop is equal, the total traveling time for any spaceship (that is
equipped with this warp-drive) depends on the number of hops it make. Moreover,
these engineers notice that distance of a hop depends on some kind of force
fields in the space where that hop is operated. To travel from a beginning to
an ending point, a spaceship may have to pass through many force fields, which
may make that spaceship hop so many times.
And from their experiments, they found some facts as follow.
Rules of Single-hop-able Sequences |
ab abcd abd bde |
Goal
Suppose that you are an engineer on
a battle spaceship. Your duty is to drive your spaceship through space as fast as possible. Your
spaceship has a probe device that can identify a sequence of force fields along
the path to your destination. In order to accomplish your duty, you have to
build a computer program to find the minimum hop based on rules and any given
sequences of force fields.
Input
Input is standard inputs which contain 2 parts of
data which are separated by a blank line.
The first part is a set of rules of single-hop-able sequences. The
number of rules is between 1 and 10,000.
The second part is a set of force fields along path that a spaceship has
to pass through. The number of sequence is between 1 and 200.
The blank line after the second part is the termination of the input.
Output
For each sequence in the second part
of input, write 2 parts of output as follows
Sample Input |
Output for Sample Input |
ab abcd abd bde CgeF abc abcd abde abdeabde abdeCgeFabde |
1 2 ab c 1 1 abcd 2 2 a bde abd e 4 4 a bde a bde a bde abd e abd e a bde abd e abd e 4 5 a bde CgeF a bde a bde CgeF abd e abd e CgeF a bde abd e CgeF abd e |
Problemsetter: Chalatip
Thumkanon
More Explanations
There are 5 rules and 5 input sequences in this sample input.
In the first sample output, there is 1 solution with 2 hops. The first hop is from the first rule.
In the second output, there is 1 solution with 1 hop using the second rule for the whole sequence.
In the third output, there are 2 solutions with 2 hops. Its first solution is from the 4th rule and the second solution is from the 3rd rule.
In the fourth output, there are 4 solutions with 4 hops. The first solution is applied using the 4th rule twice. The second and third is applied using the 3rd and 4th rules in different position. The last solution is applied using the 3rd rules twice
The last output is quite similar to the fourth one, but it is also applied with the fifth rule in the middle of the sequence.