При покупке товаров в интернет-магазинах все выбранные товары складываются в корзину. При этом покупатели могут забыть добавить какой-нибудь из нужных им товаров.
Для того, чтобы покупатели остались довольны покупкой, а магазин получил больше прибыли существует механизм рекомендаций, который определяет, какие товары обычно покупают вместе с набором уже выбранных. Например, если покупатель положил в корзину ластик, то, наверняка, ему также понадобится карандаш.
Вам необходимо разработать сервис рекомендаций, который по истории предыдущих заказов разработает для покупателя рекомендации, основанные на текущем состоянии его заказа.
Рекомендации должны быть двух типов: "с этим товаром всегда берут следующие товары" и "с этим товаром часто берут следующие товары". При этом "часто" понимается как 50% и более.
Например, если покупатель хочет купить два товара A и B, а предыдущие заказы были вида (A,
D), (B, C, E), (C, F), (C, E, F, G) и (A, B, C, E), то товары C и E надо рекомендовать как те, что
покупается всегда (вместе с товаром B), а D как тот, что покупается часто (50% случаев заказов
с товаром A).
Если товар всегда покупался с одним из заказанных, то необходимо включить в число часто покупаемых и те, которые часто встречаются с этим товаром (не менее чем в 50% случаев) в ранее сделанных заказах. Таким образом, дополнительно к товарам покупаемым часто, добавится товар F, который часто покупается с товаром C. Товар G рекомендовать не нужно, т.к. он встречается меньше, чем в 50% заказов вместе с товаром C.
Не нужно рекомендовать товары, которые уже выбрал покупатель. Если товар можно рекомендовать как "часто" и "всегда", то следует рекомендовать его только как "всегда".
Входные данные
В первой строке входного файла записывается количество старых заказов N. Следующие N строк содержат названия товаров, сделанных в этом заказе. Каждое название состоит из одного слова, слова разделены пробелами. В следующей строке содержится описание текущего заказа: набор названий товаров, разделенных пробелами.
Выходные данные
Для текущего заказа выведите две строки. Первая строка должна содержать названия товаров, которые всегда покупаются вместе с товарами из текущего заказа, вторая с названиями часто покупаемых товаров (соответственно определению часто покупаемых товаров из условия задачи).
Слова следует разделять пробелами. Порядок вывода не важен.
|
Ввод |
Вывод |
5
A D
B C E
C F
C E F G
A B C E
A B |
C E
D F |