Сможете получить MU из MI, используя 4 правила?
У вас есть 4 правила для преобразования строк. Сможете ли вы превратить MI в MU, не нарушая их?
5К открытий5К показов
У вас есть строка MI. Выясните, можно ли получить из неё строку MU, используя только следующие правила:
- Если строка заканчивается на I, можно добавить в конец U. Пример: MI -> MIU.
- Можно удвоить часть строки после M, то есть изменить Mx на Mxx. Пример: MIU -> MIUIU.
- Можно заменить III на U. Пример: MUIIIU -> MUUU.
- Можно удалить UU. Пример: MUUU -> MU.
Ответ
Нельзя.
Почему?
Если проанализировать правила, легко заметить, что у нас может быть всего одна M, которая уже есть в исходной строке. Это важно для понимания второго правила.
Теперь возьмём n — количество повторений I в строке. Для начальной строки MI n = 1, что не делится на 3. Только второе и третье правило могут изменять n, удваивая её или уменьшая на 3. Никакая из этих операций не может дать нам n, которая делится на 3 без остатка, если n не делилась на 3 до преобразований. Нам нужно получить строку MU, где n = 0 и как следствие делится на 3. Эта строка не может быть получена из MI, где n = 1 и не делится на 3.
5К открытий5К показов
Собрали самые каверзные задачи на тему программирования по Go, C# и QA, которые удивили инженеров Ozon Tech, и делимся решениями.
Собрали несколько математических задач высокого уровня сложности и добавили варианты решения на Python.
Математика и компьютерные науки идут рука об руку. Подобрали 7 математических формул разного уровня сложности для проверки — сможете ли вы их реализовать? И на всякий случай снабдили статью нашими решениями.
Собрали каверзные логические задачи с собеседований для SDE. Они кажутся сложными, но на деле довольно простые. Испытайте себя!