I. Inflation

Codeforces

IDCF10248I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

To avoid inflating the balloons by hand, the organisers also bought $n$ helium gas canisters. Each canister can only be used to inflate one balloon, and must be emptied completely into that balloon (it is not possible to disconnect a canister from a balloon before the canister has been fully used). Unfortunately the gas canisters were bought at a garage sale, and may contain differing amounts of helium. Some may even be empty! To make the best of this challenging situation, the canisters will have to be paired with the balloons smartly. The organisers want to assign all of the gas canisters to separate balloons, such that the balloon that is inflated the least (relative to its capacity) still contains the maximum possible fraction of helium inside. What is the maximum such (minimum) fraction that is possible? Balloons filled beyond their capacity will explode. Explosions are upsetting and must be avoided. The input consists of: If it is possible to fill all the balloons without any exploding, output the maximum fraction $f$ such that every balloon can be filled to at least $f$ of its capacity. Otherwise, output "-1". Your answer should have an absolute or relative error of at most $10^(-6)$. ## Input The input consists of: One line with the integer $n$ ($1 <= n <= 2 dot.op 10^5$), the number of balloons and gas canisters. One line with $n$ integers $c_1, \\dots, c_n$ ($0 <= c_i <= n$ for each $i$), the amounts of helium in the gas canisters, in decilitres. ## Output If it is possible to fill all the balloons without any exploding, output the maximum fraction $f$ such that every balloon can be filled to at least $f$ of its capacity. Otherwise, output "-1".Your answer should have an absolute or relative error of at most $10^(-6)$. [samples]

**Definitions** Let $ r, c \in \mathbb{Z}^+ $ denote the number of rows and columns of vertices, respectively. Let $ G $ be a grid graph embedded in a $ (2r-1) \times (2c-1) $ character matrix, where: - Vertices are represented by `'x'` at positions: - Odd-indexed lines $ 4k+1 $: columns $ 1, 5, 9, \dots $ (i.e., $ 4j+1 $ for $ j = 0, \dots, c-1 $) - Odd-indexed lines $ 4k+3 $: columns $ 3, 7, 11, \dots $ (i.e., $ 4j+3 $ for $ j = 0, \dots, c-1 $) - Horizontal edges: `'---'` between adjacent vertices on the same row. - Diagonal edges: `'/'` (top-left to bottom-right) or `'\'` (top-right to bottom-left) between diagonally adjacent vertices. Let $ V $ be the set of vertex coordinates $ (i, j) \in \{1, \dots, r\} \times \{1, \dots, c\} $, mapped to their 2D grid positions in the character matrix. Let $ E $ be the set of edges (horizontal, diagonal) connecting vertices in $ V $, inferred from the input matrix. **Constraints** 1. $ 1 \le r \le 3000 $, $ 1 \le c \le 6000 $ 2. The input encodes all possible edges between adjacent vertices in the triangular grid. 3. The graph is a subset of the infinite triangular lattice, bounded by $ r $ rows and $ c $ columns. **Objective** Compute the total number of **triangles** (of any size) formed by the edges in $ E $. A triangle is a set of three vertices $ \{u, v, w\} \subseteq V $ such that all three edges $ (u,v), (v,w), (w,u) \in E $, forming a face of the grid. Triangles may be oriented upward or downward and may have side lengths $ \ell = 1, 2, \dots, \min(r, c) $ (in terms of vertex steps).

API Response (JSON)

{
  "problem": {
    "name": "I. Inflation",
    "description": {
      "content": "To avoid inflating the balloons by hand, the organisers also bought $n$ helium gas canisters. Each canister can only be used to inflate one balloon, and must be emptied completely into that balloon (i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10248I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "To avoid inflating the balloons by hand, the organisers also bought $n$ helium gas canisters. Each canister can only be used to inflate one balloon, and must be emptied completely into that balloon (i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ r, c \\in \\mathbb{Z}^+ $ denote the number of rows and columns of vertices, respectively.  \nLet $ G $ be a grid graph embedded in a $ (2r-1) \\times (2c-1) $ character matrix, wh...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments