https://pastein.ru/t/grN
Загрузка данных
# N = int(input("Введите ограничение N: "))
# a, b = 1, 1
# total_sum = 0
# while a <= N:
# if a % 2 == 0:
# total_sum += a
# a, b = b, a + b
# print(f"Сумма четных чисел Фибоначчи до {N}: {total_sum}")
# ---------------------------------------------------------------------
# import math
# def is_prime(num):
# if num < 2:
# return False
# if num == 2:
# return True
# if num % 2 == 0:
# return False
# for i in range(3, int(math.sqrt(num)) + 1, 2):
# if num % i == 0:
# return False
# return True
# N = int(input("Введите четное число N > 2: "))
# print(f"Пары простых чисел для {N}:")
# for first in range(2, N // 2 + 1):
# second = N - first
# if is_prime(first) and is_prime(second):
# print(f"{first} + {second}")
# ---------------------------------------------------------------------
# K = int(input("Введите длину числа K (от 3 до 7): "))
# start = 10**(K - 1)
# end = 10**K
# print(f"Числа Армстронга {K}-го порядка")
# for num in range(start, end):
# total_sum = 0
# temp = num
# while temp > 0:
# digit = temp % 10
# total_sum += digit ** K
# temp //= 10
# if total_sum == num:
# print(num)
# ---------------------------------------------------------------------
# max_dlin = 0
# best_num = 0
# for i in range(1, 100001):
# n = i
# dlin = 1
# while n > 1:
# if n % 2 == 0:
# n //= 2
# else:
# n = 3 * n + 1
# dlin += 1
# if dlin > max_dlin:
# max_dlin = dlin
# best_num = i
# print(f"Число {best_num}")
# print(f"Длина {max_dlin}")
# ---------------------------------------------------------------------
# def main_factors(n):
# parts = []
# divise = 2
# while n > 1:
# count = 0
# while n % divise == 0:
# count += 1
# n //= divise
# if count > 0:
# parts.append(f"{divise}^{count}")
# divise += 1
# print(" * ".join(parts))
# a = int(input("Введите a = "))
# main_factors(a)
# ---------------------------------------------------------------------
# def main_factors(n):
# factors = []
# divise = 2
# while n > 1:
# while n % divise == 0:
# factors.append(divise)
# n //= divise
# divise += 1
# target2 = 2
# target3 = 3
# target5 = 5
# count2 = factors.count(target2)
# count3 = factors.count(target3)
# count5 = factors.count(target5)
# print(f"{count2},{count3},{count5}")
# return factors
# a = int(input("Введите a = "))
# print(f"Разложение числа {a} на множители: {main_factors(a)}")
# [2, 2, 2, 3, 3]
# ---------------------------------------------------------------------
# def find_numbers(n):
# massiv_numbers = []
# for num in range(1, n + 1):
# if num == 1:
# continue
# div_sum = 0
# for i in range(1, num // 2 + 1):
# if num % i == 0:
# div_sum += i
# if div_sum == num:
# massiv_numbers.append(num)
# return massiv_numbers
# a = int(input("Введите a = "))
# result = find_numbers(a)
# print(f"Совершенные числа в диапазоне от 1 до {a}: {result}")
### Блок 1: Хитрые числа и математика (Разминка для мозгов)
1. **Совершенные числа.** Напишите программу, которая находит все «совершенные числа» в диапазоне от 1 до $N$. Совершенное число — это число, равное сумме всех своих собственных делителей (например, 6 = 1 + 2 + 3).
2. **Простая факторизация.** Дано число $N$. Выведите егwhyо разложение на простые множители в виде степеней. Например, для 72 вывод должен быть: `2^3 * 3^2`.
3. **Гипотеза Коллатца (Сиракузская последовательность) на максималках.** Найдите число в диапазоне от 1 до 100 000, которое порождает самую длинную последовательность Коллатца, прежде чем дойдет до единицы. Выведите само число и длину его цепи.
4. **Числа Армстронга $K$-го порядка.** Пользователь вводит длину числа $K$ (от 3 до 7). Найдите все числа длины $K$, которые равны сумме своих цифр, возведенных в степень $K$ (например, $153 = 1^3 + 5^3 + 3^3$).
5. **Проверка гипотезы Гольдбаха.** Дано четное число $N > 2$. Выведите все возможные пары простых чисел, сумма которых равна $N$. (Например, для 28: 5+23, 11+17). Оптимизируйте циклы, чтобы не проверять лишнее.
6. **Числа Фибоначчи с условием.** Выведите сумму всех *четных* чисел Фибоначчи, которые не превышают заданного значения $N$ (например, 4 000 000).
### Блок 2: Вложенные циклы и двумерное воображение (Вынос мозга принтами)
7. **Спиральная матрица.** Пользователь вводит $N$. Выведите на экран квадратную матрицу $N \times N$, заполненную числами от 1 до $N^2$ по спирали, начиная с верхнего левого угла по часовой стрелке.
8. **Правильный треугольник Паскаля.** Выведите первые $N$ строк треугольника Паскаля, но сделайте так, чтобы вывод был отформатирован в виде симметричной пирамиды (потребуются циклы для правильного подсчета пробелов).
9. **Ромб из букв.** На вход подается латинская буква (например, 'E'). Выведите ромб, где внешний контур — это 'A', следующий слой 'B' и так далее до введенной буквы в центре.
10. **Масштабируемая шахматная доска.** Вводятся два числа: $N$ (размер доски в клетках, например 8х8) и $K$ (размер самой клетки в символах). Отрисуйте доску, где черные клетки состоят из блока символов `#` размера $K \times K$, а белые — из символов `.`.
11. **Диагональный обход матрицы.** Дана матрица $N \times M$ (можно просто генерировать координаты). Выведите её элементы зигзагом (по диагоналям: сначала (0,0), потом (0,1), (1,0), потом (2,0), (1,1), (0,2) и т.д.).
12. **Песочные часы.** Пользователь вводит нечетное число $N$. Выведите фигуру песочных часов из цифр, где в верхней и нижней строке цифры от 1 до $N$, а по мере сужения к центру крайние цифры пропадают (заменяются пробелами).
### Блок 3: Строки и последовательности (Индексы и состояния)
13. **RLE (Run-Length Encoding).** Дана строка типа `AAAABBBCCDAA`. Используя циклы, сожмите её до `4A3B2C1D2A`. И наоборот: напишите цикл для распаковки обратно.
14. **Look-and-Say (Посмотри и скажи).** Сгенерируйте $N$-й элемент последовательности, где каждый следующий элемент описывает предыдущий: 1, 11, 21, 1211, 111221, 312211 и т.д.
15. **Наивный поиск подстроки с подвохом.** Дана строка и подстрока. Найдите ВСЕ индексы вхождения подстроки, но перекрывающиеся вхождения тоже должны считаться! (Например, в "AAAA" подстрока "AA" встречается по индексам 0, 1 и 2). Не использовать встроенные методы поиска.
16. **Зигзаг-строка.** Дана строка и число строк $K$. Выведите строку так, как если бы она была написана зигзагом по $K$ строкам, а затем прочитана построчно. (Классика LeetCode).
17. **Самый длинный палиндром.** Используя вложенные циклы (без динамического программирования), найдите самую длинную подстроку в введенной строке, которая читается одинаково в обе стороны.
18. **Анаграммы в окне.** Даны длинная строка $T$ и короткая $S$. Найдите все стартовые индексы в $T$, начиная с которых идет любая перестановка (анаграмма) строки $S$. (Намек на концепцию скользящего окна в цикле).
### Блок 4: Алгоритмические задачи (Прокачка сложности O(N))
19. **Максимальная подпоследовательность (Алгоритм Кадане руками).** Дан массив положительных и отрицательных чисел. Используя ровно *один* цикл, найдите непрерывную подпоследовательность с максимальной суммой.
20. **Сортировка "Голландский национальный флаг".** Дан массив, состоящий только из 0, 1 и 2. Отсортируйте его за *один проход* цикла (используя 3 указателя), не используя дополнительную память.
21. **Скользящее среднее.** Дана последовательность из $N$ чисел и размер окна $W$. Выведите массив скользящих средних. Сделайте это эффективно: при сдвиге окна не считайте сумму $W$ элементов заново каждый раз (избавьтесь от вложенного цикла).
22. **Элемент большинства.** В массиве длины $N$ один элемент встречается строго больше $N/2$ раз. Найдите его за один проход цикла, используя только две дополнительные переменные $O(1)$ памяти (Алгоритм большинства Бойера-Мура).
23. **Слияние отсортированных массивов.** Даны два уже отсортированных массива разной длины. Используя цикл(ы), создайте третий массив, в котором элементы обоих будут слиты в отсортированном порядке без использования встроенных функций сортировки.
24. **Удаление дубликатов на месте.** Дан отсортированный массив. Используя один цикл и два указателя, измените массив так, чтобы все уникальные элементы оказались в его начале. Выведите количество уникальных элементов.
### Блок 5: Симуляции и Хардкор (Тут они начнут страдать)
25. **Улитка с усталостью.** Улитка ползет по стене высотой $H$ метров. Днем ползет на $U$ метров вверх, ночью сползает на $D$ метров вниз. Но улитка устает: каждый новый день она проползает вверх на $F\%$ меньше от *изначальной* дневной дистанции $U$ (при этом вниз сползает всегда на $D$). На какой день она выберется из колодца, или она в итоге соскользнет на дно?
26. **Игра "Жизнь" Конвея.** Реализуйте один такт (шаг) игры "Жизнь" для двумерного поля $N \times M$. (Проверка всех соседей клетки с учетом краев поля — отличная тренировка вложенных циклов и условных операторов).
27. **Захват дождевой воды (Trapping Rain Water).** Дан массив высот столбиков (ширина каждого 1). Вычислите, сколько единиц воды может скопиться между столбиками после дождя. Смогут ли студенты решить это без вложенных $O(N^2)$ циклов, а за $O(N)$?
28. **Прыжки по массиву.** Дан массив неотрицательных чисел. Каждое число означает максимальную длину прыжка вперед с этого индекса. Вы находитесь на индексе 0. Определите минимальное количество прыжков, необходимое, чтобы добраться до конца массива (или скажите, если это невозможно).
29. **Печать чека.** Напишите программу, которая принимает на вход список покупок (Название, Цена, Количество) до тех пор, пока пользователь не введет "СТОП". Затем программа должна вывести красиво отформатированный чек с рамкой из символов `*`, выравниванием названий по левому краю, цен — по правому, и итоговой суммой в конце.
30. **Расписание турнира (Round-robin).** Дано четное число команд $N$. Сгенерируйте расписание матчей "каждый с каждым" по турам. В каждом туре все команды должны сыграть ровно один матч. (Алгоритм кругового турнира требует очень элегантной работы с индексами в цикле).
