CPC '19 Contest 1 P3 - Admiral Kuznetsov - DMOJ: Modern Online Judge

CPC '19 Contest 1 P3 - Admiral Kuznetsov

Points: 12 (partial)

Time limit: 0.6s

Memory limit: 256M

Author:

crackersamdjam

Problem type

Aircraft carrier Admiral Kuznetsov

Aircraft carrier Admiral Kuznetsov's deck can hold up to $N$ $N$ 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:

Four aircraft in consecutive spots simultaneously take off in formation.
Three aircraft in consecutive spots simultaneously take off in formation.
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.

Constraints

Subtask 1 [20%]

$3 \le N \le 14$ $3 \leq N \leq 14$

Subtask 2 [80%]

$3 \le N \le 10^6$ $3 \leq N \leq 10^{6}$

Input Specification

The first line contains integer $N$ $N$ .

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

The next line contains a string of length $N$ $N$ , with $1$ $1$ representing an aircraft and $0$ $0$ 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

Copy

7
1100111
0000000

Sample Output

Copy

Explanation

One aircraft lands at position $3$ $3$ .

Aircraft $1-3$ $1 - 3$ take off.

Aircraft $5-7$ $5 - 7$ take off.

Comments

3

DEPRESSED_IDIOT commented on May 6, 2019, 11:11 p.m.

is there no case with -1 as output?

4

Plasmatic commented on May 7, 2019, 12:38 a.m.

To avoid spoiling the answer for anyone that wants to find out on their own, here it is as an editorial comment.