Чему научитесь
- Хранить последовательность в списке Python или vector C++
- Находить сумму, количество, минимум и максимум одним проходом
- Применять линейный поиск и простую симуляцию
- Перебирать небольшой набор вариантов и выбирать лучший
Как устроено занятие
Сначала разбор с примерами и короткими проверками понимания — они нужны, чтобы поймать непонятое сразу, а не через три темы.
Дальше 15 задач лестницей: разминка, основа, со звёздочкой. Занятие засчитывается, когда решено 8 — остальные не пропадают и учитываются отдельно.
После занятия — вторая часть, ещё 15 задач на те же приёмы в новых сюжетах.
Сколько это займёт
Примерно час-полтора вместе с задачами. Сроков нет: можно закрыть вкладку и вернуться когда удобно — прогресс сохранится.
Один вопрос ко многим числам
Когда во входе много чисел, обычно не нужно сравнивать каждое с каждым. Часто достаточно пройти по последовательности один раз и хранить только текущий ответ.
Список и vector
Python
n = int(input())
a = list(map(int, input().split()))
print(sum(a))
C++
int n;
cin >> n;
vector<long long> a(n);
for (long long &x : a) cin >> x;
Что хранить при поиске максимума
Что достаточно помнить во время одного прохода по массиву?
Счётчик и лучший ответ
Для подсчёта заводят счётчик и увеличивают его только когда условие выполнено. Для минимума или максимума начальное значение удобно взять из первого элемента.
Python
best = a[0]
for x in a:
best = max(best, x)
C++
long long best = a[0];
for (long long x : a) {
best = max(best, x);
}
Поиск, симуляция и перебор
Поиск проверяет элементы по очереди. Симуляция выполняет команды в том же порядке, что в условии. Полный перебор пробует все варианты, когда их заведомо мало.
Перед вложенными циклами оцените число итераций: — нормально, а — уже нет.
Практика: один проход
Сначала пять разминочных задач, затем семь основных и три необязательные задачи со звёздочкой. Проверяйте решение на примере до отправки.
Задачи со звёздочкой
Эти три задачи не нужны для зачёта. Они проверяют, получается ли собрать несколько простых приёмов без готового шаблона.
Почему одного прохода достаточно
Объясните, какие две величины достаточно хранить при поиске минимального элемента и номера его первого вхождения.