🟢 Intern — массивы#
Четыре авторские задачи на индексацию, std::vector и аккуратное использование памяти.
1. Температурный диапазон#
Метеостанция записала температуру за N дней. Найдите минимум и максимум, не сохраняя весь ряд.
Ввод: N (1 ≤ N ≤ 10^6), затем N чисел t_i (-10^6 ≤ t_i ≤ 10^6).
Вывод: минимум и максимум через пробел.
Пример:
5
12 -3 8 8 21
-3 21
Требование: время O(N), дополнительная память O(1).
2. Сжать повторы#
Дан отсортированный массив кодов событий. Оставьте по одному элементу из каждого блока одинаковых соседних значений. Выведите количество оставшихся значений и сами значения. Изменять массив нужно на месте.
Ввод: N (0 ≤ N ≤ 10^5), затем N неубывающих чисел (|a_i| ≤ 10^9).
Вывод: длина результата, затем результат.
Пример:
7
2 2 2 5 5 8 10
4
2 5 8 10
Требование: O(N) времени и O(1) дополнительной памяти.
3. Циклическая доставка#
Лента с N посылками сдвигается вправо на одну позицию: последняя посылка становится первой. Выполните K таких сдвигов и выведите порядок.
Ввод: N и K (1 ≤ N ≤ 2·10^5, 0 ≤ K ≤ 10^18), затем N меток.
Вывод: массив после сдвигов.
Пример:
5 7
1 2 3 4 5
4 5 1 2 3
Требование: O(N) времени и O(1) дополнительной памяти; не создавайте копию массива.
4. Сколько раз рос буфер?#
Динамический массив начинает с вместимости 1. При нехватке места буфер удваивается, все элементы копируются в новое хранилище. Для N добавлений найдите число расширений и общее количество скопированных элементов. Моделировать отдельные добавления нельзя.
Ввод: N (0 ≤ N ≤ 10^18).
Вывод: количество расширений и число скопированных элементов.
Пример:
9
4 15
Пояснение: вместимости 1 → 2 → 4 → 8 → 16; копируются 1+2+4+8=15 элементов. Учтите переполнение при удвоении.