問題一覧 > 通常問題

No.2146 2 Pows

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 25
作問者 : milkcoffeemilkcoffee / テスター : hamamuhamamu nok0nok0
6 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
出力
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もしくは右上の雲マークをクリックしてアカウントを作成してください。