Canadian Computing Olympiad: 2023 Day 2, Problem 1
Finn is playing a game of "Flip it and Stick it" which is abbreviated as FiSi. FiSi is a
one-player game played on two strings, and
, of
0
s and 1
s. Finn is allowed to make
moves of the following form:
- Select a substring of
and reverse it, gluing the pieces of the string back together in their original order to form the new string
.
For example, Finn may take the string
101100
, take the substring 011
starting at index
(assuming
-based string indexing), and create the string
111000
in one move.
Finn wins the game if does not contain
as a substring. Your task is to help Finn
determine the length of the shortest winning sequence of moves or tell him that the game
cannot be won.
Input Specification
The first line of input contains the string
.
The second line of input contains the string
.
In the table below, is the first bit in
,
is the second bit in
, and
is the third bit
in
, when reading from left-to-right.
Marks Awarded | Bounds on |
---|---|
Output Specification
Output the minimum number of moves needed or -1
if it is impossible to win the game.
Sample Input 1
100110
10
Sample Output 1
2
Explanation of Output for Sample Input 1
Finn starts with the string 100110
. He cannot avoid 10
as a substring in one move, but he
can in two moves.
For example, his first move could be to reverse the substring from index to index
(
110
)
to get 100011
. Then, his second move can be to reverse the substring from index to index
(
1000
) to get 000111
, which does not have 10
as a substring.
Sample Input 2
000
00
Sample Output 2
-1
Explanation of Output for Sample Input 2
No matter how many moves Finn makes, the string will always contain
as a substring.
Comments