B. Путь Поликарпа

Codeforces

IDCF751B

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Лайнландия состоит из _n_ городов, которые расположены на оси Ox. Координата _i_\-го из городов равна _x__i_. Поликарп прошел от одного города до другого по прямой кратчайшим образом. Он утверждает, что прошел расстояние _d_. Выведите количество пар городов, что Поликарп мог пройти от одного к другому. Иными словами, между которыми расстояние составляет ровно _d_. ## Входные Данные В первой строке записаны два целых числа _n_, _d_ (2 ≤ _n_ ≤ 105, 1 ≤ _d_ ≤ 109). Вторая строка содержит координаты _n_ городов — последовательность целых чисел _x_1, _x_2, ..., _x__n_ ( - 109 ≤ _x__i_ ≤ 109). Все _x__i_ — различны. ## Выходные Данные Выведите искомое количество пар городов. Пары, отличающиеся только порядком городов, следует считать одной и той же парой. ## Примеры Входные данные 6 3 6 13 4 10 5 9 Выходные данные 2 Входные данные 10 1 1 2 3 4 5 6 7 8 9 10 Выходные данные 9 [samples]

Лайнландия состоит из $n$ городов, которые расположены на оси $Ox$. Координата $i$-го из городов равна $x_i$. Поликарп прошел от одного города до другого по прямой кратчайшим образом. Он утверждает, что прошел расстояние $d$. Выведите количество пар городов, что Поликарп мог пройти от одного к другому. Иными словами, между которыми расстояние составляет ровно $d$. В первой строке записаны два целых числа $n$, $d$ ($2 ≤ n ≤ 10^5, 1 ≤ d ≤ 10^9$). Вторая строка содержит координаты $n$ городов — последовательность целых чисел $x_1, x_2, ..., x_n$ ($ - 10^9 ≤ x_i ≤ 10^9$). Все $x_i$ — различны. Выведите искомое количество пар городов. Пары, отличающиеся только порядком городов, следует считать одной и той же парой. ## Входные Данные В первой строке записаны два целых числа $n$, $d$ ($2 ≤ n ≤ 10^5, 1 ≤ d ≤ 10^9$).Вторая строка содержит координаты $n$ городов — последовательность целых чисел $x_1, x_2, ..., x_n$ ($ - 10^9 ≤ x_i ≤ 10^9$). Все $x_i$ — различны. ## Выходные Данные Выведите искомое количество пар городов. Пары, отличающиеся только порядком городов, следует считать одной и той же парой. ## Примеры Входные данные 6 3 6 13 4 10 5 9 Выходные данные 2 Входные данные 10 1 1 2 3 4 5 6 7 8 9 10 Выходные данные 9 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of cities, and $ d \in \mathbb{Z} $ be the claimed distance. Let $ X = (x_1, x_2, \dots, x_n) $ be a sequence of distinct integer coordinates of the cities on the Ox axis. **Constraints** 1. $ 2 \leq n \leq 10^5 $ 2. $ 1 \leq d \leq 10^9 $ 3. $ -10^9 \leq x_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ 4. All $ x_i $ are distinct. **Objective** Count the number of unordered pairs $ \{i, j\} $ with $ i \ne j $ such that $ |x_i - x_j| = d $.

API Response (JSON)

{
  "problem": {
    "name": "B. Путь Поликарпа",
    "description": {
      "content": "Лайнландия состоит из _n_ городов, которые расположены на оси Ox. Координата _i_\\-го из городов равна _x__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": "CF751B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Лайнландия состоит из _n_ городов, которые расположены на оси Ox. Координата _i_\\-го из городов равна _x__i_.\n\nПоликарп прошел от одного города до другого по прямой кратчайшим образом. Он утверждает, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Лайнландия состоит из $n$ городов, которые расположены на оси $Ox$. Координата $i$-го из городов равна $x_i$.\n\nПоликарп прошел от одного города до другого по прямой кратчайшим образом. Он утверждает, ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cities, and $ d \\in \\mathbb{Z} $ be the claimed distance.  \nLet $ X = (x_1, x_2, \\dots, x_n) $ be a sequence of distinct integer coordinates...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments