P9018 [USACO23JAN] Moo Route G

Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each second. However, there actually is no exit and after $T$ seconds, Bessie is back at $x=0$, tired and resigned. Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5,\cdots,(N−1).5$ , given by an array $A_0,A_1, \cdots ,A_{N−1} (1 \le N \le 10^5, 1 \le A_i \le 10^6)$. Bessie never reaches $x>N$ nor $x

N/A

N/A

### Explanation for Sample 1 Bessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times: $\texttt{RRLRLLRRLL}$ $\texttt{RRLLRRLRLL}$ ### Scoring - Inputs $2-4$: $N \le 2$ and $\max(A_i) \le 10^3$ - Inputs $5-7$: $N \le 2$ - Inputs $8-11$: $\max(A_i) \le 10^3$ - Inputs $12-21$: No additional constraints.