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.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Halloween Sale
  5. Discussions

Halloween Sale

Sort by

recency

|

662 Discussions

|

  • illogicalsleepi1
     + 0 comments
    def howManyGames(p, d, m, s):
    ans=0
    while s>=p:
        s-=p
        ans+=1
        p-=d
        if p<m:
            p=m
    return ans

  • alban_tyrex
     + 0 comments

    Here are my approaches in c++, you can see the explanation here : https://youtu.be/VFVaLMRzhV4

    Approach 1 O(n)

    int howManyGames(int p, int d, int m, int s) {
    int result = 0;
    while( s >= p){
        s -= p;
        p = max(m, p-d);
        result++;
    }
    return result;
}

    Approach 2 O(n) with recursion

    int howManyGames(int p, int d, int m, int s){
    if( s < p) return 0;
    return howManyGames( max(m, p-d), d, m, s - p) + 1;
}

    Approach 3 O(1), incomplete solution (failure of a test case), feel free to comment to share a way to complete it.

    int howManyGames(int p, int d, int m, int s) {
    int n = 1 + (p - m) / d;
    int total = (p + p - (n - 1) * d) * n / 2;
    if(total <= s) {
        return n + (s - total) / m;
    }
    else 
        return 0;
        // this return need to be computed properly
}

  • vutrantrung14821
     + 0 comments
    oreo=a=p
  q=0
  while True:
    if a<=m:
      a=m
    else:
      a-=d
    if a<=m:
      a=m
    if oreo==s:
      q+=1
      return q
      break 
    elif oreo>s:
      oreo-=a
      return q
      break
    elif oreo<s:
      q+=1
      oreo+=a

  • tangjiaqing
     + 0 comments

    C#. This is a no loop solution. It uses arithmetic sequence sum and solves quadratic equations of one variable.

    public static int Run(int init, int discount, int min, int budget)
{
var count = (int)Math.Ceiling((min - init) / -(double)discount);

// if decreased to zero, set to zero
var sum = CalculateSum(init, -discount, count);

// min = 2; diff = 8; a[k]=4, a[k+1]=-4
var minPrice = init - discount * (count - 1);
if (minPrice < 0)
{
	sum -= minPrice;
	count -= 1;
}

var remaining = budget - sum;

if (remaining > 0)
{
	// increase count
	var remainingCount = (int)Math.Floor(remaining / (double)min);

	sum += min * remainingCount;
	count += remainingCount;
}
else if (remaining < 0)
{
	// decrease count
	var estimatedCounts = CalculateSolutions(-discount, 2 * init + discount, -2 * budget);
	var estimatedCount = (int)Math.Floor(estimatedCounts.First(x => x > 0 && x <= count));

	sum = CalculateSum(init, -discount, estimatedCount);
	count = estimatedCount;
}

// number of games
return count;
}

private static double CalculateSum(int init, int diff, double count) => (init * 2 + diff * (count - 1)) * count / 2;

private static List<double> CalculateSolutions(double a, double b, double c)
{
var sqrt = Math.Sqrt(Math.Pow(b, 2) - 4 * a * c);

return
[
	(-b + sqrt) / (2 * a),
	(-b - sqrt) / (2 * a),
];
}

  • rubinaParveen
     + 0 comments
    def howManyGames(p, d, m, s):
    # Return the number of games you can buy
    cost = p
    count = 0 
    while cost <=s:
        if p-d > m:
            p = p - d
            cost += p
            count += 1   
        else:
            cost += m
            count += 1 
    return count