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

  • 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),
];
}