Количество программ из A в B (Проходящие через число) —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#56324

Исполнитель преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить $1$ ,

2. Прибавить $4$ ,

3. Умножить на $2$

Первая команда увеличивает число на экране на $1$ , вторая — на $4$ , третья — увеличивает число в $2$ раза. Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе $4$ результатом является число $27$ и при этом траектория содержит число $22$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $2$ , $6$ , $12$ .

Показать ответ и решение

a = [0] * 60
a[4] = 1
for i in range(5, 28):
    a[i] = a[i - 1] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    if i == 22:
        for j in range(22):
            a[j] = 0
print(a[27])

Ответ: 933

Ошибка.
Попробуйте повторить позже

Задача 2#30472

Исполнитель Щелчок преобразует число на экране. У исполнителя есть три команды:

1. Прибавить $3$

2. Умножить на $2$

3. Прибавить $1$

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числe $2$ результатом является число $30$ , при этом траектория вычислений содержит число $10$ .

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $6$ траектория будет состоять из чисел $9,18,19$ .

Показать ответ и решение

Решение 1 (Рекурсия)

def f(st, fn, flag, flag_number):
    if st == fn and flag:
        return 1
    if st > fn:
        return 0
    if st == flag_number: # поднимаем флаг, если дошли до требуемого значения
        flag = True
    x = f(st + 3, fn, flag, flag_number)
    y = f(st * 2, fn, flag, flag_number)
    z = f(st + 1, fn, flag, flag_number)
    return x + y + z

Решение 2 (Динамика)

a = [0] * 31 * 3
a[2] = 1
for i in range(2, 30):
    if i == 10:
        b = a[i]
        a = [0] * 31 * 3
        a[i] = b # удалили все значения кроме ячейки a[15]
    a[i + 3] += a[i]
    a[i * 2] += a[i]
    a[i + 1] += a[i]
print(a[30])

Ответ: 36126

Ошибка.
Попробуйте повторить позже

Задача 3#25783

Исполнитель Копатыч преобразует целое число, записанное на экране. У исполнителя две команды, которым присвоены номера:

1. Прибавь $1$

2. Прибавь $2$

3. Умножь на $3$

Первая из них увеличивает число на экране на $1$ , вторая увеличивает число на $2$ , третья увеличивает число в $3$ раза.

Программа для исполнителя Копатыч - это последовательность команд.

Сколько существует программ, которые преобразуют исходное число $3$ в число $14$ и при этом траектория вычислений содержит число $9$ ?

Показать ответ и решение

Решение 1 (Рекурсия)

def f(s, fi, flag = False):
    if s == 9:
        flag = True
    if (s == fi) and (flag):
        return 1
    if s > fi:
        return 0
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)
print(f(3, 14))

Решение 2 (Динамика)

a = [0] * 15
a[3] = 1
for i in range(4, 10):
    a[i] += a[i - 1]
    a[i] += a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
for i in range(1, 9):
    a[i] = 0
for i in range(10, 15):
    a[i] += a[i - 1]
    a[i] += a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
print(a[14])

Ответ: 112

Ошибка.
Попробуйте повторить позже

Задача 4#25621

Исполнитель ШКОЛКОВО преобразует число баллов ЕГЭ, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь $1$ ;

2. Прибавь $5$ ;

3. Возведи в квадрат.

Первая команда увеличивает число на экране на $1$ , вторая увеличивает его на $5$ , третья заменяет число на экране на число, равное квадрату этого числа.

Программа для исполнителя ШКОЛКОВО это последовательность команд.

Сколько существует программ, для которых при исходном числе $2$ результатом является число $26$ и при этом траектория вычислений содержит число $5$ ?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $1321$ при исходном числе $3$ траектория будет состоять из чисел $4,16,21,22$ .

Показать ответ и решение

Решение 1 (Рекурсия)

def f(start, finish):
    if start == finish:
        return 1
    if start > finish:
        return 0
    return f(start + 1, finish) + f(start + 5, finish) + f(start * start, finish)


print(f(2, 5) * f(5, 26))

Решение 2 (Динамика)

a = [0] * 27
a[2] = 1
for i in range(3, 27):
    a[i] += a[i - 1] + a[i - 5]
    sq = int(i ** 0.5)
    if sq ** 2 == i:
        a[i] += a[sq]
    if i == 5:
        for j in range(1, 5):
            a[j] = 0
print(a[26])

Решение 3 (Динамика)

a = [0] * 10000
a[2] = 1
for i in range(2, 26):
    if i == 5:
        for j in range(6, 27):
            a[j] = 0
    a[i + 1] += a[i]
    a[i + 5] += a[i]
    a[i * i] += a[i]
print(a[26])

Ответ: 372

Ошибка.
Попробуйте повторить позже

Задача 5#24745

Исполнитель КРИНЖУЛИК преобразует число на экране. У исполнителя две команды, которым присвоены номера:

Прибавить $3$ ;
Умножить на $2$ .

Первая команда увеличивает число на экране на $3$ , вторая увеличивает его в $2$ раза. Сколько существует программ, для которых при исходном числе $12$ результатом будет число $96$ , обязательно проходящее через число $30$ .

Показать ответ и решение

a = [0]*97
a[12] = 1
for i in range(15, 97):
    a[i] += a[i-3] + a[i//2] * (i % 2 == 0)
    if i == 30:
        for j in range(30):
            a[j] = 0
print(a[96])

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 6#24007

Исполнитель Кирка преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить $1$

2. Прибавить $2$

3. Умножить на $3$

Программа для исполнителя Кирка — это последовательность команд.

Сколько существует программ, для которых при исходном числе $2$ результатом является число $13$ и при этом траектория вычислений содержит число $10$ ?

Показать ответ и решение

Решение 1 (Рекурсия)

def f(s, fi, flag):
    if s > fi:
        return 0
    if s == 10:
        flag = True
    if s == fi and flag:
        return 1
    return f(s + 1, fi, flag) + f(s + 2, fi, flag) + f(s * 3, fi, flag)
print(f(2, 13, False))

Решение 2 (Динамика)

a = [0] * 14
a[2] = 1
for i in range(3, 14):
    a[i] += a[i - 1] + a[i - 2]
    if i % 3 == 0:
        a[i] += a[i // 3]
    if i == 10:
        for i in range(i):
            a[i] = 0

print(a[13])

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 7#22658

Исполнитель СКЕЛЕТОР преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

Прибавить $1$
Прибавить $4$
Умножить на $4$

Первая команда увеличивает число на экране на $1$ , вторая — на $4$ , третья — увеличивает число в $4$ раза.

Сколько существует программ, для которых при исходном числе $3$ результатом является число $27$ и при этом траектория содержит число $11$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $2$ , $6$ , $24$ .

Показать ответ и решение

Решение №1

a = [0] * 27 * 4
a[3] = 1
for i in range(3, 27):
    if i == 11:
        for j in range(i + 1, 27 * 4):
            a[j] = 0
    a[i + 1] += a[i]
    a[i + 4] += a[i]
    a[i * 4] += a[i]
print(a[27])

Решение №2

a = [0] * 28
a[3] = 1
for i in range(4, 28):
    a[i] = a[i - 1] + a[i - 4] + a[i // 4] * (i % 4 == 0)
    if i == 11:
        for j in range(i):
            a[j] = 0
print(a[27])

Ответ: 665

Ошибка.
Попробуйте повторить позже

Задача 8#22657

Исполнитель КРАБ преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

Прибавить $3$
Прибавить $4$ ,
Умножить на $2$

Первая команда увеличивает число на экране на $3$ , вторая — на $4$ , третья — увеличивает число в $2$ раза.

Сколько существует программ, для которых при исходном числе $3$ результатом является число $35$ и при этом траектория содержит число $22$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $4$ , $8$ , $16$ .

Показать ответ и решение

a = [0] * 36
a[3] = 1
for i in range(4, 36):
    a[i] = a[i - 3] + a[i - 4] + a[i // 2] * (i % 2 == 0)
    if (i == 22):
        for j in range(i):
            a[j] = 0
print(a[35])

Ответ: 108

Ошибка.
Попробуйте повторить позже

Задача 9#16525

Исполнитель СНЕГОВИК преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 1,

2. Прибавить 4,

3. Умножить на 4

Первая команда увеличивает число на экране на 1, вторая — на 4, третья — увеличивает число в 4 раза.

Сколько существует программ, для которых при исходном числе 3 результатом является число 27 и при этом траектория содержит число 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 1 траектория будет состоять из чисел 2, 6, 24.

Показать ответ и решение

  a = [0] * 1000
  a[3] = 1
  for i in range(3,11+1):
      a[i+1] += a[i]
      a[i+4] += a[i]
      a[i*4] += a[i]
  for i in range(1000):
      if i != 11:
          a[i] = 0
  for i in range(11,27+1):
      a[i+1] += a[i]
      a[i+4] += a[i]
      a[i*4] += a[i]
  print(a[27])

Ответ: 665

Ошибка.
Попробуйте повторить позже

Задача 10#16524

Исполнитель КОНЬКИ преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить 3,

2. Прибавить 4,

3. Умножить на 2

Первая команда увеличивает число на экране на 3, вторая — на 4, третья — увеличивает число в 2 раза.

Сколько существует программ, для которых при исходном числе 3 результатом является число 35 и при этом траектория содержит число 22? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 1 траектория будет состоять из чисел 4, 8, 16.

Показать ответ и решение

  a = [0] * 1000
  a[3] = 1
  for i in range(3, 22 + 1):
      a[i + 3] += a[i]
      a[i + 4] += a[i]
      a[i * 2] += a[i]
  for i in range(1000):
      if i != 22:
          a[i] = 0
  for i in range(22, 35 + 1):
      a[i + 3] += a[i]
      a[i + 4] += a[i]
      a[i * 2] += a[i]
  print(a[35])

Ответ: 108

Ошибка.
Попробуйте повторить позже

Задача 11#16523

Исполнитель Крабокраб преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

Прибавить $2$ ;
Прибавить $3$ ;
Умножить на $2$ .

Первая команда увеличивает число на экране на $2$ , вторая — на $3$ , третья — увеличивает число в $2$ раза.

Сколько существует программ, для которых при исходном числе $3$ результатом является число $18$ и при этом траектория содержит число $8$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $3,6,12$ .

Показать ответ и решение

a = [0] * 19
a[3] = 1
for i in range(4, 19):
    a[i] += a[i - 2] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    if i == 8:
        for j in range(i):
            a[j] = 0
print(a[18])

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 12#16521

Исполнитель ДОБРОЕ УТРО преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить $1$ ,

2. Прибавить $3$ ,

3. Умножить на $2$

Первая команда увеличивает число на экране на $1$ , вторая — на $3$ , третья — увеличивает число в $2$ раза.

Сколько существует программ, для которых при исходном числе $1$ результатом является число $15$ и при этом траектория содержит число $9$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $123$ при исходном числе $1$ траектория будет состоять из чисел $2,5,10$ .

Показать ответ и решение

a = [0] * 16
a[1] = 1
for i in range(2, 16):
    a[i] += a[i - 1] + a[i - 3] + a[i // 2] * (i % 2 == 0)
    if i == 9:
        for j in range(i):
            a[j] = 0
print(a[15])

Ответ: 234

Ошибка.
Попробуйте повторить позже

Задача 13#16517

Исполнитель ПОДАРОК преобразует число, записанное на экране.

У исполнителя есть команды, которым присвоены номера:

1. Прибавить $2$ ,

2. Прибавить $5$

Первая команда увеличивает число на экране на $2$ , вторая — на $5$ .

Сколько существует программ, для которых при исходном числе $1$ результатом является число $19$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $1$ траектория будет состоять из чисел $3,8,10$ .

Показать ответ и решение

  num = [0]*20
  num[1] = 1
  for i in range(2, 20):
      num[i] = num[i-2]+num[i-5]*(i > 5)
  print(num[19])

Ответ: 16

Ошибка.
Попробуйте повторить позже

Задача 14#6838

Исполнитель РЫБИНСК преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1,

2. Прибавить 2.

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя РЫБИНСК — это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений содержит число 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.

Показать ответ и решение

Пусть $R (n)$ — количество программ, которые число 1 преобразуют в число n. Тогда верно следующее утверждение:

$R(n ) = R (n − 1) + R (n − 2)$

Заполним таблицу по данной формуле до 9:

|--|---|--|--|--|--|---|---|----| |1-|2--|3-|4-|5-|6-|-7-|-8-|-9--| -1--1---2--3--5--8--13--21--34--|

По формуле $R (10 ) = R(9) + R (8) = 55$ , но по условию дано, что траектория должна проходить через число 9. Значит если мы будем проходить через 8, то условие будет не выполнено. Следовательно $R (10) = R (9) = 34$ .

Заполним таблицу до конца:

|--|--|--|---|--|--|---|---|---|----|---|----|----|-----| |1-|2-|3-|4--|5-|6-|7--|-8-|-9-|10--|11-|12--|-13-|-14--| |1 |1 |2 |3 |5 |8 |13 |21 |34 |34 |68 |102 |170 | 272 | --------------------------------------------------------

Отсюда получаем искомое количество программ — 272.

Ответ: 272