CF43C Lucky Tickets

Vasya 认为幸运票是指票号能被 $3$ 整除的票。他收集了很多这样的彩票，但有一天他的小弟 Leonid 闹情绪，决定毁掉这批收藏。首先，他把每张票都准确地撕成两半，但觉得还不够，Leonid 还把其中一部分碎片扔掉了。Vasya 看到后很惊慌，但还是尝试恢复自己的收藏。他选择若干对碎片，每对碎片重新粘合，使得每对都能组成一张幸运票。其他剩下的碎片，Vasya 只好无奈地扔掉。这样，经过 $2t$ 个碎片的粘合后，他最后得到 $t$ 张幸运票，每张都是幸运票。 Leonid 撕票时，一个碎片包含票号的前几位，另一个碎片包含剩下的数字。 Vasya 可以任意选择两片并以任意顺序粘合，但关键是最终结果必须是幸运票。例如，碎片 $123$ 和 $99$ 可以两种方式粘合：$12399$ 或 $99123$。 问：Vasya 最多能拼出多少张幸运票？

第一行包含一个整数 $n$，表示碎片数，满足 $1 \le n \le 10^{4}$。第二行包含 $n$ 个用空格分隔的数字 $a_i$（$1 \le a_i \le 10^{8}$），表示每片碎片上的数字。Vasya 只能将碎片两两配对粘合。即使某片碎片本身已经是幸运票，Vasya 也需要将它和另一片粘合后才算幸运。他不必使用所有碎片。碎片上的数字以及粘合后的票号都可能重复。

输出一个整数，表示最多可以复原出多少张幸运票。请注意，每张幸运票必须由两片碎片粘合而成。

由 ChatGPT 5 翻译