# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* iceknight1093

*pols_agyi_pols*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given N, H, and K, count the number of pairs (A, B) such that 1 \leq A, B \leq N and a frog that jumps A units upward and slips B units downward every second can escape a well of height H within K seconds.

# EXPLANATION:

Let’s fix the value of A and try to count the number of valid values of B.

This, summed up across all A, will give us our answer.

Observe that:

- If A\geq H, the frog will leave the well immediately after its first jump.
- In this case, B can be anything at all. Since we’re limited to 1 \leq B \leq N, add N to the answer.

- When A \lt H, the frog definitely needs more than one second to escape the well.

Note that in this case, if B\geq A, the frog can never leave the well - so we only need to care about 1 \leq B \lt A.

In the second case, since 1 \leq B \lt A, the frog will definitely move upward after each second.

In particular, at the x-th second, the frog will jump up to position x\cdot A - (x-1)\cdot B; and then it’ll fall back down to x\cdot (A-B).

It’s not hard to see that within these x seconds, x\cdot A - (x-1)\cdot B is also the *highest* point the frog ever reached.

So, for the frog to escape the well (that has height H) within K seconds, the inequality

should be satisfied.

Since we fixed A, the only variable here is B. So, moving things around a bit:

So, B can be any integer between 1 and \frac{K\cdot A - H}{K - 1}.

If this upper bound is \lt 1 then no valid B exist; otherwise the number of valid B is exactly

where \left\lfloor \cdot \right\rfloor denotes the floor function.

This can be computed in constant time, so we have a linear time solution since we only iterate through all A from 1 to N.

As an aside, it’s possible to do a bit more math and compute the required summation in \mathcal{O}(\log N) time: see here for instance if you’re interested.

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, k, h = map(int, input().split())
ans = 0
for a in range(1, n+1):
if a >= h: ans += n
else: ans += max(0, (a*k - h) // (k-1))
print(ans)
```