A. Tritonic Iridescence

Codeforces

IDCF957A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas. Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yellow. On the one-dimensional canvas split into _n_ consecutive segments, each segment needs to be painted in one of the colours. Arkady has already painted some (possibly none or all) segments and passes the paintbrush to you. You are to determine whether there are at least two ways of colouring all the unpainted segments so that no two adjacent segments are of the same colour. Two ways are considered different if and only if a segment is painted in different colours in them. ## Input The first line contains a single positive integer _n_ (1 ≤ _n_ ≤ 100) — the length of the canvas. The second line contains a string _s_ of _n_ characters, the _i_\-th of which is either '_C_' (denoting a segment painted in cyan), '_M_' (denoting one painted in magenta), '_Y_' (one painted in yellow), or '_?_' (an unpainted one). ## Output If there are at least two different ways of painting, output "_Yes_"; otherwise output "_No_" (both without quotes). You can print each character in any case (upper or lower). [samples] ## Note For the first example, there are exactly two different ways of colouring: _CYCMY_ and _CYMCY_. For the second example, there are also exactly two different ways of colouring: _CMCMY_ and _CYCMY_. For the third example, there are four ways of colouring: _MCYCM_, _MCYCY_, _YCYCM_, and _YCYCY_. For the fourth example, no matter how the unpainted segments are coloured, the existing magenta segments will prevent the painting from satisfying the requirements. The similar is true for the fifth example.

在欣赏无数春日色彩的迷人融合时，画家阿尔卡迪铺开了一幅长长的画布。阿尔卡迪拥有足够多的三种颜色的颜料：青色、品红色和黄色。在一维的画布上，画布被划分为 #cf_span[n] 个连续的段，每个段需要被涂成其中一种颜色。阿尔卡迪已经涂了一些段（可能没有，也可能全部），并将画笔交给了你。你需要判断是否存在至少两种方式，将所有未涂色的段着色，使得任意两个相邻的段颜色不同。两种方式被认为是不同的，当且仅当至少有一个段在两种方式中被涂成不同颜色。第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——画布的长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，其中第 #cf_span[i] 个字符为 '_C_'（表示涂成青色）、'_M_'（表示涂成品红色）、'_Y_'（表示涂成黄色），或 '_?_'（表示未涂色）。如果存在至少两种不同的着色方式，请输出 "_Yes_"；否则输出 "_No_"（均不带引号）。你可以以任意大小写形式输出每个字符。对于第一个例子，恰好有两种不同的着色方式：_CYCMY_ 和 _CYMCY_。对于第二个例子，也恰好有两种不同的着色方式：_CMCMY_ 和 _CYCMY_。对于第三个例子，有四种着色方式：_MCYCM_、_MCYCY_、_YCYCM_ 和 _YCYCY_。对于第四个例子，无论未涂色的段如何着色，已有的品红色段都会阻止着色满足要求。第五个例子同理。 ## Input 第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）——画布的长度。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]，其中第 #cf_span[i] 个字符为 '_C_'（表示涂成青色）、'_M_'（表示涂成品红色）、'_Y_'（表示涂成黄色），或 '_?_'（表示未涂色）。 ## Output 如果存在至少两种不同的着色方式，请输出 "_Yes_"；否则输出 "_No_"（均不带引号）。你可以以任意大小写形式输出每个字符。 [samples] ## Note 对于第一个例子，恰好有两种不同的着色方式：_CYCMY_ 和 _CYMCY_。对于第二个例子，也恰好有两种不同的着色方式：_CMCMY_ 和 _CYCMY_。对于第三个例子，有四种着色方式：_MCYCM_、_MCYCY_、_YCYCM_ 和 _YCYCY_。对于第四个例子，无论未涂色的段如何着色，已有的品红色段都会阻止着色满足要求。第五个例子同理。

Given: - A sequence of $ n $ segments, each assigned a color from $\{C, M, Y\}$ or marked as unknown ($?$). - Constraint: No two adjacent segments may have the same color. - Some segments are pre-painted; others are unknown (denoted by $?$). Define: - Let $ s \in \{C, M, Y, ?\}^n $ be the input string. - Let $ A $ be the set of all valid colorings $ c \in \{C, M, Y\}^n $ such that: 1. $ c_i = s_i $ for all $ i $ where $ s_i \neq ? $, 2. $ c_i \neq c_{i+1} $ for all $ i = 1, 2, \dots, n-1 $. Objective: Determine whether $ |A| \geq 2 $. Output: - "Yes" if $ |A| \geq 2 $, - "No" otherwise.

Samples

Input #1

5
CY??Y

Output #1

Yes

Input #2

5
C?C?Y

Output #2

Yes

Input #3

5
?CYC?

Output #3

Yes

Input #4

5
C??MM

Output #4

No

Input #5

3
MMY

Output #5

No

API Response (JSON)

{
  "problem": {
    "name": "A. Tritonic Iridescence",
    "description": {
      "content": "Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas. Arkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yell",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF957A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Overlooking the captivating blend of myriads of vernal hues, Arkady the painter lays out a long, long canvas.\n\nArkady has a sufficiently large amount of paint of three colours: cyan, magenta, and yell...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在欣赏无数春日色彩的迷人融合时，画家阿尔卡迪铺开了一幅长长的画布。\n\n阿尔卡迪拥有足够多的三种颜色的颜料：青色、品红色和黄色。在一维的画布上，画布被划分为 #cf_span[n] 个连续的段，每个段需要被涂成其中一种颜色。\n\n阿尔卡迪已经涂了一些段（可能没有，也可能全部），并将画笔交给了你。你需要判断是否存在至少两种方式，将所有未涂色的段着色，使得任意两个相邻的段颜色不同。两种方式被认为是不同的，...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given:\n- A sequence of $ n $ segments, each assigned a color from $\\{C, M, Y\\}$ or marked as unknown ($?$).\n- Constraint: No two adjacent segments may have the same color.\n- Some segments are pre-pain...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments