No.3433 [Cherry 8th Tune A] ADD OIL!
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : 👑
Kazun
/ テスター :
kazuppa
タグ : / 解いたユーザー数 55
作問者 : 👑
Kazun
/ テスター :
kazuppa
問題文最終更新日: 2026-01-23 00:37:55
問題ヴィジュアル
▶ オープンで問題ヴィジュアル公開
問題文
$N$ 個のギアからなる機械がある. $i~(1 \leq i \leq N)$ 番目のギアのコストは $A_i$ である. また, この機械のコストを $N$ 個のギアの総積 (掛け算)で定義する.
チェリーちゃんは潤滑油を持っている. 機械にあるギアに対してこの潤滑油を使うと, 使用先のギアのコストが $K$ だけ下がる. ただし, この潤滑油は $1$ つのギアに対してしか使えない.
潤滑油を使用した後にあり得る機械のコストの最小値を求めよ.
$T$ 個のテストケースについて答えよ.
制約
- $1 \leq T \leq 100$.
- 各テストケースに対する制約
- $2 \leq N \leq 8$.
- $1 \leq K \lt 100$.
- $K \lt A_i \leq 100 \quad (1 \leq i \leq N)$.
- 入力は全て整数である.
入力
入力は以下の形式で標準入力から与えられる.
$T$
${\rm Testcase}_1$
$\vdots$
${\rm Testcase}_T$
各テストケースは以下の形式で与えられる.
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
出力
出力は $T$ 行からなる. 第 $t~(1 \leq t \leq T)$ 行目には第 $t$ テストケースに対する解答を整数で出力せよ.
最後に改行を忘れないこと.
サンプル
サンプル1
入力
3 3 5 10 20 30 6 99 100 100 100 100 100 100 2 1 3 23
出力
3000 10000000000 46
[第 $1$ テストケースについて]
機械には $3$ 個のギアがある. それぞれのギアに対して潤滑油を使った場合における機械のコストの変化は次の様になる.
- $1$ 番目のギアに潤滑油を使った場合, $1$ 番目のギアのコストは $10 - 5 = 5$ になる. よって, 機械のコストは $5 \times 20 \times 30 = 3000$ になる.
- $2$ 番目のギアに潤滑油を使った場合, $2$ 番目のギアのコストは $20 - 5 = 15$ になる. よって, 機械のコストは $10 \times 15 \times 30 = 4500$ になる.
- $3$ 番目のギアに潤滑油を使った場合, $3$ 番目のギアのコストは $30 - 5 = 25$ になる. よって, 機械のコストは $10 \times 20 \times 25 = 5000$ になる.
以上から, $1$ 番目のギアに潤滑油を使う場合が機械のコストが最小になる. そして, その場合のコストは $3000$ である.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。