H. Cinema

Codeforces

IDCF10110H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Rami and K of his friends are going to watch a movie tonight. There are only one row that contains some available seats, all other rows are taken. Given the description of this row, Rami wants to know if he can find consecutive seats available to sit with his friends. The first line of input contains a single integer T, the number of test cases. The first line of each test case consists of two-separated integers C, K (1 ≤ C, K ≤ 105), the number of seats in the row and the number of friends going with Rami, respectively. The second line contains a string of C digits, where 0 represents an empty seat, and 1 represents taken one. For each test case, print a single line with *yes* if Rami can find a place for him and his friends, otherwise print *no*. ## Input The first line of input contains a single integer T, the number of test cases.The first line of each test case consists of two-separated integers C, K (1 ≤ C, K ≤ 105), the number of seats in the row and the number of friends going with Rami, respectively.The second line contains a string of C digits, where 0 represents an empty seat, and 1 represents taken one. ## Output For each test case, print a single line with *yes* if Rami can find a place for him and his friends, otherwise print *no*. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ C_k \in \mathbb{Z} $ be the number of seats in the row. - Let $ K_k \in \mathbb{Z} $ be the number of friends (so Rami and his friends require $ K_k + 1 $ consecutive seats). - Let $ S_k \in \{0,1\}^{C_k} $ be a binary string representing seat availability: $ S_k[i] = 0 $ means empty, $ S_k[i] = 1 $ means taken. **Constraints** 1. $ 1 \le T \le 10^5 $ 2. For each $ k \in \{1, \dots, T\} $: - $ 1 \le C_k \le 10^5 $ - $ 1 \le K_k \le 10^5 $ - $ S_k $ has length $ C_k $, with each character in $ \{0,1\} $ **Objective** For each test case $ k $, determine if there exists a contiguous substring of $ S_k $ of length $ L_k = K_k + 1 $ such that all characters in the substring are $ 0 $. Output "yes" if such a substring exists, otherwise "no".

API Response (JSON)

{
  "problem": {
    "name": "H. Cinema",
    "description": {
      "content": "Rami and K of his friends are going to watch a movie tonight. There are only one row that contains some available seats, all other rows are taken. Given the description of this row, Rami wants to know",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10110H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Rami and K of his friends are going to watch a movie tonight. There are only one row that contains some available seats, all other rows are taken. Given the description of this row, Rami wants to know...",
      "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\\} $:  \n- Let $ C_k \\in \\mathbb{Z} $ be the number of seats in the row.  \n- Let $ K_k ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments