B. Count Palindromes

Codeforces

IDCF10058B

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Given two times when seen on a digital clock, count the number of moments between these two times (both start and end time included) when the time was a palindrome. A digital clock shows time in the format HH:MM:SS (hours:minutes:seconds). For example, 2:40:38 pm is represented as 14:40:38. The first line contains q ( ≤ 105) queries. This is followed by q lines each containing two time strings, t1 and t2, which are 6 digit integers that represent times shown by a digital clock. It is ensured that t1 and t2 are valid times(t1 occurs on or before t2). For each query in one line print the number of palindromic times. Query 1: Only 1 moment is considered in this case, i.e., 00:00:01. We can clearly see that 00:00:01 is not a palindromic string. Query 4: Between 02:38:15 and 03:01:16, there are 3 moments that are palindromic strings. They are 02:44:20, 02:55:20 and 03:00:30. Note that the time as seen on a digital clock should appear as a palindrome. 1 is a palindrome, but 00:00:01 on a digital clock is not. ## Input The first line contains q ( ≤ 105) queries. This is followed by q lines each containing two time strings, t1 and t2, which are 6 digit integers that represent times shown by a digital clock. It is ensured that t1 and t2 are valid times(t1 occurs on or before t2). ## Output For each query in one line print the number of palindromic times. [samples] ## Note Query 1: Only 1 moment is considered in this case, i.e., 00:00:01. We can clearly see that 00:00:01 is not a palindromic string. Query 4: Between 02:38:15 and 03:01:16, there are 3 moments that are palindromic strings. They are 02:44:20, 02:55:20 and 03:00:30. Note that the time as seen on a digital clock should appear as a palindrome. 1 is a palindrome, but 00:00:01 on a digital clock is not.

**Definitions** Let $ t \in \mathbb{Z} $ be the number of queries. Let $ Q = \{(T_1^{(k)}, T_2^{(k)}) \mid k \in \{1, \dots, t\}\} $ be the set of queries, where for each $ k $: - $ T_1^{(k)}, T_2^{(k)} $ are 6-digit strings representing valid times in HH:MM:SS format (00:00:00 to 23:59:59). - $ T_1^{(k)} \leq T_2^{(k)} $ lexicographically (i.e., $ T_1^{(k)} $ occurs on or before $ T_2^{(k)} $). **Constraints** 1. $ 1 \leq t \leq 10^5 $ 2. Each time string $ T = \text{HHMMSS} $ satisfies: - $ 0 \leq \text{HH} \leq 23 $ - $ 0 \leq \text{MM} \leq 59 $ - $ 0 \leq \text{SS} \leq 59 $ **Objective** For each query $ k $, count the number of times $ T $ in the inclusive range $ [T_1^{(k)}, T_2^{(k)}] $ such that the 6-digit string $ T = d_1d_2d_3d_4d_5d_6 $ satisfies: $$ d_1 = d_6, \quad d_2 = d_5, \quad d_3 = d_4 $$

API Response (JSON)

{
  "problem": {
    "name": "B. Count Palindromes",
    "description": {
      "content": "Given two times when seen on a digital clock, count the number of moments between these two times (both start and end time included) when the time was a palindrome.  A digital clock shows time in the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10058B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given two times when seen on a digital clock, count the number of moments between these two times (both start and end time included) when the time was a palindrome. \n\nA digital clock shows time in the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of queries.  \nLet $ Q = \\{(T_1^{(k)}, T_2^{(k)}) \\mid k \\in \\{1, \\dots, t\\}\\} $ be the set of queries, where for each $ k $:  \n- $ T_1^{(k)}, T...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments