SRM 480, D2, 250-Pointer (Cryptography)

James S. Plank

Fri Oct 28 18:28:52 EDT 2016
Try this first on your own. If you get stuck or frustrated, then come back here.


















































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 ≤ 262, you need to use a 64-bit integer. In C++, this is a long long. Calculate your product using that, and you're done.