実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
1 から N の番号がついた N 人の人がいます。
人 i はキーエンス本社ビルの建築面積を S_i 平方メートルであると予想しました。
キーエンス本社ビルは下図のような形をしています。ただし、a,b はある 正の整数 です。
つまり、キーエンス本社ビルの建築面積は 4ab+3a+3b 平方メートルと表されます。
N 人のうち、この情報のみによって、予想した面積が確実に誤りであるとわかる人数を求めてください。
制約
- 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
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?
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