CPC '19 Contest 1 P3 - Admiral Kuznetsov

View as PDF

Submit solution


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

Author:
Problem type
Aircraft carrier Admiral Kuznetsov

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

  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.

Constraints

Subtask 1 [20%]

3 \leq N \leq 14

Subtask 3 [80%]

3 \leq N \leq 10^6

(new cases for N = 5 in addition to contest data)

Input Specification

The first line contains integer N.

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

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

7
1100111
0000000

Sample Output 1

3

Explanation

One aircraft lands at position 3.

Aircraft 1-3 take off.

Aircraft 5-7 take off.


Comments


  • -1
    subscriber  commented on May 14, 2019, 3:39 p.m.

    What code is expect the problem?


  • -2
    subscriber  commented on May 14, 2019, 10:02 a.m.

    RoronoaZoro is get WA. What mean WA?


    • 2
      Zeyu  commented on May 14, 2019, 12:00 p.m.

      WA stands for "Wrong Answer", which indicates that the submitted code is outputting an answer different from what the problem is expecting.