Coin Flipping

View as PDF

Submit solution


Points: 5
Time limit: 1.5s
Memory limit: 125M

Author:
Problem types

You are playing a game with N coins lined up side by side in a straight line, each coin either head or tails. Each move consists of taking 2 adjacent coins and flipping both coins (switching each coin from heads to tails or vice versa). The objective of this game is to get all the coins to be tails in the least number of moves.

Input Specification

The first line will consist of an integer N (1<N<3000001). The next N lines will contain the result of a coin flip, either a 0 (representing tails) or a 1 (representing heads).

Output Specification

In the exact order of the coins entered, your program will output the minimum number of moves required to win the game (all coins to be tails). If it is impossible to get all coins to be tails, output -1.

Sample Input 1

5
0
1
0
1
0

Sample Output 1

2

Sample Input 2

6
1
1
0
0
1
0

Sample Output 2

-1

For Python Users

In order to receive an AC verdict on this problem, you should submit in PyPy.


Comments


  • 0
    abcdefghijk123  commented on Nov. 3, 2024, 2:57 a.m. edited

    For Python users: In order to receive an AC verdict on this problem, you should submit in PyPy.