- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: August, 2010 -
**Competitors who opened the problem**: 755 -
**Competitors who submitted a solution**: 709 -
**Number of correct solutions**: 694 -
**Accuracy (percentage correct vs those who opened)**: 91.9% -
**Average Correct Time**: 9 minutes, 35 seconds.

First off, you need to figure out -- given a collection of numbers, which number do I increment so that the product is increased by the largest amount? It shouldn't be too hard to see that you need to increment the smallest number.

[If you want to prove that formally, you can. Suppose you have a collection of numbers whose
product is *P*. And suppose you have two numbers in the collection, *a* and *b*
such that *a < b*.
If you increment *a*, you change the product from *P* to *P(a+1)/a*.
If you increment *b*, you change the product to *P(b+1)/b*. Since
*a < b*,
we know that *(a+1)/a > (b+1)/b*. (If you are stuck on that, think about examples: 3/2 is definitely greater than 101/100, right?) That means incrementing *a* will increase the
factor by the greatest amount.]

So, you need to find the minimum element and increment it. I would do that by sorting the vector and then incrementing the first element.

Now how about calculating the product? Since you are told that the product will be ≤ 2^{62}, you need to use a 64-bit integer. In C++, this is a **long long**. Calculate your product using that, and you're done.