Форум » Динамическое программирование » ЕГЭ-23 № 7212 не сходится ответ » Ответить
ЕГЭ-23 № 7212 не сходится ответ
Тяжельникова: ЕГЭ-23 № 7212 не сходится ответ from functools import * @lru_cache(None) def pp(n,b,e,op): if n==e: return 1 elif n<b-10 or n>e+10 or n%10==1: return 0 if op=='a' or op=='b': return pp(n+6,b,e,'c')+pp(n*3,b,e,'d') else: return pp(n-1,b,e,'a')+pp(n-3,b,e,'b')+pp(n+6,b,e,'c')+pp(n*3,b,e,'d') r1=pp(5,5,26,'_') r2=pp(26,26,58,'_') print(r1,"*",r2,"=",r1*r2) 114 * 262 = 29868 вместо 2732 Подскажите, пожалуйста, какие ограничения не учтены?
Ответов - 8
Ж: У вас, я думаю, есть ошибка в том, что вы не учитываете, что вычитание могло произойти в конце прохода от 5 до 26 и в начале прохода от 26 до 58. Но я тоже не получаю нужный ответ, хотя указанный выше момент учитываю [pre2] f=lambda n,s,tr,k: \ f(n-1, s+'-', tr+[n], k+(n%10==1)) +\ f(n-3, s+'-', tr+[n], k+(n%10==1)) +\ f(n+6, s+'+', tr+[n], k+(n%10==1)) +\ f(n*3, s+'+', tr+[n], k+(n%10==1)) \ if (k==0 and '--' not in s and n!=58 and n<=61) else (n==58 and k==0 and '--' not in s and 26 in tr ) print( f(5, '',[],0)) [/pre2] мой ответ 16965. Я получаю его разными кодами. Есть подозрение, что необходимо ограничение на то, чтобы числа в траектории не повторялись. В этом случае мой ответ 1761.
Тяжельникова: Спасибо за ответ) Вычитание последним ходом учтено, т.к. идет проверка: n<b-10 or n>e+10 По вашей догадке, исключила повторяющиеся числа. p1=[]; p2=[] from functools import * @lru_cache(None) def pp(n,b,e,op,path): if n==e: if b==5: p1.append(path+' '+str(n)) if b==26: p2.append(path+' '+str(n)) return 1 elif n<b-10 or n>e+10 or n%10==1: return 0 if op=='a' or op=='b': return pp(n+6,b,e,'c',path+' '+str(n))+pp(n*3,b,e,'d',path+' '+str(n)) else: return pp(n-1,b,e,'a',path+' '+str(n))+pp(n-3,b,e,'b',path+' '+str(n))+pp(n+6,b,e,'c',path+' '+str(n))+pp(n*3,b,e,'d',path+' '+str(n)) r1=pp(5,5,26,'_',path="") r2=pp(26,26,58,'_',path="") print(r1,"*",r2,"=",r1*r2) u1=[]; u2=[] for x in p1: m=x.split() s=set(m) if len(m)==len(s): m.pop(); m.pop(0) u1.append(' '.join(m)) for x in p2: m=x.split() s=set(m) if len(m)==len(s): m.pop(); m.pop(0) u2.append(' '.join(m)) print("исключила с повторяющимися числами",len(u1),"*",len(u2),"=",len(u1)*len(u2)) k1=0; k2=0 for i in range(len(u1)): pr=1 for j in range(len(u1)): if i!=j and u1[j] in u1: pr=0 if pr==1: k1+=1 for i in range(len(u2)): pr=1 for j in range(len(u2)): if i!=j and u2[j] in u2: pr=0 if pr==1: k2+=1 print("исключила траектории, для которых другая траектория являтся их частью",k1,"*",k2,"=",k1*k2) ---- 114 * 262 = 29868 исключила с повторяющимися числами 49 * 93 = 4557 исключила траектории, для которых другая траектория являтся их частью 32 * 79 = 2528 все равно не 2732
Ж: (используйте подсказку наверху в желтом прямоугольнике, чтобы в коде сохранялись отступы) Мне кажется, что вы не исключаете эти два минуса в траектории на стыке, т.к. 114 - это число всех способов попасть из 5 в 26 ровно как и 262 - это число всех способов попасть из 26 в 58 без проверки того, что происходит на стыке этих траекторий. Я убрала из вашего кода эту проверку, заменила на N>100, чтобы глубины рекурсии хватило (все равно из 100 в 58 не попасть) , ответ не изменился. [pre2] from functools import * @lru_cache(None) def pp(n,b,e,op): if n==e: return 1 elif n>100 or n%10==1: return 0 if op=='a' or op=='b': return pp(n+6,b,e,'c')+pp(n*3,b,e,'d') else: return pp(n-1,b,e,'a')+pp(n-3,b,e,'b')+pp(n+6,b,e,'c')+pp(n*3,b,e,'d') [/pre2] Чтобы проверить стык, я в более длинном варианте программы поступала так: считала запуски: 5-27 с последней операцией в траектории не -1 * 27-26 * 26-58 с первой операцией в траектории не -1 и не -3 5-29 с последней операцией в траектории не -3 * 29-26 * 26-58 с первой операцией в траектории не -1 и не -3 5-23 с любой последней операцией * 23-26 * 26-58 с любой последней операцией через последнюю операцию умножение в 26 не попасть, так что этот вариант не считаем Ответ получался тот же, что я писала выше.
Тяжельникова: Спасибо за ответ)) Для полной картины хотелось бы комментарии автора ответа с сайта.
Ж: Это да. Я на 99 процентов уверена в своем решении и не понимаю, как можно получить авторский ответ...
Тяжельникова: На сайте в задании ответ стал 16965. Пока я писала программу, чтобы выйти на ваш ответ, я обнаружила дубли строк-траекторий. [pre2] m=[] def pp(n,op,ch): if n==58: if ('26' in ch) and (not '--' in op): m.append(ch) return 1 else: return 0 elif n<5-10 or n>58+10 or n%10==1 or '--' in op: return 0 else: return pp(n-1,op+'-',ch+','+str(n))+pp(n-3,op+'-',ch+','+str(n))+pp(n+6,op+'+',ch+','+str(n))+pp(n*3,op+'*',ch+','+str(n)) r=pp(5,'','') print(r) print(len(m)) s=set() for x in m: s.add(x) print(len(s)) [/pre2] 16965 16965 13220 Таким образом, без дублей траекторий ответ получается 13220
Ж: В данной задаче уникальными должны быть программы, а не траектории (одни и те же числа в траектории мы можем получить разными операциями) Вот две одинаковые траектории, но в них число 9 получено разными способами 3+6 и 3*3 ',5,2,6,3,9,8,24,23,29,26,32,38,44,50,56,53,59', ',5,2,6,3,9,8,24,23,29,26,32,38,44,50,56,53,59' Есть задача 7222, в которой оговорено условие на уникальность траекторий: (А. Минак) У исполнителя Калькулятор имеются три команды, которые обозначены латинскими буквами: А. Прибавь 1 B. Прибавь младшую цифру C. Прибавь старшую цифру Программа для исполнителя – это последовательность команд, каждая из которых изменяет число. Сколько существует программ c разными траекториями, для которых при исходном числе 82 результатом является число 124, и при этом траектория вычислений содержит число 95 и число 103? Траектория вычисления программы – это последовательность результатов выполнения всех команд программы. Например, при исходном числе 17 траектория вычислений программы CBA будет состоять из чисел 18, 26, 27.
Тяжельникова: Точно )
полная версия страницы