Пару дней назад сидели с моим менеджером в Хуавее и делились задачами с собеседований в Meta, которые у нас были за жизнь (я тут недавно снова собесилась на стажировку в Meta, прошла техэтапы до team matching, но это SWE ML, а не совсем рисерч, поэтому, думаю, октажусь). Так вот, он задал мне задачку, которую ему дали на собесе на какую-то высокую reseach позицию. Я ее сходу решить не смогла, но решила потом (сегодня утром). Она показалась мне довольно красивой, поэтому давайте вам тоже расскажу Есть пять дверей [d_1, d_2, d_3, d_4, d_5] и один ключ. В каждый момент времени ключ находится за одной из дверей. Вы можете открыть любую дверь и посмотреть, есть ли там ключ. После того, как вы открываете дверь, ключ перемещается в дверь слева или справа от него. То есть, если он был в двери d_i, то перемещается в дверь d_{i-1} или d_{i+1} (но если ключ был в двери d_1, он может переместиться только в d_2, а если был в d_5, то только в d_4, т.е. двери не зациклены). После того, как ключ переместился, вы снова можете открыть дверь, и т.д.Вам на вход дается последовательность открывания дверей [o_1, o_2, ... o_n] произвольной длины. Можно ли по последовательность понять, гарантирует ли эта посоедовательность нахождение ключа при любых возможных начальных позициях и перемещениях ключа? Если да, то как это сделать и какова сложность алгоритма? Если нет, то докажите, что нельзя.От себя еще добавлю второй пункт: можно ли придумать последовательность [o_1, o_2, ... o_n] , которая гарантирует нахождение ключа? Если да, то докажите, что она всегда находит ключ, и предложите ее устройство. Если нет, то докажите, что это невозможно(Мой менеджер ее, кстати, не решил, и вообще верил, что она в таком виде нерешаемая и с условием что-то не так)
