Задача 10A. Наивный байесовский классификатор

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Пусть задан некоторый язык, описываемый множеством слов W, |W| = mmN. Требуется построить наивный байесовский классификатор f: B↦ C = {i}k − 1i = 0, где {0, 1}m⊇ B = lN∈ Wlw(μ)|w∈ W} — множество представлений всех возможных сообщений составленных на языке W в виде мешка слов, δw — мера Дирака, δx(A) = {1,x∈ A,0,x∉ A..

При этом процесс классификации происходит следующим образом

  1. Сформировать базовый классификатор с априорными вероятностями классов p(c∈ C) = 1k и условными вероятностями слов p(w∈ W|c∈ C) = 1m;
  2. Для каждого поступившего сообщения μi и его класса ci
    1. Получить предсказание ^ci по μi с использованием текущего классификатора;
    2. Обновить классификатор с использованием сообщения μi и настоящего значения его класса ci.

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

Первая строка входного файла содержит натуральные числа n, m, k — количество сообщений, мощность языка и количество классов соответственно. В каждой их следующих n строк содержится m чисел 0 или 1 и одно натуральное число ci — представление сообщения в виде мешка слов и значение его класса.

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

Выходной файл должен содержать n натуральных чисел — предсказанное значение класса каждого сообщения на момент его получения.

Ограничения

10⩽ n⩽ 7500

8⩽ m⩽ 100

2⩽ k⩽ 10

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

Стандартный вход Стандартный выход
1
10 8 2
0 1 1 1 1 0 0 1 1
1 0 1 0 0 1 0 0 0
1 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0
0 1 0 1 1 1 1 0 1
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 1 1
1 0 0 0 0 1 0 1 0
1 1 1 1 0 1 1 1 0
0 1 0 1 1 0 0 0 1
0
0
1
0
1
0
1
0
1
1

0.063s 0.012s 15