Задача J. Байесовский классификатор

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Пусть задано вещественное пространство Rn. Требуется написать программу, классифицирующую точки с использованием байесовского классификатора B(x) = arg maxi = 0,m − 1(πi fNk(μi, Σi)(x)m − 1j = 0,i≠ jλi,j), где m — количество классов, πi — априорная вероятность класса, fNk(μi, Σi) — функция плотности многомерного нормального распределения Nk(μi, Σi) со средним μi и матрицей ковариации Σi, λi,j — штраф за ошибочною классификацию класса i в качестве класса j.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λm строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате xi,0, xi,1, …, xi,n − 1, ci, где xi,j вещественные числа — координаты точки i, ci{0,1,…,m − 1} — класс точки. Последние l строк содержат по n вещественных чисел — координаты точек тестовой выборки.

Формат выходного файла

Выходной файл должен содержать l целых чисел — предсказанные классы точек тестовой выборки.

Ограничения

n{2, 3}

2 ⩽ m ⩽ 9

2 ⩽ k, l ⩽ 103

1 ⩽ λi,j ⩽ 5

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2 6 2
0 1
1 0
1 1 0
1 2 0
2 1 0
-1 -1 1
-1 -2 1
-2 -1 1
2 2
-2 -2
0 1

0.082s 0.015s 15