No.2146 2 Pows

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 :

milkcoffee / テスター :

hamamu

nok0

7 ProblemId : 8749 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-11-25 22:34:26

問題文

各要素が $2$ のべき乗数であるような、空でない多重集合 $S$ を考えます。

$2$ のべき乗数とは、非負整数 $i$ を用いて $2^i$ と表せる整数のことを言います。

ここで、 $S$ に含まれる要素数を $x$ 、要素の種類数を $y$ 、要素の最大値を $2^z$ として、 $S$ のコストを $Ax+By+Cz$ と定義します。

例えば、 $S= \{ 1, 1, 2, 8 \}$ であれば、 $x=4, y=3, z=3$ となります。

$N$ 未満の各非負整数 $k$ $(0 \leq k \leq N-1)$ について、以下の問いに答えてください。

$S$ の要素の和を $N$ で割ったあまりが $k$ であるような $S$ を考えます。 $S$ のコストの最小値を求めてください。

入力

 $N$   $A$   $B$   $C$

$2 \leq N \leq 2 \times 10^5$
$1 \leq A,B,C \leq 10^9$
入力は全て整数である

出力

$N$ 行出力してください。
$i$ 行目には、 $k=i-1$ の答えを整数で出力してください。

サンプル

サンプル1

入力

3 5 2 1

出力

15
7
8

$k=0$ の場合：
$S= \{1,2 \}$ のとき、 $x=2,y=2,z=1$ であり、コストは $5 \times 2+2 \times 2 + 1 \times 1=15$ で、これが最小です。
$k=1$ の場合：
$S= \{1 \}$ のとき、 $x=1,y=1,z=0$ であり、コストは $5 \times 1+2 \times 1 + 1 \times 0=7$ で、これが最小です。
$k=2$ の場合：
$S= \{2 \}$ のとき、 $x=1,y=1,z=1$ であり、コストは $5 \times 1+2 \times 1 + 1 \times 1=8$ で、これが最小です。

サンプル2

入力

13 25 35 5

出力

例えば $k=3$ の場合では、 $S= \{ 16 \}$ のときにコストが最小値になります。
このとき $x=1,y=1,z=4$ であり、コストは $80$ です。

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