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

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

Условие

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

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

Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λm строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате xi,0, xi,1, …, xi,n1, ci, где xi,j вещественные числа — координаты точки i, ci{0,1,…,n1} — класс точки. Последние 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.102s 0.017s 15