Неделя 2

Домашнее задание к семинару. Два указателя, окно, префиксные суммы

скачать .ipynb lab02_hw_tests.py

Домашнее задание 2

После семинара 2 решите пять задач. Сдаёте этот файл семинаристу.

На больших тестах квадратный перебор не успеет: тестер даёт TLE (лимит 2 секунды на тест), не только «не тот ответ».

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

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

Как на семинаре: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

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

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

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

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

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

In [ ]:
import sys
from pathlib import Path

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

from lab02_hw_tests import (
    test_task1,
    test_task2,
    test_task3,
    test_task4,
    test_task5,
)

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

Задача 1. Различные значения

Дан массив целых чисел из диапазона от $0$ до $1000$ включительно. Выведите все значения, которые встречаются в массиве хотя бы один раз, в порядке возрастания, каждое ровно один раз. Сколько раз значение встретилось — не важно, важно только, было оно или нет.

Вход. Первая строка: целое $n$ ($1 \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i \le 1000$).

Выход. Одна строка из значений, встретившихся в массиве, по возрастанию, через пробел.

-> 6
-> 3 1 3 2 1 3
--
<- 1 2 3

-> 5
-> 7 7 7 7 7
--
<- 7

-> 4
-> 0 1000 0 5
--
<- 0 5 1000
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_hw_tests import test_task1


def task1():
    n = int(input())
    a = list(map(int, input().split()))
    print(0)


test_task1(task1)

Задача 2. Пара с ближайшей суммой

Дан массив из $n$ целых чисел, упорядоченный по неубыванию, и число $S$. Среди всех пар элементов с разными индексами найдите пару, сумма которой отличается от $S$ меньше всего, и выведите эту сумму.

Если ближайших пар несколько и суммы у них разные, подойдёт сумма любой из них. Индексы выводить не нужно: проверяющему достаточно, чтобы выведенное число было суммой какой-нибудь пары и стояло так же близко к $S$, как лучшая пара.

Расстоянием до $S$ считается $|a_i + a_j - S|$.

Вход. Первая строка: $n$ и $S$ ($2 \le n \le 2\cdot 10^5$, $|S| \le 2\cdot 10^9$). Вторая строка: $n$ чисел, $a_1 \le \ldots \le a_n$, $|a_i| \le 10^9$.

Выход. Одно целое — сумма пары, ближайшей к $S$.

-> 4 9
-> 2 7 11 15
--
<- 9

-> 4 18
-> 2 7 11 15
--
<- 18

-> 7 10
-> 1 4 4 6 8 9 20
--
<- 10

-> 4 0
-> -10 0 0 10
--
<- 0
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_hw_tests import test_task2


def task2():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    print(0)


test_task2(task2)

Задача 3. Максимальная сумма отрезка длины $k$

Дан массив из $n$ целых чисел и число $k$. Рассматриваются все отрезки длины $k$: с индексов $1\ldots k$, $2\ldots k+1$, …, $n-k+1\ldots n$ (нумерация с единицы). Для каждого отрезка посчитайте сумму его элементов и выведите наибольшую из этих сумм.

Вход. Первая строка: $n$ и $k$ ($1 \le k \le n \le 2\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одно целое — максимальная сумма отрезка длины $k$.

-> 5 3
-> 1 2 3 4 5
--
<- 12

-> 4 4
-> 2 -1 2 -1
--
<- 2

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

-> 6 2
-> 7 0 7 0 7 0
--
<- 7
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_hw_tests import test_task3


def task3():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(0)


test_task3(task3)

Задача 4. Смена знаков

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

Например, массив 5 0 -7 2 -1 превращается в -7 -1 5 2 0: отрицательные были в порядке $-7, -1$, неотрицательные — в порядке $5, 0, 2$.

Разрешается изменять данный массив. Старайтесь обойтись дополнительной памятью $O(1)$: нельзя собирать отрицательные в отдельный список.

Вход. Первая строка: $n$ ($1 \le n \le 2\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одна строка из $n$ чисел — массив после перестановки.

-> 4
-> 3 -1 0 -4
--
<- -1 -4 3 0

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

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

-> 5
-> 5 0 -7 2 -1
--
<- -7 -1 5 2 0

-> 2
-> 0 -5
--
<- -5 0
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_hw_tests import test_task4


def task4():
    n = int(input())
    a = list(map(int, input().split()))
    print(*a)


test_task4(task4)

Задача 5. Максимальная сумма пары на расстоянии

Дана последовательность из $n$ целых чисел и число $K$. Рассматриваются пары элементов с разными индексами, у которых номера отличаются не менее чем на $K$ (порядок элементов в паре не важен, стоять рядом они не обязаны). Найдите наибольшую сумму такой пары.

Нумерация элементов с единицы: у соседних элементов номера отличаются на $1$. При $K = 1$ подходит любая пара с разными индексами. Пара существует всегда, потому что $K < n$.

Числа могут быть и отрицательными; ответ на единицу меньше нуля — это нормально.

Вход. Первая строка: $n$ и $K$ ($2 \le n \le 2\cdot 10^5$, $1 \le K < n$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одно целое — максимальная сумма подходящей пары.

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

-> 6 3
-> 1 100 -50 2 3 -7
--
<- 103

-> 4 2
-> 3 -5 4 10
--
<- 13

-> 4 1
-> -1 -2 -3 -4
--
<- -3
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_hw_tests import test_task5


def task5():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(0)


test_task5(task5)

Сдача

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

  • сохранили ноутбук: File → Save;
  • рядом с ноутбуком лежит lab02_hw_tests.py;
  • в ячейке решения есть from lab02_hw_tests import test_taskN (после перезапуска ядра выполните эту ячейку снова).

Пришлите этот файл .ipynb семинаристу в личные сообщения до дедлайна.

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