Автор задачи: Мария Жогова, разработчики: Владимир Рябчун и Даниил Орешников
Для решения первых двух подзадач можно было написать полный перебор возможных действий. Во второй подзадаче следовало помечать точки как достижимые, и при попадании в какую-то точку по второму разу не перебирать дальнейшие перемещения из нее.
Для решения остальных подзадач заметим следующий факт. Пусть всего было сделано $$$x$$$ шагов вперед и $$$y$$$ шагов вправо, тогда суммарно за такие перемещения было потрачено $$$ax + by$$$ топлива. Таким образом, все достижимые точки можно описать уравнением $$$ax + by \leqslant s$$$. Задача сводится к тому, чтобы найти количество целочисленных решений такого уравнения.
В четвертой подзадаче проходит следующее решение: переберем количество сделанных шагов вправо $$$f$$$, тогда на движение прямо останется $$$S - af$$$ топлива, за которое можно попасть в точки от $$$(f, 0)$$$ до $$$(\left\lfloor\frac{s - af}{b}\right\rfloor, 0)$$$. Посчитать сумму таких величин по всем $$$f$$$ можно за время $$$\mathcal{O}\left(\left\lfloor\frac{s}{a}\right\rfloor\right)$$$.
В третьей подзадаче можно было заметить, что при целых $$$\frac{s}{b}$$$ и $$$\frac{s}{a}$$$ количество точек с целыми координатами в треугольнике между точками $$$(0, 0)$$$, $$$(0, \left\lfloor\frac{s}{b}\right\rfloor)$$$ и $$$(\left\lfloor\frac{s}{a}\right\rfloor, 0)$$$ равно половине точек с целыми координатами в прямоугольнике с вершиной в точке $$$(\frac{s}{a}, \frac{s}{b})$$$, не считая точек на диагонали $$$ax + by = S$$$.
Точки в таком прямоугольнике посчитать просто: их ровно $$$\left(\frac{s}{a} + 1\right) \cdot \left(\frac{s}{b} + 1\right)$$$. А точки на диагонали следут между крайними с шагом $$$\left(+\frac{a}{\mathrm{gcd}(a, b)}, -\frac{b}{\mathrm{gcd}(a, b)}\right)$$$, то есть их количество равно $$$\frac{s \cdot \mathrm{gcd}(a, b)}{ab} + 1$$$. Осталось сложить и поделить пополам, время работы решения — $$$\mathcal{O}(1)$$$.
Для решения оставшихся подгрупп внимательнее рассмотрим формулу для ответа, которую получили ранее: $$$$$$\left\lfloor\frac{s}{b}\right\rfloor + \left\lfloor\frac{s - a}{b}\right\rfloor + \ldots + \left\lfloor\frac{s - \left\lfloor\frac{s}{a}\right\rfloor a}{b}\right\rfloor\text{.}$$$$$$ Представим каждую дробь $$$\left\lfloor\frac{s - ta}{b}\right\rfloor$$$ как $$$\frac{s - ta}{b} - \frac{(s - ta) \bmod b}{b}$$$. Слагаемые первого вида образуют арифметическую прогрессию (за $$$d_a$$$ обозначим $$$\left\lfloor\frac{s}{a}\right\rfloor$$$): $$$$$$\frac{s}{b} + \frac{s - a}{b} + \ldots + \frac{s - d_a a}{b} = \frac{1}{b} \cdot \left(s (d_a + 1) - a \frac{d_a (d_a + 1)}{2}\right)\text{.}$$$$$$
А слагаемые второго вида образуют последовательность остатков по модулю $$$b$$$, начинающуюся в $$$s \bmod b$$$ и идущую с шагом $$$-a$$$. Можно заметить, что каждые $$$\frac{b}{\mathrm{gcd}(a, b)}$$$ идущих подряд элементов этой последовательности образуют период из остатков вида $$$(a \bmod b) + k \mathrm{gcd}(a, b)$$$ для целых $$$k$$$ (просто записанных в другом порядке). Сумму такого периода тоже можно посчитать по формуле геометрической прогрессии, а количество периодов, которые целиком войдут в ответ, равно $$$\left\lfloor\frac{d_a + 1}{\frac{b}{\mathrm{gcd}(a, b)}}\right\rfloor$$$.
После останется только хвост из остатков, которых меньше, чем длина периода. Но в таком случае их сумму можно просто посчитать циклом за $$$\mathcal{O}(b)$$$.
Для полного решения достаточно выбрать оптимальное из двух решений: за $$$\mathcal{O}\left(\frac{s}{b}\right)$$$ и за $$$\mathcal{O}(b)$$$ для каждого набора входных данных в зависимости от того, какая из двух величин меньше.