← 返回题目列表

Codeforces · 1166/A

A. 寂静的课堂

中文机器翻译题面 查看原题

Nlogonia 高中一年级有 $$$n$$$ 名学生。校长希望将学生分成两个教室(每个学生必须位于其中一间教室)。如果两个名字以相同字母开头的不同学生被放在同一间教室,他们会很健谈(因为他们一定有很多共同点)。令 $$$x$$$ 为分组中此类学生对的数量。对 $$$(a, b)$$$ 和 $$$(b, a)$$$ 是相同的,并且只计算一次。

例如,如果有 $$$6$$$ 学生:“olivia”、“jacob”、“tanya”、“jack”、“oliver”和“jessica”,则:

- 分成两个教室(“jack”、“jacob”、“jessica”、“tanya”)和(“olivia”、“oliver”)将给出 $$$x=4$$$ (第一个教室中的 $$$3$$$ 聊天对,第二个教室中的 $$$1$$$ 聊天对),
- 分成两个教室(“jack”、“tanya”、“olivia”)和(“jessica”、“oliver”、“jacob”)将给出 $$$x=1$$$(第一个教室中的 $$$0$$$ 聊天对,第二个教室中的 $$$1$$$ 聊天对)。

您将获得 $$$n$$$ 名称的列表。通过将学生分成教室,我们可以获得的最低 $$$x$$$ 是多少?

请注意,将所有学生安排在其中一间教室,而另一间教室空着是有效的。

输入

第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 100$$$) — 学生人数。

在 $$$n$$$ 行之后。

第 $$$i$$$ 行包含第 $$$i$$$ 学生的姓名。

保证每个名称都是一串小写英文字母,长度最多$$$20$$$。请注意,多个学生可能具有相同的姓名。

输出

输出必须包含单个整数 $$$x$$$ — 闲聊对的最小可能数量。

示例

输入 #1

4
jorge
jose
oscar
jerry

输出 #1

1

输入 #2

7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo

输出 #2

2

输入 #3

5
mike
mike
mike
mike
mike

输出 #3

4

注意

在第一个样本中,最小对数为 $$$1$$$。例如,可以通过将除何塞以外的所有人都安排在一个教室,将何塞安排在另一间教室,这样豪尔赫和杰瑞就成为唯一健谈的一对来实现这一点。

在第二个样本中,最小配对数为 $$$2$$$。例如,这可以通过将神兵卫、五郎兵卫、七郎寺和久三放在一个房间中,并将平八、胜四郎和菊千代放在另一个房间来实现。在这种情况下,这两对是 kambei 和 kyuzo,以及 katsushiro 和 kikuchiyo。

在第三个样本中,最小配对数为 $$$4$$$。这可以通过将三名名叫 mike 的学生安排在一间教室,将另外两名学生安排在另一间教室来实现。因此,一间教室将有三对闲聊,而另一间教室将有一对闲聊。