Задача на массивы по Python

Question

Задача на массивы по Python

Рейтинг: -1Ответов: 1Опубликовано: 18.01.2023

Начал на днях изучать олимпиадное программирование и это очень сложно ведь я имею мало опыта в решении задач. Начались трудности с этой задачей.

В классе учится n учеников. В школах у каждого школьника есть свое место. Ученик под номером i сидит за i-той партой. Сегодня староста класса хочет похулиганить. Она решила посадить учеников так чтобы ни один ученик не сидел на своем месте. Она просит вас найти количество способов это сделать по модулю 1 0 9 + 7 10 9 +7. Например, если в классе 3 ученика тогда всего есть два способа как их можно посадить ( [ 231 ] , [ 312 ] ) ([231],[312]).

Формат входного файла Дается n ( 1 ≤ n ≤ 1000000 ) n(1≤n≤1000000) - количество учеников в классе.

У меня появилась идея решить таким способом. Человек вводит число k, допустим. Потом создается цикл в котором составляется массив от 1 до k, затем в программа в случайном порядке перемешивает элементы массива и складывает их, и если попалась сумма(в формате строки), которой еще не было и не было в обратном порядке то она попадает в массив (t) с вариантами рассадки учеников. Потом если по истечении 10 циклов не добавлены новые строки в массив t, то подсчитывается количество элементов массива и отправляется в терминал.

У меня получилось реализовать только половину функций (до случайного порядка). Здесь у меня не особо нет идей. Вроде бы можно использовать модуль random, но можно ли там указать чтобы не было повторений в генерации случайных чисел в определенном диапазоне? Print внизу я использовал чтобы проверять, будет ли каждый раз случайная первая сумма массива.

Код внизу:

students = int(input())
studentslist = []
partanumberslist = []
m = 1
i = 0
while not m > students:
    studentslist.append(str(m))
    m = m + 1

def mix_list(studentslist):
    global secondlist
    secondlist = studentslist[:]
    list_length = len(secondlist)
    for i in range(list_length):
        index_aleatory = random.randint(0, list_length - 1)
        temp = list[i]
        secondlist[i] = list[index_aleatory]
        secondlist[index_aleatory] = temp
    return secondlist

mix_list(studentslist=studentslist)

while not i == 10:
    print(b''.join((secondlist)))

python строки случайные-числа массивы

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Можно попробовать такой подход. Берем, например, первые 6 случаев:

1 ученик, комбинаций пересадки 0
2 ученика >> 1
3 ученика >> 2
4 ученика >> 9
5 учеников >> 44
6 учеников >> 265

Наблюдаем закономерность - каждое следующее число подходящих комбинаций равно предыдущее число комбинаций * число учеников +/- 1. Например, число комбинаций для 5 учеников = 44 = 9*5-1, а для 6 учеников = 265=44*6+1. Эта единица меняет знак при каждой итерации. Напишем такой код:

N = 1000000
res = 0
d = 10 ** 9 - 7
sign = 1
for i in range(1, N):
    res = (res * (i + 1) + sign) % d
    sign = -sign
print(f'Комбинаций для {N} учеников по модулю 10**9-7 = {res}')

Комбинаций для 1000000 учеников по модулю 10**9-7 = 558002412

Примечание. Насчет корректности получения остатка % d на каждой итерации не вполне уверен. Проверил на 10 учениках таким кодом, совпало.

import itertools

lst = list('0123456789')
good = 0
for i in itertools.permutations(lst, len(lst)):
    res = sum(x == i[n] for n, x in enumerate(lst))
    if res == 0:
        good += 1
print(good)

Задача на массивы по Python

Ответы