M. Kim Possible and the Mooks and the Reversinator

Codeforces

IDCF10253M

Time6000ms

Memory800MB

Difficulty—

English · Original

Formal · Original

Kim Possible has infiltrated Dr. Drakken's lair for the third time and has to fight off some MOOKS and MEEKS in order to stop him from his evil schemes. Like both previous times, Dr. Drakken knew Team Possible was coming for him as they always have. So he prepared a magical scientific device to strengthen his army of MOOKS and MEEKS. All the MOOKS and MEEKS form a straight line and Kim Possible has to fight them starting from the first one. The MEEKS don't fight because they are tired, but the MOOKS take Kim one minute to defeat. Whenever Kim Possible defeats a MOOK, the MOOK will use his McGuffin which drains all of his energy and throws Kim Possible back to the start of the line. All the MEEKS in front of the MOOK get re-energized and turn back into MOOKS with their McGuffin fully recharged, but the MOOK that used his McGuffin turns into a MEEK, fully drained of energy. This time however, the scientific genius Wade provided Kim Possible with a new device called the Reversinator. The Reversinator can reverse the order of a section of the line, but it can only be used once. To be precise, when the reversinator is used to reverse the section from the $i$th opponent to the $j$th opponent, $i$ and $j$ swap positions, $i + 1$ and $j -1$ swap positions, and so on. Given the initial line of MOOKS and MEEKS and the optimal use of the Reversinator, how many minutes will it take for Kim Possible to defeat all the MOOKS and turn them into MEEKS, assuming the Reversinator is used exactly once before Kim starts fighting? Since the answer may be very large, output the answer mod $10^9$. The first line of input contains $t$, the number of test cases. Each test case consists of a single line containing a string $s$ consisting of the letters _E_ and _O_. The $i$th character of $s$ is: *Constraints* We denote the length of $s$ by $| s |$. For each test case, output a single line containing a single integer denoting the answer for that test case modulo $10^9$. ## Input The first line of input contains $t$, the number of test cases. Each test case consists of a single line containing a string $s$ consisting of the letters _E_ and _O_. The $i$th character of $s$ is: _E_ if the $i$th opponent is a MEEK _O_ if the $i$th opponent is a MOOK *Constraints*We denote the length of $s$ by $| s |$. $1 <= t <= 35000$ $1 <= | s | <= 5 dot.op 10^5$. The sum of the $| s |$ across all test cases in a single file is $<= 5 dot.op 10^5$. ## Output For each test case, output a single line containing a single integer denoting the answer for that test case modulo $10^9$. [samples]

**Definitions** Let $ r, c \in \mathbb{Z}^+ $ denote the dimensions of the grid. Let $ (i, j) \in \{1, \dots, r\} \times \{1, \dots, c\} $ denote the starting position. **Constraints** 1. $ 1 \leq r, c \leq 100 $ 2. $ 1 \leq i \leq r $, $ 1 \leq j \leq c $ **Objective** Determine whether a Hamiltonian path exists on the $ r \times c $ grid starting at $ (i, j) $, visiting each cell exactly once. If such a path exists, output a sequence of moves (U, D, L, R) tracing it; otherwise, output "IMPOSSIBLE".

API Response (JSON)

{
  "problem": {
    "name": "M. Kim Possible and the Mooks and the Reversinator",
    "description": {
      "content": "Kim Possible has infiltrated Dr. Drakken's lair for the third time and has to fight off some MOOKS and MEEKS in order to stop him from his evil schemes. Like both previous times, Dr. Drakken knew Tea",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 819200
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10253M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Kim Possible has infiltrated Dr. Drakken's lair for the third time and has to fight off some MOOKS and MEEKS in order to stop him from his evil schemes.\n\nLike both previous times, Dr. Drakken knew Tea...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ r, c \\in \\mathbb{Z}^+ $ denote the dimensions of the grid.  \nLet $ (i, j) \\in \\{1, \\dots, r\\} \\times \\{1, \\dots, c\\} $ denote the starting position.  \n\n**Constraints**  \n1. $ 1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments