Maximum splitting (Codeforces 870C)
Tags: Greedy, number theory

You are given several queries. In the i-th query you are given a single positive integer ni. You are to represent ni as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.

Input: The first line contains single integer q (1 ≤ q ≤ 105) — the number of queries.q lines follow. The (i + 1)-th line contains single integer ni (1 ≤ ni ≤ 109) — the i-th query.

Output: For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.

Note: 12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.8 = 4 + 4, 6 can't be split into several composite summands.1, 2, 3 are less than any composite number, so they do not have valid splittings.

Sample Inputs:
1
12

2
6
8

3
1
2
3

Sample Outputs:
3

1
2

-1
-1
-1

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
import threading

class Tail_Recursion_Optimization:

    def __init__(self, RECURSION_LIMIT, STACK_SIZE):
        setrecursionlimit(RECURSION_LIMIT)
        threading.stack_size(STACK_SIZE)
        return None

class SOLVE:

    def solve(self):
        R = stdin.readline
        W = stdout.write
        ans = []
        for i in range(int(R())):
            n = int(R())
            if n in [1, 2, 3, 5, 7, 11]:
                ans.append('-1')
            elif not n % 2:
                if not n % 4:
                    ans.append(str(n // 4))
                else:
                    ans.append(str(1 + (n - 6) // 4))
            else:
                n -= 9
                if not n % 4:
                    ans.append(str(1 + n // 4))
                else:
                    ans.append(str(2 + (n - 6) // 4))
        W('\n'.join(ans))
        return 0

def main():
    s = SOLVE()
    s.solve()
threading.Thread(target=main).start()

Solution (Python):
import sys
input = sys.stdin.readline

def solve(n):
    dp = {5: -1, 7: -1, 9: 1, 11: -1}
    q = []
    for _ in range(n):
        ni = int(input())
        if 1 <= ni <= 3:
            print(-1)
            continue
        if ni in dp:
            print(dp[ni])
            continue
        if ni % 4 == 0 or (ni - 2) % 4 == 0:
            print(ni // 4)
        elif (ni - 9) % 4 == 0 or (ni - 11) % 4 == 0:
            print((ni - 9) // 4 + 1)
        else:
            print(-1)
n = int(input())
solve(n)

Solution (Python):
n = int(input())
lst = []
for i in range(n):
    a = int(input())
    cnt = a // 4
    a = a - cnt * 4
    if a == 0 or (a == 2 and cnt >= 1):
        pass
    elif a == 1 and cnt >= 2:
        cnt -= 1
    elif a == 3 and cnt >= 3:
        cnt -= 1
    else:
        cnt = -1
    lst.append(cnt)
for i in range(n):
    print(lst[i])