409670: GYM103677 G2 Family Farm II

Note that there are two versions of this problem. Read the input section for more details.

Rays Rais (short for Ray's Raisins) has been a big name in family owned raisin business around the area for a long time. So long, in fact, that apparently their name has been changed a few times since its creation!

As you read through ancient business records, you learn that Rays Rais was actually created by a man named Ray, who originally named the company after himself: Rays. But it wasn't very clear what a business named Rays sold, so he decided to double the name to get "Rays Rays", where the second Rays was supposed to be short for Raisins.

As time passed, it wasn't very clear that the second "Rays" was supposed to stand for Raisins, so it was eventually changed to "Rais", which caused a bit of confusion for a couple years as people adjusted to the new name.

Turns out, lots of family businesses did a similar thing to slowly rename their business. Namely, they would apply one of two operations to their business name:

• Operation 1: Repeat the name by concatenating a copy of it to the end.
• Operation 2: Change a single letter in the name.

As you study these names, you quickly realize that businesses tended to avoid changing their name, as it would get confusing for their customers!

Currently, you are trying to piece together the name of your favorite raisin business over time, but some of the details are missing; in fact, you only know of some of the names they've used, and when they were in use. Given this list of names, can you determine the minimum number of operations the business could've performed that would be consistent with the names you observe?

The first line of input contains a single integer, $$$1 \leq n \leq 20$$$, the number of names you've recorded.

Then, $$$n$$$ lines follow, with the $$$i+1$$$th line containing a name $$$s_i$$$, consisting of only lowercase Latin letters. It is guaranteed that for all $$$2 \leq i \leq n$$$, there exists an integer $$$k \geq 0$$$ for which $$$|s_{i+1}| = 2^k|s_i|$$$. In this version of the problem, there is no constraint on $$$k$$$.

Furthermore, it is guaranteed that $$$|s_i| <= 10^5$$$ for all $$$i$$$.

Output a single integer, the minimum number of operations the business could've performed so that its name over time would appear as $$$s_1$$$, then $$$s_2$$$, and so forth.

2
rays
raysrais

2

4
a
bb
cccc
dddddddd

10