F. black-white

Codeforces
IDCF10094F
Time2000ms
Memory64MB
Difficulty
English · Original
Formal · Original
Steven met his old friend Mikael yesterday and he told him about a very interesting game. The game board is made of N cells aligned in a row , and two colored stones in two different fixed positions of this row. The first stone is white, and the second is black. Steven plays with the white stone, and Mikael plays with the black one. The two players play alternately, Each player in his turn can move his stone one cell to the right or to the left, but he cannot move it outside the board or onto a cell occupied by the other player. Steven goes first. The player who cannot make any move loses. Steven and Mikael have become very good at playing this game, so they can know the winner of the game just by looking at the starting state of the board. Can you do the same? You are given the initial game board and you should know who is the winner of this match, considering both players playing optimally (if both players play optimally the game will end). The first line of input is an integer T which represents the number of test cases. Each of the next T lines consists three integers N , W , B , the length of the game board , the position of the white stone , the position of the black stone (2  ≤  N  ≤  100000) (1  ≤  B , W  ≤  N) For each test case, output a single line representing its answer; if Steven is the winner output _"Steven"_ (without quotes) otherwise _"Mikael"_ (without quotes). ## Input The first line of input is an integer T which represents the number of test cases. Each of the next T lines consists three integers N , W , B , the length of the game board , the position of the white stone , the position of the black stone (2  ≤  N  ≤  100000) (1  ≤  B , W  ≤  N) ## Output For each test case, output a single line representing its answer; if Steven is the winner output _"Steven"_ (without quotes) otherwise _"Mikael"_ (without quotes). [samples]
**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ N \in \mathbb{Z} $ be the board length, $ W \in \mathbb{Z} $ the position of the white stone, $ B \in \mathbb{Z} $ the position of the black stone, with $ 2 \leq N \leq 100000 $, $ 1 \leq W, B \leq N $, and $ W \neq B $. **Constraints** 1. $ 1 \leq T \leq \text{unspecified} $ 2. $ |W - B| \geq 2 $ (stones are not adjacent initially, since they occupy distinct cells and cannot overlap) **Objective** Define the gap between stones as $ d = |W - B| - 1 $. The game is an impartial two-player turn-based game on a line with two non-overlapping stones, where each player can move their stone one unit left or right without crossing the other stone or leaving the board. Steven (white) moves first. The outcome depends on the parity of the number of available moves in the symmetric game equivalent: Let $ g = d - 1 $. The game reduces to a variant of Kayles or a one-dimensional impartial game with two movable pieces constrained by each other. In optimal play, the winner is determined by the parity of the **number of free spaces between the stones**, i.e., $ d = |W - B| - 1 $. If $ d $ is odd → Steven wins. If $ d $ is even → Mikael wins. Thus, compute: $$ d = |W - B| - 1 $$ $$ \text{Winner} = \begin{cases} \text{Steven} & \text{if } d \equiv 1 \pmod{2} \\ \text{Mikael} & \text{if } d \equiv 0 \pmod{2} \end{cases} $$
API Response (JSON)
{
  "problem": {
    "name": "F. black-white",
    "description": {
      "content": "Steven met his old friend Mikael yesterday and he told him about a very interesting game. The game board is made of N cells aligned in a row , and two colored stones in two different fixed positions o",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10094F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Steven met his old friend Mikael yesterday and he told him about a very interesting game. The game board is made of N cells aligned in a row , and two colored stones in two different fixed positions o...",
      "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, let $ N \\in \\mathbb{Z} $ be the board length, $ W \\in \\mathbb{Z} $ the position of the white stone, $ B \\i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments