C. Coin Graph

Codeforces

IDCF10053C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

First of all you must know that the name of this problem is irrelevant to what we want! You are given an integer s. Find a simple connected graph such that the sum of lengths of the shortest paths between all pairs of its vertices is s. Input contains a signle integer s. (0 ≤ s ≤ 105) Print "Impossible" (without the quotes) if there is no graph, satisfying the described conditions. Otherwise in the first line print two space-separated integers n and m — the number of vertices and edges in your graph, respectively. Each of following m lines contain two space-separated integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi) — two vertices, connected by an edge in the resulting graph. If there are several answers you can print any of them. A graph is simple if it has no self-loops or multiple edges between the same vertices. All edges in a simple graph are unweighted and undirected. A graph is connected if there is a path connecting every pair of vertices. ## Input Input contains a signle integer s. (0 ≤ s ≤ 105) ## Output Print "Impossible" (without the quotes) if there is no graph, satisfying the described conditions. Otherwise in the first line print two space-separated integers n and m — the number of vertices and edges in your graph, respectively. Each of following m lines contain two space-separated integers ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi) — two vertices, connected by an edge in the resulting graph. If there are several answers you can print any of them. [samples] ## Note A graph is simple if it has no self-loops or multiple edges between the same vertices. All edges in a simple graph are unweighted and undirected. A graph is connected if there is a path connecting every pair of vertices.

**Definitions** Let $ s \in \mathbb{Z} $ with $ 0 \leq s \leq 10^5 $. **Objective** Find a simple connected graph $ G = (V, E) $ such that the sum of the lengths of all shortest paths between every pair of distinct vertices equals $ s $, i.e., $$ \sum_{\{u,v\} \subseteq V, u \neq v} \text{dist}(u,v) = s $$ If no such graph exists, output "Impossible". Otherwise, output: - $ n = |V| $, $ m = |E| $ - $ m $ edges $ (u_i, v_i) $, with $ 1 \leq u_i < v_i \leq n $, forming a simple connected graph.

API Response (JSON)

{
  "problem": {
    "name": "C. Coin Graph",
    "description": {
      "content": "First of all you must know that the name of this problem is irrelevant to what we want! You are given an integer s. Find a simple connected graph such that the sum of lengths of the shortest paths be",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10053C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "First of all you must know that the name of this problem is irrelevant to what we want!\n\nYou are given an integer s. Find a simple connected graph such that the sum of lengths of the shortest paths be...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\mathbb{Z} $ with $ 0 \\leq s \\leq 10^5 $.  \n\n**Objective**  \nFind a simple connected graph $ G = (V, E) $ such that the sum of the lengths of all shortest paths between e...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments