luogu#P11137. [APC001] B - Checker

[APC001] B - Checker

题目背景

小 K 正在出公开赛。他有一个 idea,但他担心重题,因此,他需要确认这题是不是重题。不过他还有很多事情要做,因此他把这个任务交给了你。

题目描述

题库里共有 n n 道题目,每道题目的名称都是一个长度不足 10 10 的字符串。设题目名称长度为 kk,我们定义两道题为重题当且仅当两道题题目名称有 k2\ge \left\lceil\frac{k}{2} \right\rceil 的相同位置的字符相同。

现在小 K 把这道题交给了你,希望你帮他查重(即,将自己的题目与其他的题目进行一一比对,判断是否为重题)。

输入格式

先输入一个正整数 n n 表示题库中的题目数量,之后输入一个字符串 s s 表示小 K 出的题目的名称。

之后 n n 行每行一个字符串表示这些题目的名称。

输入的每个字符串长度相同。

输出格式

两行,第一行输出重题数量,若没有重题则第二行输出 Good job!,否则输出 Make persistent efforts.

3
chachong
abcabcat
chocolat
noiprp++
0
Good job!
10
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
apc001_b
10
Make persistent efforts.
25
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0
Good job!

提示

【样例解释 #1】

题目名为 chachong,与第一题中的 0 0 个字符相同,与第二题中的 3 3 个字符相同,与第三题中的 00 个字符相同,而每题都有 8 8 个字符,没有与小 K 出的题目有大于等于 8×50%=4 8 \times 50\% = 4 个字符相同的题目。

【样例解释 #2】

请注意有可能在题库中也包含重题。

【数据规模】

对于 100%100\% 的数据,保证 1n104,1k10 1 \le n \le 10^4 ,1\le k\le10,每个字符串长度相同,且不含不可见字符。