PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Tester: abhidot
Editorialist: iceknight1093
DIFFICULTY:
835
PREREQUISITES:
None
PROBLEM:
Chef’s kiln is at Y degrees, and he has an ore that melts at X degrees.
In the i-th second, the kiln’s temperature increases by i degrees.
Find the time needed for the ore’s melting temperature to be reached.
EXPLANATION:
It’s enough to directly simulate the process!
That is, start with the temperature at Y, and in the i-th step, increase it by i.
Stop once you reach \geq X.
This is fast enough because the temperature grows quickly: after i seconds, the temperature is exactly Y + \frac{i\cdot (i+1)}{2}, so it will take about 2\sqrt{X-Y} seconds for us to reach X, which is pretty small.
TIME COMPLEXITY
\mathcal{O}(\sqrt{X-Y}) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
x, y = map(int, input().split())
ans = 0
while y < x:
y += ans + 1
ans += 1
print(ans)