Maximum splitting [Codeforces Round #440 A]

http://codeforces.com/contest/871/problem/A

Q個の以下のクエリに答える。
ある数Nが与えられるので、これを合成数(4以上の非素数)の和で表す。
何個の数で表せられるか答えよ。無理なら"-1"

Q≦10^5, N≦10^9

解法

http://codeforces.com/contest/871/submission/31335818

実験してみると、場合分けで解けると分かる。
　
偶数の場合
4の倍数であれば、全部4の和とできるため、N/4が答え
4の倍数でないなら、6が1つと他全部4の和とできるため、(N-6)/4+1が答え
　
奇数の場合
「奇数+偶数」であり、奇数でかつ合成数で最小のものは9なので、9+偶数と分ければいい。
偶数の部分は上の場合分けを使って最大何個の和で表現できるか計算すればいい。

int N;
int solve() {
    cin >> N;

    if (N < 4) return -1;
    if (N == 5 or N == 7 or N == 11) return -1;

    int ans = 0;

    if (N % 2 == 1) {
        ans++;
        N -= 9;
    }

    assert(N % 2 == 0);

    if (N % 4 == 0) ans += N / 4;
    else ans += (N - 6) / 4 + 1;

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int Q; cin >> Q;
    rep(q, 0, Q) printf("%d\n", solve());
}