We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
O(1) solution in C++.
define F(n) as sum from k=0 to n of (p-dk), which equals (n+1)(p-nd/2).
The last term in this series that is not smaller than m is at k_max = floor((p-m)/d).
Let F_max = F(k_max). There are two cases: case 1: if s >= F(k_max), then we can pay all the money in the series, which has k_max+1 terms, plus floor( (s-F_max)/m ) games at m each.
On the other hand, case 2: if s < F(k_max), we cannot afford to buy the first k_max+1 games, so we must truncate the series prematurely by finding the largest value g < k_max such that F(g) < s.
Note that F(g) is an inverted parabola, and since we only care about the left half of the parabola where it's increasing, we want the largest integer strictly smaller than the smaller root of F(g). Using the quadratic formula, the smaller root of F(g) is g = b - sqrt(b^2 - c), where b = p/d-1/2 and c = 2(s-p)/d. The largest integer strictly smaller than this g is ceil(g)-1. Accounting for the fact that the sum F starts at k=0 and not k=1, the total number of terms is then ceil(g)-1+1 = ceil(g).
Halloween Sale
You are viewing a single comment's thread. Return to all comments →
O(1) solution in C++. define F(n) as sum from k=0 to n of (p-dk), which equals (n+1)(p-nd/2). The last term in this series that is not smaller than m is at k_max = floor((p-m)/d). Let F_max = F(k_max). There are two cases: case 1: if s >= F(k_max), then we can pay all the money in the series, which has k_max+1 terms, plus floor( (s-F_max)/m ) games at m each.
On the other hand, case 2: if s < F(k_max), we cannot afford to buy the first k_max+1 games, so we must truncate the series prematurely by finding the largest value g < k_max such that F(g) < s. Note that F(g) is an inverted parabola, and since we only care about the left half of the parabola where it's increasing, we want the largest integer strictly smaller than the smaller root of F(g). Using the quadratic formula, the smaller root of F(g) is g = b - sqrt(b^2 - c), where b = p/d-1/2 and c = 2(s-p)/d. The largest integer strictly smaller than this g is ceil(g)-1. Accounting for the fact that the sum F starts at k=0 and not k=1, the total number of terms is then ceil(g)-1+1 = ceil(g).