Для начала заметим, что порядок нажатия кнопок значения не имеет из-за ассоциативности операции «логическое или», поэтому достаточно выбирать только множество кнопок, на которые Майлзу нужно нажать.
Для решения первой подзадачи как раз достаточно перебрать это самое множество кнопок за $$$O(2^n)$$$.
Для решения второй подзадачи требовалось реализовать более эффективный алгоритм. Таким, например, мог стать поиск в ширину по неявному графу параллельных вселенных: находясь в какой-то текущей вселенной $$$x$$$, попробуем нажать каждую из кнопок $$$a_i$$$ и добавим число $$$x \lor a_i$$$ в очередь состояний. Такое решение в худшем случае работает за $$$O(\max(a) \cdot n)$$$.
Для решения задачи на полный балл требовалось решать задачу отдельно по битам. Для этого можно было использовать следующие утверждения:
Используя утверждения, написанные выше, можно было разработать следующий алгоритм:
Логично, что тогда мы сделаем не больше $$$100$$$ (даже не больше $$$30$$$) перемещений, а также доберемся до вселенной с номером $$$b$$$, если это вообще возможно.