A. Sherlock Bones

Codeforces

IDCF10135A

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case. He is given a string of zeros and ones and length N. Let F(x, y) equal to the number of ones in the string between indices x and y inclusively. Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, sj is equal to 1, and F(i, j) is equal to F(j, k). The first line of input is T – the number of test cases. The first line of each test case is an integer N (3 ≤ N ≤ 2 × 105). The second line is a string of zeros and ones of length N. For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k). ## Input The first line of input is T – the number of test cases.The first line of each test case is an integer N (3 ≤ N ≤ 2 × 105).The second line is a string of zeros and ones of length N. ## Output For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k). [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 2 \times 10^5 $, and let $ s = s_1 s_2 \dots s_n \in \{0,1\}^n $ be a binary string. Define $ F(i, j) = \sum_{\ell=i}^{j} s_\ell $ for $ 1 \leq i \leq j \leq n $. **Constraints** 1. $ 1 \leq T \leq \text{unknown} $ (not bounded in input, but implied by constraints on $ n $) 2. For each test case: - $ 3 \leq n \leq 2 \times 10^5 $ - $ s_i \in \{0,1\} $ for all $ i \in \{1, \dots, n\} $ **Objective** Count the number of ordered triples $ (i, j, k) $ such that: - $ 1 \leq i < j < k \leq n $, - $ s_j = 1 $, - $ F(i, j) = F(j, k) $.

API Response (JSON)

{
  "problem": {
    "name": "A. Sherlock Bones",
    "description": {
      "content": "The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case. He is g",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10135A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.\n\nHe is g...",
      "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, let $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 2 \\times 10^5 $, and let $ s = s_1 s_2 \\dots s_n \\in \\{0,1\\}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments