102271: [AtCoder]ABC227 B - KEYENCE building

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $200$ points

Problem Statement

There are $N$ people numbered $1$ to $N$.

Person $i$ guessed the building area of KEYENCE headquarters building to be $S_i$ square meters.

The shape of KEYENCE headquarters building is shown below, where $a$ and $b$ are some positive integers.
That is, the building area of the building can be represented as $4ab+3a+3b$.

Based on just this information, how many of the $N$ people are guaranteed to be wrong in their guesses?

Sketch of KEYENCE headquarters building

Constraints

  • $1 \leq N \leq 20$
  • $1 \leq S_i \leq 1000$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$S_1$ $\ldots$ $S_N$

Output

Print the answer.


Sample Input 1

3
10 20 39

Sample Output 1

1

The area would be $10$ square meters if $a=1,b=1$, and $39$ square meters if $a=2,b=3$.

However, no pair of positive integers $a$ and $b$ would make the area $20$ square meters.

Thus, we can only be sure that Person $2$ guessed wrong.


Sample Input 2

5
666 777 888 777 666

Sample Output 2

3

Input

题意翻译

有 $n$ 个正整数,记第 $i$ 个数为 $s_i$ 。求有多少个 $i$ 满足:不定方程 $4ab+3a+3b=s_i$ 无正整数解?

Output

得分:$200$分

问题描述

有$N$个人,编号为$1$到$N$。

第$i$个人猜测KEYENCE总部大楼的建筑面积为$S_i$平方米。

KEYENCE总部大楼的形状如下图所示,其中$a$和$b$是一些正整数
也就是说,该建筑的建筑面积可以用$4ab+3a+3b$来表示。

仅根据这些信息,有多少人肯定猜错了他们的猜测?

KEYENCE总部大楼草图

约束条件

  • $1 \leq N \leq 20$
  • $1 \leq S_i \leq 1000$
  • 输入中的所有值都是整数。

输入

输入通过标准输入给出,格式如下:

$N$
$S_1$ $\ldots$ $S_N$

输出

输出答案。


样例输入1

3
10 20 39

样例输出1

1

如果$a=1,b=1$,建筑面积为$10$平方米;如果$a=2,b=3$,建筑面积为$39$平方米。

但是,没有任何一对正整数$a$和$b$可以使建筑面积为$20$平方米。

因此,我们只能确定第$2$个人猜错了。


样例输入2

5
666 777 888 777 666

样例输出2

3

加入题单

上一题 下一题 算法标签: