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.
Halloween Sale
Halloween Sale
Sort by
recency
|
639 Discussions
|
Please Login in order to post a comment
Python Loopless O(1) Solution
Explantion
The amounts spent can be thought of as a series I'll call them s1 and s2.
s1 = p, p-d, p-2d, p-3d... p-kd where p-kd<=m
Solve for k
p-kd <= m
k = (p-d)//m
s1 = p+p+p+p...p -(d+2d+3d+4d... kd) where there are k+1 additions of p
s1 = p(k+1) - d(1+2+3+4...k)
s1 = p(k+1) - dk(k+1)//2
s2 = m+m+m...m where s2<=s-s1 and we have an unknown amount of them n
s2 = nm
Solve for n
n = s2/m but s2 <= s-s1
n = (s-s1)//m
In the case that m has been reached, the amount of games is k+1+n which is equal to k+1+(s-s1)//m There is also the case where the m has not been reached so we solve for k to find how many games are bought in that case s1 equals s
s = p(k+1) - dk(k+1)/2
2s = 2pk + 2p - dk^2 - dk
dk^2 + dk-2pk + 2s-2p = 0
dk^2 + (d-2p)k + 2s-2p = 0
Use the quadratic formula where a = d, b = d-2p, c = 2s-2p
k = (2p-d +- sqrt(d^2 - 4pd + 4p^2 - 4d(2s-2p))) / (2d)
k = (2p-d +- sqrt(d^2 - 4pd + 4p^2 - 8ds+8dp))) / (2d)
k = (2p-d +- sqrt(d^2 + 4pd + 4p^2 - 8ds))) / (2d)
Now don't ask me why this last part works because I fiqured it out through trial and error but if anyone has an explanation I would love to hear it.
k = ceil((2p-d - sqrt(d^2 + 4pd + 4p^2 - 8ds))) / (2d))
in C# public static int howManyGames(int p, int d, int m, int s) { // Return the number of games you can buy int noofgames=0; if (p<= s) { noofgames++; }
int remainingamt = s-p; //60 int amt=0;
int price=p; while(amt<=remainingamt) {
price = price-d;
if (price <=m) { price = m; }
//Console.WriteLine("price " + Convert.ToString(price)); amt = amt+price;
//Console.WriteLine("amt " + Convert.ToString(amt));
if (amt <= remainingamt) { noofgames++; //Console.WriteLine("noofgames " + Convert.ToString(noofgames));
}
c#
public static int howManyGames(int p, int d, int m, int s)
C# Solution