C. Solution for Cube

Codeforces
IDCF887C
Time2000ms
Memory256MB
Difficulty
brute forceimplementation
English · Original
Chinese · Translation
Formal · Original
During the breaks between competitions, top-model Izabella tries to develop herself and not to be bored. For example, now she tries to solve Rubik's cube 2x2x2. It's too hard to learn to solve Rubik's cube instantly, so she learns to understand if it's possible to solve the cube in some state using 90-degrees rotation of one face of the cube in any direction. To check her answers she wants to use a program which will for some state of cube tell if it's possible to solve it using one rotation, described above. Cube is called solved if for each face of cube all squares on it has the same color. https://en.wikipedia.org/wiki/Rubik's_Cube ## Input In first line given a sequence of 24 integers _a__i_ (1 ≤ _a__i_ ≤ 6), where _a__i_ denotes color of _i_\-th square. There are exactly 4 occurrences of all colors in this sequence. ## Output Print «_YES_» (without quotes) if it's possible to solve cube using one rotation and «_NO_» (without quotes) otherwise. [samples] ## Note In first test case cube looks like this: <center>![image](https://espresso.codeforces.com/bc1250d14845df6e78946bdc2afac10793ba28e5.png)</center>In second test case cube looks like this: <center>![image](https://espresso.codeforces.com/d7d1089a7e87327730903d379853d7195207df16.png)</center>It's possible to solve cube by rotating face with squares with numbers 13, 14, 15, 16.
在比赛间隙,顶级模特 Izabella 试图提升自己而不至于无聊。例如,现在她尝试解决 2x2x2 魔方。 直接学习如何瞬间还原魔方太难了,因此她学习如何判断在某个状态下,是否可以通过一次 90 度旋转某个面(任意方向)来还原魔方。 为了验证她的答案,她希望使用一个程序,该程序能对魔方的某种状态判断是否可以通过上述的一次旋转来还原。 魔方被称为已还原,当且仅当魔方的每个面上的所有小方块颜色都相同。 https://en.wikipedia.org/wiki/Rubik's_Cube 第一行给出一个包含 24 个整数的序列 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 6]),其中 #cf_span[ai] 表示第 #cf_span[i] 个小方块的颜色。该序列中每种颜色恰好出现 4 次。 如果可以通过一次旋转还原魔方,请输出 «_YES_»(不含引号),否则输出 «_NO_»(不含引号)。 在第一个测试用例中,魔方看起来像这样: 在第二个测试用例中,魔方看起来像这样: 可以通过旋转包含编号为 13、14、15、16 的小方块的面来还原魔方。 ## Input 第一行给出一个包含 24 个整数的序列 #cf_span[ai] (#cf_span[1 ≤ ai ≤ 6]),其中 #cf_span[ai] 表示第 #cf_span[i] 个小方块的颜色。该序列中每种颜色恰好出现 4 次。 ## Output 如果可以通过一次旋转还原魔方,请输出 «_YES_»(不含引号),否则输出 «_NO_»(不含引号)。 [samples] ## Note 在第一个测试用例中,魔方看起来像这样: 在第二个测试用例中,魔方看起来像这样: 可以通过旋转包含编号为 13、14、15、16 的小方块的面来还原魔方。
Let the cube state be represented as a vector $ \mathbf{c} = (c_1, c_2, \dots, c_{24}) $, where each $ c_i \in \{1,2,3,4,5,6\} $, and each color appears exactly four times. The cube has six faces, each consisting of four squares. Define the face index sets: - Front: $ F = \{1,2,3,4\} $ - Back: $ B = \{5,6,7,8\} $ - Up: $ U = \{9,10,11,12\} $ - Down: $ D = \{13,14,15,16\} $ - Left: $ L = \{17,18,19,20\} $ - Right: $ R = \{21,22,23,24\} $ A face is **solved** if all four of its squares have the same color. The cube is **solved** if all six faces are solved. Define the set $ \mathcal{R} $ of all possible single 90° rotations (clockwise or counterclockwise) of any one face. There are 6 faces × 2 directions = 12 possible moves. For each rotation $ r \in \mathcal{R} $, let $ \text{apply}(r, \mathbf{c}) $ denote the resulting cube state after applying rotation $ r $ to state $ \mathbf{c} $. **Objective:** Determine whether there exists a rotation $ r \in \mathcal{R} $ such that $ \text{apply}(r, \mathbf{c}) $ is a solved cube. Equivalently: > Does there exist $ r \in \mathcal{R} $ such that for every face $ f \in \{F,B,U,D,L,R\} $, all elements in $ \text{apply}(r, \mathbf{c})|_f $ are equal? Output "YES" if such $ r $ exists; otherwise, output "NO".
Samples
Input #1
2 5 4 6 1 3 6 2 5 5 1 2 3 5 3 1 1 2 4 6 6 4 3 4
Output #1
NO
Input #2
5 3 5 3 2 5 2 5 6 2 6 2 4 4 4 4 1 1 1 1 6 3 6 3
Output #2
YES
API Response (JSON)
{
  "problem": {
    "name": "C. Solution for Cube",
    "description": {
      "content": "During the breaks between competitions, top-model Izabella tries to develop herself and not to be bored. For example, now she tries to solve Rubik's cube 2x2x2. It's too hard to learn to solve Rubik'",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF887C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "During the breaks between competitions, top-model Izabella tries to develop herself and not to be bored. For example, now she tries to solve Rubik's cube 2x2x2.\n\nIt's too hard to learn to solve Rubik'...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在比赛间隙,顶级模特 Izabella 试图提升自己而不至于无聊。例如,现在她尝试解决 2x2x2 魔方。\n\n直接学习如何瞬间还原魔方太难了,因此她学习如何判断在某个状态下,是否可以通过一次 90 度旋转某个面(任意方向)来还原魔方。\n\n为了验证她的答案,她希望使用一个程序,该程序能对魔方的某种状态判断是否可以通过上述的一次旋转来还原。\n\n魔方被称为已还原,当且仅当魔方的每个面上的所有小方块颜色都...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let the cube state be represented as a vector $ \\mathbf{c} = (c_1, c_2, \\dots, c_{24}) $, where each $ c_i \\in \\{1,2,3,4,5,6\\} $, and each color appears exactly four times.\n\nThe cube has six faces, ea...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments