VectorCostSequence
TCCC06 Round 1A · 2006-08-22 · by AdminBrett
TCCC06 Round 1A · 2006-08-22 · by AdminBrett · Brute Force, Simple Math
Problem Statement
Problem Statement
Without consulting your data structures textbook, you have coded up a
homemade Vector class. At any point in time the vector has a
capacity, the maximum number of values it can hold, and a
size, the number of values it currently holds. Typically,
adding or removing an element costs 1. If you attempt to add a value
to the vector when the size and capacity are equal, the capacity is doubled and then
the element is added. This incurs a cost of c+1, where c is the
capacity before the insertion. If removing an element makes the size
exactly half (no rounding) of the capacity, then the cost is only 1,
but the capacity is reduced to the size. Initially, the capacity is 1
and the size is 0. Return the smallest number of additions and
removals that will produce the cost d.
Constraints
- d will be between 1 and 1,000,000,000, inclusive.
Examples
0)
1 Returns: 1
Performing a single addition gives a cost of 1.
1)
2 Returns: 2
Adding an element and then removing it gives a cost of 2.
2)
3 Returns: 2
3)
4 Returns: 3
4)
5 Returns: 4
5)
6 Returns: 3
We can achieve a cost of 6 with 3 additions. The first costs 1, the second costs 2 and the last costs 3.
Submissions are judged against all 81 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class VectorCostSequence with a public method int getSmallest(int d) · 81 test cases · 2 s / 256 MB per case