#программирование
РАЗВЁРТКИ КУБОВ (МИСиС, 1984)
Даны две развертки кубов, на гранях которых записаны натуральные числа.
Определить, относятся ли эти развертки к одному и тому же кубу.
+++
Мой комментарий:
для начала договоримся и уточним, что на развертках указаны ОДНИ И ТЕ ЖЕ ЧИСЛА, скажем от 1 до 6 (на нашей картинке это не так 😉). Иначе, на мой взгляд, вообще затруднительно анализировать.
АЛГОРИТМ РЕШЕНИЯ
(код обсудим отдельно, я делал на R)
Понятно, что речь о том, что эквивалентные кубики должны переходить друг в друга посредством какой-то (!) комбинации поворотов, и нам надо придумать, как организовать эти повороты, чтобы не крутить кубики случайно и хаотично.
(Кстати, понятно, что живые кубики, будь они у нас в руках, мы бы крутили именно случайно и хаотично 😂, но на самом деле это не совсем так - человек, причем как обычный человек так и математик - мыслит адаптивно, и наше верчение включало бы постепенное подмечание каких-то закономерностей.
Это интереснейший когнитивный процесс, но совершенно ясно, что задачка по программированию, даже олимпиадная, не может и не должна его воспроизводить, это слишком сложно. Для современного ИИ, может, уже и не так сложно, но это совсем другая история. Нам нужно решение достаточно простое для реализации школьником.)
___
Решение разбивается на 3 этапа.
1. Найдем единицу ("1") на 1-м кубике и на на 2-м. Посмотрим, что находится на ПРОТИВОПОЛОЖНОЙ грани (как у 1-го, так и 2-го кубика). Ясно, что это должно быть одно и то же число. Если это не так, то ДАВАЙ ДО СВИДАНЬЯ - кубики (точнее, их развертки) НЕ ИДЕНТИЧНЫ. Все определилось достаточно быстро.
2. Если же напротив "1" в обоих кубиках стоит одно и то же число (пусть условно это "2"), то есть основания НАДЕЯТЬСЯ, что развёртки МОГУТ оказаться эквивалентными. Только могут, и это надо проверить. Для этого сначала повернем каждый кубик так, что "1" оказалось НА ВЕРХНЕЙ ГРАНИ. Очевидно, при этом у каждого кубика теперь "2" оказалось на нижней грани.
3. Теперь все совсем просто - выходим на финишную прямую. Нам надо проверить, что остальные числа (кроме "1" и "2") в обоих кубиках находятся на идентичных местах. Ясно что эти числа (в нашем примере это "3", "4", "5" и "6") в обоих кубиках находятся на боковых гранях, но они могут быть упорядочены по-разному.
У нас сейчас есть одна выделенная ось вращения кубика, проходящая через верхнюю и нижнюю грани. Легко видеть, что нам требуется не более 4-х поворотов на 90* (в любую но одну сторону - хоть по часовой стрелке, хоть против), чтобы обнаружить полное совпадение боковых граней - либо убедиться в его отсутствии.