E. Pairs

Codeforces
IDCF10093E
Time2000ms
Memory64MB
Difficulty
English · Original
Formal · Original
In the secret book of ACM, it’s said:_* “Glory for those who write short ICPC problems. May they live long, and never get Wrong Answers”* _. Everyone likes problems with short statements. Right? Let’s have five positive numbers: X1,X2,X3,X4,X5. We can form 10 distinct pairs of these five numbers. Given the sum of each one of the pairs, you are asked to find out the original five numbers. The first line will be the number of test cases T. Each test case is described in one line which contains 10 numbers, these are the sum of the two numbers in each pair. Notice that the input has no particular order, for example: the first number doesn’t have to be equal to {X1+ X2}. All numbers are positive integers below 100,000,000. For each test case, print one line which contains the number of the test case, and the five numbers X1,X2,X3,X4,X5 in ascending order, see the samples and follow the output format. There always exists a unique solution. ## Input The first line will be the number of test cases T. Each test case is described in one line which contains 10 numbers, these are the sum of the two numbers in each pair. Notice that the input has no particular order, for example: the first number doesn’t have to be equal to {X1+ X2}. All numbers are positive integers below 100,000,000. ## Output For each test case, print one line which contains the number of the test case, and the five numbers X1,X2,X3,X4,X5 in ascending order, see the samples and follow the output format. There always exists a unique solution. [samples]
**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ S = \{s_1, s_2, \dots, s_{10}\} $ be a multiset of 10 positive integers representing the pairwise sums of five unknown positive integers $ X = \{x_1, x_2, x_3, x_4, x_5\} $, where $ x_1 < x_2 < x_3 < x_4 < x_5 $. **Constraints** 1. $ 1 \leq T \leq \text{unknown} $ (implied by input) 2. Each $ s_i \in \mathbb{Z}^+ $, $ s_i < 100{,}000{,}000 $ 3. The multiset $ S $ consists exactly of the $ \binom{5}{2} = 10 $ pairwise sums $ x_i + x_j $ for $ 1 \leq i < j \leq 5 $. 4. A unique solution $ (x_1, x_2, x_3, x_4, x_5) $ exists for each $ S $. **Objective** For each test case, recover the unique ordered tuple $ (x_1, x_2, x_3, x_4, x_5) $ such that $ x_1 < x_2 < x_3 < x_4 < x_5 $ and $$ \{x_i + x_j \mid 1 \leq i < j \leq 5\} = S $$ Output the tuple in ascending order.
API Response (JSON)
{
  "problem": {
    "name": "E. Pairs",
    "description": {
      "content": "In the secret book of ACM, it’s said:_* “Glory for those who write short ICPC problems. May they live long, and never get Wrong Answers”* _.  Everyone likes problems with short statements. Right?  Let",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10093E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the secret book of ACM, it’s said:_* “Glory for those who write short ICPC problems. May they live long, and never get Wrong Answers”* _.  Everyone likes problems with short statements. Right?  Let...",
      "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, let $ S = \\{s_1, s_2, \\dots, s_{10}\\} $ be a multiset of 10 positive integers representing the pairwise su...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments