Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

関連商品

インターネット通販サイトでは、ユーザが現在見ている商品と同じページに、過去に他のユーザによって、現在見ている商品と一緒に買われた別の商品をいくつか表示してくれます。関連性の高いと思われる商品を提示することで、売り上げを伸ばすことができると考えられているからです。

似たようなことは、一緒に買われることが多い商品を近くに配置する、という工夫として、近所のスーパーマーケットでも目にすることができます（例えば、パンとジャムのような）。あなたの仕事は、商品配置の工夫を助けるプログラムを書くことです。今回は、ある基準となる回数を設定し、一緒に買われた回数が基準回数以上である、２つの商品の組み合わせを求めたいと思います。

一緒に買われた商品の情報と基準回数が与えられたとき、基準回数以上一緒に買われた商品２つの組み合わせを出力するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N F
info1
info2
:
infoN

１行目に、一緒に買われた商品の情報の数 N (1 ≤ N ≤ 100) と、基準回数 F (1 ≤ F ≤ 100) が与えられる。続く N行に、一緒に買われた商品の情報が与えられる。一緒に買われた商品の情報 infoi は、以下の形式で与えられる。

M item1 item2 ...  itemM

M (1 ≤ M ≤ 10) は、この情報がいくつの商品を含むかを表す。itemj は、この買い物で買われた商品の名前であり、英小文字だけから成る長さ 1 以上 30 以下の文字列である。infoi の中に同じ商品が与えられることはない。

Output

１行目に基準回数以上一緒に買われた商品２つの組み合わせの数を出力し、２行目以降に組み合わせをすべて出力する。ただし、組み合わせが一つもない場合は２行目以降には何も出力しない。

出力の順番は、組み合わせ内の商品名どうしを、辞書式順序（英和辞書で単語が並んでいる順番）で並べたあと、組み合わせどうしについては以下のようにする。

 一つ目の商品名どうしを比較して、辞書式順序で早いほうが先。

 同じ場合は、二つ目の商品名どうしを比較して、辞書式順序で早いほうが先。

商品名はスペース一つで区切り、商品の組み合わせは改行一つで区切る。

Sample Input 1

5 2
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread

Sample Output 1

3
bread milk
bread potato
cornflakes milk

Sample Input 2

5 5
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread

Sample Output 2

0



Sample input:
5 2
3 bread milk banana
2 milk cornflakes
3 potato bread milk
4 cornflakes bread milk butter
2 potato bread


Sample output:
3
bread milk
bread potato
cornflakes milk

Submission status: Wrong Answer

Solution code:

N,F = [int(i) for i in input().split()]

itemsets = []

for l in range(N):
    items = input().split()
    M = int(items.pop(0))
    
    items.sort()

    for i in range(len(items)):
        for j in range(i+1, len(items)):
            itemsets.append(items[i] + " " + items[j])

itemsets.sort()
    
cnt = 1
ans = []
ans.append("")
for i in range(1, len(itemsets)):
    if itemsets[i] == itemsets[i-1]:
        cnt = cnt + 1
        if cnt >= F and itemsets[i] != ans[-1]:
            ans.append(itemsets[i])
    else:
        cnt = 1
        if F == 1:
            ans.append(itemsets[i])

ans.pop(0)
print(len(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import Counter
counter = Counter()
n, f = map(int, input().split())
for _ in range(n):
  items = input().split()
  m = int(items[0])
  items = items[1:]
  items.sort()
  for i in range(m):
    for j in range(i + 1, m):
      counter[(items[i], items[j])] += 1

lst = [(k, v) for k, v in counter.most_common() if v >= f]
lst.sort()
lst.sort(key=lambda t:-t[1])
print(len(lst))
for k, v in lst:
  print(*k)

Submission status: Accepted

Solution code:

N,F = [int(i) for i in input().split()]

itemsets = []

for l in range(N):
    items = input().split()
    M = int(items.pop(0))
    
    items.sort()

    for i in range(len(items)):
        for j in range(i+1, len(items)):
            itemsets.append(items[i] + " " + items[j])

itemsets.sort()
    
cnt = 1
ans = []
if F > 1:
    ans.append("")
    for i in range(1, len(itemsets)):
        if itemsets[i] == itemsets[i-1]:
            cnt = cnt + 1
            if cnt >= F and itemsets[i] != ans[-1]:
                ans.append(itemsets[i])
        else:
            cnt = 1
    ans.pop(0)
else:
    ans = itemsets

print(len(ans))
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
from itertools import combinations
N, F= map(int, input().split())
goods= [sorted(g) for _ in range(N) for g in list(combinations(list(map(str, input().split()))[1:], 2))]
sets=set((g[0], g[1]) for g in goods)
s= [(s[0], s[1]) for s in sets if goods.count([s[0], s[1]])>=F]
n= [sum(1 for s in sets if goods.count([s[0], s[1]])>=F)]

for a in n:
    print(a)
else:
    if n[0]!=0:
        for t in sorted(sorted(s, key=lambda x: x[1])):
            print(*t)

Submission status: Accepted

Solution code:
n, f = map(int, input().split())
pair = {}
for i in range(n):
    m, *items = input().split()
    m = int(m)
    for p in range(m):
        for q in range(p):
            key = tuple(sorted([items[p], items[q]]))
            pair[key] = pair.get(key, 0) + 1
ans = sorted(key for key in pair if pair[key] >= f)
print(len(ans))
if ans:
    for a, b in ans:
        print(a, b)

Submission status: Accepted

Solution code:
import sys

l = input().split()
f = int(l[1])

t = {}

for l in sys.stdin:
    e = l.split()
    m = int(e.pop(0))
    s = sorted(e)
    for i in range(m):
        for j in range(i+1,m):
            k = (s[i],s[j])
            if k in t:
                t[k] += 1
            else:
                t[k] =  1

f = list(sorted(filter(lambda x: t[x] >= f, t)))
print(len(f))
for e in f:
    print("{0:s} {1:s}".format(e[0],e[1]))

Submission status: Accepted

Solution code:
n, f = map(int, input().split())
a = {}
for _ in range(n):
    m, *c = input().split()
    m = int(m)
    for i in range(m - 1):
        for j in range(i + 1, m):
            p = (min(c[i], c[j]), max(c[i], c[j]))
            if p in a:a[p] += 1
            else:a[p] = 1
b = []
for k in a:
    if a[k] >= f:b.append((k,a[k]))
b.sort(key = lambda x:x[0][1])
b.sort(key = lambda x:x[0][0])
print(len(b))
for i in b:print(*i[0])

Submission status: Accepted

Solution code:
from collections import Counter
counter = Counter()
n, f = map(int, input().split())
for _ in range(n):
  items = input().split()
  m = int(items[0])
  items = items[1:]
  items.sort()
  for i in range(m):
    for j in range(i + 1, m):
      counter[(items[i], items[j])] += 1

lst = [(k, v) for k, v in counter.most_common() if v >= f]
lst.sort()
print(len(lst))
for k, v in lst:
  print(*k)

Submission status: Accepted

Solution code:
N, F = map(int, input().split())
data = []
tmp = {}
for i in range(N) :
    data.append(list(input().split()))
    for x in range(1, len(data[i]) - 1) :
        for y in range(x+1, len(data[i])) :
            a = data[i][x]
            b = data[i][y]
            a, b = min(a, b), max(a, b)
            if (a, b) not in tmp :
                tmp[(a, b)] = 1
            else :
                tmp[(a, b)] += 1

ans = []
for k in tmp :
    if tmp[k] >= F :
        ans.append(list(k))

ans = sorted(ans, key = lambda x: x[1])
ans = sorted(ans)
print(len(ans))
if len(ans) != 0 :
    for i in range(len(ans)) :
        print(*ans[i])

Submission status: Accepted

Solution code:
N, F = map(int, input().split())
data = []
tmp = {}
for i in range(N) :
    data.append(list(input().split()))
    for x in range(1, len(data[i]) - 1) :
        for y in range(x+1, len(data[i])) :
            a = data[i][x]
            b = data[i][y]
            a, b = min(a, b), max(a, b)
            if (a, b) not in tmp :
                tmp[(a, b)] = 1
            else :
                tmp[(a, b)] += 1

ans = []
for k in tmp :
    if tmp[k] >= F :
        ans.append(list(k))

ans = sorted(ans, key = lambda x: x[1])
ans = sorted(ans)
print(len(ans))
if len(ans) != 0 :
    for i in range(len(ans)) :
        print(*ans[i])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
#sys.setrecursionlimit(3**12)


class Info:
    def __init__(self,arg_item_A,arg_item_B):
        self.item_A = arg_item_A
        self.item_B = arg_item_B
        if self.item_B < self.item_A:
            self.item_A,self.item_B = self.item_B,self.item_A

    def __lt__(self,another):
        if self.item_A != another.item_A:
            return self.item_A < another.item_A
        else:
            return self.item_B < another.item_B


SIZE = 1000

N,F = map(int,input().split())
num_item = 0
ITEM = {}
rev_ITEM = {}

table = [[0]*SIZE for _ in range(SIZE)]

for _ in range(N):
    M,*input_str = map(str,input().split())
    M = int(M)
    for i in range(M):
        if input_str[i] not in ITEM:
            ITEM[input_str[i]] = num_item
            rev_ITEM[num_item] = input_str[i]
            num_item += 1
    for i in range(M-1):
        for k in range(i+1,M):
            table[ITEM[input_str[i]]][ITEM[input_str[k]]] += 1
            table[ITEM[input_str[k]]][ITEM[input_str[i]]] += 1

ANS = []

for i in range(num_item-1):
    for k in range(i+1,num_item):
        if table[i][k] >= F:
            ANS.append(Info(rev_ITEM[i],rev_ITEM[k]))

print("%d"%(len(ANS)))
ANS.sort()

for i in range(len(ANS)):
    print("%s %s"%(ANS[i].item_A,ANS[i].item_B))

Submission status: Accepted

Solution code:

def combinations(l):
    sl = sorted(l)
    r = range(len(sl)-1)
    for i in r:
        for j in range(i+1, len(sl)):
            yield (sl[i], sl[j])


m,n = [ int(s) for s in input().split() ]
d = {}

for i in range(m):
    l = input().split()[1:]
    for e in combinations(l):
        if e in d:
            d[e] += 1
        else:
            d[e] = 1
sl = sorted([e[0][0] + " " + e[0][1] for e in d.items() if e[1] >= n])
print(len(sl))
for i in sl:
    print(i)