A. Diplomas and Certificates

Codeforces

IDCF818A

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

There are _n_ students who have taken part in an olympiad. Now it's time to award the students. Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called _winners_. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be **exactly** _k_ times greater than the number of diplomas. The number of _winners_ must **not be greater than half of the number of all students** (i.e. not be greater than half of _n_). It's possible that there are no _winners_. You have to identify the maximum possible number of _winners_, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not _winners_. ## Input The first (and the only) line of input contains two integers _n_ and _k_ (1 ≤ _n_, _k_ ≤ 1012), where _n_ is the number of students and _k_ is the ratio between the number of certificates and the number of diplomas. ## Output Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not _winners_ in case when the number of _winners_ is maximum possible. It's possible that there are no _winners_. [samples]

有 #cf_span[n] 名学生参加了竞赛。现在是时候为学生颁奖了。其中一些学生将获得文凭，一些将获得证书，其他人则什么也得不到。获得文凭和证书的学生被称为 _优胜者_。但计算文凭和证书数量有一些规则：证书的数量必须 *恰好* 是文凭数量的 #cf_span[k] 倍。_优胜者_ 的数量必须 *不超过* 所有学生数量的一半（即不超过 #cf_span[n] 的一半）。可能没有 _优胜者_。你需要根据这些规则，找出可能的最大 _优胜者_ 数量。同时，对于这种情况，你需要计算获得文凭的学生人数、获得证书的学生人数以及非 _优胜者_ 的学生人数。输入的第一行（也是唯一一行）包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 1012]），其中 #cf_span[n] 是学生人数，#cf_span[k] 是证书数量与文凭数量的比值。输出三个数：当 _优胜者_ 数量达到最大可能值时，获得文凭的学生人数、获得证书的学生人数以及非 _优胜者_ 的学生人数。可能没有 _优胜者_。 ## Input 输入的第一行（也是唯一一行）包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 1012]），其中 #cf_span[n] 是学生人数，#cf_span[k] 是证书数量与文凭数量的比值。 ## Output 输出三个数：当 _优胜者_ 数量达到最大可能值时，获得文凭的学生人数、获得证书的学生人数以及非 _优胜者_ 的学生人数。可能没有 _优胜者_。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 10^{12} $. Let $ d $ be the number of diplomas, $ c $ the number of certificates, and $ w = d + c $ the number of winners. Let $ r = n - w $ be the number of non-winners. **Constraints** 1. $ c = k \cdot d $ 2. $ w = d + c = d(1 + k) \leq \left\lfloor \frac{n}{2} \right\rfloor $ 3. $ d \in \mathbb{Z}_{\geq 0} $ **Objective** Maximize $ w = d(1 + k) $ subject to $ d(1 + k) \leq \left\lfloor \frac{n}{2} \right\rfloor $. Then output $ (d, c, r) = \left( d, k \cdot d, n - d(1 + k) \right) $, where $$ d = \left\lfloor \frac{\left\lfloor \frac{n}{2} \right\rfloor}{1 + k} \right\rfloor $$

Samples

Input #1

18 2

Output #1

3 6 9

Input #2

9 10

Output #2

0 0 9

Input #3

1000000000000 5

Output #3

83333333333 416666666665 500000000002

Input #4

1000000000000 499999999999

Output #4

1 499999999999 500000000000

API Response (JSON)

{
  "problem": {
    "name": "A. Diplomas and Certificates",
    "description": {
      "content": "There are _n_ students who have taken part in an olympiad. Now it's time to award the students. Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Stud",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF818A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ students who have taken part in an olympiad. Now it's time to award the students.\n\nSome of them will receive diplomas, some wiil get certificates, and others won't receive anything. Stud...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "有 #cf_span[n] 名学生参加了竞赛。现在是时候为学生颁奖了。\n\n其中一些学生将获得文凭，一些将获得证书，其他人则什么也得不到。获得文凭和证书的学生被称为 _优胜者_。但计算文凭和证书数量有一些规则：证书的数量必须 *恰好* 是文凭数量的 #cf_span[k] 倍。_优胜者_ 的数量必须 *不超过* 所有学生数量的一半（即不超过 #cf_span[n] 的一半）。可能没有 _优胜者_。\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 10^{12} $.  \nLet $ d $ be the number of diplomas, $ c $ the number of certificates, and $ w = d + c $ the number of winners.  \nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments