Форум » Выполнение и анализ алгоритмов для исполнителей » ЕГЭ-12 з.323 » Ответить
ЕГЭ-12 з.323
Коробко: Здравствуйте, можно хоть какую-нибудь подсказку, как можно в задаче 323 ЕГЭ-12 догадаться о начальной строке s = '2222' + 38*'1' + '32'*30 Спасибо.
Ответов - 1
Статный Дмитрий: Здравствуйте! Спасибо за оставленный вопрос. В данном случае необходимо немного проанализировать алгоритм и выяснить, какое расположение будет более выгодным. Например, - в скобках буду писать сумму цифр - 33 (6) -> 12 (3) — невыгодно; 11 (2) -> 32(5) — выгодно; 22 (4) -> 31 (4) — сумма неизменна. Выгодно или невыгодность заключается в том, что нам необходимо выбрать самый оптимальный способ, который увеличивает сумму цифр. Поэтому можно заметить, что первая замена самая лучшая для нас - будем пользоваться именно ей и придумывать строчку такой, чтобы комбинаций 11 было как можно больше. Можно ли сразу записать все 1-ки друг за другом? Получим строчку 1111...1111 (38шт) в результате работы алгоритма - 323232..323232 и заметим, что здесь не будет комбинаций 33 или 22, которые смогут повлиять на нашу сумму. Поэтому нас устраивает этот вариант и дальше необходимо максимально выгодно распределить оставшиеся цифры в строке. Ну а как это сделать? Нам необходимо избегать комбинаций 33 и 22, значит, будем ставить их либо как 23, либо как 32. Если ставить как 32, то необходимо после строки 111...11111, т.к после обработки строка с единицами будет оканчиваться на 2-ку, а начинаться на 3-ку, следовательно, впереди этой строки можно поставить только комбинации 23, а после нее - 32, чтобы избежать появления 22 или 33. А далее остаётся 4 двойки, которые нужно поставить таким же образом. А их уже выгодно поставить в начало строки, т.к если ставить после 323232...3232, то получим комбинации 22. И получаем строчку '2222' + '1'*38 + '32'*30.
полная версия страницы