D. Max or Min .. that is the question!

Codeforces

IDCF10106D

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Omar is a very lucky person. One day he found an array of five integers in the middle of the street! Because Omar loves pre-calculations, he looked at the numbers and immediately marked the maximum number and the minimum number among them, just in case someone asked him about such information! The next day people started asking questions about the array. Most people asked about the maximum number and the minimum number as expected, but one question was beyond all Omar's expectations! The question was: "what is the maximum number we can get from choosing two distinct numbers from the array, such that their multiplication is as large as possible ?" It's a sure thing that Omar can easily calculate this information, but as everyone knows .. he is a very busy person. Can you help him answering the question? The first line of the input contains T the number of test cases. Each test case is represented with five integers on a single line separated by spaces, the numbers that Omar found. All numbers are positive, distinct integers and less than 1000. For each test print one integer. The answer to the question above. ## Input The first line of the input contains T the number of test cases.Each test case is represented with five integers on a single line separated by spaces, the numbers that Omar found. All numbers are positive, distinct integers and less than 1000. ## Output For each test print one integer. The answer to the question above. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of categories. Let $ K \in \mathbb{Z}^+ $ be Nay’s position in the queue. Let $ A = (a_1, a_2, \dots, a_N) $ be a sequence of non-negative integers representing the prices of jewels in each category. **Constraints** 1. $ 1 \leq N \leq 10^5 $ 2. $ 1 \leq K \leq \binom{N}{2} $ 3. $ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $ **Objective** The set of all possible distinct pairs of categories is $ \binom{N}{2} $. Clients select unordered pairs $ \{i, j\} $ with $ i \ne j $, and no pair may be repeated. The cost of selecting pair $ \{i, j\} $ is $ a_i + a_j $. The first $ K-1 $ clients will choose the $ K-1 $ cheapest distinct pairs. Nay, as the $ K $-th client, must choose the $ K $-th cheapest distinct pair. Find the minimum total cost of the $ K $-th smallest sum $ a_i + a_j $ over all unordered pairs $ \{i, j\} $ with $ i < j $. $$ \text{Answer} = \text{the } K\text{-th smallest value in } \left\{ a_i + a_j \mid 1 \leq i < j \leq N \right\} $$

API Response (JSON)

{
  "problem": {
    "name": "D. Max or Min .. that is the question!",
    "description": {
      "content": "Omar is a very lucky person. One day he found an array of five integers in the middle of the street! Because Omar loves pre-calculations, he looked at the numbers and immediately marked the maximum n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10106D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Omar is a very lucky person. One day he found an array of five integers in the middle of the street!\n\nBecause Omar loves pre-calculations, he looked at the numbers and immediately marked the maximum n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of categories.  \nLet $ K \\in \\mathbb{Z}^+ $ be Nay’s position in the queue.  \nLet $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of non-negativ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments