C. Find Amir

Codeforces

IDCF805C

Time1000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

A few years ago Sajjad left his school and register to another one due to security reasons. Now he wishes to find Amir, one of his schoolmates and good friends. There are _n_ schools numerated from 1 to _n_. One can travel between each pair of them, to do so, he needs to buy a ticket. The ticker between schools _i_ and _j_ costs and can be used multiple times. Help Sajjad to find the minimum cost he needs to pay for tickets to visit all schools. He can start and finish in any school. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the number of schools. ## Output Print single integer: the minimum cost of tickets needed to visit all schools. [samples] ## Note In the first example we can buy a ticket between the schools that costs .

几年前，Sajjad 因安全原因离开了他的学校并注册到另一所学校。现在他希望找到他的同学兼好友 Amir。有 #cf_span[n] 所学校，编号从 #cf_span[1] 到 #cf_span[n]。任意两所学校之间都可以通行，为此他需要购买一张票。学校 #cf_span[i] 和学校 #cf_span[j] 之间的票价格为，且可多次使用。请帮助 Sajjad 计算他访问所有学校所需的最少票价。他可以从任意学校出发，也在任意学校结束。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 学校的数量。请输出一个整数：访问所有学校所需的最少票价。在第一个例子中，我们可以购买一张在两所学校之间、价格为的票。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 学校的数量。 ## Output 请输出一个整数：访问所有学校所需的最少票价。 [samples] ## Note 在第一个例子中，我们可以购买一张在两所学校之间、价格为的票。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of schools, labeled $ 1 $ to $ n $. Let the cost of a ticket between any two distinct schools $ i $ and $ j $ be $ c_{i,j} = 1 $. **Constraints** $ 1 \leq n \leq 10^5 $ **Objective** Find the minimum total cost to visit all $ n $ schools, where tickets between any pair of schools cost 1 and can be reused. This is equivalent to finding the minimum cost of a connected subgraph spanning all $ n $ vertices — i.e., a spanning tree. The minimum number of edges required to connect $ n $ vertices is $ n - 1 $, and each edge costs 1. Thus, the minimum cost is: $$ n - 1 $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Find Amir",
    "description": {
      "content": "A few years ago Sajjad left his school and register to another one due to security reasons. Now he wishes to find Amir, one of his schoolmates and good friends. There are _n_ schools numerated from 1",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF805C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A few years ago Sajjad left his school and register to another one due to security reasons. Now he wishes to find Amir, one of his schoolmates and good friends.\n\nThere are _n_ schools numerated from 1...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "几年前，Sajjad 因安全原因离开了他的学校并注册到另一所学校。现在他希望找到他的同学兼好友 Amir。\n\n有 #cf_span[n] 所学校，编号从 #cf_span[1] 到 #cf_span[n]。任意两所学校之间都可以通行，为此他需要购买一张票。学校 #cf_span[i] 和学校 #cf_span[j] 之间的票价格为  ，且可多次使用。请帮助 Sajjad 计算他访问所有学校所需的最...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of schools, labeled $ 1 $ to $ n $.  \nLet the cost of a ticket between any two distinct schools $ i $ and $ j $ be $ c_{i,j} = 1 $.\n\n**Constrai...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments