Задача №113350. Машинное обучение
Ваш друг Вася учит машины. Точнее, он занимается машинным обучением, и недавно перед ним поставили задачу: кластеризовать по темам все письма из архива компании. Итогом плодотворной работы по изучению статей и алгоритмов стала программа, реализующая разработанный Васей алгоритм кластеризации.
На вход алгоритм принимает матрицу вхождений — такую таблицу, где строки соответствуют письмам, а столбцы словам. В j -й клетке i -й строки стоит 1 , если слово с номером j содержится в письме с номером i .
Проблема Васи состоит в том, что системные администраторы забыли дать Васе доступ к письмам и уже ушли домой, а результат надо представить начальству уже завтра утром! К счастью, предыдущим заданием Васи было построение поисковой системы по архиву, поэтому у него остался доступ к обратному индексу . В рамках данной задачи обратный индекс — это файл, в каждой строчке которого сначала записано слово, а потом названия писем, в которых это слово встречается.
Ваша задача — построить по данному обратному индексу матрицу вхождений для Васиной задачи, в которой i -я строка будет соответствовать i -му в лексикографическом порядке названию письма. Слова можно пронумеровать как вам удобно — Васин алгоритм классификации не зависит от порядка столбцов.
В первой строке ввода содержится число n ( 1 ≤ n ≤ 100 ) — количество строк в обратном индексе. Cледующие n строк ввода соответствуют строкам обратного индекса. Каждая из них содержит не менее двух и не более 100 слов. Первое слово в строке — это некоторое слово, встречающееся в письмах, следующие слова соответсвуют названиям писем, в которых данное слово встречается. Суммарное количество слов во всех строках не превосходит 1000 .
Все слова имеют длину, не превышающую 10 символов, и состоят из маленьких английских букв. Гарантируется, что первые слова во всех строках попарно различные.
Вам нужно вывести матрицу вхождений слов в письма, то есть матрицу из « 0 » и « 1 », где в i -й строке на j -м месте стоит « 1 », если слово с номером j встречается в письме с номером i . Письма нумеруются в порядке лексикографической сортировки, а нумерацию слов вы выбираете сами. Числа внутри одной строки нужно разделять пробелом, а строки между собой — переводом строки.
Лексикографическим порядком называется порядок следования строк, который можно встретить, например, в словаре. Формально: строка s 1 лексикографически меньше строки s 2 , если выполнено одно из двух условий: либо s 1 является префиксом s 2 , либо в первой позиции, где строки отличаются, в s 1 стоит меньший символ.
3 bob gamea gameb alice gamea mail spam
1 1 0 0 1 0 0 0 1
1 bob gamea gameb
1 1