Домашнее задание к семинару. Квадратичные и линейные сортировки
скачать .ipynb hw-lecture.tex lab03_hw_tests.py
Домашнее задание 3
После семинара 3 решите пять задач. Сдаёте этот файл семинаристу.
На больших тестах квадратный перебор не успеет: тестер даёт TLE (лимит 2 секунды на тест), не только «не тот ответ».
Можно смотреть свой ноутбук семинара 3. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.
ДЗ к лекции 3 (текст в LaTeX) — отдельно, лектору: это задание не заменяет.
Как устроен ноутбук
Как на семинаре: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.
Положите этот файл .ipynb и файл lab03_hw_tests.py в одну папку. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.
Ввод, вывод и тесты
Решение — функция без аргументов: внутри input и print, как в контесте. Тест подставляет входы сам. Не заполняйте поле ввода Jupyter.
В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.
Импорт тестов стоит в каждой ячейке с решением. Если перезапустите ядро, достаточно снова выполнить эту ячейку — отдельно «подключать библиотеку в начале» не обязательно, хотя общая ячейка ниже тоже есть.
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import (
test_task1,
test_task2,
test_task3,
test_task4,
test_task5,
)
print('Тесты подключены')
Задача 1. Нарушения неубывания
Дан массив из $n$ целых чисел. Сколько есть индексов $i$ ($1 \le i < n$), для которых $a_i > a_{i+1}$?
Вход. Первая строка: целое $n$ ($1 \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 10^9$).
Выход. Одно целое число.
-> 5
-> 1 2 2 4 9
--
<- 0
-> 3
-> 7 7 7
--
<- 0
-> 5
-> 5 4 3 2 1
--
<- 4
-> 4
-> 1 3 2 4
--
<- 1
-> 1
-> 0
--
<- 0
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import test_task1
def task1():
n = int(input())
a = list(map(int, input().split()))
print(-1)
test_task1(task1)
Задача 2. Порядок по модулю
Дан массив из $n$ целых чисел. Выведите его элементы в таком порядке: по неубыванию $|a_i|$; если модули равны — по неубыванию самих чисел $a_i$.
Вход. Первая строка: целое $n$ ($1 \le n \le 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 10^9$).
Выход. $n$ целых чисел через пробел.
-> 5
-> 5 -2 2 -5 0
--
<- 0 -2 2 -5 5
-> 2
-> -3 3
--
<- -3 3
-> 3
-> 0 0 0
--
<- 0 0 0
-> 1
-> 7
--
<- 7
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import test_task2
def task2():
n = int(input())
a = list(map(int, input().split()))
print(0)
test_task2(task2)
Задача 3. По последней цифре
Дан массив из $n$ целых неотрицательных чисел. Упорядочьте его по неубыванию последней десятичной цифры каждого числа (то есть $a_i \bmod 10$). Если последние цифры равны, относительный порядок этих элементов должен остаться таким же, как во входе.
Вход. Первая строка: целое $n$ ($1 \le n \le 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i \le 10^9$).
Выход. $n$ целых чисел через пробел.
-> 3
-> 12 23 34
--
<- 12 23 34
-> 3
-> 25 5 15
--
<- 25 5 15
-> 3
-> 10 20 30
--
<- 10 20 30
-> 1
-> 0
--
<- 0
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import test_task3
def task3():
n = int(input())
a = list(map(int, input().split()))
print(0)
test_task3(task3)
Задача 4. $k$-й по неубыванию
Дан массив из $n$ целых чисел из диапазона от $0$ до $1000$ включительно и число $k$. Если выписать элементы массива в неубывающем порядке, какое число стоит на месте $k$? Нумерация с единицы: при $k = 1$ это минимум массива.
Вход. Первая строка: $n$ и $k$ ($1 \le k \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i \le 1000$).
Выход. Одно целое число.
-> 6 4
-> 3 1 3 2 1 3
--
<- 3
-> 5 1
-> 7 7 7 7 7
--
<- 7
-> 4 3
-> 0 1000 0 5
--
<- 5
-> 5 5
-> 4 1 4 2 4
--
<- 4
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import test_task4
def task4():
n, k = map(int, input().split())
a = list(map(int, input().split()))
print(0)
test_task4(task4)
Задача 5. Точки
Даны $n$ точек на плоскости с целыми координатами. Выведите их в таком порядке: по неубыванию $x$; при равных $x$ — по неубыванию $y$.
Если у двух точек совпадают и $x$, и $y$, их взаимный порядок в ответе может быть любым.
Вход. Первая строка: целое $n$ ($1 \le n \le 10^5$). Далее $n$ строк: в каждой два целых $x$ и $y$ ($|x|, |y| \le 10^9$).
Выход. $n$ строк x y.
-> 3
-> 3 1
-> 1 2
-> 2 0
--
<- 1 2
<- 2 0
<- 3 1
-> 2
-> 1 5
-> 1 2
--
<- 1 2
<- 1 5
-> 3
-> 2 3
-> 2 1
-> 1 9
--
<- 1 9
<- 2 1
<- 2 3
-> 1
-> 0 0
--
<- 0 0
import sys
from pathlib import Path
sys.path[:0] = [str(Path.cwd())]
from lab03_hw_tests import test_task5
def task5():
n = int(input())
for _ in range(n):
input()
print(0, 0)
test_task5(task5)
Сдача
Перед отправкой проверьте:
- сохранили ноутбук:
File → Save; - рядом с ноутбуком лежит
lab03_hw_tests.py; - в ячейке решения есть
from lab03_hw_tests import test_taskN(после перезапуска ядра выполните эту ячейку снова).
Пришлите этот файл .ipynb семинаристу в личные сообщения до дедлайна.
Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход.
ДЗ к лекции (LaTeX) сдаёте лектору, не в этот файл.