I. Home Sweet Home

Codeforces

IDCF10108I

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some cool information about binary numbers and operators, and he gave her this challenge to pass the time. Coach Fegla asked her if she could find the number of ways to choose two integers, A and B, such that (L ≤ A, B ≤ R) and the XOR of the binary representations of A and B (without leading zeros) is palindrome in binary. For example, , after removing leading zeros 101 is palindrome. The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases. Each test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 1012). For each test case print the number of ways on a single line. A string of binary digits is a palindrome if it can be read the same from either direction. For example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not. means XOR, remember that: Warning: large Input/Output data, be careful with certain languages. ## Input The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.Each test case will contain two space - separated integers L, R (0 ≤ L ≤ R ≤ 1012). ## Output For each test case print the number of ways on a single line. [samples] ## Note A string of binary digits is a palindrome if it can be read the same from either direction.For example: 0, 11 and 10101 are palindromes, while 10 and 10011 are not. means XOR, remember that: Warning: large Input/Output data, be careful with certain languages.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $, let $ L_k, R_k \in \mathbb{Z} $ with $ 0 \leq L_k \leq R_k \leq 10^{12} $. Let $ S_k = \{ (A, B) \in \mathbb{Z}^2 \mid L_k \leq A, B \leq R_k \} $. **Constraints** 1. $ 1 \leq T \leq 128 $ 2. For each $ k $: $ 0 \leq L_k \leq R_k \leq 10^{12} $ **Objective** For each test case $ k $, compute: $$ N_k = \left| \left\{ (A, B) \in S_k \mid \text{bin}(A \oplus B) \text{ is a binary palindrome (without leading zeros)} \right\} \right| $$ where $ \text{bin}(n) $ denotes the binary representation of $ n \in \mathbb{N}_0 $ without leading zeros, and a string is a palindrome if it equals its reverse.

API Response (JSON)

{
  "problem": {
    "name": "I. Home Sweet Home",
    "description": {
      "content": "While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10108I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "While Coach Fegla and Noura were flying back home from Marrakech after attending the ICPC2015 World Finals, they got really bored in their 6 - hour plane trip, so the coach decided to tell Noura some ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ L_k, R_k \\in \\mathbb{Z} $ with $ 0 \\leq L_k \\leq R_k \\leq 10^{12} $.  \nLet...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments