Точность распознавания птиц по ближайшему наблюдению

В парке ведутся две таблицы наблюдений за птицами. В первой таблице для каждой птицы записаны измерения: размах крыльев, длина клюва и масса. Во второй таблице по тому же идентификатору указаны вид птицы и часть выборки.

Нужно оценить точность метода 1NN на отложенной части. Для птицы из отложенной части методом 1NN выбирается птица из обучающей части с наименьшим расстоянием, после чего ей назначается вид выбранной птицы.

Пусть у птиц a и b известны значения признаков из множества S. Расстояние между ними определяется формулой

d(a, b) = sqrt((sum((a_i - b_i)^2 для i из S)) / |S|).

Признак со значением NA считается пропущенным и не входит в множество S. Обучающая птица, у которой нет ни одного совместно известного признака с рассматриваемой птицей, не участвует в выборе ближайшей. Гарантируется, что для каждой птицы отложенной части найдётся хотя бы одна подходящая обучающая птица.

Если минимальное расстояние достигается у нескольких обучающих птиц, выбирается птица с меньшим идентификатором. Точностью называется доля птиц отложенной части, для которых предсказанный вид совпал с указанным во второй таблице видом: accuracy = correct / q, где q — число птиц отложенной части. Гарантируется, что обучающая и отложенная части непусты.

Формат ввода

В первой строке дано целое число n — число птиц.

В следующих n строках находится первая таблица. Каждая строка содержит четыре значения: id wing beak mass, где id — идентификатор птицы, wing — размах крыльев в сантиметрах, beak — длина клюва в миллиметрах, mass — масса в граммах. Вместо любого из трёх измерений может стоять строка NA.

В следующих n строках находится вторая таблица. Каждая строка содержит три значения: id part species, где id — идентификатор птицы, part равно train или test, species — вид птицы.

Идентификаторы в каждой таблице не повторяются, а множества идентификаторов в двух таблицах совпадают.

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

Выведите точность метода 1NN на птицах с part = test с тремя знаками после десятичной точки.

Ограничения

2 <= n <= 4000.

1 <= id <= 1000000000.

Каждое известное значение wing — целое число от 1 до 300.

Каждое известное значение beak — целое число от 1 до 200.

Каждое известное значение mass — целое число от 1 до 100000.

Длина строки species составляет от 1 до 20 символов. Строка species состоит из строчных латинских букв.

В каждой из частей train и test есть хотя бы одна птица.