## CPC '19 Contest 1 P3 - Admiral Kuznetsov

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 256M

Author:
Problem type

Aircraft carrier Admiral Kuznetsov's deck can hold up to aircraft in line. Today's challenge will be to reach a certain aircraft configuration in the shortest time possible.

All aircraft are on deck with their crews. In one unit of time, one of three things can happen:

1. Four aircraft in consecutive spots simultaneously take off in formation.

2. Three aircraft in consecutive spots simultaneously take off in formation.

3. One aircraft lands at an empty spot on deck.

There are an infinite number of land-based aircraft in the air, so the third operation can always be called.

#### Input Specification

The first line contains integer .

The next line contains a string of length , with representing an aircraft present and representing an empty spot on the deck.

The next line contains a string of length , with representing an aircraft and representing an empty spot in the final configuration.

#### Output Specification

Output the minimum units of time required to reach the final configuration.

If the final configuration can not be reached, print -1.

#### Sample Input

7
1100111
0000000

#### Sample Output

3

#### Explanation

One aircraft lands at position .

Aircraft take off.

Aircraft take off.