C. Candy division

Codeforces

IDCF10159C

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Your older sister has three kids. Whenever you go to visit her, you bring along a bag of candies for the kids. There are n candies in the bag. You want to give all the candies to the kids, but you also want to teach them a little math along the way. Therefore, you gave them not just the bag of candies but also one simple rule: each of the kids must take an integer fraction of candies in the bag. In other words, the amount of candies each kid takes must be a divisor of n. Formally, in order to divide all the candies the kids have to find three _positive_ integers a1, a2, a3 such that n = a1 + a2 + a3 and each ai divides n. The first line of the input contains a single integer t – the number of test cases to follow. Each of the following t lines of the input contains the integer n. You may assume that 1 ≤ t ≤ 100 and 1 ≤ n ≤ 1018. Output t lines. The k-th line will solve the k-th test case and will contain three integers ai as specified above. If there are multiple solutions you may select an arbitrary one. If there are no solutions, output the word _'IMPOSSIBLE'_ instead (quotes only for clarity). ## Input The first line of the input contains a single integer t – the number of test cases to follow. Each of the following t lines of the input contains the integer n. You may assume that 1 ≤ t ≤ 100 and 1 ≤ n ≤ 1018. ## Output Output t lines. The k-th line will solve the k-th test case and will contain three integers ai as specified above. If there are multiple solutions you may select an arbitrary one. If there are no solutions, output the word _'IMPOSSIBLE'_ instead (quotes only for clarity). [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $, let $ n_k \in \mathbb{Z}^+ $ be the total number of candies. **Constraints** 1. $ 1 \le t \le 100 $ 2. $ 1 \le n_k \le 10^{18} $ for all $ k \in \{1, \dots, t\} $ **Objective** For each test case $ k $, find three positive integers $ a_1, a_2, a_3 \in \mathbb{Z}^+ $ such that: $$ a_1 + a_2 + a_3 = n_k \quad \text{and} \quad a_i \mid n_k \quad \text{for all } i \in \{1,2,3\} $$ If no such triple exists, output "IMPOSSIBLE".

API Response (JSON)

{
  "problem": {
    "name": "C. Candy division",
    "description": {
      "content": "Your older sister has three kids. Whenever you go to visit her, you bring along a bag of candies for the kids. There are n candies in the bag. You want to give all the candies to the kids, but you als",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10159C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Your older sister has three kids. Whenever you go to visit her, you bring along a bag of candies for the kids. There are n candies in the bag. You want to give all the candies to the kids, but you als...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let $ n_k \\in \\mathbb{Z}^+ $ be the total number of candies.\n\n**Constraints**  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments