問題一覧 > 通常問題

No.2374 ASKT Subsequences

レベル : / AI推定難易度 : 1275 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 119
作問者 : Kanten4205 / テスター : KowerKoint2010 hibit_at poyon
お気に入りにしたユーザー ProblemId : 9677 / 自分の提出
問題文最終更新日: 2023-07-07 00:44:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 396 (Asakatsu Presents 2) (順位表) の他の問題:

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$.
You are given an integer sequence $A$ of length $N$. Find the number of Asakatsu-type subsequences among the subsequences of the integer sequence $A$. Here, even if $2$ subsequences are the same as integer sequences, they are counted as distinct if they are taken from different positions.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。