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

Задача . Как называется цвет


Задача

Темы:

Цвет на экране задаётся тремя числами от 0 до 255 — яркостью красной, зелёной и синей составляющих (RGB). Есть n эталонных цветов с названиями. Определите название новых цветов методом k ближайших соседей с голосованием:

  1. расстояние между цветами (r1, g1, b1) и (r2, g2, b2) — евклидово; для сравнения достаточно его квадрата (r1 − r2)² + (g1 − g2)² + (b1 − b2)²;
  2. эталоны упорядочиваются по возрастанию расстояния; при равных расстояниях раньше идёт эталон, который стоит раньше во входных данных; первые k — соседи;
  3. каждый сосед голосует за своё название; побеждает название с наибольшим числом голосов;
  4. если таких названий несколько, побеждает то из них, чей ближайший представитель стоит раньше в списке соседей.

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

В первой строке — n и k (1 ≤ k ≤ n ≤ 1500). В каждой из следующих n строк — три целых числа от 0 до 255 и название: одно слово из русских или латинских букв. Затем число m (1 ≤ m ≤ 1000) и m строк по три целых числа от 0 до 255.

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

Для каждого нового цвета в отдельной строке — его название.

Пример

Ввод Вывод
6 3
255 0 0 красный
200 0 0 красный
0 0 255 синий
0 0 200 синий
255 255 0 жёлтый
220 220 0 жёлтый
3
230 20 20
40 40 220
240 200 10
красный
синий
жёлтый

Пояснение

Цвет (240, 200, 10): три ближайших эталона — два жёлтых и один красный. Жёлтых голосов больше — ответ «жёлтый».

Подсказка: голоса удобно считать в словаре {название: число голосов}.


Примеры
№Входные данныеВыходные данные
1
6 3
255 0 0 красный
200 0 0 красный
0 0 255 синий
0 0 200 синий
255 255 0 жёлтый
220 220 0 жёлтый
3
230 20 20
40 40 220
240 200 10
красный
синий
жёлтый
Статистика успешных решений по компиляторам
 Кол-во
Python2