I. Симметричные биты

Codeforces

IDCF10096I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Перед тем как стать исследователем пещер, дрон Пётр долгое время служил в Дронных Войсках Особого Назначения, где совершил очень много боевых вылетов. После окончания службы он решил сделать себе надпись на борту — общее число секунд, которые он провел в полёте на заданиях — 1274329 секунд. Поскольку Пётр — перфекционист, а число 1274329 далеко от идеала, он решил записать это число в двоичной системе счисления и получил 100110111000111011001. Пётр очень обрадовался, потому что получившаяся запись оказалась палиндромом, то есть одинаково читалась слева направо и справа налево. Такое совпадение глубоко засело в процессор нашего героя, и он решил выяснить, как много существует подобных чисел. Он рассказал эту историю нам, а мы даём вам задачу. Чтобы она была не такой простой, вы должны найти количество чисел, битовая запись которых является палиндромом, на отрезке [L; R]. Ввод содержит целые числа L и R (1 ≤ L ≤ R ≤ 1018). Выведите одно целое число — ответ на задачу. В первом тесте числами с двоичной записью-палиндромом являются 3, 5, 7. ## Входные Данные Ввод содержит целые числа L и R (1 ≤ L ≤ R ≤ 1018). ## Выходные Данные Выведите одно целое число — ответ на задачу. ## Пример Входные данные2 8Выходные данные3 ## Примечание В первом тесте числами с двоичной записью-палиндромом являются 3, 5, 7. [samples]

**Definitions** Let $ N \in \mathbb{Z}^+ $ be the number of pieces, $ M \in \mathbb{Z}_{\geq 0} $ the number of connecting methods. Let $ E = \{ (a_i, b_i, t_i) \mid i \in \{1, \dots, M\} \} $ be the set of edges, where $ a_i, b_i \in \{1, \dots, N\} $, $ a_i \neq b_i $, and $ t_i \in \mathbb{Z}^+ $ is the time cost of method $ i $. Let $ G = (V, E) $ be the undirected graph with $ V = \{1, \dots, N\} $ and edge weights $ t_i $. Let $ \mathcal{T} $ be the set of all spanning trees of $ G $ (if $ G $ is disconnected, then no spanning tree exists — but problem guarantees connectivity). Let $ T_{\min} = \arg\min_{T \in \mathcal{T}} \sum_{e \in T} t_e $ be the set of minimum spanning trees (MSTs). Let $ t_i^* \in \mathbb{Z}_{\geq 0} $ be the new weight of edge $ i $, with $ |t_i^* - t_i| $ being the number of retraining days for method $ i $. **Constraints** 1. $ 1 \leq N \leq 20 $, $ 0 \leq M \leq 1000 $ 2. $ 1 \leq t_i \leq 10^6 $ 3. $ t_i^* \in \mathbb{Z}_{\geq 0} $, $ t_i^* \leq 10^9 $ 4. The graph remains connected under $ t_i^* $ 5. The MST under weights $ t_i^* $ is **unique** **Objective** Minimize total retraining days: $$ \sum_{i=1}^{M} |t_i^* - t_i| $$ subject to the MST under $ \{t_i^*\} $ being unique.

API Response (JSON)

{
  "problem": {
    "name": "I. Симметричные биты",
    "description": {
      "content": "Перед тем как стать исследователем пещер, дрон Пётр долгое время служил в Дронных Войсках Особого Назначения, где совершил очень много боевых вылетов. После окончания службы он решил сделать себе надп",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10096I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Перед тем как стать исследователем пещер, дрон Пётр долгое время служил в Дронных Войсках Особого Назначения, где совершил очень много боевых вылетов. После окончания службы он решил сделать себе надп...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ be the number of pieces, $ M \\in \\mathbb{Z}_{\\geq 0} $ the number of connecting methods.  \nLet $ E = \\{ (a_i, b_i, t_i) \\mid i \\in \\{1, \\dots, M\\} \\} $ be ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments