Олимпиадный тренинг

Задача . kNN-классификация: голосование соседей


Задача

Темы:

Сеть магазинов хочет заранее понять, будет ли у нового магазина высокая посещаемость. Для уже работающих магазинов известно число домохозяйств рядом xi и класс ci: 1 — посещаемость высокая, 0 — нет.

Для прогноза используется метод k ближайших соседей с голосованием. Чтобы предсказать класс нового магазина с числом домохозяйств x:

  1. для каждого известного магазина вычислим расстояние |xi − x|;
  2. упорядочим известные магазины по возрастанию расстояния; если расстояния равны, раньше идёт магазин, который стоит раньше во входных данных;
  3. возьмём первые k магазинов — это соседи;
  4. прогноз — тот класс, который встречается у соседей чаще. Так как k нечётно, ничьей не бывает.

Напишите программу, которая делает такой прогноз для нескольких новых магазинов. Пользоваться библиотеками машинного обучения нельзя — алгоритм нужно написать самостоятельно.

Входные данные

В первой строке даны два целых числа n и k — число известных магазинов и число соседей (1 ≤ k ≤ n ≤ 1000, k нечётно).

В каждой из следующих n строк даны два целых числа xi и ci — число домохозяйств рядом с магазином (0 ≤ xi ≤ 105) и его класс (ci равно 0 или 1).

В следующей строке дано целое число m — число новых магазинов (1 ≤ m ≤ 1000). В каждой из следующих m строк дано одно целое число x — число домохозяйств рядом с новым магазином (0 ≤ x ≤ 105).

Выходные данные

Для каждого нового магазина в порядке входных данных выведите в отдельной строке его класс: 0 или 1.

Пример

Ввод Вывод
4 3
1000 0
1400 0
1700 1
2300 1
2
1600
2100
0
1

Пояснение

Известны четыре магазина: (1000, 0), (1400, 0), (1700, 1), (2300, 1), k = 3.

Для x = 1600 расстояния равны 600, 200, 100, 700. Соседи — третий, второй и первый магазины, их классы 1, 0, 0. Нулей больше — ответ 0.

Для x = 2100 расстояния равны 1100, 700, 400, 200. Соседи — четвёртый, третий и второй магазины, их классы 1, 1, 0. Ответ 1.

Подсказка: если классы — это 0 и 1, то сумма классов соседей равна числу голосов «за 1». Класс 1 побеждает, если голосов больше k / 2.


Примеры
№Входные данныеВыходные данные
1
4 3
1000 0
1400 0
1700 1
2300 1
2
1600
2100
0
1
Статистика успешных решений по компиляторам
 Кол-во
Python2