d2p1 — CCO Canadian_Computing_Olympiad
Task type: batch | Time limit: 1 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: case analysis, ad-hoc

# 2023 Canadian Computing Olympiad
## Day 2, Problem 1: Flip it and Stick it

#### Time Limit: 1 second

#### Problem Description

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, S and T, of 0s and 1s. Finn is allowed to make moves of the following form:

*   Select a substring of S and reverse it, gluing the pieces of the string back together in their original order to form the new string S.

For example, Finn may take the string S = 101100, take the substring 011 starting at index 2 (assuming 1-based string indexing), and create the string S = 111000 in one move.

Finn wins the game if S does not contain T 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 S (1 ≤ |S| ≤ 200 000).

The second line of input contains the string T (1 ≤ |T| ≤ 3).

In the table below, T₁ is the first bit in T, T₂ is the second bit in T, and T₃ is the third bit in T, when reading from left-to-right.

| Marks Awarded | Bounds on T      |
| :------------ | :----------------- |
| 1 mark        | |T| = 1            |
| 3 marks       | |T| = 2, T₁ ≠ T₂   |
| 4 marks       | |T| = 2            |
| 5 marks       | |T| = 3, T₁ ≠ T₃   |
| 5 marks       | |T| = 3, T₁ ≠ T₂   |
| 7 marks       | |T| = 3            |

#### 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 Sample Output 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 4 to index 6 (110) to get 100011. Then, his second move can be to reverse the substring from index 1 to index 4 (1000) to get 000111, which does not have 10 as a substring.

#### Sample Input 2

```
000
00
```

#### Sample Output 2

```
-1
```

#### Explanation of Sample Output 2

No matter how many moves Finn makes, the string S will always contain T as a substring.

Starter code: