Ошибка.
Попробуйте повторить позже
У исполнителя Хитритель две команды, которым присвоены номера:
1. Прибавь
2. Раздели на
Первая из них увеличивает число на экране на вторую же можно применять только для четных чисел, и она делит его на
Программа для Хитрителя — это последовательность команд. Сколько есть программ, которые применяют вторую команду не более раз и преобразуют число в число ?
Ключевое замечание, необходимое для решения задачи — заметим, что нет смысла рассматривать числа большие так как из них даже четырежды применив вторую операцию не получится получить число . Далее достаточно написать — количество программ заканчивающихся в числе и при этом использующие ровно шагов второго типа. База динамики . Переход в динамике: . Конечно стоит аккуратно проверять, что .
Решение на C++
void solve(){ //dp[x][cnt] - количество программ приводящие в число x, //и при этом использовали ровно cnt операций второго типа vector<vector<int>> dp(16 * 20 + 1, vector<int>(5, 0)); dp[10][0] = 1; for(int cnt = 0; cnt < 5; ++cnt){ for(int x = 0; x <= 16 * 20; ++x){ if(x + 1 < 16 * 20 + 1) //операция прибавить 1 dp[x + 1][cnt] += dp[x][cnt]; if(x % 2 == 0 && cnt + 1 < 5) //операция разделить на 2 dp[x / 2][cnt + 1] += dp[x][cnt]; } } cout << dp[20][0] + dp[20][1] + dp[20][2] + dp[20][3] + dp[20][4] << ’\n’; }
Решение на Python
dp = [[0] * 5 for _ in range(16 * 20 + 1)] dp[10][0] = 1 for cnt in range(5): for x in range(16 * 20 + 1): if x + 1 <= 16 * 20: dp[x + 1][cnt] += dp[x][cnt] if x % 2 == 0 and cnt + 1 < 5: dp[x // 2][cnt + 1] += dp[x][cnt] print(sum(dp[20]))
Решение с помощью рекурсии
from functools import lru_cache @lru_cache(None) def f(st, end, cnt): if (st > 20*16): return 0 if (cnt > 4): return 0 if (st == end): return 1 + f(st//2,end,cnt+1) + f(st+1, end, cnt) if (st%2 == 0): return f(st+1, end, cnt) + f(st//2, end, cnt+1) else: return f(st+1, end, cnt) print(f(10,20,0))
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок взял пример с задания, купил саженца и переехал в волшебную страну. Деревьев в этой стране нет, поэтому нарубить дров исполнитель не может. Почва в волшебной стране, разумеется, волшебная, если посадить саженцев, то они вырастут в деревья за дней. При этом, деревья, посаженные в разные дни, растут независимо друг от друга, т.е. если в первый день посадили саженца, а во второй еще один, то к третьему дню можно будет спилить дерева. Каждое дерево дает единиц дров и новых саженца. Исполнитель хочет узнать за какое минимальное количество дней он сможет собрать минимум единиц дров.
Решение 1 (Рекурсия)
def f(day, count_drova, count_sajenec, days, tree): global minim if day > minim: # если день перешел минимальное количество дней, # то мы заканчиваем return i = 0 while i < len(days): # массив дней, когда должны вырасти очередные деревья if days[i] == day: days.pop(i) a = tree.pop(i) count_drova += 10 * a # растет количество дров count_sajenec += 2 * a # растет количество саженцев i -= 1 # -1 тут и +1 ниже скомпенсируют удаленный элемент i += 1 if count_drova >= 200 and day < minim: minim = day return for i in range(1, count_sajenec + 1): if i * 10 + count_drova > 200: # не нужно рассматривать варианты, # которые будут заведомо дольше чем мы хотим break # посадили i деревьев f(day + 1, count_drova, count_sajenec - i, days.copy() + [i + day], tree.copy() + [i]) minim = 10000000000 f(1, 0, 3, [], []) print(minim)
Решение 2 (Динамика)
ans = [] ans.append((1, 0, 3)) # (сколько прошло дней, сколько есть дров, сколько есть саженцев) otv = 10000000 for operations in range(1000): can_get = [] for i in ans: days, wood, seed = i if wood >= 200: otv = min(otv, days) continue for j in range(1, seed + 1): # сажаем j саженцев if j == 1: can_get.append((days + j, wood + j * 10, seed + j)) else: can_get.append((days + j - 1, wood + j * 10, seed + j)) if len(can_get) == 0: break ans = can_get print(otv)
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть четыре команды:
1. Прибавить 1
2. Умножить на 2 и прибавить 1
3. Умножить на 2 и вычесть 1
4. Умножить на 4 и прибавить 1
Программа для исполнителя — это последовательность команд.
Исполнитель хочет выяснить какое минимальное количество простых чисел он может посетить при перемещении из числа 10 в число 300.
Решение 1 (Рекурсия)
def is_prime(n): for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return n != 1 from functools import lru_cache @lru_cache(None) def f(st, fn, primes): global count if is_prime(st): primes += 1 if st == fn: if primes < count: count = primes return if st > fn: return f(st + 1, fn, primes) f(st * 2 + 1, fn, primes) f(st * 2 - 1, fn, primes) f(st * 4 + 1, fn, primes) count = 100000000000 f(10, 300, 0) print(count)
Решение 2 (Динамика)
def is_prime(n): if n < 2: return 0 for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return 0 return 1 a, primes = [10000000] * 301, [0] * 301 a[10] = 0 # для начала определим для каждого числа от 1 до 300 # простое оно, или нет for i in range(2, 301): if is_prime(i): primes[i] = 1 # далее реализуем динамическое решение задачи for i in range(10, 300): a[i + 1] = min(a[i + 1], a[i] + primes[i + 1]) if i * 2 + 1 < 301: a[i * 2 + 1] = min(a[i * 2 + 1], a[i] + primes[i * 2 + 1]) if i * 2 - 1 < 301: a[i * 2 - 1] = min(a[i * 2 - 1], a[i] + primes[i * 2 - 1]) if i * 4 + 1 < 301: a[i * 4 + 1] = min(a[i * 4 + 1], a[i] + primes[i * 4 + 1]) print(a[300])
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок находится на первой ступеньке очень длинной лестницы. У исполнителя есть 3 команды:
1. Подняться на одну ступеньку и потратить одну единицу энергии.
2. Перешагнуть через одну ступеньку (подняться на две) и потратить 3 единицы энергии
3. Перешагнуть через две ступеньки (подняться на 3 ступеньки) и потратить 6 единиц энергии
Программа для исполнителя — это последовательность команд.
У исполнителя в запасе 60 единиц энергии, длина лестницы 25 ступенек. За какое минимальное количество команд исполнитель сможет добраться до последней ступеньки и сохранить максимальный для такого количества команд запас энергии. Если запас энергии исполнителя кончается, он отчаивается и не идет дальше, кроме случая, если он уже на 25 ступеньке. В ответе укажите количество команд и максимальный сохраненный запас энергии.
Решение 1 (Рекурсия)
from functools import lru_cache @lru_cache(None) def f(st, fn, en, comand): global count, ener if st == fn and en >= 0: if comand < count: count = comand ener = en #если количество шагов совпало, # то мы берем максимум энергии elif comand == count and en > ener: ener = en return # вылет из программы if en < 0: return f(st + 1, fn, en - 1, comand + 1) f(st + 2, fn, en - 3, comand + 1) f(st + 3, fn, en - 6, comand + 1) count = 10000000 ener = -1 f(1, 25, 60, 0) print(count, ener)
Решение 2 (Динамика)
ans = [] ans.append((1, 60, 0)) # (текущая ступенька, текущее кол-во энергии, кол-во сделанных ходов) otv, mn_com = -100000000, 100000000 for operations in range(1000): can_get = [] for i in ans: step, energy, go = i if (step > 25) or (energy < 0): continue if (step == 25) and (energy >= 0): if mn_com == go: # берем минимум команд и максимум энергии mn_com = go otv = max(otv, energy) continue elif mn_com > go: mn_com = go otv = energy continue # все возможные ходы can_get.append((step + 1, energy - 1, go + 1)) can_get.append((step + 2, energy - 3, go + 1)) can_get.append((step + 3, energy - 6, go + 1)) # если больше ходов нет, выходим из цикла if len(can_get) == 0: break ans = can_get.copy() print(mn_com, otv)
Ошибка.
Попробуйте повторить позже
У исполнителя Щелчок есть куча камней, но он очень одинок, с ним никто не играет в камушки, поэтому он придумал игру для себя сам. У исполнителя есть 3 команды:
1. Прибавить 3 камушка в кучу
2. Умножить количество камушков в куче на 2 и вычесть 1
3. Если количество камней в куче больше 9, то реверсировать количество камней в куче и прибавить 1 (10 2 , 123 322)
Программа для исполнителя — это последовательность команд.
Какое минимальное количество команд содержит программа, которая проходит через 8 различных простых чисел. Исполнитель начинает с числа 2 (первое число тоже считается, если оно простое)
Решение 1 (Рекурсия)
def is_prime(n): for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return n > 1 def f(st, count_operation, set_prime): global count if count_operation > count: return # выход из программы без действий if is_prime(st): set_prime.add(st) if len(set_prime) == 8: count = min(count, count_operation) return f(st + 3, count_operation + 1, set_prime.copy()) f(st * 2 - 1, count_operation + 1, set_prime.copy()) if st > 9: f(int(str(st)[::-1]) + 1, count_operation + 1, set_prime.copy()) count = 10000000000 f(2, 0, set()) print(count)
Решение 2 (Динамика)
def is_prime(n): if n < 2: return 0 for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return 0 return 1 primes = [0] * 100000 # для начала определим для каждого числа от 1 до 99999 # простое оно, или нет for i in range(2, 100000): if is_prime(i): primes[i] = 1 # далее реализуем динамическое решение задачи ans = [] ans.append((2, 1)) otv, flag = 100000000, 0 for operations in range(1000): can_get = [] for i in ans: a, pr = i if pr == 8: otv = operations flag = 1 break can_get.append((a + 3, pr + primes[a + 3])) can_get.append((a * 2 - 1, pr + primes[a * 2 - 1])) if a > 9: s = str(a) s = s[::-1] new_num = int(s) + 1 can_get.append((new_num, pr + primes[new_num])) if flag: break ans = can_get print(otv)
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок очень хочет быть похожим на исполнителя Робота, поэтому учится двигаться по прямоугольной системе координат. У исполнителя есть три команды:
1. Прибавить 2 к координате X ((1, 2) (3, 2))
2. Умножить координату X на 2 ((1, 2) (2, 2))
3. Переместиться вверх на любое количество клеток от 1 до разницы между нынешней координатой и стеной, (стеной считается прямая y = «значение Y у конечной точки»)
Пример для команды 3, y = 5 — стена, ((1, 1) (1, 2), или (1, 1) (1, 3), или ..., или (1, 1) (1, 5))
Программа для исполнителя — это последовательность команд.
Сколько существует различных программ, которые приведут исполнителя из точки с координатами (1, 2) в точку с координатами (12, 19).
Решение 1 (Рекурсия)
from functools import lru_cache @lru_cache(None) def f(st, fn): if st == fn: return 1 if st[0] > fn[0] or st[1] > fn[1]: return 0 c1 = f((st[0] + 2, st[1]), fn) c2 = f((st[0] * 2, st[1]), fn) c = [0] * (fn[1] - st[1] + 1) for i in range(1, fn[1] - st[1] + 1): c[i] = f((st[0], st[1] + i), fn) return c1 + c2 + sum(c) print(f((1, 2), (12, 19)))
Решение 2 (Динамика)
dp = [[0] * 20 for i in range(13)] dp[1][2] = 1 for x in range(1, 13): for y in range(2, 20): if x + 2 < 13: dp[x + 2][y] += dp[x][y] if x * 2 < 13: dp[x * 2][y] += dp[x][y] for to in range(y + 1, 20): dp[x][to] += dp[x][y] print(dp[12][19])
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует двоичное число на экране. У исполнителя есть две команды:
1. Приписать 1 справа (1 11)
2. Приписать бит четности справа, если это 0, слева, если это 1 (бит четности — количество нулей в числе по модулю 2, 10 110, 100 1000)
Программа для исполнителя — это последовательность команд.
Сколько существует различных программ, которые переводят 1 в 95 в двоичной системе счисления.
Решение 1 (Рекурсия)
def f(st, fn): if st == fn: return 1 if len(st) > len(fn): return 0 x = f(st + "1", fn) if st.count("0") % 2 == 0: y = f(st + "0", fn) else: y = f("1" + st, fn) return x + y print(f("1", "1011111"))
Решение 2 (Динамика)
def to_bin(n): # перевод из десятичной СС в двоичную a = "" while n > 0: a = str(n % 2) + a n //= 2 return a # Если s="1010", то команда n=int(s, base=2) переводит число 1010 # из 2-й СС в 10-ю СС a = [0] * 96 a[1] = 1 for i in range(1, 95): cur_num = to_bin(i) new_num = int(cur_num + "1", base=2) if new_num < 96: a[new_num] += a[i] chet_bit = cur_num.count("0") % 2 if chet_bit: new_num = int("1" + cur_num, base=2) else: new_num = int(cur_num + "0", base=2) if new_num < 96: a[new_num] += a[i] print(a[95])
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть две команды:
1. Прибавить 4
2. Вычесть 5
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 20. При этом исполнитель не может посетить одно и то же число дважды и может двигаться пока не перейдет границы отрезка [-20; 40], при переходе границ исполнитель разрушается.
Решение 1 (Рекурсия)
def f(start, finish, limits, visited): if (start == finish): return 1 if (start < limits[0]) or (start > limits[1]): return 0 if (start in visited): return 0 vis = visited.copy() vis.add(start) x = f(start + 4, finish, limits, vis) y = f(start - 5, finish, limits, vis) return x + y print(f(1, 20, (-20, 40), set()))
Решение 2 (Динамика)
ans = [] ans.append((1, set([1]))) otv = 0 for operations in range(1000): can_get = [] for i in ans: a, vis = i vis_first = vis.copy() vis_second = vis.copy() if a == 20: otv += 1 continue if ((a + 4) in vis) == 0 and (a + 4 <= 40): vis_first.add(a + 4) can_get.append((a + 4, vis_first)) if ((a - 5) in vis) == 0 and (a - 5 >= -20): vis_second.add(a - 5) can_get.append((a - 5, vis_second)) if len(can_get) == 0: break ans = can_get print(otv)
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 1
2. Прибавить номер предыдущей операции
3. Прибавить номер следующей операции
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 24, при этом команда 3 встречается в программе чаще чем команда 2? Примеры программ: 33312 — True, 312 — False. Считать, что первая выполняемая операция это прибавить 1. Для первой выполняемой операции считать, что предыдущая операция была прибавить 1. Команда 3 не может завершать программу.
Стоит сказать, что динамическое решение данной задачи будет занимать длительное время выполнения и большой объем памяти, в силу того, что для каждой программы из условия требуется хранить значений (текущее число, количество операций типа , количество операций типа , номер предыдущей операции и номер следующей операции). Поэтому рекомендуется решать эту задачу с помощью рекурсии.
from functools import lru_cache @lru_cache(None) def f(st, fn, count_2, count_3, old, next): if st == fn and count_3 > count_2 and old != 3: return True if st > fn: return False x = [0] * 3 for i in range(3): if next == 1: x[i] = f(st + 1, fn, count_2, count_3, 1, i + 1) if next == 2: x[i] = f(st + old, fn, count_2 + 1, count_3, 2, i + 1) if next == 3: x[i] = f(st + i + 1, fn, count_2, count_3 + 1, 3, i + 1) return sum(x) print(f(1, 24, 0, 0, 1, 1))
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:
1. Прибавить 3
2. Умножить на 2
3. Приписать любую цифру от 0 до 9 справа (1 10, или 1 11, или 1 12 и т.д.)
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числe 1 результатом является число 48, при этом команда 3 встречается в программе чаще чем команда 2? Примеры программ: 33312 — True, 312 — False
Стоит сказать, что динамическое решение получается довольно трудоемким и громоздким, поэтому рекомендуется использовать рекурсивную реализацию в данной задаче.
Решение 1 (Рекурсия)
def f(st, fn, count_2, count_3): if st == fn and count_3 > count_2: return True if st > fn: return False x = f(st + 3, fn, count_2, count_3) y = f(st * 2, fn, count_2 + 1, count_3) z = [0] * 10 for i in range(10): z[i] = f(st * 10 + i, fn, count_2, count_3 + 1) return x + y + sum(z) print(f(1, 48, 0, 0))
Решение 2 (Динамика)
ans = set() ans.add((1, 0, 0)) # (куда пришли, сколько раз использовали вторую команду, раз использовали третью команду) otv = 0 for operations in range(1000): can_get = set() for i in ans: a, cnt_2, cnt_3 = i if (a == 48) and (cnt_2 < cnt_3): otv += 1 continue if a + 3 <= 48: can_get.add((a + 3, cnt_2, cnt_3)) if a * 2 <= 48: can_get.add((a * 2, cnt_2 + 1, cnt_3)) for j in range(9): new_numb = int(str(a) + str(j)) if new_numb <= 48: can_get.add((new_numb, cnt_2, cnt_3 + 1)) if len(can_get) == 0: break ans = can_get print(otv)
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть две команды:
1. Приписать 0 справа (1 10)
2. Приписать копию числа задом наперед справа (10 1001)
Программа для исполнителя — это последовательность команд.
Сколько существует различных программ, которые переводят 7 в десятиразрядное число.
Решение 1 (Рекурсия)
def f(st): global count if len(st) == 10: count += 1 print(st) if len(st) < 10: f(st + "0") # приписать 0 справа f(st + st[::-1]) # приписать копию числа справа count = 0 f("7") print(count)
Решение 2 (Динамика)
ans = [] otv = 0 ans.append("7") for operations in range(1000): can_get = [] for i in ans: if len(i) == 10: otv += 1 new_st = i + "0" if len(new_st) <= 10: can_get.append(new_st) new_st = i + i[::-1] if len(new_st) <= 10: can_get.append(new_st) if len(can_get) == 0: break ans = can_get print(otv)
Ошибка.
Попробуйте повторить позже
Исполнитель Щелчок преобразует число на экране. У исполнителя есть две команды:
1. Прибавить
2. Умножить на
Программа для исполнителя — это последовательность команд.
В какое минимальное число мог направиться исполнитель из числа , если до пункта назначения он добрался с помощью различных программ.
a[1] = 1
for i in range(1, 30):
a[i + 1] += a[i]
a[i * 2] += a[i]
print(a.index(36))
Ошибка.
Попробуйте повторить позже
У исполнителя Калькулятор есть две команды, которым присвоены номера:
- Прибавить
- Прибавить
Определите число, для получения которого из числа существует программы.
Решение 1 (Рекурсия)
def f(s, fi): if s > fi: return 0 if s == fi: return 1 return f(s + 2, fi) + f(s + 5, fi) for i in range(6,100): if f(5, i) == 34: print(i) break
Решение 2 (Динамика)
a = [0] * 101 a[5] = 1 for i in range(6, 101): a[i] += a[i - 2] + a[i - 5] print(a.index(34))
Ошибка.
Попробуйте повторить позже
У исполнителя Калькулятор есть три команды, которым присвоены номера:
1. Прибавить
2. Прибавить
3. Умножить на
Найдите длину самой короткой программы, в результате выполнения которой при исходном числе результатом является число .
a = [0] * 300 a[0] = 10**20 a[1] = 0 for i in range(2, 300): x, y, z = 10**10, 10**10, 10**10 x = a[i - 1] + 1 if i >= 5: y = a[i - 5] + 1 if i % 3 == 0: z = a[i // 3] + 1 a[i] = min(x, y, z) print(a[227])
Ошибка.
Попробуйте повторить позже
У исполнителя Кабачок есть три команды, которым присвоены номера:
1. Прибавить 2
2. Прибавить 4
3. Прибавить 5
Определите число, для получения которого из числа 31 существует 1001 программа.
a = [0] * 100 a[31] = 1 for i in range(32, 100 + 1): a[i] = a[i-2] + a[i-4] + a[i-5] if a[i] == 1001: print(i) break