ФМШ 2007 (Шапарин Е.А.)

одно целое

a = int(input())

одно вещественное

a = float(input())

несколько целых в одной строке

a, b = map(int, input().split())

список целых, в одну строку через пробел

lst = list(map(int, input().split()))

Список целых, одно число в строке

lst = [input() for i in range(int(input()))]

cписок в строку

print(*lst)

несколько print в строку через ‘+’

print(…, end = ‘+’)

несколько значений в print через ‘+’

print(a, b, sep = ‘+’)

форматированный вывод

Округление вверх

(a + b -1) // b

a больше нуля - 1, ноль - ноль

2 - (a + 2) // (a + 1)

Создать одномерный список нулей

lst = [0] * N

Создать список целых неотрицательных чисел

lst = [i for i in range(N)]

Преобразовать строку в список символов

lst = list(s)

Преобразовать список чисел в список строк

lst = list(map(str, lst))

Преобразовать список строк в строку

s = ‘ ’.join(lst)

Отсортировать текущий список

lst.sort()

Отсортировать текущий список по убыванию

lst.sort(reverse=True)

Получить новый отсортированный список с сохранением имеющегося

l = sorted(lst)

Сортировка по любому параметру. func – функция, которая вызывается для каждого элемента и возвращает значения, по которым происходит сортировка.  Пример – сортировка по убыванию.

def func(a):

    return -a

lst.sort(key=func)

То же самое в одну строчку. Сортировка по остатку

lst = [5, 4, 3, 2, 1]

lst.sort(key=(lambda x: x % 2))

print(lst)

[4, 2, 5, 3, 1]

Быстрый перебор, например, координат точек в списке точек

for a, b in [[1, 2], [3, 4], [5, 6]]:

    print(a, b)

1 2

3 4

5 6

Перебор значений списка с индексом

for i, x in enumerate([7, 123, 2, 222]):

    print(i, x)

0 7

1 123

2 2

3 222

Объединение первых элементов списков, вторых и т.д.

for a, b, c in zip([1, 2, 3], ["a", "b", "c"], [[1, 2, 3], "asda", 11111]):

    print(a, b, c)

1 a [1, 2, 3]

2 b asda

3 c 11111

Получить координаты точек, которые находятся в одном списке

a = [1, 2, 3, 4, 5, 6]

for x1, x2 in zip(a[::2], a[1::2]):

    print(x1, x2)

1 2

3 4

5 6

Получить список координат

list(zip([1, 2, 3], [4, 5, 6]))

[(1, 4), (2, 5), (3, 6)]

Транспонирование матрицы

coords = [[1, 2], [11, 22], [33, 44]]

list(map(list,zip(*coords)))

[[1, 11, 33], [2, 22, 44]]

Быстрая сортировка

О(n*log₂n)

Сортировка подсчетом

О(n+m), n - количество чисел, m - количество значений

Алгоритм Евклида

O(5*log₁₀n)

Бинарный поиск

O(log₂n)

Два указателя

О(n)

Линейный поиск

О(n)

Суфиксные, префиксные суммы

О(n)

Сканлайн

О(n)

Тернарный поиск

O(log₃n²)

Проблема Гольдабха

Любое четное число больше 4 можно представить в виде суммы двух простых чисел. Проверено для 4*10¹⁸.

Любое четное число можно представить в виде суммы не более чем 6 простых чисел. Доказано в 1995 году.

Тернарная проблема Гольдбаха

Любое нечетное число, больших 7, можно представить в виде суммы трех простых слагаемых. Доказано в 2013 году

Теорема Ламе

Сложность алгоритма Евклида меньше чем O(5*log₁₀n)