L. SOS

Codeforces

IDCF10177L

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first. On each move, a player must fill an 'S' or 'O' into an empty cell. After the move, if there are 3 consecutive cells from left to right form the word "SOS", the player wins the game and the game finished. If the board gets filled up without SOS appearing consecutively, no one wins the game, the game end with draw. Now, if both Mr. Panda and Mr. Sheep play optimally, find out the result of the game. The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains one line consists of one number N, indicating the size of the game board. For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from 1) and _y_ is the game result if both players play optimally. "Panda" for Mr. Panda winning the game, "Sheep" for Mr. Sheep winning the game, "Draw" for draw game. In the first test case, as there are only 3 cells, both players cannot win as Mr. Sheep only has one move and after his move, there is still one cell left empty. So Mr. Sheep is impossible to win, but it's easy for him to avoid Mr. Panda to win. He can either fill 'O' in the first or third cell, or fill 'S' in the second cell to make it a draw game. ## Input The first line of the input gives the number of test cases, T. T test cases follow.Each test case contains one line consists of one number N, indicating the size of the game board. 1 ≤ T ≤ 1000. 1 ≤ N ≤ 1000. ## Output For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from 1) and _y_ is the game result if both players play optimally. "Panda" for Mr. Panda winning the game, "Sheep" for Mr. Sheep winning the game, "Draw" for draw game. [samples] ## Note In the first test case, as there are only 3 cells, both players cannot win as Mr. Sheep only has one move and after his move, there is still one cell left empty. So Mr. Sheep is impossible to win, but it's easy for him to avoid Mr. Panda to win. He can either fill 'O' in the first or third cell, or fill 'S' in the second cell to make it a draw game.

**Definitions** Let $ N \in \mathbb{Z}^+ $ denote the length of the $ 1 \times N $ game board. Let $ P $ denote the first player (Mr. Panda), and $ S $ denote the second player (Mr. Sheep). Players alternate turns, starting with $ P $. On each turn, a player places either 'S' or 'O' in an empty cell. A player wins immediately if, after their move, there exists a substring "SOS" in three consecutive cells. If all cells are filled without any "SOS" substring, the game ends in a draw. **Constraints** 1. $ 1 \leq T \leq 1000 $ 2. For each test case: $ 1 \leq N \leq 1000 $ **Objective** For each $ N $, determine the game outcome under optimal play: - "Panda" if Mr. Panda has a winning strategy, - "Sheep" if Mr. Sheep has a winning strategy, - "Draw" if neither can force a win.

API Response (JSON)

{
  "problem": {
    "name": "L. SOS",
    "description": {
      "content": "Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first. On each move, a player mus",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10177L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Panda and Mr. Sheep are playing a game on a 1 × N game board. Initially, all the cells are empty. Mr. Panda and Mr. Sheep take alternate moves and Mr.Panda moves first.\n\nOn each move, a player mus...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $ denote the length of the $ 1 \\times N $ game board.  \nLet $ P $ denote the first player (Mr. Panda), and $ S $ denote the second player (Mr. Sheep).  \nPlay...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments