Форум » Выполнение и анализ алгоритмов для исполнителей » 12 - 272 (Джобс) » Ответить
12 - 272 (Джобс)
AnnaPershina: Здравствуйте, подскажите, пожалуйста, в чем ошибка? Что-то явно упускаю в рассуждениях. [pre2] m=0 for x in range(1,200): for y in range (1,200): for z in range (1,200): s='1'*x+'3'*y+'13'*z while '12' in s or '13' in s: s=s.replace('12','21',1) s = s.replace('31', '23', 1) s = s.replace('13', '23', 1) if s.count('1')==0: summ=s.count('2')*2+s.count('3')*3 if summ==404: m=max(m,x+y+z*2) print(m) [/pre2] Программа либо долго выполняется, либо выдает неправильный ответ, Руками, конечно, задача решается недолго, но как ускорить программу ?
Ответов - 7
AnnaPershina: Без программы рассуждения такие: заметим,что если будут стоять 13,то они заменятся на 23, и сумма 2+3=5 , тогда достаточно начальная строка около 160 элекментов. Поэтому нужно ,чтобы были сначала 1, а потом 3. заметим, 1113 превращается в 2223. Значит поставим две 3 и остальное 1. тогда 404-2*3=398. 398/2=199 значит 199 "1" и две "3" 199+2=201
Поляков: AnnaPershina пишет: Руками, конечно, задача решается недолго, но как ускорить программу ? Не стоит решать такие задачи программой (методом грубой силы).
AnnaPershina: Понятно. Спасибо.
Винникова: А можно сочетать рассуждение и программу. В данном случае мы видим, что 2 цифры меняются на 2, значит в итоге цифр будет столько же, сколько было. В итоговой строке только двойки и тройки, т.е. 2*x+3*y=404. А вот x и y пусть подберет программа. x+y искомый результат.
aln1947: Рассуждения Винниковой программа Паршиной (исправл.): [pre2].. #12.272 m=0 for x in range(1,300): for y in range (1,10): s='1'*x+'3'*y while '12' in s or '13' in s: s=s.replace('12','21',1) s = s.replace('31', '23', 1) s = s.replace('13', '23', 1) if s.count('1')==0: summ=s.count('2')*2+s.count('3')*3 if summ==404: m=max(m,x+y) print(m) # Rez = 201, t = 3 min .[/pre2],
Винникова: aln1947 пишет: Рассуждения Винниковой программа Паршиной После рассуждения можно, в данном случае, ограничиться этим: [pre2] for d in range(1, 1000): for t in range(1, 1000): if 2*d+3*t == 404: print(d+t) [/pre2]
s11kai: Винникова пишет: for d in range(1, 1000): for t in range(1, 1000): if 2*d+3*t == 404: print(d+t) Очень, очень красивое решение!
полная версия страницы