P2039 [AHOI2009] Checkers

On a board with 1 row and $N$ columns (where $N$ is odd), there are $K$ red squares. In this situation, you have a checker on the leftmost square. Your goal is to move it to the rightmost square. Before the movement begins, you may place pieces on any empty squares on the board. After the game starts, you may place pieces only on red squares at any time. The movement rule is: each move you may choose exactly one piece and jump over an adjacent piece to the empty square immediately beyond; the jumped-over piece is captured and removed from the board. If the square immediately beyond the adjacent piece is occupied, the jump is not allowed. Answer the following two questions: 1. Before the movement starts, what is the minimum number of pieces you must place to complete the task? 2. If the number of pieces placed before the start is minimized, what is the minimum number of pieces you must place during the movement? Additional clarifications on the rules: 1. Pieces can only be placed on empty squares, whether before the movement starts or during the game. 2. The original piece on the leftmost square before the movement starts must never be captured.

The first line contains a positive odd integer $N$. The second line contains $N$ integers. If the $i$-th integer is $1$, then the $i$-th square is red; otherwise, it is white. The numbers are separated by spaces.

Output two lines. Each line contains one integer, representing the answers to the first and second questions, respectively.

Before the game starts, you can place a piece on the second square. After the game starts, use the leftmost piece to capture it and thus move to the third square. Then, since the fourth square is red, you can place a piece there during the game, and use the piece that has moved to the third square to capture it, thereby reaching the end. Constraints: - For $100\%$ of the testdata, $1 \le N \le 1000$, and the numbers in the output do not exceed $10^{15}$. - For $30\%$ of the testdata, $N \le 20$. Source: [Ahoi2009] checker. Translated by ChatGPT 5