E. Potent Plants

Codeforces

IDCF10253E

Time3000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Some agents attack with knives, others use only their bare fists. Several use guns of some sort, from small pistols to long range rifles. Then there are those who use very flashy explosions. You smirk to yourself as you think of those guys. "They could hardly call themselves Agents of Covert Missions." As for you, you pride yourself in using herbs—special plants that you grow yourself. These plants of yours produce potent leaves which could be turned into powder and pills for different uses: causing paralysis, inducing sleep, and extracting the truth from people. Unfortunately, the Center for Interior Architecture wasn't that meticulous when designing your headquarters. You have many plants of differing weights, but the area where you are growing your plants can only handle up to a maximum weight $w$. Will you be able to grow all of your plants? The first line of input contains a single integer $t$ denoting the number of test cases. Each test case is on one line, starting with an integer $w$ as described above, then a string $S$ representing your collection of plants. Each plant is represented by an uppercase letter, from "_A_" to "_Z_". Plants denoted by "_A_" are of weight $1$, "_B_" of weight $2$, and so on until "_Z_" with weight $26$. *Constraints* For each test case, print a line stating if you could grow all the plants. Output only "_YES_" or "_NO_" (without the quotes). ## Input The first line of input contains a single integer $t$ denoting the number of test cases. Each test case is on one line, starting with an integer $w$ as described above, then a string $S$ representing your collection of plants.Each plant is represented by an uppercase letter, from "_A_" to "_Z_". Plants denoted by "_A_" are of weight $1$, "_B_" of weight $2$, and so on until "_Z_" with weight $26$.*Constraints* $1 <= t <= 10^5$ $0 <= w <= 10^9$ $1 <= | S | <= 10^6$ Sum of $| S |$ in all cases will not exceed $10^6$ $S$ is composed of uppercase English characters ## Output For each test case, print a line stating if you could grow all the plants. Output only "_YES_" or "_NO_" (without the quotes). [samples]

**Definitions** Let $ r, c, k \in \mathbb{Z}^+ $ denote the grid dimensions and maximum allowed open doors. Let $ G = (V, E) $ be a grid graph of size $ r \times c $, where each cell $ (i,j) \in \{1,\dots,r\} \times \{1,\dots,c\} $ is a vertex. Each cell is labeled: - $ \texttt{\#} $: wall (impassable), - $ \texttt{.} $: empty space (passable), - $ \texttt{D} $: door (passable only if open). Let $ s = (s_i, s_j) \in V $ be the agent’s entry cell, and $ t = (t_i, t_j) \in V $ be the bomb location, both guaranteed to be non-wall cells. Let $ O \subseteq \{ \text{door cells} \} $ be the set of open doors, with $ |O| \leq k $. **Constraints** 1. $ 1 \leq r, c \leq 50 $, $ 0 \leq k \leq 10 $ 2. $ s $ and $ t $ are not walls. 3. The agent may move to an adjacent cell if it is an empty space or an open door (cost = 1 second). 4. The agent may toggle the state of any adjacent door (open ↔ closed) at cost = 1 second. 5. At all times, the number of open doors $ |O| \leq k $. **Objective** Determine the minimum time required for the agent to reach $ t $ from $ s $, under the above movement and door-toggle rules, or report that it is impossible.

API Response (JSON)

{
  "problem": {
    "name": "E. Potent Plants",
    "description": {
      "content": "Some agents attack with knives, others use only their bare fists. Several use guns of some sort, from small pistols to long range rifles. Then there are those who use very flashy explosions. You smir",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10253E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Some agents attack with knives, others use only their bare fists. Several use guns of some sort, from small pistols to long range rifles. Then there are those who use very flashy explosions.\n\nYou smir...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ r, c, k \\in \\mathbb{Z}^+ $ denote the grid dimensions and maximum allowed open doors.  \nLet $ G = (V, E) $ be a grid graph of size $ r \\times c $, where each cell $ (i,j) \\in \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments