No.1861 Required Number
タグ : / 解いたユーザー数 99
作問者 :
shiomusubi496
For this problem, we recommend using PyPy instead of Python.
It has been confirmed that the intended solution gets TLE in Python.
Problem Statement
You are given an integer sequence $A = (A_1, A_2,..., A_N)$ of length $N$.
Here, consider a sequence of positive integers $B = (B_1, B_2, \ldots, B_M)$ that satisfies all of the following conditions.
- $1 \leq B_1 < B_2 < \cdots < B_M \leq N$
- $\displaystyle \sum_{i=1}^M A_{B_i} = K$
Determine whether such a $B$ exists. If it does not exist, print -1;
if it exists, print the number of positive integers that are always contained in $B$, no matter how $B$ is chosen.
Input
$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$
The input satisfies the following constraints.
- $1 \leq N \leq 10000 = 10^4$
- $0 \leq K \leq 1000 = 10^3$
- $0 \leq A_i \leq K$ $(1 \leq i \leq N)$
- If $N = 1$, then $K \geq 1$ (added by the administrators on 2026/10/17)
- All input values are integers.
However, since this problem can also be solved under stronger constraints, the following cases are included.
- $1 \leq N \leq 100000 = 10^5$
- $0 \leq K \leq 100000 = 10^5$
- $0 \leq A_i \leq K$ $(1 \leq i \leq N)$
- If $N = 1$, then $K \geq 1$ (added by the administrators on 2026/10/17)
- All input values are integers.
These cases are added as evil cases, so they are judged but do not affect the final verdict. Note that getting them correct does not increase your score.
Output
If no $B$ satisfying the conditions in the problem statement exists, print -1; if one exists, print the number of positive integers that are always contained in $B$, no matter how $B$ is chosen.
Sample
Sample 1
Input
5 12
1 3 5 2 4
Output
2
The sequences $B$ satisfying the conditions are the following:
$(1, 3, 4, 5), (2, 3, 5) $
There are $2$ of them, and the integers contained in both of these $2$ sequences are $3, 5$, so print $2$.
Sample 2
Input
2 1000
8 8
Output
-1
No $B$ satisfying the conditions exists.
Sample 3
Input
3 7
3 3 4
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。