Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Кубик Рубика

(Время: 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

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

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



https://kaluga.masterzamkov.pro/vskryitie-avto