Практикум и контрольная №1

За одиннадцать занятий набрался инструмент, которого хватает на большую часть школьных олимпиадных задач начального уровня. Новой темы сегодня не будет — будет проверка, что всё это работает вместе.

Главная сложность практикума в том, что тема не подписана. Раньше задача стояла сразу после разбора, и было понятно, что применять. Теперь нет, и первый шаг — понять по условию, какой приём нужен.

Признаки, по которым это видно:

Часто в одной задаче встречается сразу два признака: перебрать числа от 1 до $n$ и у каждого посмотреть цифры — это for снаружи и разбор внутри. Такие задачи и составляют практикум.

Условие: «вводятся числа, ввод заканчивается нулём; найдите, сколько среди них чисел с суммой цифр больше 10».

Что здесь понадобится?

Все они уже встречались. Здесь они собраны вместе — вместе с признаком, по которому ошибка узнаётся, не перечитывая код целиком.

Ввод и вычисления

1. Числа в одной строке прочитаны как в разных — или наоборот. Признак: программа падает на первом же тесте.
2. Обычное деление вместо целочисленного. Признак: в ответе .0 или дробь там, где ждали целое.
3. Порядок сравнений в цепочке if — elif перепутан, и более общее условие стоит раньше частного. Признак: часть случаев не срабатывает никогда.

Циклы

4. range(1, n) вместо range(1, n + 1). Признак: ответ почти верный, ошибка ровно на границе.
5. Накопитель заведён внутри цикла. Признак: ответ равен вкладу последнего элемента.
6. print внутри цикла вместо после. Признак: вместо одного числа — целая история накопления.
7. Максимум начат с нуля. Признак: на отрицательных данных ответ 0.
8. Переменная из условия while не меняется в теле. Признак: превышение времени. Не ускоряйте — ищите пропущенную строку.

Числа и перебор

9. Ноль не обработан: while n > 0 на нуле не выполняется ни разу.
10. Исходное число потеряно разбором — копию надо делать до цикла.
11. Двойной цикл там, где данных слишком много. Признак: превышение времени при верном решении. Перемножьте длины циклов до отправки.

В задаче $n$ до $100\,000$, и решение перебирает все пары $(i, j)$ — то есть делает $n^2$ шагов.

Сколько это миллиардов операций? Введите целое число.

Практикум устроен так, что каждая задача опирается на конкретное занятие. Если видите, что приём не вспоминается, — возвращайтесь точечно, а не перечитывайте всё подряд.

Порядок работы

Сначала практикум — пятнадцать задач с подсказками про то, где смотреть. Потом контрольная — шесть задач без подсказок вовсе.

Смысл именно в таком порядке: практикум показывает, что подзабылось, и это можно закрыть до среза. Контрольная не для оценки, а для ответа на один вопрос — можно ли идти дальше, в модуль про строки.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

Подсказки в условиях остались, но они теперь другие: не «сделайте так», а «здесь стоит вспомнить вот это».

Задача: «вводятся числа, ввод заканчивается нулём; найдите наибольшее из них и количество чисел с чётной суммой цифр».

Ученик написал:

best = 0
count = 0
x = int(input())

while x != 0:
    if x > best:
        best = x
    s = 0
    while x > 0:
        s += x % 10
        x //= 10
    if s % 2 == 0:
        count += 1
    x = int(input())

print(best, count)

Программа работает, но отвечает неверно. Найдите обе ошибки — они из разных тем — и объясните, что программа выведет на входе −4, −2, 0.