Форум » Выполнение и анализ алгоритмов для исполнителей » Задача 255, задание 12 » Ответить
Задача 255, задание 12
check8386: "(Джобс) ... Дана программа для Редактора: ПОКА НЕ нашлось (><) заменить(>1, 3>) заменить(>2, 2>) заменить(>3, 1>) заменить(3<, <1) заменить(2<, <3) заменить(1<, <2) КОНЕЦ ПОКА На вход приведённой ниже программе поступает строка, начинающаяся с символа «>», затем содержащая 20 цифр 1, 15 цифр 2 и 40 цифр 3, расположенных в произвольном порядке и оканчивающаяся символом «<». Определите максимальную возможную сумму числовых значений цифр строки, получившейся в результате выполнения программы. Так, например, если результат работы программы представлял бы собой строку, состоящую из 50 цифр 4, то верным ответом было бы число 200." Во-первых, программа приведена не ниже, а выше. Во-вторых, результат выполнения программы зависит только от порядка следования цифр во входной строке, иначе программа всегда выдавала бы одинаковый результат. Не лучше ли переформулировать условие примерно так: На вход программе поступает строка, начинающаяся с символа «>», содержащая 20 цифр 1, 15 цифр 2, 40 цифр 3 и оканчивающаяся символом «<». В каком порядке должны располагаться цифры во входной строке, чтобы сумма цифр, получившаяся в результате выполнения программы, была максимально возможной? В ответе запишите эту максимально возможную сумму.
Ответов - 6
Поляков: check8386 пишет: На вход программе поступает строка, начинающаяся с символа «>», содержащая 20 цифр 1, 15 цифр 2, 40 цифр 3 и оканчивающаяся символом «<». В каком порядке должны располагаться цифры во входной строке, чтобы сумма цифр, получившаяся в результате выполнения программы, была максимально возможной? В ответе запишите эту максимально возможную сумму. Да, спасибо, так лучше. Поправил.
Вилена: Коллеги, как вы получаете ответ 145? можно узнать ваш секрет?
EugeneJobs: Для начала надо исследовать различные конфигурации строк. Например, понять, где выгоднее ставить 1. 2 и 3 - вначале или в конце. Дальше ответ будет несложно получить.
Вилена: Коллеги, вот мой код для задачи, только урезан в пять раз. Здесь идет перебор всевозможных строк. Во всех строках ответ 26. Если применить этот код для исходной задачи, то перебор будет долгим, но ответ такой же 130, но не 145. Поэтому, еще раз к вам обращаюсь, как вы получили ответ 145, не держите в секрете, поделитесь своим решением, пожалуйста. [pre2] from itertools import product from tqdm import tqdm def fin(ss): s = '>' + ss + '<' while '><' not in s: s = s.replace('>1', '3>', 1) s = s.replace('>2', '2>', 1) s = s.replace('>3', '1>', 1) s = s.replace('3<', '<1', 1) s = s.replace('2<', '<2', 1) s = s.replace('1<', '<3', 1) s = s.replace('><', '', 1) rt = sum(list(map(int, s))) return rt, s f = list(product('123', repeat=15)) g = set() for s in tqdm(f): t = ''.join(s) if t.count('1') == 4 and t.count('2') == 3 and t.count('3') == 8: g.add(t) mx = 0 for i in tqdm(g): mx = max(fin(i)[0], mx) # print(i, fin(i)[1], mx) print(mx)[/pre2]
Поляков: Вилена пишет: как вы получили ответ 145, не держите в секрете, поделитесь своим решением [pre2] s = '>' + '1'*20 + '3'*40 + '2'*15 + '<' while not '><' in s: s = s.replace( '>1', '3>', 1 ) s = s.replace( '>2', '2>', 1 ) s = s.replace( '>3', '1>', 1 ) s = s.replace( '3<', '<1', 1 ) s = s.replace( '2<', '<3', 1 ) s = s.replace( '1<', '<2', 1 ) s = s.replace( '><', '', 1 ) print( sum( map(int, s) ) )[/pre2]
Вилена: Благодарю, Константин Юрьевич, не увидела, что предпоследний реплейс меняет не 2 на 2, а 2 на 3. В этом вся соль!!!
полная версия страницы