Форум » Выполнение и анализ алгоритмов для исполнителей » задача 6415 неправильный ответ » Ответить
задача 6415 неправильный ответ
1llumi: Ответ на сайте: 54 Правильный ответ: 45 строка: 0211211112221121111211111111112111111112121211211111111221112111212122112111112112111121111211111111222221112111122212111111111212111211222111121211111111111111211211210
Ответов - 3
Поляков: Спасибо, ответ исправлен.
YNK: Ответ 54 тоже актуален, но при условии неубывания чисел в исходной строке (за исключением последнего нуля.) 1llumi Кстати очень интересно было бы посмотреть ваше решение. Я, используя Python, навскидку вижу решение только через permutations, но это съедает слишком много времени и памяти... Если вы использовали решение по ссылкеЗадача 6415. Источник: Поляков., то там перебираются не все варианты входящих строк...
Ж: Здесь есть аналитическое решение: Сумма цифр строки не меняется при всех преобразованиях, кроме последнего. Оно же может быть выполнено максимум 1 раз. Значит исходная сумма цифр строки (122*1+40*2+х*2 = 202+х*2) сохранится или уменьшится на 1. Минимальное простое число большее 202 - 211. Получить его можно из суммы 212. Значит двоек было минимум 40+5 = 45 Теперь надо только привести пример такой строки: 11111(121 единица)2222(45 двоек)010 (не проверяла, но думаю, подойдет)
полная версия страницы