No.2374 ASKT Subsequences
タグ : / 解いたユーザー数 119
作問者 :
KowerKoint2010
hibit_at
poyon
Problem Statement
For an integer sequence, a (not necessarily contiguous) subsequence $(a_1, a_2, a_3, a_4)$ of length $4$ is called an Asakatsu-type subsequence if it satisfies the following condition.
- There exists a positive integer $k$ such that $a_2 = a_1 + (k + 10), a_3 = a_2 - k, a_4 = a_3 + (k + 1)$ all hold for this $k$.
Input
$N$ $A_1\ A_2\ \cdots \ A_N$
- $4 \leq N \leq 2000$
- $1 \leq A_i \leq 2000\ (1 \leq i \leq N)$
- All inputs are integers.
Output
Print on $1$ line the number of Asakatsu-type subsequences among the subsequences of the integer sequence $A$.
Sample
Sample 1
Input
4 1 15 11 16
Output
1
The subsequence $(A_1, A_2, A_3, A_4)$ is an Asakatsu-type subsequence, because with $k = 4$ we have $A_2 = A_1 + (4 + 10),\ A_3 = A_2 - 4, A_4 = A_3 + (4 + 1)$, which satisfies the condition in the problem statement.
Among the subsequences of the integer sequence $A$, this is the only Asakatsu-type subsequence, so print $1$.
Sample 2
Input
10 1 19 4 14 11 50 15 20 11 20
Output
4
Each of the following $4$ subsequences is an Asakatsu-type subsequence.
- $(A_1, A_2, A_5, A_8)=(1,19,11,20)\ \cdots\ k = 8$ satisfies the condition.
- $(A_1, A_2, A_5, A_{10})=(1,19,11,20)\ \cdots\ k = 8$ satisfies the condition.
- $(A_1, A_2, A_9, A_{10})=(1,19,11,20)\ \cdots\ k = 8$ satisfies the condition.
- $(A_1, A_4, A_5, A_7)=(1,14,11,15)\ \cdots\ k = 3$ satisfies the condition.
Sample 3
Input
10 1 1 1 1 1 1 1 1 1 1
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。