キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）
翻译中…
Problem Statement
翻译中…
All KEYENCE product names consist of two uppercase English letters.
They have already used $N$ product names, the $i$-th of which $(1\leq i\leq N)$ is $S_i$.
Once a product name is used, it cannot be reused, so they decided to create an NG (Not Good) list to quickly identify previously used product names.
翻译中…
The NG list must satisfy the following conditions.
翻译中…
- It consists of one or more strings, each consisting of uppercase English letters.
- For each already used product name, there exists at least one string in the list that contains the name as a (contiguous) substring.
- None of the strings in the list contain any length-
$2$(contiguous) substring that is not an already used product name.
翻译中…
Find the minimum possible number of strings in the NG list.
翻译中…
Constraints
翻译中…
$1\leq N\leq 26^2$$N$is an integer.- Each
$S_i$is a string of length$2$consisting of uppercase English letters. - All
$S_1,S_2,\ldots,S_N$are distinct.
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N
S_1
S_2
\vdots
S_N翻译中…
Output
翻译中…
Print the minimum possible number of strings in the NG list.
翻译中…
样例
Input #1
7
AB
BC
CA
CD
DE
DF
XX
Output #1
3
One NG list satisfying the conditions is the one consisting of the following three strings:
- `CABCDE`
- `DF`
- `XX`
This has three strings, and there is no NG list satisfying the conditions with $2$ or fewer strings, so print $3$.
Input #2
5
AC
BC
CD
DE
DF
Output #2
2
One NG list satisfying the conditions is the one consisting of the following two strings:
- `ACDE`
- `BCDF`
Note that each used product name may appear in multiple strings in the NG list or multiple times within the same string.
Input #3
6
AB
AC
CB
AD
DB
BA
Output #3
1
For example, an NG list consisting only of `ABACBADB` satisfies the conditions.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。