[基础训练营-后期-第一周-T7] 数迷

题目描述

小 A 有 $n$ 个正整数 $a_1,a_2,\dots,a_n$。他想将正整数 $a_i$ 变为一个可以被 $4$ 整除的正整数。

他定义一次操作为：

• 选定两个数位 $l,r$，将从前往后第 $l$ 位到第 $r$ 位全部删除，剩下的数保留原来顺序地组成一个新的整数。
• 例如说：对于正整数 $31415926$，选定 $l=5,r=7$ 进行删除，则剩下的数为 $31416$，其恰为可以被 $4$ 整除的正整数。
• 数位不能全部删除，例如对于 $31415926$，不能选定 $l=1,r=8$。

小 A 对于每个正整数，最多只想进行一次操作。小 A 想要知道以下两个问题的答案：

• 一共有多少个正整数可以在不超过一次操作的情况下变为能够被 $4$ 整除的数；
• 在满足上一个问题的情况下，他至少累计要操作几次？

输入格式

第一行输入一个正整数 $n$，表示正整数个数；

第二行开始，往下 $n$ 行，每行输入一个正整数，表示 $a_i$。

输出格式

输出两行：

• 第一行一个整数表示，一共有多少个正整数可以在不超过一次操作的情况下变为能够被 $4$ 整除的数。
• 第二行一个整数表示，在满足上一个问题的情况下，他至少累计要操作几次。

样例 #1

样例输入 #1

4
1236
114
81
15

样例输出 #1

3
2

提示

【样例解释】

• 对于 $1236$，不需要进行任何操作已经是 $4$ 的倍数；
• 对于 $114$，令 $l=1,r=2$，将数字变为 $4$，即可为 $4$ 的倍数；
• 对于 $81$，令 $l=r=2$，将数字变为 $8$，即可为 $4$ 的倍数；
• 对于 $15$，其无法成为 $4$ 的倍数。

一共有 $3$ 个正整数可以在不超过一次操作的情况下变为能够被 $4$ 整除的数。在这种情况下，小 A 最少只要进行 $2$ 次操作。因此输出分别为 $3$ 和 $2$。

【数据范围】

• 对于前 $30\%$ 的数据，保证 $1\le n\le 10$，$1\le a_i\le 100$。
• 对于前 $60\%$ 的数据，保证 $1\le n\le 10$，$1\le a_i\le 10^9$。
• 对于 $100\%$ 的数据，$1\le n\le 100$，$1\le a_i\le 10^{18}$。