AtCoder Regular Contest 080
翻译中…
Problem Statement
翻译中…
There are infinitely many cards, numbered $1$, $2$, $3$, $...$ Initially, Cards $x_1$, $x_2$, $...$, $x_N$ are face up, and the others are face down.
翻译中…
Snuke can perform the following operation repeatedly:
翻译中…
- Select a prime
$p$greater than or equal to$3$. Then, select$p$consecutive cards and flip all of them.
翻译中…
Snuke's objective is to have all the cards face down. Find the minimum number of operations required to achieve the objective.
翻译中…
Constraints
翻译中…
$1 ≤ N ≤ 100$$1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7$
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N
x_1 x_2 ... x_N翻译中…
Output
翻译中…
Print the minimum number of operations required to achieve the objective.
翻译中…
样例
Input #1
2
4 5
Output #1
2
Below is one way to achieve the objective in two operations:
- Select $p = 5$ and flip Cards $1$, $2$, $3$, $4$ and $5$.
- Select $p = 3$ and flip Cards $1$, $2$ and $3$.
Input #2
9
1 2 3 4 5 6 7 8 9
Output #2
3
Below is one way to achieve the objective in three operations:
- Select $p = 3$ and flip Cards $1$, $2$ and $3$.
- Select $p = 3$ and flip Cards $4$, $5$ and $6$.
- Select $p = 3$ and flip Cards $7$, $8$ and $9$.
Input #3
2
1 10000000
Output #3
4
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。