Maximum splitting (Codeforces 872C)
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):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
    return [int(x) for x in sys.stdin.readline().split()]

def LI_():
    return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
    return [float(x) for x in sys.stdin.readline().split()]

def LS():
    return sys.stdin.readline().split()

def I():
    return int(sys.stdin.readline())

def F():
    return float(sys.stdin.readline())

def S():
    return input()

def main():
    q = I()
    r = []
    for _ in range(q):
        n = I()
        if n % 2 == 1:
            n -= 9
            if n == 0:
                r.append(1)
            elif n < 4:
                r.append(-1)
            else:
                r.append(n // 4 + 1)
        else:
            t = n // 4
            if t < 1:
                r.append(-1)
            else:
                r.append(n // 4)
    return '\n'.join(map(str, r))
print(main())

Solution (Python):
def check(n):
    if n < 4:
        return -1
    c = n // 4
    r = n % 4
    if r == 0 or r == 2:
        return c
    if r == 1:
        if c < 2:
            return -1
        else:
            return c - 1
    if r == 3:
        if c < 3:
            return -1
        else:
            return c - 1
q = int(input())
answer = []
while q > 0:
    q -= 1
    answer.append(str(check(int(input()))))
print('\n'.join(answer))

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from io import BytesIO, IOBase
from math import gcd, floor, sqrt, ceil
setrecursionlimit(10000)

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not a:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = a.count(b'\n') + (not a)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(a), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
input = lambda : stdin.readline().rstrip('\r\n')
inp = lambda : int(input())
st = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
int_arr = lambda : list(map(int, input().strip().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().strip().split())
get_int = lambda : map(int, input().strip().split())
get_float = lambda : map(float, input().strip().split())
mod = 1000000007
q = inp()
for _ in range(q):
    n = inp()
    if n <= 3:
        print(-1)
    elif n % 2 == 0:
        if n % 4 == 0:
            print(n // 4)
        else:
            print(n // 4 - 1 + 1)
    elif n <= 7:
        print(-1)
    else:
        n -= 9
        if n != 0:
            if n >= 4:
                if n % 4 == 0:
                    print(n // 4 + 1)
                else:
                    print(n // 4 - 1 + 2)
            else:
                print(-1)
        else:
            print(1)