A. Maximum splitting

Codeforces

IDCF871A

Time2000ms

Memory256MB

Difficulty—

dpgreedymathnumber theory

English · Original

Chinese · Translation

Formal · Original

You are given several queries. In the _i_\-th query you are given a single positive integer _n__i_. You are to represent _n__i_ 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 _n__i_ (1 ≤ _n__i_ ≤ 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. [samples] ## 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.

你被给定若干查询。在第 #cf_span[i]-th 个查询中，你被给定一个正整数 #cf_span[ni]。你需要将 #cf_span[ni] 表示为尽可能多的合数加数之和，并输出这个最大数量；如果不存在这样的拆分，则输出 _-1_。一个大于 #cf_span[1] 的整数是合数，当且仅当它不是素数，即它具有不等于 #cf_span[1] 和其自身的正因数。第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105]) —— 查询的数量。接下来 #cf_span[q] 行，第 (#cf_span[i + 1])-th 行包含一个整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 109]) —— 第 #cf_span[i]-th 个查询。对于每个查询，输出在合法的合数加数拆分中可能的最大加数个数，或 _-1_（如果不存在这样的拆分）。 #cf_span[12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12]，但第一种拆分具有最多的加数个数。 #cf_span[8 = 4 + 4]，#cf_span[6] 无法拆分为多个合数加数。 #cf_span[1, 2, 3] 小于任何合数，因此它们没有合法的拆分。 ## Input 第一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 105]) —— 查询的数量。#cf_span[q] 行follow。第 (#cf_span[i + 1])-th 行包含一个整数 #cf_span[ni] (#cf_span[1 ≤ ni ≤ 109]) —— 第 #cf_span[i]-th 个查询。 ## Output 对于每个查询，输出在合法的合数加数拆分中可能的最大加数个数，或 _-1_（如果不存在这样的拆分）。 [samples] ## Note #cf_span[12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12]，但第一种拆分具有最多的加数个数。#cf_span[8 = 4 + 4]，#cf_span[6] 无法拆分为多个合数加数。#cf_span[1, 2, 3] 小于任何合数，因此它们没有合法的拆分。

**Definitions** Let $ q \in \mathbb{Z} $ be the number of queries. Let $ N = (n_1, n_2, \dots, n_q) $ be the sequence of positive integers, where $ n_i \in \mathbb{Z}^+ $. Let $ C \subset \mathbb{Z}^+ $ be the set of composite numbers: $ C = \{ k \in \mathbb{Z}^+ \mid k > 1 \text{ and } k \text{ is not prime} \} $. **Constraints** 1. $ 1 \le q \le 10^5 $ 2. For each $ i \in \{1, \dots, q\} $: $ 1 \le n_i \le 10^9 $ **Objective** For each $ n_i $, find the maximum integer $ k \ge 1 $ such that there exist $ c_1, c_2, \dots, c_k \in C $ satisfying: $$ n_i = \sum_{j=1}^k c_j $$ If no such representation exists, output $ -1 $.

Samples

Input #1

1
12

Output #1

Input #2

2
6
8

Output #2

1
2

Input #3

Output #3

\-1
-1
-1

API Response (JSON)

{
  "problem": {
    "name": "A. Maximum splitting",
    "description": {
      "content": "You are given several queries. In the _i_\\-th query you are given a single positive integer _n__i_. You are to represent _n__i_ as a sum of maximum possible number of composite summands and print this",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF871A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given several queries. In the _i_\\-th query you are given a single positive integer _n__i_. You are to represent _n__i_ as a sum of maximum possible number of composite summands and print this...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定若干查询。在第 #cf_span[i]-th 个查询中，你被给定一个正整数 #cf_span[ni]。你需要将 #cf_span[ni] 表示为尽可能多的合数加数之和，并输出这个最大数量；如果不存在这样的拆分，则输出 _-1_。\n\n一个大于 #cf_span[1] 的整数是合数，当且仅当它不是素数，即它具有不等于 #cf_span[1] 和其自身的正因数。\n\n第一行包含一个整数 #cf_s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ N = (n_1, n_2, \\dots, n_q) $ be the sequence of positive integers, where $ n_i \\in \\mathbb{Z}^+ $.  \nLet $ C \\subset \\mathb...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments