Problem Statement
You are playing a game with Goblin Rabblemasters in Magic: the Gathering.
You are going to play T turns of the game. In the beginning of each turn you will add one new Goblin Rabblemaster to your army.
Goblin Rabblemaster is a creature with the following properties:
- It attacks each turn, except for the turn it entered the game.
- Whenever it attacks, it deals (2+G) damage, where G is the number of other goblins of any kind who attack that turn.
- Each turn (including the turn it entered the game), immediately before your goblins attack, Goblin Rabblemaster adds an ordinary Goblin to your army.
An ordinary Goblin is a creature with the following properties:
- It attacks each turn, including the turn when it entered the game.
- Whenever it attacks, it deals 1 damage.
Calculate and return the total amount of damage your goblins will deal during the game.
Definition
- Class:
- GoblinRabblemaster
- Method:
- totalDamage
- Parameters:
- int
- Returns:
- long
- Method signature:
- long totalDamage(int T)
- (be sure your method is public)
Constraints
- T will be between 1 and 47,000, inclusive.
Examples
1
Returns: 1
Turn 1: You add a Goblin Rabblemaster. The Rabblemaster adds an ordinary Goblin. The Goblin attacks and deals 1 damage.
3
Returns: 33
Turn 1: You add a Goblin Rabblemaster. The Rabblemaster adds an ordinary Goblin. The Goblin attacks and deals 1 damage. Turn 2: You add a second Goblin Rabblemaster. Each Rabblemaster adds an ordinary Goblin. Three Goblins and the first Rabblemaster attack together. Each Goblin deals 1 damage, and the Rabblemaster deals (2+3) = 5 damage. Turn 3: You add a third Goblin Rabblemaster. Each Rabblemaster adds an ordinary Goblin. Six Goblins and two Rabblemasters attack. Each Rabblemaster sees 7 other attacking goblins and deals (2+7) = 9 damage. Total damage dealt each turn is 1, 8, and 24 for a grand total of 33 damage.
6
Returns: 336
2
Returns: 9
4
Returns: 85
5
Returns: 180
9
Returns: 1395
34632
Returns: 179843828988917574
47000
Returns: 610037993078363250
3455
Returns: 17842507022880
32677
Returns: 142547124990728284
44444
Returns: 487776862341098415
40000
Returns: 320048000599990000
470
Returns: 6177551220
The answer for any valid test case is guaranteed to fit into a signed 64-bit integer variable. Watch out for integer overflow, variables with a smaller range of values are not sufficient.
45678
Returns: 544246164414765258