C. Maximum splitting

Codeforces

IDCF872C

Time2000ms

Memory256MB

Difficulty—

dpgreedymathnumber theory

English · Original

Chinese · Translation

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] 个查询。对于每个查询，输出在合法的合数加数划分中可能的最大加数个数，或 _-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] 个查询。 ## 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] 小于任何合数，因此它们没有合法的划分。

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": "C. 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": "CF872C"
  },
  "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_spa...",
      "is_translate": true,
      "language": "Chinese"
    }
  ]
}

Full JSON Raw Segments