# Halloween Sale

# Halloween Sale

+ 5 comments A simple approach

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

+ 7 comments My implementation in C with O(1) running time complexity. It does not use any loop.

#include <stdio.h> #include <math.h> int main (void) { int p, d, m, s; int n, t; scanf("%d%d%d%d", &p, &d, &m, &s); if (s < p) { n = 0; } else { n = 1 + (p - m) / d; t = n * (2 * p - (n - 1) * d) / 2; if (s >= t) { n += (s - t) / m; } else { int b = 2 * p + d; n = (b - sqrt(b * b - 8 * d * s)) / (2 * d); } } printf("%d\n", n); }

+ 11 comments def howManyGames(p, d, m, s): games = 0 while s >= 0: s -= p p = max(p - d, m) games += 1 return games - 1

+ 2 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).

int howManyGames(int p, int d, int m, int s) { const int k_max = floor((p-m)/d); const int F_max = (k_max+1)*p-((k_max+1)*k_max*d)/2; if(s >= F_max){ return k_max + 1 + (s-F_max)/m; }else{ const double b = p*1.0/d - 0.5; const double g = b-sqrt(b*b-2.0/d*(s-p)); return ceil(g); } }

+ 6 comments Hi may I ask if anybody getting this error while passing tests? I passed all tests except number 7. Input is '99 3 1 5555', expected output is '3905'. My output is also '3905' but HackerRank keeps complaining it is wrong ...

Sort 470 Discussions, By:

Please Login in order to post a comment