Codeforces Round #440 Div. 2 C. Maximum splitting

問題ページ
Problem - C - Codeforces

概要

q個(1<=q<=10^5)個のクエリが与えられる。各クエリでは整数n(1<=n<=10^9)が与えられる。整数nを合成数の和として表したとき、最大の合成数の個数を各クエリで答えろ。

考えたこと

1. できるだけ小さい合成数をつかったほうがよさそう
2. 合成数は小さい方から4,6,9,10,12…となっている
3. nが小さいときについて実験してみる

n
1  -1
2  -1
3  -1
4  1 (4)
5  -1
6  1 (6)
7  -1
8  2 (4+4)
9  1 (9)
10 2 (4+6)
11 -1
12 3 (4+4+4)
13 2 (4+9)
14 3 (4+4+6)
15 2 (5+9)
16 4 (4+4+4+4)

1. 4と6を使えば4以上の偶数はすべて表現できる
2. 同様に4と6と9を使えば13以上のすべての数が表現できる
3. したがって答えが-1になるのはn=1,2,3,5,7,11のみ
4. 偶数であればfloor(n[i]/4)が答えになり、奇数であればfloor((n[i]-9)/4)+1が答えになる

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int n[100010];
signed main(void)
{
  int q;
  cin >> q;
  REP(i, q) cin >> n[i];

  REP(i, q) {
    if(n[i] == 1 || n[i] == 2 || n[i] == 3 || n[i] == 5 || n[i] == 7 || n[i] == 11) {
      cout << -1 << endl;
    } else if(n[i]%2) {
      cout << (n[i]-9)/4 + 1 << endl;
    } else {
      cout << n[i]/4 << endl;
    }
  }

  return 0;
}