問題一覧 > 通常問題

No.1808 Fullgold Alchemist

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 155
作問者 : MasKoaTS / テスター : Kanten4205 ygussany
お気に入りにしたユーザー ProblemId : 7006 / 自分の提出
問題文最終更新日: 2024-11-28 18:35:01
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 327 (順位表) の他の問題:

Problem Statement

There are $N$ types of ores numbered $1,2, \dots ,N$, and there are $A_{1},A_{2}, \dots ,A_{N}$ pieces of them, respectively.

The alchemist Koa performs the following action on them any number of times, $0$ or more: "freely choose either one of the following $2$ types of operations and execute it".

  • Choose $1$ pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$, consume $1$ piece of ore $i$, and produce $1$ piece of ore $j$.

  • Consume $M$ pieces each of ores $1,2, \dots ,N$ and produce $1$ gold nugget.

What is the maximum number of gold nuggets Koa can produce?

Constraints

  • $1 \leq N \leq 2 \times 10^{5}$

  • $1 \leq M \leq 10^{9}$

  • $0 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

  • All input values are integers.

Input

The input is given in the following format.

$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
  • Line $1$ contains $N$ and $M$ in this order, separated by half-width spaces.

  • Line $2$ contains $A_{1},A_{2},\dots,A_{N}$ in this order, separated by half-width spaces.

Output

Print the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
4 3
5 3 1 3
Output
1

After repeating the operation of consuming $1$ piece of ore $1$ to produce $1$ piece of ore $3$ a total of $2$ times, consuming $3$ pieces each of ores $1, 2, 3, 4$ produces $1$ gold nugget.

It is not possible to produce $2$ or more gold nuggets.

Sample 2
Input
10 2
9 8 7 6 5 4 3 2 1 0
Output
2
Sample 3
Input
7 10
0 100 100 100 100 100 100
Output
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。