No.33 Many Amoebas
nmnmnmnmnmnmnmProblem Statement
There are \(N\) amoebas on a straight line.
Each amoeba is given an initial coordinate.
All initial coordinates are integers.
After one second, an amoeba splits into three.
Then, one of them moves by \(-D\) from its current coordinate.
Another one moves by \(+D\) from its current coordinate.
The last one stays at the same coordinate.
Also, when two or more amoebas are at the same coordinate,
they merge into one.
Find how many amoebas there will be after \(T\) seconds,
starting from the initial \(N\) amoebas.
Input
N D T X0 X1 ... Xn-1
\(1\le N\le 100\) (N is an integer)
\(1\le D \le 10^9\) (D is an integer)
\(1\le T \le10^9\) (T is an integer)
-\(10^9\le Xi \le10^9\) (Xi is the initial position of the i-th amoeba)
Output
Ans
Output Ans, the number of amoebas after T seconds.
Note that the answer does not fit in a 32-bit value.
Do not forget to include a newline.
Sample
Sample 1
Input
2 3 1 0 7
Output
6
Initially, there is 1 amoeba at coordinate 0 and 1 amoeba at coordinate 7.
After 1 second, there are 6 amoebas in total, at coordinates -3, 0, 3, 4, 7, 10.
Sample 2
Input
2 3 2 0 6
Output
7
Initially, there is 1 amoeba at coordinate 0 and 1 amoeba at coordinate 6.
After 1 second, there are 5 amoebas in total, at coordinates -3, 0, 3, 6, 9.
The amoebas at coordinate 3 merged into 1.
After 2 seconds, there are 7 amoebas in total, at coordinates -6, -3, 0, 3, 6, 9, 12.
Sample 3
Input
2 3 1 0 2
Output
6
Initially, there is 1 amoeba at coordinate 0 and 1 amoeba at coordinate 2.
After 1 second, there are 6 amoebas in total, at coordinates -3, -1, 0, 2, 3, 5.
Amoebas do not merge while moving after splitting.
Merging occurs only when they are at the same coordinate.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。