Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

Кубик Рубика

(Время: 3 сек. Память: 16 Мб Сложность: 67%)
Кубик Рубика

Кубик Рубика – популярная головоломка в форме куба, состоящая из множества мелких кубиков. Каждая видимая сторона такого кубика окрашена в определенный цвет. Повороты сторон кубика позволяют переупорядочить цветные квадраты множеством различных способов. Целью игры служит поиск последовательности поворотов сторон куба таким образом, чтобы он вернулся в первоначальное состояние, где каждая из граней состоит из квадратов одного цвета.

Доказано, что число всех достижимых различных состояний традиционного 6-цветного кубика Рубика 3×3×3 равно 43 252 003 274 489 856 000, а оптимальная последовательность ходов, необходимых для сборки кубика Рубика из любого состояния не превышает 20. Алгоритм, собирающий кубик Рубика за минимальное число ходов, традиционно называется «алгоритмом Бога», а 20 – числом Бога.

Рассмотрим более простую модель кубика Рубика 2×2×2, в которой используется всего 3 цвета: красный (R), синий (B) и зеленый (G). При этом противоположные грани окрашены в одинаковый цвет. Под ходом будем понимать вращение одной из граней на угол 90º. Поскольку всего 6 граней (передняя (F), левая (L), задняя (B), правая (R), верхняя (U) и нижняя (D)), то всего может быть 12 различных ходов (по часовой и против часовой стрелки для каждой грани). Ходы обозначаются буквами соответствующих граней, если ход происходит против часовой стрелки, то после буквы ставится апостроф (ASCII 39).

По заданной конфигурации трехцветного кубика Рубика 2×2×2 требуется найти оптимальный алгоритм (алгоритм Бога), решающий головоломку.

Входные данные

Входной файл INPUT.TXT содержит две строки, определяющие конфигурацию кубика Рубика. Первая строка содержит информацию о цветах верхнего слоя для каждой грани – пары символов, разделенные пробелом. Вторая строка аналогичным образом описывает нижние слои. Порядок граней (слева направо): передняя, левая, задняя, правая, верхняя, нижняя.

Выходные данные

В выходной файл OUTPUT.TXT выведите оптимальное решение головоломки для заданной конфигурации кубика Рубика. Если решений несколько, выведите любое. Если задана начальная конфигурация (кубик Рубика собран), то следует вывести «Solved».

Примеры

INPUT.TXTOUTPUT.TXT
1RR GG RR GG BB BB
RR GG RR GG BB BB
Solved
2RR BG GR GB GR BB
GG BR GR RB BB GR
F'R
3BR GR GR GR BB RR
BG RG RG BB GB BG
LULU'LB'DBR

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Все попытки] [Лучшие попытки]

 
     
Югорский НИИ ИТ, Югорский ФМЛ