А знаете ли вы, как работают рекомендательные системы? Если нет, то эта задача будет для вас своеобразным введением в данную тему.
Представим, что мы разрабатываем сервис для рекомендации фильмов. Пользователи, просмотревшие некоторый фильм, ставят ему оценку — «Нравится» или «Не нравится».
Пусть теперь некоторый пользователь хочет, чтобы ему посоветовали ещё не просмотренный фильм, который ему наверняка понравится. Попробуем найти пользователей с похожими вкусами и предложить то, что понравилось им.
Более формально, определим коэффициент близости двух пользователей как сумму количества фильмов, которые понравились им обоим, количества фильмов, которые не понравились им обоим, а также количества фильмов, которые они оба ещё не смотрели. Рассчитаем коэффициенты близости для всех пользователей (по отношению к тому пользователю, которому нужно выдать рекомендацию).
Теперь определим рейтинг фильма: каждая положительная оценка увеличивает рейтинг на коэффициент близости того пользователя, который её поставил, а каждая отрицательная оценка уменьшает рейтинг на коэффициент близости того пользователя, который её поставил. Рассчитаем рейтинг для всех непросмотренных фильмов и выведем в качестве рекомендации тот фильм, который имеет наибольшее значение рейтинга.
Сможете ли вы воплотить в жизнь описанный метод получения рекомендаций?
Выходные данные
Выведите номер фильма, рекомендуемого первому пользователю. Если подходящих фильмов несколько, выведите номера каждого из них в возрастающем порядке.
Фильмы нумеруются от 1 до M в порядке описания во входных данных.