I. A Movie in Byteland

Codeforces

IDCF10191I

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

There are two ways of reading names in Byteland. Either from left to right, or from right to left. For example, if a person called "mike" went to Byteland, the citizens might call him "mike" or "ekim". Feras is the Casting Director for a new movie. There are N actors in Byteland, and he has to choose some of them to act in the new movie. Feras knows that all of the actors are good, so he is only worried about what order he is going to use in the list of chosen actors. An actor i would be disappointed if another actor j was listed before him, while actor i has a lexicographically smaller name in any of the two ways mentioned above. In other words, he will be disappointed if actor j was listed before actor i in the *final list and* siltr < sjltr or sirtl < sjrtl. siltr is the name of actor i written from left to right. sirtl is the name of actor j written from right to left. Feras wants to choose the maximum number of actors possible such that there exists a way to order them so that none of them would be disappointed. In addition, he wants that in each pair of consecutive names on the list, exactly one of them contains the letter "m" . (His crush's name has too many letters "m" and he wants to remember her while producing the movie) The first line contains an integer T, the number of test cases. The first line of each test contains the number of actors N. (1 ≤ N ≤ 105) Then N lines follow, the ith line contains the name of the ith actor written from left to right, the name consists of lowercase english letters. (1 ≤ |si| ≤ 105). It's guaranteed that the sum of the lengths of all the names in each test case will not exceed 106 For each test print one line containing one integer, the maximum possible number of actors Feras can choose while keeping him and all the chosen actors happy. Large I/O files. Please consider using fast input/output methods. ## Input The first line contains an integer T, the number of test cases. The first line of each test contains the number of actors N. (1 ≤ N ≤ 105) Then N lines follow, the ith line contains the name of the ith actor written from left to right, the name consists of lowercase english letters. (1 ≤ |si| ≤ 105). It's guaranteed that the sum of the lengths of all the names in each test case will not exceed 106 ## Output For each test print one line containing one integer, the maximum possible number of actors Feras can choose while keeping him and all the chosen actors happy. [samples] ## Note Large I/O files. Please consider using fast input/output methods.

**Definitions** Let $ n, m, s \in \mathbb{Z} $ with $ 1 \leq n, m \leq 2000 $, $ 1 \leq s \leq 10^{10} $. Let $ B = \{(x_i, y_i) \mid i \in \{1, \dots, n\}\} $ be the set of beagle starting positions. Let $ W = \{(x_j, y_j, w_j) \mid j \in \{1, \dots, m\}\} $ be the set of water bowls, where $ w_j \in \mathbb{Z} $, $ 1 \leq w_j \leq 100 $, is the water volume at bowl $ j $. **Constraints** 1. Each beagle must drink exactly 1 liter of water. 2. Time to travel from point $ (x_1, y_1) $ to $ (x_2, y_2) $ is $ |x_1 - x_2| + |y_1 - y_2| $ seconds (Manhattan distance). 3. Time to drink 1 liter of water is 10 seconds. 4. Total time per beagle (travel + drinking) must be $ \leq s $ seconds. 5. Each water bowl $ j $ can supply at most $ w_j $ liters (i.e., be assigned to at most $ w_j $ beagles). 6. Each beagle must be assigned to exactly one water bowl. 7. Each water bowl can be assigned to multiple beagles, up to its capacity $ w_j $. **Objective** Determine whether there exists a valid assignment of $ n $ beagles to $ m $ water bowls such that: - Each beagle $ i $ is assigned to some bowl $ j $, - $ \text{distance}((x_i, y_i), (x_j, y_j)) + 10 \leq s $, - The number of beagles assigned to bowl $ j $ does not exceed $ w_j $. Output "YES" if such an assignment exists; otherwise, output "NO".

API Response (JSON)

{
  "problem": {
    "name": "I. A Movie in Byteland",
    "description": {
      "content": "There are two ways of reading names in Byteland. Either from left to right, or from right to left. For example, if a person called \"mike\" went to Byteland, the citizens might call him \"mike\" or \"ekim\"",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10191I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are two ways of reading names in Byteland. Either from left to right, or from right to left. For example, if a person called \"mike\" went to Byteland, the citizens might call him \"mike\" or \"ekim\"...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m, s \\in \\mathbb{Z} $ with $ 1 \\leq n, m \\leq 2000 $, $ 1 \\leq s \\leq 10^{10} $.  \nLet $ B = \\{(x_i, y_i) \\mid i \\in \\{1, \\dots, n\\}\\} $ be the set of beagle starting positi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments