K. Deck Sorting

Codeforces

IDCF10221K

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have a deck of cards, lying on the table in front of you face up. The cards can be red, green and blue, and you know the order of cards in the deck. You want to sort the cards so that the cards of each color form a continuous segment. The order of colors doesn't matter. The table doesn't have much free space — only for two piles of cards. In one turn, you take a top card from the deck and put it onto the top of one of the piles, face up. After all cards are distributed to the piles, you take one of these piles and put it onto the top of the other pile, again, face up. Is it possible to sort the cards with the described procedure? The input contains a string of characters «_R_», «_G_» and «_B_». Its length is between $1$ and $1000$. The characters correspond to the colors of the cards in the deck, starting from the top one. Output «_YES_» or «_NO_», depending on if it's possible to sort the deck or not. In the first sample the deck is «_RGBRGB_» (starting from the top card). The 1st, the 4th and the 5th cards can be put to the first pile (it will be «_GRR_»), and the 2nd, the 3rd and the 6th cards can be put to the second pile (it will be «_BBG_»). After that the second pile can be put to the top of the first one, and the deck becomes sorted: «_BBGGRR_». ## Input The input contains a string of characters «_R_», «_G_» and «_B_». Its length is between $1$ and $1000$. The characters correspond to the colors of the cards in the deck, starting from the top one. ## Output Output «_YES_» or «_NO_», depending on if it's possible to sort the deck or not. [samples] ## Note In the first sample the deck is «_RGBRGB_» (starting from the top card). The 1st, the 4th and the 5th cards can be put to the first pile (it will be «_GRR_»), and the 2nd, the 3rd and the 6th cards can be put to the second pile (it will be «_BBG_»). After that the second pile can be put to the top of the first one, and the deck becomes sorted: «_BBGGRR_».

**Definitions** Let $ A, B \in \mathbb{Z}^+ $ be two positive integers. Let $ P \in \{0,1,\dots,9\}^* $ be a string representing $ A \times B $, with exactly one character replaced by `*` (denoting a missing non-zero digit). **Constraints** 1. $ 1 \leq A, B < 10^6 $ 2. $ 1 \leq |P| < 2 \times 10^6 $ 3. The missing digit is in $ \{1, 2, \dots, 9\} $ 4. $ A \times B $ has exactly $ |P| $ digits, with one digit replaced by `*`. **Objective** Find the unique digit $ d \in \{1, 2, \dots, 9\} $ such that replacing `*` in $ P $ with $ d $ yields the string representation of $ A \times B $.

API Response (JSON)

{
  "problem": {
    "name": "K. Deck Sorting",
    "description": {
      "content": "You have a deck of cards, lying on the table in front of you face up. The cards can be red, green and blue, and you know the order of cards in the deck. You want to sort the cards so that the cards of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10221K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a deck of cards, lying on the table in front of you face up. The cards can be red, green and blue, and you know the order of cards in the deck. You want to sort the cards so that the cards of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A, B \\in \\mathbb{Z}^+ $ be two positive integers.  \nLet $ P \\in \\{0,1,\\dots,9\\}^* $ be a string representing $ A \\times B $, with exactly one character replaced by `*` (denotin...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments