PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: pols_agyi_pols
Editorialist: iceknight1093
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)