差异 - المسألة

#10351. 差异

الإحصائيات

对于一个集合 $S$，我们可以把其中所有元素从小往大排序，我们定义这个集合的差异值为排好序后，相邻两个数的差的最大值

你有 $Q$ 个差异值不超过 $K$ 非负整数集合，已知每个集合中最小元素为 $0$，最大元素为 $N+1$

现在已知给出 $1$ 到 $N$ 每个元素在 $Q$ 个集合中的出现次数对$M$取模的结果，求在满足条件的情况下， $Q$ 的最小值是多少，无解请输出 -1

输入描述

第一行三个整数 $N$, $K$, $M$ 接下来一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 个元素的出现次数对 $M$ 取模的结果

输出描述

一行一个整数表示 $Q$ 的最小值，无解输出 -1

样例输入1

3 2 8
0 0 1

样例输出1

样例输入2

3 1 9
2 3 3

样例输出2

-1

数据范围

对于10%的数据， $K = 1$

对于另外10%的数据， $K = 2$ 且 $N = 5$

对于另外20%的数据， $K = 2$ 且 $N \leq 50$

对于另外15%的数据，保证答案小于$M$，且$N \leq 50$

对于另外25%的数据， $N \leq 20$

对于100%的数据， $1 \leq N \leq 500000, 1 \leq K \leq N, 2 \leq M \leq 10^9$

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0