Hayato and School (Codeforces 1780A)
Tags: Greedy, constructive algorithms

Today Hayato came home from school with homework.In the assignment, Hayato was given an array $$$a$$$ of length $$$n$$$. The task was to find $$$3$$$ numbers in this array whose sum is odd. At school, he claimed that there are such $$$3$$$ numbers, but Hayato was not sure, so he asked you for help.Answer if there are such three numbers, and if so, output indices $$$i$$$, $$$j$$$, and $$$k$$$ such that $$$a_i + a_j + a_k$$$ is odd.The odd numbers are integers that are not divisible by $$$2$$$: $$$1$$$, $$$3$$$, $$$5$$$, and so on.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.For each test case, the first line contains one integer $$$n$$$ ($$$3 \le n \le 300$$$) — the length of $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output: For each test case, in the first line print one word "YES" (without quotes) if there are $$$3$$$ numbers with an odd sum or "NO" (without quotes) if there are no such $$$3$$$ numbers.If the answer exists, then on the second line print $$$3$$$ distinct integers $$$i, j, k$$$ ($$$1 \le i, j, k \le n$$$) — the indices of the numbers. If there are several answers, output any.

Note: In the first test case, there is one way to choose $$$3$$$ numbers, and since $$$1 + 1 + 1 = 3$$$, this triple is fine for us.In the second test case, you need to choose the numbers $$$1, 2, 2$$$, since $$$1 + 2 + 2 = 5$$$.In the third test case, there is one way to choose three numbers, but $$$1 + 2 + 3 = 6$$$ is an even number, so the required triple does not exist.In the fifth test case, no matter what three numbers we choose, their sum is even.

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

Sample Outputs:
YES
1 2 3
YES
3 4 1
NO
YES
1 3 4
NO
YES
1 3 5

Solution (Python):
def i():
    n = int(input())
    s = list(input().split())
    o = []
    e = []
    for x in range(n):
        if s[x][-1] in ['1', '3', '5', '7', '9']:
            if x > 1:
                return f'YES\n1 2 {x + 1}'
            elif x == 1:
                e.append(str(x))
            o.append(str(x + 1))
            for y in range(x + 1, n):
                if s[y][-1] in ['2', '4', '6', '8', '0']:
                    e.append(str(y + 1))
                    if len(e) == 2:
                        return 'YES\n' + ' '.join(o[0:1] + e[:2])
                else:
                    o.append(str(y + 1))
                    if len(o) == 3:
                        return 'YES\n' + ' '.join(o)
            break
    return 'NO'
t = int(input())
a = []
for _ in range(t):
    a.append(i())
print('\n'.join(a))

Solution (Python):
class Solution:

    def __init__(self):
        pass

    def solve(self):
        t = int(input())
        result = []
        for i in range(t):
            n = int(input())
            arr = list(map(int, input().split()))
            odd_index = []
            even_index = []
            j = 1
            for a in arr:
                if a % 2 == 0:
                    even_index.append(j)
                else:
                    odd_index.append(j)
                if len(even_index) + len(odd_index) >= 3 and len(odd_index) >= 1 and (not (len(odd_index) == 2 and len(even_index) == 1)):
                    break
                j += 1
            if len(odd_index) >= 3:
                result.append([True, '{} {} {}'.format(odd_index[0], odd_index[1], odd_index[2])])
            elif len(odd_index) == 2:
                if len(even_index) == 1:
                    result.append([False])
                else:
                    result.append([True, '{} {} {}'.format(odd_index[0], even_index[0], even_index[1])])
            elif len(odd_index) == 1:
                result.append([True, '{} {} {}'.format(odd_index[0], even_index[0], even_index[1])])
            else:
                result.append([False])
        for x in result:
            if x[0]:
                print('YES')
                print(x[1])
            else:
                print('NO')
if __name__ == '__main__':
    sol = Solution()
    sol.solve()

Solution (Python):
for p in [*open(0)][2::2]:
    c = (a, b) = [[], []]
    i = 0
    for x in p.split():
        i += 1
        c[int(x) % 2] += (i,)
    a = b[~len(b) & 1:] + a
    print(*(['NO'], ['YES'] + a[:3])[b > [] < a[2:]])