Форум » Выполнение и анализ алгоритмов для исполнителей » Задание 14, номер 200 » Ответить

Задание 14, номер 200

Гость: Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось (222) заменить (222, 1) заменить (111, 2) КОНЕЦ ПОКА КОНЕЦ Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2019 двоек)? Не могу разобраться в этом задании. Где я ошибаюсь? Начало - встречаю три двойки, заменяю единицей. До конца строки единиц нет, замена трех единиц на двойку в начале строки. И так три раза подряд. Потом с начала строки замена трех двоек на единицу и трех единиц на двойку. Получается 121..1(2010)2..2(2010). Два цикла замена двоек и единиц приводит к строке 12221.11(2006)2..2(2004). Теперь замена трех двоек с начала строки, замена трех единиц. Получается 1121..1(2003)2..2(2004). Через пять циклов получается строка 121..1(1992)2..2(1992). Т.о. от 121..1(2010)2..2(2010) к 121..1(1992)2..2(1992) у нас поглощаются по 8 цифр. 2010/8 получаю 251 циклов + 2 цифры в остатке. Беру на один цикл меньше, т.е. по 10 цифр "1" и "2". Это строка 1211111111112222222222. Повторяю программу. Получается 112212.

Ответов - 18, стр: 1 2 All

polyakovss: Здравствуйте! При решении таких задач нужно прежде всего определить какого вида строка повторяется. В этой задаче будет повторяться не строка вида 1...12...2, а строка, которая получится после выполнения одного цикла, то есть строка вида 21...12...2. Первоначально в этой строке будет в начале её одна 2, затем 2017 единиц, а после них 2016 двоек. Добьемся того, чтобы этот вид строки вновь повторился. Количество "1" уменьшится на 6 и количество "2" после всех единиц уменьшится также на 6 (в начале строки будет еще одна "2"). 2017 mod 6 = 1, а 2016 mod 6 = 0. Так как 2016 mod 6 = 0, то нужно "вернуться на один шаг", то есть рассмотреть строку 21111111222222, где после "2" идет 1+6 единиц, а после них 6 "2". Применяя программу к строке 21111111222222, получим ответ 21. Ответ: 21.

Гость: Спасибо за ответ! Но мне не все понятно. "Первоначально в этой строке будет в начале её одна 2, затем 2017 единиц, а после них 2016 двоек." - это понятно. Потом 221...12...2, где единиц будет 2015, а двоек 2013. В следующем цикле 2221...12...2, где единиц 2013, а двоек 2010. Но потом читаем строку сначала и заменяем первые три двойки на единицу и последующие три единицы на двойку. Получаем 121...12...2 единиц и двоек по 2010 штук. Как "Добьемся того, чтобы вид строки 21...12...2 вновь повторился." у вас эта строка получилась?

Тим: *PRIVAT*


polyakovss: Можно сообразить, что поскольку должна получиться строка 21111111222222, в которой после одной "2" идут 7 "1", а затем 6 "2", то такой же ответ 21 будет для исходной строки вида (7+6k+2) "1" и (6+6k+3) "2", где k = 1, 2, 3, .... Минимальное количество "1" и "2" - 15. Но возьмем 21, чтобы было более понятно. 1) 111111111111111111111222222222222222222222 2) 21111111111111111111222222222222222222 ("2"+ (21-2) "1" + (21-3) "2") 3) 21111111111111111111222222222222222222 222111111111111111222222222222 ("222"+15 "1" + 12 "2"). Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. То есть 22211 заменяется на 2. Получится 21111111111111222222222222 ("2" + 13 "1" + 12 "2"). По сравнению со строкой в пункте 2 количество "1" уменьшилось на 6, количество "2" после них также уменьшилось на 6. 4) 21111111111111222222222222 222111111111222222 ("222" + 9 "1" + 6 "2"). Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. То есть 22211 заменяется на 2. Получится 21111111222222 ("2" + 7 "1" + 6 "2"). По сравнению со строкой в пункте 3 количество "1" снова уменьшилось на 6, количество "2" после них также снова уменьшилось на 6. 5) Применяя программу к этой строке, получим ответ 21. Обратите внимание, что под циклом здесь нужно понимать не цикл программы, а цикл приведения строки к прежнему виду 21...12...2. В этом разборе мы прошли такой цикл дважды - в пункте 3 и в пункте 4. Вы пишете: Но потом читаем строку сначала и заменяем первые три двойки на единицу и последующие три единицы на двойку. Это ошибка. Правильно так: читаем строку сначала и заменяем первые три двойки на единицу, а эту единицу и последующие две единицы заменяем на двойку, то есть 22211 заменяем на 2.

Гость: Доброе утро! Спасибо за ответ! "Теперь первые 222 заменяются на 1, а первые 111 (с учетом только что полученной "1") заменяются на 2. " - разве машина, прочитав первые три двойки, заменив их на 1 возвращается к началу строки? В моем понимании, в цикле должно быть последовательное прочтение: заменив три двойки на единицу, следующие три единицы машина меняет на двойку. Значит здесь я не права? Получается, что после каждой замены мы должны учитывать цифру, которую получили? И эта цифра будет считаться первой в прочтении?

polyakovss: Здравствуйте! В условии задачи сказано: Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w) нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Поэтому каждая команда "заменить" заменяет в строке первое слева вхождение цепочки v на цепочку w.

Гость: Спасибо! Теперь у меня пошло. 201 номер получился:)

Гость: Здравствуйте. Подскажите, пожалуйста. Почему из строки 2 1111111 222222 мы получаем 21? В условии задачи сначала стоит команда заменить(222,1) и только потом заменить(111,2). 21111111222222---2211111222---222111---12. Да, если сначала применить команду заменить(111,2), то получаем 21. Почему не влияет порядок команд в условии? Я никак не пойму.

polyakovss: Здравствуйте! Вы пишете: 21111111222222---2211111222---222111---12. Вы пишете: В условии задачи сначала стоит команда заменить(222,1) и только потом заменить(111,2). Верно. Поэтому 222111 --- 1111 1111 --- 21 Замечание При входе в цикл для строки 222111 условие "ПОКА нашлось (222)" выполняется. Поэтому последовательно в указанном у условии порядке выполняются ОБЕ команды заменить (222, 1) заменить (111, 2) уже без проверки нашлось ли (222).

cabanov.alexey: Потому что 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на шесть единиц и двоек меньше!) 336 раз вычитаем по шесть единиц и двоек, получим 111 222 ->21

Гость: Спасибо большое. С вами все понятно)

polyakovss: Здравствуйте, Алексей Михайлович! Вы пишете: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!) Для примера Вы рассмотрели строку 111 111 111 111 222 222 222 222. 1) Для этой строки в результате работы алгоритма будет получено 2211, а не 21. 2) Любое одинаковое количество "1" и "2" для примера в этой задаче брать нельзя. Посмотрите здесь (polyakovss Сообщение: 135) 2) В этой задаче нет повторения строки, в которой сначала все "1", а затем все "2". Посмотрите здесь (polyakovss Сообщение: 134) 3) Вы пишете: 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!) Нет. Цикл не закончился. В нем выполняется еще команда "заменить (111, 2)". Поэтому 22 111 111 11 222 222 -> 222 111 111 222 -> 21111222 4) Вы пишете: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 (стало на три единицы и двойки меньше!) Почему "стало на три единицы и двойки меньше!", если в Вашем варианте рассуждений их сначала было по 12, а осталось по 6?

cabanov.alexey: Пример нужен чтобы понять, сколько единиц и двоек будет убираться из строки. Распишу. Берём строку из 12 единиц и двоек (число произвольно). 1 итерация: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 2 итерация: 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 3 итерация: 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 Получили строку, подобную начальной! Но на 6 единиц и двоек меньше. Перенесёмся в оригинальный пример. По аналогии после 3 итераций будут пропадать по 6 единиц и двоек. Это будет продолжаться 2019:3=336.5 раз. Половинки не считаем, значит 336 раз, за которые пропадут 2016 цифр в каждой группе. В конце получим 111 222 -> 21.

polyakovss: Вы пишете: 1 итерация: 111 111 111 111 222 222 222 222 -> 2 111 111 111 1 222 222 222 2 итерация: 2 111 111 111 1 222 222 222 -> 2 2 111 111 1 1 222 222 3 итерация: 2 2 111 111 1 1 222 222 -> 2 2 2 111 1 1 222 222 -> 1 111 1 1 222 222 Так будет, если в цикле сначала выполняется команда "заменить (111, 2)", а затем команда "заменить (222, 1)". Но по условию: НАЧАЛО ПОКА нашлось (222) заменить (222, 1) заменить (111, 2) КОНЕЦ ПОКА КОНЕЦ Поэтому 3 итерация: 2 2 111 111 1 1 222 222 -> 2 2 111 111 111 222 -> 222 111 111 222 4 итерация: 222 111 111 222 -> 111 111 1 222 -> 2 111 1 222 Строка, подобная начальной, не повторяется! Повторяется строка вида 2 1...1 2...2. Замечание Если в цикле сначала выполняется команда "заменить (111, 2)", а затем команда "заменить (222, 1)", то в результате работы алгоритма получится 12, а вовсе не 21, хотя первые 3 итерации будут именно такими, как Вы указали, и количество "1" и "2" уменьшается на 6.

StupNum: гораздо более простое и лаконичное решение на питоне с выводом всех проходов алгоритма для подобной задачи [pre2] l=(2018*'1' + 2019*'2') k=0 while l.find('111') != -1: l=l.replace('111','2',1) l=l.replace('222','1',1) k+=1 print('Prohod #',k, ': ',l, '\n') print('OTVET: ',l)[/pre2]



полная версия страницы