B. Anany in the Army

Codeforces

IDCF10288B

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Anany was happily doing his military service, but someday he got bored. He was daydreaming about the moment he gets back to problem-solving when he suddenly noticed three sticks on the ground. He challenged his soul (pun intended) to solve the following problem: You can choose $textbf(o n e)$ stick and increase its length by any amount (integer or non-integer) less than or equal to $k$ units. You will then form a triangle using the sticks. What is the maximum area of a triangle that you can get? The first line of input contains an integer $T$, the number of test cases. Each of the next $T$ lines contains 4 space-separated integers each — the lengths of the 3 sticks, followed by $k$. All the numbers are positive integers and do not exceed $10^4$. It's guaranteed you can always form a non-degenerate triangle. For each test case, print the maximum area on a single line. The answer will be considered correct if its absolute or relative error does not exceed $10^(-4)$. ## Input The first line of input contains an integer $T$, the number of test cases.Each of the next $T$ lines contains 4 space-separated integers each — the lengths of the 3 sticks, followed by $k$.All the numbers are positive integers and do not exceed $10^4$.It's guaranteed you can always form a non-degenerate triangle. ## Output For each test case, print the maximum area on a single line. The answer will be considered correct if its absolute or relative error does not exceed $10^(-4)$. [samples]

**Definitions** Let $ G = (V, E) $ be an undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges, where $ V = \{1, 2, \dots, n\} $ and $ E $ contains no duplicate edges. Let $ c $ be the number of connected components in $ G $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq m \leq 10^5 $ 3. Each edge $ (u_i, v_i) \in E $ satisfies $ 1 \leq u_i, v_i \leq n $, $ u_i \neq v_i $, and no repeated edges. **Objective** Find the minimum number $ k = c - 1 $ of edges to add such that $ G $ becomes connected. Output: - $ k $ - $ k $ edges $ (u_j, v_j) $, each connecting two nodes from distinct connected components, such that the resulting graph is connected. *(Any valid set of $ k $ edges is acceptable.)*

API Response (JSON)

{
  "problem": {
    "name": "B. Anany in the Army",
    "description": {
      "content": "Anany was happily doing his military service, but someday he got bored. He was daydreaming about the moment he gets back to problem-solving when he suddenly noticed three sticks on the ground. He chal",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10288B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anany was happily doing his military service, but someday he got bored. He was daydreaming about the moment he gets back to problem-solving when he suddenly noticed three sticks on the ground. He chal...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges, where $ V = \\{1, 2, \\dots, n\\} $ and $ E $ contains no duplicate edges.\n\nLet $ c $ be the numb...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments