Форум » Выполнение и анализ алгоритмов для исполнителей » Задача 6416 неправильный ответ » Ответить
Задача 6416 неправильный ответ
1llumi: Ответ на сайте: 70 Правильный: 63 Строка: 0222222122111222121112212121122221112212212122212212222222222112211222222222112112211122111112212211211211211211112111122112211211212222121212220
Ответов - 7
Marigood: Если не подбирать расположение цифр в строке, а взять исходную строку s = '0' + '2' * 80 + '1' * n + '0', то получается сумма 223 при n=65.
Ж: Заметим, что при выполнении оперций: заменить (02, 101) - сумма цифр не меняется заменить (11, 2) - сумма цифр не меняется заменить (012, 30) - сумма цифр не меняется заменить (010, 00) - сумма цифр уменьшается на 1, причем 1 раз, т.к. после этой замены появляются 00 и программа завершается Исходная сумма цифр строки 2*80+1*60+еще чуток (единиц больше 60) - итого сумма была >=220 220 не простое 221 не простое 222 - не простое 223 - ПРОСТОЕ!! --> единиц не меньше 63 Это оценка - меньше, чем 63 единицы быть не может, а пример с 63 единицами показан выше.
Поляков: Спасибо, ответ и решение исправлены.
borisbot: Добрый день! Верный ответ на самом деле 64!!! Если обращаться к сообщению от 12.06.23 можно заметить ошибку в рассуждениях. А конкретно: В условии задания нас просят указать ИСХОДНОЕ количество единиц. Сумма цифр числа, которая в конце окажется простым числом - 223. Данное число мы получаем после того, как вычтем из 224 единицу. Таким образом сумма двоек в исходном числе составляет 160, а сумма единиц 64 соответственно. Спасибо!
Ж: Не думаю, что я ошиблась в ответе. ( а рассуждения я немного поправила) Исходная сумма цифр строки 2*80+1*60+еще чуток (единиц больше 60) - итого сумма была >=220. Первое простое число после 220 включительно - 223 --> единиц было не менее 63 (2*80+63=223) Вот код, который при исходной строке с 63 единицами, удовлетворяющей условию задачи, выдает в конце строку сумма цифр которой равна 223 [pre2] s='0222222122111222121112212121122221112212212122212212222222222112211222222222112112211122111112212211211211211211112111122112211211212222121212220' print(s.count('1')) print(s.count('2')) print(s.count('0')) while '00' not in s: s=s.replace('02','101',1) s = s.replace('11', '2', 1) s = s.replace('012', '30', 1) s = s.replace('010', '00', 1) print(sum(int(c) for c in s)) [/pre2]
gutgut: Процитирую сначала участника с ником Ж: "Заметим, что при выполнении операций: заменить (02, 101) - сумма цифр не меняется заменить (11, 2) - сумма цифр не меняется заменить (012, 30) - сумма цифр не меняется заменить (010, 00) - сумма цифр уменьшается на 1, причем 1 раз, т.к. после этой замены появляются 00 и программа завершается" Но тогда возникает резонный вопрос: раз сумма цифр исходной строки уменьшается на 1, то в ней должно быть не 63, а 64 единицы? Подвох здесь в том, что завершающая комбинации из двух нулей может получиться (и на самом деле получается для строки, предложенной в качестве решения) после замены 012 на 30, так как 30 плюс последний 0 даст 300 и алгоритм завершится без вычитания единицы! Для проверки моего предположения я написал программу для строки из сообщения 1llumi, отключив в программе последнюю замену. Программа вывела сумму цифр строки-результата 223. Так что правильный ответ 63, только как его получить?
Ж: Согласна с Подвох здесь в том, что завершающая комбинации из двух нулей может получиться (и на самом деле получается для строки, предложенной в качестве решения) после замены 012 на 30, так как 30 плюс последний 0 даст 300 и алгоритм завершится без вычитания единицы! В конце строки как раз и стоит двойка (я не заметила этот момент). Пример подходящей строки и код остаются те же. [pre2] s = '0222222122111222121112212121122221112212212122212212222222222112211222222222112112211122111112212211211211211211112111122112211211212222121212220' print(s.count('1')) print(s.count('2')) print(s.count('0')) while '00' not in s: s = s.replace('02', '101', 1) s = s.replace('11', '2', 1) s = s.replace('012', '30', 1) # s = s.replace('010', '00', 1) print(sum(int(c) for c in s)) [/pre2]
полная версия страницы