Семинар. Модель RAM и асимптотика на Python

Семинар 1. Среда и задачи с памятью $O(1)$

На этой паре вы поставите рабочую среду, решите несколько задач в стиле контеста и сдадите этот файл в LMS.

Дополнительная память $O(1)$ здесь значит простое: несколько переменных. Весь вход в список складывать не нужно — так вы привыкнете думать о памяти до сложных структур данных.

Задачи 1–8 — основа занятия. Девятая и десятая — если после восьмой осталось время.

Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: тесты это не заметят, а на зачёте рядом никого не будет.

Как устроен ноутбук

Два типа ячеек: Markdown (текст, как этот) и Code (Python).

Два режима. В командном вы работаете с ячейкой целиком: добавить, удалить, запустить. В режиме правки курсор внутри ячейки, вы меняете текст. В командный режим — Esc, в правку — Enter.

Полезные сочетания:

Shift+Enter — выполнить ячейку и перейти к следующей;
Ctrl+Enter — выполнить и остаться в ней.

Скачайте с сайта курса этот файл .ipynb и файл lab01_tests.py в одну папку. Без файла тестов проверка ниже не запустится. Откройте ноутбук из этой папки.

Среда

Если ячейка ниже уже печатает 4, Python у вас есть — ничего не переустанавливайте.

Если интерпретатора ещё нет, в терминале:

curl -LsSf https://astral.sh/uv/install.sh | sh
uv python install 3.12
uv venv
source .venv/bin/activate
uv pip install jupyterlab
jupyter lab

На Windows активация: .venv\Scripts\activate. Как ставить uv: https://docs.astral.sh/uv/getting-started/installation/

Подойдёт и обычный Python 3 с IDLE, VS Code или уже установленным Jupyter. Если установка не идёт — напишите семинаристу и переходите к задачам: среда нужна, но не взамен решения.

Проверка:

In [ ]:

print('Python готов к работе')
print(2 + 2)

Ввод, вывод и тесты

В контесте программа читает данные и печатает ответ:

input() возвращает строку до конца строки;
int(...) делает из неё целое число;
print(...) пишет ответ.

Решение в этом ноутбуке — функция без аргументов. Внутри те же input и print. Тест сам подставляет готовые входы. Не заполняйте поле ввода Jupyter — числа с клавиатуры не нужны.

В каждой задаче уже стоит заглушка: она что-то читает и всегда печатает один и тот же неверный ответ. Сначала запустите ячейку: увидите «не OK», вход теста, «ожидалось» и «получено». Потом замените тело функции и запустите снова.

In [ ]:

import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]

from lab01_tests import (
    test_task0,
    test_task1,
    test_task2,
    test_task3,
    test_task4,
    test_task5,
    test_task6,
    test_task7,
    test_task8,
    test_task9,
)

print('Тесты подключены')

Разряды числа: `//` и `%`

Как из числа 179 достать первую цифру? Разделить на 100 и отбросить дробную часть. В Python это оператор // — целое деление. Последняя цифра — остаток от деления на 10: %. Среднюю можно получить, сначала отбросив единицы (n // 10), затем взяв остаток от деления на 10.

В ячейке ниже разберите число. Сумма трёх цифр для 179 должна получиться 17. Подставьте, например, 987 и посмотрите, что изменится.

In [ ]:

# Поменяйте 179 на другое трёхзначное и перезапустите ячейку
n = 179
print('сотни:', n // 100)
print('десятки:', (n // 10) % 10)
print('единицы:', n % 10)
print('сумма:', n // 100 + (n // 10) % 10 + n % 10)

Теперь тем же приёмом решите задачу: сумма цифр произвольного трёхзначного числа со входа.

Задача 1. Сумма цифр трёхзначного числа

Дано трёхзначное число. Найдите сумму его цифр.

Вход. Одно целое число от 100 до 999.

Выход. Одно число — сумма цифр.

-> 179
<- 17

In [ ]:

def task0():
    n = int(input())
    print(0)


test_task0(task0)

Одно логическое условие

Операции and и or собирают несколько проверок в одно выражение. Год високосный, если он кратен 4 и не кратен 100, или кратен 400. Отдельный if на каждый случай не нужен: одно условие и два ответа — YES или NO.

Посмотрите остатки для типичных годов:

In [ ]:

# Поменяйте годы и перезапустите ячейку
print('2000 % 400 =', 2000 % 400)
print('1900 % 100 =', 1900 % 100)
print('2004 % 4 =', 2004 % 4)

Соберите из таких проверок одно условие и ответьте YES или NO.

Задача 2. Високосный год

Требуется определить, является ли данный год високосным. Год високосный, если его номер кратен 4, но не кратен 100, а также если он кратен 400.

Вход. Натуральное $N$ — номер года ($0 < N < 100000$).

Выход. YES, если год високосный, и NO иначе.

-> 1
<- NO

-> 2000
<- YES

In [ ]:

def task1():
    year = int(input())
    print('NO')


test_task1(task1)

Вложенные решения: сначала «существует ли»

Когда исходов несколько и они взаимоисключающие, удобно идти снаружи внутрь. Для треугольника сначала проверьте неравенство: каждая сторона строго меньше суммы двух других. Если нет — треугольника не существует. Если да — сравните квадраты сторон и выберите один тип: прямоугольный, остроугольный или тупоугольный.

Не стоит писать четыре независимых if подряд: они легко начнут спорить друг с другом.

Сначала решите, существует ли треугольник, затем выберите один из трёх типов.

Задача 3. Тип треугольника

Определите тип треугольника с данными сторонами.

Вход. Три неотрицательных целых числа — стороны. Каждое число с новой строки.

Выход. Одно слово:

right — прямоугольный,
acute — остроугольный,
obtuse — тупоугольный,
impossible — треугольника с такими сторонами нет.

-> 3
-> 4
-> 5
<- right

In [ ]:

def task2():
    a = int(input())
    b = int(input())
    c = int(input())
    print('impossible')


test_task2(task2)

Цикл без списка

while повторяет тело, пока условие истинно. Число можно печатать сразу, не складывая в список через append: так меньше памяти, и условие следующей задачи просит именно цикл.

Идея: держать очередное натуральное $k$ и, пока $k^2$ не превосходит $N$, печатать квадрат и увеличивать $k$.

Напечатайте квадраты, не большие 20:

In [ ]:

# Поменяйте 20 на другое N и перезапустите ячейку
limit = 20
k = 1
while k * k <= limit:
    print(k * k, end=' ')
    k += 1
print()

Напечатайте в цикле все квадраты, не превосходящие заданное $N$.

Задача 4. Список квадратов

По данному натуральному $N$ напечатайте все квадраты натуральных чисел, не превосходящие $N$, в порядке возрастания.

В этой задаче необходимо использовать цикл.

Вход. Целое $N$, не больше $10000$.

Выход. Последовательность чисел через пробел.

-> 50
<- 1 4 9 16 25 36 49

In [ ]:

def task3():
    n = int(input())
    print(0)


test_task3(task3)

Одна переменная, которая растёт

Иногда «последовательность» не нужно хранить: достаточно обновлять текущее значение. Если вклад каждый год увеличивается на $p$ процентов, а копейки отбрасываются, новый размер — целое деление:

x = x * (100 + p) // 100

Годы считайте в отдельной переменной, пока вклад меньше цели. Список сумм по годам не нужен.

Один шаг от 100 рублей и 10 процентов:

In [ ]:

# Поменяйте x или p и перезапустите ячейку
x, p = 100, 10
x = x * (100 + p) // 100
print('через год:', x)

Повторяйте такой шаг, пока вклад не достигнет цели, и посчитайте годы.

Задача 5. Банковский вклад

Вклад составляет $x$ рублей. Ежегодно он увеличивается на $p$ процентов, после чего дробная часть копеек отбрасывается. Определите, через сколько лет вклад составит не менее $y$ рублей.

Вход. Три натуральных числа: $x$, $p$, $y$.

Выход. Число лет.

-> 100 10 200
<- 8

In [ ]:

def task4():
    x, p, y = map(int, input().split())
    print(0)


test_task4(task4)

Двоичный порядок: только удвоение

Нужно наименьшее целое $k$ такое, что $2^k \ge N$. В следующей задаче нельзя возводить в степень и нельзя писать if. Заведите power = 1 и k = 0 и в цикле удваивайте power, пока оно меньше $N$, каждый раз увеличивая $k`.

Сколько удвоений нужно, чтобы из 1 получить число не меньше 10?

In [ ]:

# Поменяйте 10 на другое N и перезапустите ячейку
n = 10
power = 1
k = 0
while power < n:
    power *= 2
    k += 1
print('шагов:', k)
print('степень двойки:', power)

Тем же удвоением найдите наименьшее $k$ для произвольного $N$.

Задача 6. Двоичный логарифм

По данному натуральному $N$ выведите такое наименьшее целое $k$, что $2^k \ge N$.

Необходимо использовать цикл. Инструкция if запрещена. Возведение в степень использовать нельзя.

Вход. Натуральное $N$, не больше $10000$.

Выход. Число $k$.

-> 10
<- 4

In [ ]:

def task5():
    n = int(input())
    print(0)


test_task5(task5)

Редукция: прочитали, обновили, забыли

Представьте поток чисел неизвестной длины. Как понять, что он кончился, не спрашивая заранее, сколько их будет? Часто в конец ставят сторожевое значение — здесь ноль, который в саму последовательность не входит.

Весь поток в список копировать не нужно: вы не обязаны помнить все числа, только ответ. Две переменные: текущий максимум и сколько раз он встретился. Прочитали число — либо сменили максимум и обнулили счётчик, либо увеличили счётчик, если число равно максимуму. После этого само число можно забыть.

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

Задача 7. Количество элементов, равных максимуму

Последовательность состоит из натуральных чисел и завершается числом 0. Определите, сколько элементов равны её наибольшему элементу. Числа после нуля считывать не нужно.

Вход. Целые числа, последнее из них — 0 (ноль в последовательность не входит). До завершающего нуля присутствует хотя бы одно натуральное число.

Выход. Одно число.

-> 1
-> 3
-> 3
-> 1
-> 0
<- 2

In [ ]:

def task6():
    print(0)


test_task6(task6)

Поток строк до маркера

Иногда длина входа заранее неизвестна: вы читаете строки, пока не встретите маркер конца. В следующей задаче это номер начальника A999AA. Его и всех, кто после него, штрафовать не нужно.

Для каждой предыдущей машины смотрите скорость и три цифры номера. На одну строку хватает нескольких переменных — список всех машин не нужен. Цифры можно вытащить из середины номера или разобрать через // и %, как в первой задаче.

Читайте машины до номера начальника и копите сумму штрафов.

Задача 8. Гаишник

Зарплата патрульного складывается из штрафов за скорость строго больше 60 км/ч. Штраф зависит от номера: три одинаковые цифры — 1000, ровно две совпадают — 500, все разные — 100. Рабочий день кончается номером начальника A999AA (латинская буква A); начальника штрафовать нельзя.

Вход. Строки «скорость и номер» (буква, три цифры, две буквы). Число строк заранее неизвестно. Кто приехал после начальника, не штрафуется.

Выход. Одно целое — сумма штрафов за день.

-> 80 E101PA
-> 61 M555OH
-> 60 H222OM
-> 10 A999AA
<- 1500

In [ ]:

def task7():
    print(0)


test_task7(task7)

Если осталось время

Две задачи ниже — для тех, кто уже закрыл тестами первые восемь. Новых конструкций почти нет: снова счётчики и несколько переменных вместо списка.

Четыре счётчика вместо массива

У плоскости четыре четверти. Точку на оси никуда не кладут. Чтобы найти самую населённую четверть, достаточно четырёх переменных-счётчиков, без списка точек. Если максимум одинаковый у нескольких четвертей, берут четверть с меньшим номером.

Четырьмя счётчиками найдите самую населённую четверть.

Задача 9. Точки на плоскости

Дан набор точек с целочисленными координатами. Определите номер координатной четверти, в которой точек больше всего. Точки с нулевой координатой не принадлежат ни одной четверти. Если таких четвертей несколько, выведите четверть с меньшим номером.

Нумерация координатных четвертей:

I: $x>0,\ y>0$;
II: $x<0,\ y>0$;
III: $x<0,\ y<0$;
IV: $x>0,\ y<0$.

Вход. Сначала $N$, затем $N$ строк с координатами $x$ $y$.

Выход. Номер четверти и число точек в ней.

-> 3
-> -5 -5
-> -5 -2
-> 1 1
<- 3 2

In [ ]:

def task8():
    n = int(input())
    print('1 0')


test_task8(task8)

Два наибольших и два наименьших

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

Двумя наибольшими и двумя наименьшими найдите максимальное произведение.

Задача 10. Максимальное произведение

Среди $N$ целых чисел найдите два, произведение которых максимально. Массивы использовать запрещено.

Вход. Сначала $N$ ($2 \le N \le 10000$), затем $N$ целых чисел по одному в строке.

Выход. Одно число — произведение.

-> 5
-> 2
-> 8
-> 1
-> 3
-> 2
<- 24

In [ ]:

def task9():
    n = int(input())
    print(0)


test_task9(task9)

Сдача

Перед отправкой проверьте:

сохранили ноутбук: File → Save;
рядом с ноутбуком лежит lab01_tests.py;
ячейка с импортом тестов выполнена;
отправили этот файл .ipynb в задание семинара 1 на courses.ai.msu.ru.

Если LMS не открывается, пришлите файл семинаристу в личные сообщения до конца дня.

Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально.

Семинар. Модель RAM и асимптотика на Python

Семинар 1. Среда и задачи с памятью $O(1)$

Как устроен ноутбук

Среда

Ввод, вывод и тесты

Разряды числа: // и %

Задача 1. Сумма цифр трёхзначного числа

Одно логическое условие

Задача 2. Високосный год

Вложенные решения: сначала «существует ли»

Задача 3. Тип треугольника

Цикл без списка

Задача 4. Список квадратов

Одна переменная, которая растёт

Задача 5. Банковский вклад

Двоичный порядок: только удвоение

Задача 6. Двоичный логарифм

Редукция: прочитали, обновили, забыли

Задача 7. Количество элементов, равных максимуму

Поток строк до маркера

Задача 8. Гаишник

Если осталось время

Четыре счётчика вместо массива

Задача 9. Точки на плоскости

Два наибольших и два наименьших

Задача 10. Максимальное произведение

Сдача

Разряды числа: `//` и `%`