No.266 最終進化を目指せ
yuppe19 😺問題文
$P$君は、とあるソーシャルゲームで遊んでいます。
ゲームで使用するカードの強化と進化に関する問題です。
あるキャラクターのカードは最終形態になるまでに $N$ 回進化します。
進化させたいカードに素材を[進化合成]することでカードは進化します。
一回進化するのに必要な素材は、そのキャラクターの未進化形態のカード一枚です。
また、カードには潜在能力があり、$k$ 番目の進化状態のカードの潜在能力は $S_{k}$ 個です。
潜在能力は、同じ進化状態のカードを素材として[強化合成]することで[覚醒]することができます。
新たに[覚醒]する潜在能力の数は、素材として使用するカードが現状で[覚醒]している潜在能力の合計数に $1$ 加えた数です。
ただし、[強化合成]した結果、[覚醒]している潜在能力が、その形態で[覚醒]できる最大の潜在能力を超えた場合、その最大潜在能力数になります。
進化時には、進化するカードが[覚醒]している潜在能力の数は増減しないまま、ひとつ上の形態になります。
進化の素材として使用するカードがいくらかの潜在能力を[覚醒]していても、
[進化合成]では潜在能力の新たな[覚醒]は行われないことに注意しましょう。
上記を踏まえ、ゲームにおいて入手できるのは潜在能力が[覚醒]していない未進化の形態のカードだけであるとする場合、
最終形態のカードを作成するためにはカードを最低何枚入手する必要があるか、
最終形態の[覚醒]している潜在能力の数ごとに求めてください。
入力
$N$
$S_{0}\ S_{1}\ ...\ S_{N}$
$N$ は非負整数。$S_{k} (0 \le k \le N)$ も非負整数。
$0 \le N \le 10$
$0 \le S_{0} \le S_{1} \le ... \le S_{N} \le 10$
出力
最終状態にするための必要なカードの数を潜在能力が未覚醒から全覚醒まで（つまり$S_{N}+1$個）、覚醒数が昇順になる順に空白区切りで出力してください。
最後の数字を出力した後は空白をつけずにそのまま改行してください。
サンプル
サンプル1
入力
3 1 3 6 9
出力
4 5 7 8 11 12 14 16 19 20
一例として、出力例の $5$ 番目の数字 $11$ について説明する。
入手できるカードが $11$ 枚あれば、潜在能力が $4$ つ[覚醒]した最終形態のカードが作成できる。
(1) 未進化(未覚醒) =強化=> 未進化( $1$ 覚醒) =進化=> $2$ 番目の形態( $1$ 覚醒) ... $3枚\times2セット$
(2) 未進化(未覚醒) =進化=> $2$ 番目の形態(未覚醒) ... $2枚$
(3) (1)の1セットと(2)を強化 => $2$ 番目の形態( $2$ 覚醒) =進化=> $3$ 番目の形態( $2$ 覚醒) ... $1枚$
(4) (1)の残りの1セット =進化=> $3$ 番目の形態( $1$ 覚醒) ... $1$ 枚
(5) (3)と(4)を強化 => $3$ 番目の形態( $4$ 覚醒) =進化=> 最終形態( $4$ 覚醒) ... $1$ 枚
合計すると、$3\times2 + 2 + 1 + 1 + 1 = 11$ 枚。
サンプル2
入力
3 0 0 0 0
出力
4
サンプル3
入力
4 0 0 0 0 10
出力
5 10 15 20 25 30 35 40 45 50 55
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。