Задача к ЕГЭ по информатике на тему «подсчет количества слов/чисел» №19

Просмотров 9 Комментарии 0

Друг составляет пятизначные числа, используя цифры от $2$ до $8$ включительно. Цифры в числе могут использоваться только один раз или не использоваться совсем. Рядом с чётными числами не должно стоять чётных, а рядом с нечётными не должно стоять нечётных. Сколько различных чисел друг может составить?

Пусть первая цифра числа чётная, тогда она может быть одной из $4$ цифр. Вторая нечётная, она может быть одной из $3$ цифр. Третья чётная, она может быть одной из $3$ оставшихся чётных чисел. Четвёртая нечётная, она может быть одной из $2$ оставшихся нечётных цифр. Пятая чётная, может быть одной из $2$ оставшихся чётных. Значит в таком случае друг может составить $4 ⋅ 3 ⋅ 3 ⋅ 2 ⋅ 2 = 144$ различных числа. Если первая цифра нечётная, то по той же логике мы можем составить $3 ⋅ 4 ⋅ 2 ⋅ 3 ⋅ 1 = 72$ различных чисел. Всего друг может составить $144 + 72 = 216$ чисел.
Решение программой (циклы):

ans = set()
alf = ’2345678’

for x1 in alf:
    for x2 in alf:
        for x3 in alf:
            for x4 in alf:
                for x5 in alf:
                    w = x1 + x2 + x3 + x4 + x5
                    if len(w) == len(set(w)):
                        w1 = w.replace(’4’, ’2’).replace(’6’, ’2’).replace(’8’, ’2’)
                        w1 = w1.replace(’5’, ’3’).replace(’7’, ’3’)
                        if (’22’ not in w1) and (’33’ not in w1):
                            ans.add(w)
print(len(ans))

Решение программой (itertools):

from itertools import permutations

ans = set()
alf = ’2345678’

for x in permutations(alf, 5):
    w = ’’.join(x)
    w1 = w.replace(’4’, ’2’).replace(’6’, ’2’).replace(’8’, ’2’)
    w1 = w1.replace(’5’, ’3’).replace(’7’, ’3’)
    if (’22’ not in w1) and (’33’ not in w1):
        ans.add(w)

print(len(ans))

Ответ: 216