Помогите решить задачу ЕГЭ с помощью Python

Question

Сколько существует чисел, восьмеричная запись которых содержит 5 цифр, причем в записи нет цифры 1. Также все цифры записи различны и никакие две чётные и две нечётные цифры не стоят рядом.

Мой код:

a = "01234567"
c = 0
for l1 in a:
  for l2 in a:
    for l3 in a:
      for l4 in a:
        for l5 in a:
          w = l1 + l2 + l3 + l4 + l5
          if len(set(w)) == len(w) and int(w) % 2 == 0 and int(w[0]) % 2 == 0 and w.count("1") == 0:
            c += 1
          elif len(set(w)) == len(w) and int(w) % 2 != 0 and int(w[0]) % 2 != 0 and w.count("1") == 0:
        

c += 1
print(c)

Подскажите, как более корректно написать условие if.

Правильный ответ: 180

Answer 1

if len(set(w)) == len(w) and int(w) % 2 == 0 and int(w[0]) % 2 == 0 and w.count("1") == 0:
    c += 1
elif len(set(w)) == len(w) and int(w) % 2 != 0 and int(w[0]) % 2 != 0 and w.count("1") == 0:

c += 1
print(c)

Замените на:

if len(set(w)) == 5 and int(w) % 2 == 0 and int(w[0]) % 2 == 0 and "11" not in w and "33" not in w and "55" not in w and "77" not in w:
    c += 1

print(c)

Answer 2

В своих конспектах нашел такой код, решает по идее эту же задачу, но более аккуратно:

import itertools

alphabet = "01234567"
even = "0246"
odd = "1357"

count = 0

for e in itertools.permutations(alphabet, 5):
    flag = True
    for i in range(len(e) - 1):
        if (e[i] in even and e[i + 1] in even) or (e[i] in odd and e[i + 1] in odd) or e[0] == '0' or e.count('1') != 0:
            flag = False
    if flag:
        count += 1

print(count)

Подоход к решению здесь примерно такой же как и у вас, только перестановки всех элементов алфавита получаем с помощью itertools. Если пытаться упростить этот код, надо думать в сторону математики, сколько подходящих чисел будет на этом интервале. Но, как я помню, это вообще не важно для ЕГЭ, лишь бы работало и ответ выводило

Answer 3

if len(set(w)) == 5 //все числа различны
int(w) % 2 == 0 //число четное
int(w[0]) % 2 == 0 //первая цифра числа четное
"11" not in w and "33" not in w and "55" not in w and "77" not in w//нет двух четных или нечетных которые стоят рядом

Answer 4

 A(3,2)*A(4,2)+3*A(3,2)*A(3,2)=6*12+3*6*6=180

Первое слагаемое - количество чисел, начинающихся с нечётной цифры, второе - количество чисел, начинающихся с чётной цифры, кроме нуля.

A(n,k)=n!/(n-k)! - количество размещений

Посмотрим, как такое можно получить. Создадим списки чётных и нечетных цифр, и будем аккуратно генерировать все возможные наборы в лексикографическом порядке. Первый оборот внешнего цикла перебирает наборы, начинающиеся с чётной цифры, а второй - с нечётной. Для получения первой цифры первые элементы списков не используем, а для последующих цифр не берём единицу. Мы удаляем каждую взятую цифру из списка, чтобы она не появилась снова, а потом аккуратно вставляем на прежнее место. Для двух последних цифр удаление-вставку уже не будем делать.

digits =  [[0,2,4,6],[1,3,5,7]]
cnt = 0
for odds in range(2):
    for k1 in digits[odds][1:]:
        digits[odds].remove(k1)
        for k2 in digits[1-odds][1-odds:]:
            digits[1-odds].remove(k2)
            for k3 in digits[odds][odds:]:
                digits[odds].remove(k3)
                for k4 in digits[1-odds][1-odds:]:
                    for k5 in digits[odds][odds:]:
                        print(k1,k2,k3,k4,k5)
                        cnt+=1
                digits[odds].insert(k3//2, k3)
            digits[1-odds].insert(k2//2, k2)
        digits[odds].insert(k1//2, k1)
print(cnt)

2 3 0 5 4
2 3 0 5 6
2 3 0 7 4
2 3 0 7 6
2 3 4 5 0
...
7 6 3 4 5
7 6 5 0 3
7 6 5 2 3
7 6 5 4 3

Однако можно заметить, что вставка на нужное место не особо и нужна, если сами варианты нас не интересуют, а только их количество. Более того, и на фактическое значение цифр наплевать, важна только чётность и количество. Поэтому перемножим количество оборотов всех внутренних циклов, и сложим эти произведения для четного и нечётного начала. После удаления всего лишнего останется такое:

cnts = [1,1]
for odds in range(2):
    nums = [4, 4]
    cnts[odds] *= nums[odds] - 1
    nums[odds] -= 1
    cnts[odds] *= nums[1-odds] - odds
    nums[1-odds] -= 1
    cnts[odds] *= nums[odds] - 1 + odds
    nums[odds] -= 1
    cnts[odds] *= nums[1-odds] - odds
    cnts[odds] *= nums[odds] - 1 + odds
print(sum(cnts))

По сути это реализация формул, приведённых в начале.

Answer 5

eo, cnt = str.maketrans({'0': '0', '2': '0', '4': '0', '6': '0', '1': '1', '3': '1', '5': '1', '7': '1'}), 0
for i in range(int('10000', 8), int('100000', 8)):  # перебираем вcе пятизначные восьмеричные числа от 0o10000 до 0o77777
    s = oct(i)[2:]  # переводим целое число в восьмеричную систему и откусываем префикс '0o'
    s1 = s.translate(eo)  # меняем все четные на 0, нечетные на 1 по словарю для дальнейшей проверки на рядом стоящие чет/нечет
    cnt += len(set(s)) == 5 and '1' not in s and '00' not in s1 and '11' not in s1  # итоговая проверка числа - если True, то к счетчику добавляется единица
print(cnt)

БЛОГ НА HUSL

Помогите решить задачу ЕГЭ с помощью Python

Ответы (5 шт):