問題一覧 > 通常問題

No.33 アメーバがたくさん

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 165
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
3 ProblemId : 6 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:18

問題文

\(N\)匹のアメーバが1直線上にいます。
各アメーバには初期座標が与えられます。
初期座標はすべて整数座標です。
アメーバは1秒後に3つに分裂します。
その後、1匹は現在の座標から\(-D\)だけ移動します。
もう1匹は現在の座標から\(+D\)だけ移動します。
最後の1匹はそのままの座標です。
また、アメーバは同じ座標に2匹以上いると、
合体して1匹になります。
最初に\(N\)匹いたアメーバが\(T\)秒後には
何匹になっているか答えなさい。

入力

N D T
X0 X1 ... Xn-1

\(1\le N\le 100\) (Nは整数)
\(1\le D \le 10^9\)(Dは整数)
\(1\le T \le10^9\)(Tは整数)
-\(10^9\le Xi \le10^9\)(Xiはi番目のアメーバの初期位置)

出力

Ans

T秒後のアメーバの数Ansを返してください。
答えは32ビット値におさまらないので注意してください。
改行を入れるのも忘れずに。

サンプル

サンプル1
入力
2 3 1
0 7
出力
6

最初、座標0に1匹、座標7に1匹アメーバがいます。
1秒後、アメーバは座標-3、0、3、4、7、10に合計6匹います。

サンプル2
入力
2 3 2
0 6
出力
7

最初、座標0に1匹、座標6に1匹アメーバがいます。
1秒後、アメーバは座標-3、0、3、6、9に合計5匹います。
座標3でアメーバが合体して1匹になりました。
2秒後、アメーバは座標-6、-3、0、3、6、9、12に合計7匹います。

サンプル3
入力
2 3 1
0 2
出力
6

最初、座標0に1匹、座標2に1匹アメーバがいます。
1秒後、アメーバは座標-3、-1、0、2、3、5に合計6匹います。
分裂後の移動中にアメーバが合体することはありません。
同じ座標にいるときのみ合体が発生します。

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