Problem: We have N questions in a question paper. Each correct answer would mean +a marks and wrong answer would mean -b marks. Leaving a question unattended would give a 0 marks. Tell how many different total marks are possible in terms of N ,a,b.

E.g.: N=1 ,a=4 , b=3

ans–>3

N=2, a=1, b=1

ans–>5

Edit-problem link

what are the constraints on N,a,b?

please check the edit i made

An equivalent formation of the question is: How many different values can ax-by take such that x, y \ge 0 and x+y \le n.

Maximum value of this is a\cdot N - b \cdot 0 \le 10^6 and minimum value is a\cdot 0 - b \cdot N \ge -10^6, so we can just iterate through each value and check if it is possible.

We check if a number r is possible as follows.

Let d = \gcd(a,b). We know, if r is possible, d must divide r. Using to Bezout’s identity, there exist x_0, y_0 such that ax_0-by_0 = d. We can multiple both sides by \frac{r}{d} to get a solution ax_1 - by_1 = r. All other solutions to ax - by = r are given by (x,y) = \left(x_1 + k\frac{b}{d}, y_1 + k\frac{a}{d} \right) where k is an integer. If we can find a k such that x\ge 0, y\ge 0, x+y \le N, r is possible. There is a range of k for each of these 3 inequalities, we just check if the intersection of these ranges is non empty.

1 Like

Thank You very much for this awesome solution!

1 Like