TopCoder Statistics - Problem Statement

Problem Statement

The banking method is sometimes used to calculate the amortized cost of a process. In our system, every time a value is written to memory, it will cost 1 dollar. We are going to use this system to study the behavior of a dynamic array. The array starts empty with some initial capacity. If an item is added to the array, a memory write occurs, and the cost is 1 dollar. If the item added doesn't fit in the array, a new array is allocated which is twice the size of the previous array. All of the elements from the old array must be copied over, costing 1 dollar for each element copied. Then the new item must be added, costing another dollar. For example, if 3 adds occur to an array with initial capacity 1:

Action     Capacity      Size      Cost Incurred
-------------------------------------------------
Start      capacity = 1  size = 0  (empty)
Add        capacity = 1  size = 1  (cost = 1)
Add        Doesn't fit
 -allocate capacity = 2  size = 0  (empty)
 -copy     capacity = 2  size = 1  (cost = 1)
 -add      capacity = 2  size = 2  (cost = 1)
Add        Doesn't fit
 -allocate capacity = 4  size = 0  (empty)
 -copy     capacity = 4  size = 2  (cost = 2)
 -add      capacity = 4  size = 3  (cost = 1)

So the total cost is 1+1+1+2+1 = 6. Given the initial capacity of the empty array, and the number of adds that occur, return the cost.

Definition

Class:: BankingArray
Method:: addCost
Parameters:: int, int
Returns:: int
Method signature:: int addCost(int initialCapacity, int numAdds)
(be sure your method is public)

Constraints

initialCapacity is between 1 and 1000, inclusive.
numAdds is between 0 and 500000000, inclusive.

Examples

1

3

Returns: 6

From the problem statement.
3

3

Returns: 3

All of the items fit in the array.
1

500000000

Returns: 1036870911

Many adds.
1

0

Returns: 0

No adds.
634

297982078

Returns: 630380036
264

423903158

Returns: 977551022
203

264004014

Returns: 689725667
309

194356621

Returns: 518366296
377

125345147

Returns: 323001346
421

362110707

Returns: 803560782
670

492805262

Returns: 1195350512
366

117974666

Returns: 309863708
888

40454108

Returns: 98649188
990

183048899

Returns: 442570469
233

202416923

Returns: 446734898
769

491203819

Returns: 1297557994
600

358658956

Returns: 987803956
736

12542628

Returns: 36659140
326

24798727

Returns: 67527873
862

700487

Returns: 1582313
976

319280748

Returns: 830984860
784

212945211

Returns: 623986219
172

380164300

Returns: 1101584416
973

308783538

Returns: 818914789
851

443335302

Returns: 889503539
289

180139708

Returns: 483177883
802

474124479

Returns: 1315081629
194

404161883

Returns: 811009177
815

65115579

Returns: 171938444
762

338324759

Returns: 737831453
262

274353231

Returns: 549079881
7

96735512

Returns: 214176017
500

180210803

Returns: 442354303
21

256412875

Returns: 608734390
953

500000000

Returns: 1499291975

Statistics

Problem Statement for "BankingArray"

Problem Statement

Definition

Constraints

Examples