Решающий пень задаёт об объекте ровно один вопрос: «x ⩾ t?» — где t — некоторое вещественное число. Для каждого из двух возможных ответов заранее задаётся предсказываемый класс: белый или чёрный. Эти классы могут совпадать.

Какое наибольшее число правильных предсказаний может дать решающий пень на следующей выборке?

На числовой прямой расположены точки:
1 (белая)
3 (белая)
4 (чёрная)
5 (чёрная)
7 (чёрная)
10 (белая)

Классификатор относит объекты к положительному или отрицательному классу.
Обозначим:
TP — число объектов положительного класса, верно отнесённых к положительному классу;
FN — число объектов положительного класса, ошибочно отнесённых к отрицательному классу;
TN — число объектов отрицательного класса, верно отнесённых к отрицательному классу;
FP — число объектов отрицательного класса, ошибочно отнесённых к положительному классу.
Используются следующие метрики:
полнота (recall) = TP / (TP + FN)
специфичность (specificity) = TN / (TN + FP)
точность (precision) = TP / (TP + FP)

Модель имеет полноту 0.9 и специфичность 0.9. Долей положительного класса назовём отношение числа объектов положительного класса (то есть TP + FN) ко всем объектам выборки.

Определите долю положительного класса при точности 0.5.

Определите долю положительного класса при точности 0.9.

Дана выборка из 7 объектов. Значения признака у объектов равны 0, 1, 4, 10, 14, 20, 22. Каждому объекту соответствует метка класса, равная 0 или 1; метки нам неизвестны. Для каждого объекта алгоритм находит ближайший (по расстоянию между значениями признака) к нему среди остальных объектов и предсказывает, что метка у них одинаковая. Во всех семи случаях алгоритм сделал верное предсказание. Сколько объектов могло иметь метку 0? Укажите все подходящие варианты. Каждый ответ записывайте в отдельное поле, добавляя их при необходимости.

Файл: matches.csv
В файле содержатся результаты всех матчей футбольного чемпионата. В чемпионате участвуют 16 команд. Каждая команда играет с каждой другой два раза: один раз дома и один раз в гостях. Таким образом, в файле находятся результаты 240 матчей.
Файл содержит четыре столбца:
• home_team — название команды хозяев;
• away_team — название команды гостей;
• home_goals — число голов хозяев;
• away_goals — число голов гостей.

За победу команда получает 3 очка, за ничью — 1 очко, за поражение — 0 очков.
Выполните следующие действия:
1. Для каждого матча определите, сколько очков получили хозяева и сколько — гости.
2. Для каждой команды сложите очки, набранные во всех её матчах. Расположите команды по убыванию суммы очков и получите исходную турнирную таблицу.
Гарантируется, что первое и последнее места в исходной таблице определяются однозначно.

Определите победителя исходной таблицы. Запишите название команды.

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

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

После проведения всех матчей команда, занявшая последнее место, снялась с чемпионата, выразив несогласие с рядом судейских решений. По регламенту результаты всех матчей с её участием аннулировали.
Выполните следующие действия:
1. Удалите из данных все матчи, в которых снявшаяся команда была хозяином или гостем.
2. Для оставшихся матчей повторите начисление и суммирование очков. Составьте новую турнирную таблицу.

Определите количество очков команды, занявшей первое место в новой таблице.
Гарантируется, что в новой таблице победитель набрал строго больше очков, чем команда на втором месте.

Лучевой поиск

Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Илья решил своими руками написать лучевой поиск (beam search). Этот алгоритм хранит несколько кандидатов, у каждого из которых есть числовая оценка — скор. На каждом шаге кандидатов модифицируют, скоры пересчитывают, а худших кандидатов удаляют.
В код Ильи закралась грубая ошибка: обновление просто прибавляет ко скору каждого кандидата одно и то же число x. Удаление при этом работает так, как задумано: код удаляет кандидата с наименьшим скором и записывает этот скор в лог. Если кандидатов с наименьшим скором несколько, удаляется любой из них — на записанное значение это не влияет. Удалённый кандидат в поиске больше не участвует, и последующие обновления его не меняют.
Изначально у Ильи n кандидатов, скор i-го из них равен a_i. Затем код выполняет q действий — обновлений и удалений — в известном порядке. Помогите Илье узнать, какие числа окажутся в логе.

Формат входных данных

В первой строке ввода даны два целых числа n и q — количество кандидатов и количество действий (1 ⩽ n, q ⩽ 2 · 10^5).
Во второй строке через пробел перечислены n целых чисел a_i — начальные скоры кандидатов (1 ⩽ a_i ⩽ 10^6).
В следующих q строках описаны действия в порядке выполнения. Каждое имеет один из двух видов:
• 1 x — обновление: скор каждого оставшегося кандидата увеличивается на x (1 ⩽ x ⩽ 1000);
• 2 — удаление кандидата с наименьшим скором среди оставшихся.

Гарантируется, что среди действий есть хотя бы одно удаление и всего удалений не больше n.

Формат выходных данных

Для каждого удаления в порядке выполнения действий выведите в отдельной строке скор удалённого кандидата.

Система оценивания

Тесты из условия не оцениваются. Остальные тесты оцениваются независимо друг от друга, каждый — в 1 балл.

Группа 1: 5 тестов, 5 баллов, дополнительные ограничения: n, q ⩽ 2000
Группа 2: 7 тестов, 7 баллов, дополнительные ограничения: Без дополнительных ограничений

Замечание

В первом примере три кандидата со скорами 5, 1 и 3.
• Действие 1: скоры увеличиваются на 2 и становятся 7, 3, 5.
• Действие 2: удаляется кандидат со скором 3, остаются 7 и 5.
• Действие 3: удаляется кандидат со скором 5, остаётся 7.
• Действие 4: скор увеличивается на 10 и принимает значение 17.
• Действие 5: удаляется кандидат со скором 17.

Примеры:

Ввод:
3 5
5 1 3
1 2
2
2
1 10
2

Вывод:
3
5
17

Ввод:
5 5
5 4 3 2 1
2
2
2
2
2

Вывод:
1
2
3
4
5

Ввод:
4 4
7 7 7 7
2
1 1
2
2

Вывод:
7
8
8

Ввод:
2 4
10 1000000
1 1000
2
1 1000
2

Вывод:
1010
1002000

Самая необычная строка

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Для эксперимента в области машинного обучения собран набор из n объектов. Каждый объект описывается m бинарными признаками: значение каждого признака равно 0 или 1. Объекты пронумерованы от 1 до n в том порядке, в котором они записаны в наборе данных.
Для оценки того, насколько объект отличается от остальных объектов, используется расстояние Хэмминга. Расстоянием Хэмминга между двумя объектами называется количество признаков, значения которых у этих объектов различаются.
Необычностью объекта назовём сумму расстояний Хэмминга от него до всех объектов набора.
Требуется найти объект с максимальной необычностью и значение его необычности. Если максимальная необычность достигается у нескольких объектов, следует выбрать объект с наименьшим номером.

Формат входных данных

В первой строке вводятся через пробел два натуральных числа n и m (1 ⩽ n · m ⩽ 200000).
В следующих n строках вводится по m цифр (0 или 1) в каждой.

Формат выходных данных

Выведите два числа через пробел: номер (наименьший) самой необычной строки и её необычность.

Примеры:

Ввод:
3 4
0101
1100
0000

Вывод:
1 4

Ввод:
4 3
111
110
101
000

Вывод:
4 7