Andrew and Stones (Codeforces 1637C)
Tags: Greedy, implementation

Andrew has $$$n$$$ piles with stones. The $$$i$$$-th pile contains $$$a_i$$$ stones. He wants to make his table clean so he decided to put every stone either to the $$$1$$$-st or the $$$n$$$-th pile.Andrew can perform the following operation any number of times: choose $$$3$$$ indices $$$1 \le i < j < k \le n$$$, such that the $$$j$$$-th pile contains at least $$$2$$$ stones, then he takes $$$2$$$ stones from the pile $$$j$$$ and puts one stone into pile $$$i$$$ and one stone into pile $$$k$$$. Tell Andrew what is the minimum number of operations needed to move all the stones to piles $$$1$$$ and $$$n$$$, or determine if it's impossible.

Input: The input contains several test cases. The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.The first line for each test case contains one integer $$$n$$$ ($$$3 \leq n \leq 10^5$$$) — the length of the array.The second line contains a sequence of integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array elements.It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case print the minimum number of operations needed to move stones to piles $$$1$$$ and $$$n$$$, or print $$$-1$$$ if it's impossible.

Note: In the first test case, it is optimal to do the following:   Select $$$(i, j, k) = (1, 2, 5)$$$. The array becomes equal to $$$[2, 0, 2, 3, 7]$$$.  Select $$$(i, j, k) = (1, 3, 4)$$$. The array becomes equal to $$$[3, 0, 0, 4, 7]$$$.  Twice select $$$(i, j, k) = (1, 4, 5)$$$. The array becomes equal to $$$[5, 0, 0, 0, 9]$$$. This array satisfy the statement, because every stone is moved to piles $$$1$$$ and $$$5$$$.  There are $$$4$$$ operations in total.In the second test case, it's impossible to put all stones into piles with numbers $$$1$$$ and $$$3$$$:   At the beginning there's only one possible operation with $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 1, 2]$$$.  Now there is no possible operation and the array doesn't satisfy the statement, so the answer is $$$-1$$$. In the third test case, it's optimal to do the following:   Select $$$(i, j, k) = (1, 2, 3)$$$. The array becomes equal to $$$[2, 0, 2]$$$. This array satisfies the statement, because every stone is moved to piles $$$1$$$ and $$$3$$$.  The is $$$1$$$ operation in total.In the fourth test case, it's impossible to do any operation, and the array doesn't satisfy the statement, so the answer is $$$-1$$$.

Sample Inputs:
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2

Sample Outputs:
4
-1
1
-1

Solution (Python):
for s in [*open(0)][2::2]:
    a = list(map(int, s.split()))[1:-1]
    if len(a) == 1 and a[0] & 1 or a.count(1) == len(a):
        print(-1)
    else:
        print(sum([(i + 1) // 2 for i in a]))

Solution (Python):
for s in [*open(0)][2::2]:
    a = list(map(int, s.split()))[1:-1]
    if len(a) == 1 and a[0] & 1 or a.count(1) == len(a):
        print(-1)
    else:
        print(sum([(i + 1) // 2 for i in a]))

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    if n == 3:
        print(a[1] // 2 if a[1] % 2 == 0 else -1)
        return
    ok = False
    ans = 0
    for i in range(1, n - 1):
        ok = ok or a[i] > 1
        if a[i] % 2 != 0:
            ans += (a[i] + 1) // 2
        else:
            ans += a[i] // 2
    print(ans if ok else -1)

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()