A. A Blend of Springtime

Codeforces
IDCF989A
Time1000ms
Memory256MB
Difficulty
implementationstrings
English · Original
Chinese · Translation
Formal · Original
%epigraph%%epigraphtext% _When the curtains are opened, a canvas unfolds outside. Kanno marvels at all the blonde colours along the riverside — not tangerines, but blossoms instead."What a pity it's already late spring," sighs Mino with regret, "one more drizzling night and they'd be gone." "But these blends are at their best, aren't they?" Absorbed in the landscape, Kanno remains optimistic._%endepigraphtext%%endepigraph%The landscape can be expressed as a row of consecutive cells, each of which either contains a flower of colour amber or buff or canary yellow, or is empty. When a flower withers, it disappears from the cell that it originally belonged to, and it spreads petals of its colour in its two neighbouring cells (or outside the field if the cell is on the side of the landscape). In case petals fall outside the given cells, they simply become invisible. You are to help Kanno determine whether it's possible that after some (possibly none or all) flowers shed their petals, at least one of the cells contains all three colours, considering both petals and flowers. Note that flowers can wither in arbitrary order. ## Input The first and only line of input contains a non-empty string $s$ consisting of uppercase English letters '_A_', '_B_', '_C_' and characters '_._' (dots) only ($\lvert s \rvert \leq 100$) — denoting cells containing an amber flower, a buff one, a canary yellow one, and no flowers, respectively. ## Output Output "_Yes_" if it's possible that all three colours appear in some cell, and "_No_" otherwise. You can print each letter in any case (upper or lower). [samples] ## Note In the first example, the buff and canary yellow flowers can leave their petals in the central cell, blending all three colours in it. In the second example, it's impossible to satisfy the requirement because there is no way that amber and buff meet in any cell.
"真遗憾,春天已经快结束了," 米诺遗憾地叹气,"再下一场细雨,它们就都要消失了。" "但这些花此刻正美得极致,不是吗?" 看着这幅景色,kanno 依然充满希望。 这片景色可以表示为一排连续的格子,每个格子要么包含一朵琥珀色、buff色或金丝雀黄色的花,要么为空。 当一朵花凋谢时,它会从原本所在的格子消失,并向其两个相邻的格子(如果该格子位于景观边缘,则花瓣会飘到外界)散落与其颜色相同的花瓣。若花瓣飘出给定的格子范围,它们将直接变得不可见。 你需要帮助 Kanno 判断:是否可能在某些花(可能没有、也可能全部)凋谢后,至少有一个格子中同时出现全部三种颜色(包括花朵和花瓣)。注意,花朵可以按任意顺序凋谢。 输入的第一行且唯一一行包含一个非空字符串 $s$,仅由大写英文字母 '_A_'、'_B_'、'_C_' 和字符 '_._'(点)组成($lvert s rvert lt.eq 100$),分别表示包含琥珀色花、buff色花、金丝雀黄色花的格子,以及无花的格子。 如果存在某个格子可能同时包含全部三种颜色,则输出 "_Yes_",否则输出 "_No_"。 你可以以任意大小写形式输出每个字母。 在第一个示例中,buff 花和金丝雀黄色花可以将花瓣洒在中间的格子,使该格子融合全部三种颜色。 在第二个示例中,这是不可能满足要求的,因为琥珀色和 buff 色不可能在任何格子中相遇。 ## Input 输入的第一行且唯一一行包含一个非空字符串 $s$,仅由大写英文字母 '_A_'、'_B_'、'_C_' 和字符 '_._'(点)组成($lvert s rvert lt.eq 100$),分别表示包含琥珀色花、buff色花、金丝雀黄色花的格子,以及无花的格子。 ## Output 如果存在某个格子可能同时包含全部三种颜色,则输出 "_Yes_",否则输出 "_No_"。你可以以任意大小写形式输出每个字母。 [samples] ## Note 在第一个示例中,buff 花和金丝雀黄色花可以将花瓣洒在中间的格子,使该格子融合全部三种颜色。在第二个示例中,这是不可能满足要求的,因为琥珀色和 buff 色不可能在任何格子中相遇。
Let $ s $ be a string of length $ n $ over the alphabet $ \{ \texttt{A}, \texttt{B}, \texttt{C}, \texttt{.} \} $, where: - $ \texttt{A} $: cell contains an amber flower, - $ \texttt{B} $: cell contains a buff flower, - $ \texttt{C} $: cell contains a canary yellow flower, - $ \texttt{.} $: empty cell. Each flower at position $ i $ (0-indexed) can wither and spread petals of its color to its neighbors: positions $ i-1 $ and $ i+1 $, if they exist. Let $ C_i \subseteq \{ \texttt{A}, \texttt{B}, \texttt{C} \} $ denote the set of colors present in cell $ i $ after any subset of flowers have withered, where: - The original flower (if any) contributes its color. - Each neighboring flower that withers contributes its color. We are to determine: Does there exist an index $ i \in \{0, 1, \dots, n-1\} $ such that $ C_i = \{ \texttt{A}, \texttt{B}, \texttt{C} \} $? --- **Formal Condition:** There exists an index $ i \in [0, n-1] $ such that: $$ \{ \texttt{A}, \texttt{B}, \texttt{C} \} \subseteq \left( \{ s[i] \} \cup \{ s[i-1] \mid i-1 \geq 0 \} \cup \{ s[i+1] \mid i+1 < n \} \right) \setminus \{ \texttt{.} \} $$ Equivalently, define for each cell $ i $: $$ \text{Colors}(i) = \left\{ x \in \{ \texttt{A}, \texttt{B}, \texttt{C} \} \mid x = s[i] \text{ or } x = s[i-1] \text{ (if } i > 0\text{) or } x = s[i+1] \text{ (if } i < n-1\text{)} \right\} $$ Then output "Yes" if $ \exists i \in [0, n-1] $ such that $ \text{Colors}(i) = \{ \texttt{A}, \texttt{B}, \texttt{C} \} $, else "No". --- **Alternative Equivalent Formulation:** Let $ A, B, C \subseteq \{0, 1, \dots, n-1\} $ be the sets of indices where characters 'A', 'B', 'C' appear respectively. Then, for a cell $ i $ to contain all three colors, it must satisfy: - $ i \in A \cup (A-1) \cup (A+1) $, - $ i \in B \cup (B-1) \cup (B+1) $, - $ i \in C \cup (C-1) \cup (C+1) $, where $ S \pm 1 = \{ x \pm 1 \mid x \in S \} \cap [0, n-1] $. Thus, output "Yes" if: $$ \left( A \cup (A-1) \cup (A+1) \right) \cap \left( B \cup (B-1) \cup (B+1) \right) \cap \left( C \cup (C-1) \cup (C+1) \right) \neq \emptyset $$ Otherwise, output "No".
Samples
Input #1
.BAC.
Output #1
Yes
Input #2
AA..CB
Output #2
No
API Response (JSON)
{
  "problem": {
    "name": "A. A Blend of Springtime",
    "description": {
      "content": "%epigraph%%epigraphtext% _When the curtains are opened, a canvas unfolds outside. Kanno marvels at all the blonde colours along the riverside — not tangerines, but blossoms instead.\"What a pity it's a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF989A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "%epigraph%%epigraphtext% _When the curtains are opened, a canvas unfolds outside. Kanno marvels at all the blonde colours along the riverside — not tangerines, but blossoms instead.\"What a pity it's a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "\"真遗憾,春天已经快结束了,\" 米诺遗憾地叹气,\"再下一场细雨,它们就都要消失了。\"\n\n\"但这些花此刻正美得极致,不是吗?\" 看着这幅景色,kanno 依然充满希望。\n\n这片景色可以表示为一排连续的格子,每个格子要么包含一朵琥珀色、buff色或金丝雀黄色的花,要么为空。\n\n当一朵花凋谢时,它会从原本所在的格子消失,并向其两个相邻的格子(如果该格子位于景观边缘,则花瓣会飘到外界)散落与其颜色相同的花...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ s $ be a string of length $ n $ over the alphabet $ \\{ \\texttt{A}, \\texttt{B}, \\texttt{C}, \\texttt{.} \\} $, where:\n\n- $ \\texttt{A} $: cell contains an amber flower,  \n- $ \\texttt{B} $: cell cont...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments