H. Gas Stations

Codeforces

IDCF10160H

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block will go to the nearest block that has a gas station. The distance between two blocks i and j is |i - j|, where |x| is the absolute value of x. The government wants to move at most one station from its original block to another block. What is the maximum distance that a citizen has to cross to get to his/her nearest station, if the government operated in a way that minimizes this distance? The first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases. The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city. The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block. It is guaranteed that there’s at least one block that has a gas station. The total sum of n overall test cases doesn't exceed 5 × 106. For each test case, print the answer on a single line. ## Input The first line of input contains a single integer T (1 ≤ T ≤ 1200), the number of test cases.The first line of each test case contains a single integer n (1 ≤ n ≤ 105), the number of blocks in the city.The second line contains a string s of n characters, each character is either ‘+’, which represents a block with one gas station, or ‘.’ which represents a normal block.It is guaranteed that there’s at least one block that has a gas station.The total sum of n overall test cases doesn't exceed 5 × 106. ## Output For each test case, print the answer on a single line. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ denote the number of blocks. - Let $ s_k \in \{+,\ .\}^{n_k} $ be a string representing the city, where $ s_k[i] = '+' $ if block $ i $ has a gas station, and $ s_k[i] = '.' $ otherwise. - Let $ G_k = \{ i \in \{1, \dots, n_k\} \mid s_k[i] = '+' \} $ be the set of blocks with gas stations. **Constraints** 1. $ 1 \le T \le 1200 $ 2. $ 1 \le n_k \le 10^5 $ for each $ k $ 3. $ |G_k| \ge 1 $ for each $ k $ 4. $ \sum_{k=1}^T n_k \le 5 \times 10^6 $ **Objective** Let $ d(i) = \min_{g \in G_k} |i - g| $ be the distance from block $ i $ to its nearest gas station. Let $ D_k = \max_{i \in \{1, \dots, n_k\}} d(i) $ be the maximum distance any citizen must travel. The government may move **at most one** gas station from its current block to any other block (possibly empty), i.e., replace one element $ g \in G_k $ with some $ g' \in \{1, \dots, n_k\} \setminus G_k $, or leave $ G_k $ unchanged. Find the **minimum possible value of $ D_k $** after such a move.

API Response (JSON)

{
  "problem": {
    "name": "H. Gas Stations",
    "description": {
      "content": "The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block wi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10160H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The city of single direction consists of n blocks in a row, numbered from 1 to n from left to right. *All of them are populated by citizens*, and some of them has gas stations. People in each block wi...",
      "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 $ n_k \\in \\mathbb{Z} $ denote the number of blocks.  \n- Let $ s_k \\in \\{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments