No.2146 2 Pows
タグ : / 解いたユーザー数 26
作問者 :
milkcoffee
/ テスター :
hamamu
nok0
問題文
各要素が $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
出力
150 60 65 80 70 105 85 115 75 100 110 95 90
例えば $k=3$ の場合では、 $S= \{ 16 \}$ のときにコストが最小値になります。
このとき $x=1,y=1,z=4$ であり、コストは $80$ です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。